Бурбаки - Книга 1. Теория множеств (947355), страница 16
Текст из файла (страница 16)
П, 6 1, упр. 2). 5 Н, Втявпкп г НРиложение. хАРАктеРистикА теРмОВ и сООтнОшений 67 ПРИЛОЖЕНИЕ ХАРАКТЕРИСТИКА ТЕРМОВ И СООТНОШЕНИЙ Когда метаматематика перерастает элементарный уровень настоящей главы, она широко использует результаты математики; мы уже отмечали это во введении. Цель нашего приложения — дать пример рассуждений такого рода'). Мы начнем с установления некоторых результатов, относящихся к математической теории свободных моноидоа („ Алгебра", гл. 1, ф 1, и'3); затем мы рассмотрим мета- математическое „применение" их к характеристике термов и соотношений произвольной теории. 1. Знака и слова 'Пусть Б — непустое множество, элементы которого будут называться далее знаками (эта терминология приспособлена к метаматематическому применению, которое мы имеем в виду). Пусть Ьо(3) — свободный моноид, порожденный множеством 8 („ Алгебра", гл.
1. э 1, п' 3); его элементы (называемые' словами) могут быть отождествлены с конечными последовательностями А =(зг) гокгкр элементов из Б; мы будем записывать закон композиции в 1ю(5) мультипликативно, так что АВ есть последовательность, получаемая соединением последовательностей А и В. Пустое слово 8 является нейтральным элементом в ).о(8). Напомним, что длина 1(А) слова А ~ (ю (Я) есть число элементов в последовательности А: 1(АВ) = = 1(А) + 1(В); словй длины 1 суть знаки, Обозначим через 1.(5) множество непустых слов моноида Ьо(Б), Предположим, кроме того, что задано отображение з — ь п(з) множества Б в множество И целых чисел, больших или равных нулю; для всякого непустого слова А = (з,), „из 1. (Б) положим ~ок~к» п(А) = лг п(з ) и п(И) =О; мы говорим, что п(А) есть вес слова А. г-о Очевидно, что п(АВ)=п(А)+п(В), Если А=А'ВА", то мы говорим, что слово В есть сегмент слова А (истинный сегмент, если, кроме того.
В ~ А). Если А' (соответственно А") пусто, то мы говорим, что В есть начальный (соответственно коняевой) сегмент слова А. Если 1(А')=К то мы говорим, что В начинается на (А+1)-и месте. ') Результаты, установленные в настоящем приложении, не будут использоваться в дальнейшей части Трактата. Если А =ВС1)ЕР (где слова В. С, 1), Е, Р могут быть пустыми). мы говорим, что сегменты С и В слова А не пересекаются. 2. Знаменательные слова Назовем знаменательной последовательностью всякую последовательность (А,),<1<„слов из (.о(5), обладающую следующим свойством: для каждого слова А; в этой последовательности выполняется одно из двух следующих условий: 1' А, есть знак веса О.
2' Существуют р слов Аг, Аг, ..., А~ из рассматриваемой »' '''' р последовательности с индексами, меньшими 1, и знак У веса р, такие, что А~ =у'А»,А~, ... Аг . Знаменательными словами мы называем слова, встречающиеся в знаменательных последовательностях. Сразу же получается следующий результат: Предложение 1. Если А,, А,, ..., Ар являются знаменательными слогами, а у есть знак веса р, то слово УА,Аг ... А знаменательно. 3. Характеристика знаменательных слов Слово А Е !.о(Я) называется равновесным. если оно обладает двумя следующими свойствами: 1' 1(А)=п(А)+1 (откуда следует, что А не пусто); 2' для всякого истинного начального сегмента В слова А выполняется неравенство 1(В) (п(В).
Предложение 2. Для того чтобы слово было знаменательным, необходимо и достаточно, чтобы око было равновесным. В самом деле, пусть А — знаменательное слово, встречающееся в знаменательной последовательности А,, А,, ..., А„; мы покажем индукцией по А, что каждое слово А» равновесно.
Предположим, что это уже установлено для всех А1 с индексом у к„й, и докажем это для А . Если А„ — знак веса О (что является единственной возможной гипотезой при й = 1), то А» равновесно, потому что 1(А») = 1 и и (А„) = О. В пРотивном слУчае А» =)'В,Вг ... В , где У вЂ” знак веса р и слова В) имеют вид А, с 1 ч. к, а следовательно, являются, по предположению, равновесными словами. Итак, (А») = 1+1(В,)+1(Вг)+ ... +1(Вр) = 1+(п(В»)+ 1)+(п(В )+ 1) + +(п(Вр)+ 1) = = 1+ р+ и (В ) + п (Вг) + ... + и (Вр) = 1+ и (А „). Пусть, с другой стороны, С вЂ” истинный начальный сегмент слова А„и пусть в — наибольшее из целых чисел т ( р, таких, что Вы есть сегмент слова С; тогда С = уВ,Вг ...
В 1), где 4 ПРИЛОЖЕНИЕ. ХАРАКТЕРИСТИКА ТЕРМОВ И СООТНОШЕНИЙ 69 ГЛ. Е ОПИСАНИЕ ФОРМАЛЬНОЯ МАТЕМАТИКИ 68 П вЂ” истинный начальный сегмент слова Вд+,. Следовательно, !(С)=1+1(В,)+ ... +1(В~)+!(П) < 1 +(п(В1) + 1)+ +(п(Вд)+ 1)+п(!)) ( р+ и (В,) + ... + п (В ) + и (О) = п (С), Следовательно, А„ равновесно. Чтобы доказать, что. обратно, всякое равновесное слово знаме- нательно, нам понадобятся две леммы. Лемма !.
Пусть А — равновесное слово. Для каждого целого числа й, такого. что 0 ( й < 1(А), существует и единстзен равновесный сегмент 5 слова А, начинающийся ка (к+1)-м месте. Единственность сегмента В вытекает сразу же из следующего замечания: если Т вЂ” равновесное слово, то, по определению.
ни один истинный начальный сегмент слова Т не является равновесным. Докажем существование сегмента В. Положим А = ВС, где 1(В) й. Для всякого такого 1, что 0(1(с)=!(С), пусть Сс есть начальный сегмент слова С длины 1. Так как  — истинный начальный сегмент слова А, то ! (С ) = ! (А) — ! (В) )~ п (А) + 1 — п (В) = и (С )-+ 1. С другой стороны, 0=1(Сз) (и(Сь)=0. Пусть 1 — наибольшее из целых чисел !(с!, таких, что 1(С„) (и(СА) для 0 (й (с; тогда !(С,) (п(С,) и !(Сс+,))~п(С,+1)+-1.
Покажем, что Сс, равновесно. Условие, относящееся к истинным начальным сегментам, выполнено в силу определения числа 1. С другой стороны, п (С,„,) + 1 < ! (Сс ь 1) = ! (С ) + 1 ( п (С ) +- 1 < п (С,,) + 1; следовательно, !(С„.+1)= п(С,„,)+ 1, что завершает доказательство. Лемма 2. Всякое равновесное слово А может быть представлено е виде А=уА1Аг ... А, где зсе А, равновесны и п(с') = р.
В самом деле, пусть )' — начальный знак слова А. Согласно лемме 1, А можно записать в виде УА1Аг ... А , где все А, равновесны: достаточно определить А, по индукции как равновесный сегмент слова А, начинающийся на й(1)-и месте, где 11(1) = 2+ ллс~ !(А1). !<с Кроме того, 1+!(А,)+ ... +!(Ар)=1(А)=и(А)+1 (г)+и(А1)++и(Ар)+1 =п(У)+(1(А)) — 1)-+ ...
+.(!(Ар) — 1)+. откуда и(у') = р. Коль скоро леммы доказаны, нетрудно показать индукцией по длине слова А, что всякое равновесное слово А знаменательно ввиду леммы 2 и предложения 1. Следствие 1. Пусть А †знаменательн слово. Для всякого целого числа й, такого, что 0 (к <1(А), существует и является единственным знаменательный сегмент слова А, начинающийся ка (й+1)-м месте. Следствие 2. Всякое зкамекателькое слово А может быть представлено, причем единственным образом, з виде УА1Аг...
А, где есе А, знаменательны и п(Я = р„, б. Применение к зкакосочетанапм произвольной математической теории Предположим, что множество 5 есть множество знаков математической теории сT. Положим п(())=0, п(т)=п( 1)=1, п('!)=2, и(х)=0 для каждой буквы х; наконец, для каждого специального знака з теории су пусть п(з) есть вес этого з, фиксируемый заданием этой теории су. Пусть А — знакосочетание теории ,T. Обозначим символом А' слово, получаемое стиранием всех связей в А, и будем говорить, что знакосочетание А равновесно, если А' равновесно (в Ь (Б)). Мы будем называть сегментом знакосочетания А всякое знакосочетание, получаемое путем снабжения какого-либо сегмента В слова А' теми связями, которые в А соединяли два знака сегмента Я. Кгитегий 1.
Если А — терм или соотношение теории Т, то А — равновесное зкакосочетикие. В самом деле, пусть А„А,, ..., А„есть формативная конструкция теории,T, в которой встречается А. Рассуждая по индукции, предположим доказанным, что все А. с индексом с'(1 равновесны, и докажем, что знакосочетание А; равновесно. Это устанавливается совершенно так же, как в первой части доказательства предложения 2, за исключением того случая, когда А, имеет вид т„(В) с В=АР ! <!.
В этом случае пусть С есть знакосочетание, получаемое замещением буквы х на каждом месте, где х встречается в В, символом (); слово А; тождественно с тС'. Но В' равновесно; следовательно, и С' равновесно (ибо и (сз)=и(х)=0); следовательно, Ас тоже равновесно. Итак, мы получили необходимое условие для того, чтобы знакосочетание теории Д' было термам или соотношением.
Это условие, как мы увидим, не является достаточным. Пусть А в равновесное знакосочетание теории сТ. Если А начинается с буквы или знака (), то А неизбежно сводится к этому начальному знаку (следствие 2 предложения 2). Во всех остальных ГЛ. ! ОПИСАНИЕ ФОРМАЛЬНОЙ МАТЕМАТИКИ 7О пРилОжение. ХАРАктеРистикА термов и сООтношений 71 Упр. случаях мы определим знакосочетание или знакосочетания. антецедентные к А. 1' Если А начинается с 1, или с ьг, или со специального знака, то А' представимо единственным образом в виде ~В,В» ...
В, где .1' — знак веса р)~1 и все В; равновесны (следствие 2 предложения 2). Назовем знакосочетаниями, антецедентными к А, сегменты А,, Аг, ..., Ар знакосочетания А, соответствующие сегментам В,,ВТР ..., Вр слова А'. Кроме того. Иы скажем, что А — совершенно равновесное знакосочетание, если А тождественно с УА,А» ... Ар, или, иначе говоря, если в А ни одна связь не соединяет у'с каким-нибудь из Вг или два разных В~ друг с другом. 2' Если А начинается с т, то А' имеет вид ТВ, где  — равновесно (следствие 2 предложения 2). Мы назовем энакосочетаиием, антецедентным к А, любое из знакосочетаний А,, определяемых следующим образом: все знаки () в В, связанные в А с начальным с, заменяются буквой х, отличной от других букв, встречающихся в В, а связи, соединяющие в А два знака знакосочетания В, восстанавливаются.
(Если вместо х подставить букву у, также не встречающуюся в В. то получится не что иное, как знакосочетание (у(х)А,)А Кроме того, мы скажем, что А есть соеершекио равновесное зиакосочетание, если А тождественно с т„(А~), или, иначе говоря, если ни одна связь не соединяет начальное т со знаками из В, отличными от (). Тогда можно сформулировать следующий критерий: Критерий 2. Лусть А — равновесное знакосочетаиие теории,T.
Для того чтобы А было термам, необходимо и достаточно, чтобы заполнилось одно из следующих условий: 1) А сводится к одной букве; 2) А начинается с т, совершенно равновесно, и аитецедеитиые зиакосочетания суть соотношения (согласно СР8, достаточно проверить, что какое-нибудь одно антецедентное знакосочетание есть соотношение); 3) А начинается с субстантиеного знака, совершенно раеноеесно, и антецедеитные знакосочетания суть термы.
Для того чтобы А было соотношением, необходимо и достаточно, чтобы выполнялось одно из следующих условий: 1) А начинаетси с ~/ или 1, совершенно раеноеесно, и антецедентные зиакосочетаиия суть соотношения; 2) А начинается с реляционного знака. совершенно раеноеесно, и антецедентные зиакосочетаиин суть термы. Эти условия достаточны, согласно критериям СР1 — СР4 (8 1, п' 4). Докажем, что они необходимы. Если А — соотношение, то мы уже видели (8 1, п' 3), что А начинается с ~/, с 1 или с реляционного знака. Во всех трех случаях рассуждаем аналогично. Если, например, А начинается с Т/, то А имеет вид ~/ВС, где В и С вЂ” соотношения, так что В, С суть знакосочетания, антецедентные для А; следовательно, знакосочетание А совершенно равновесно.
Если А — терм, то А либо сводится к одной букве. либо начинается с субстантивного знака, или с т. Во втором случае мы рассуждаем, как ранее. Если А начинается с т, то из определения формативной конструкции видно, что А имеет вид тх(В), где  — соотношение и х — буква. Поэтому можно принять В за антецедентное к А, и. следовательно, А — совершенно равновесное знакосочетание. Если требуется узнать, является ли данное знакосочетание А (не сводящееся к одной букве) соотношением(соответственно термам) теории 7", то сначала надо проверить, равновесно лк А и начинается ли оно с Ч, или с ~, или с реляционного знака (соотеетственно с т или субстантивного знака).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
