markov_teorija_algorifmov (522344), страница 22
Текст из файла (страница 22)
Ввиду (8) и (9) У есть вхождение атома в систему Х, т. е. элемент этой системы. Левое крыло этого элемента пусто и потому, согласно определению номера элемента, [уь -,к[[А»э[ Х Л ] [Я 19,4.4]. Таким образом, натуральное число Л удовлетворяет предикату Р.
Ввиду (8) имеем ЦХть~)]], н потому [Х')[ [4(!)], а ( Х' — !) есть натуральное число. усть М вЂ” число, меньшее ([Х' — ]). Докажем импликацию (10) «если М удовлетворяет Р, то М] удовлетворяет Р». Пусть М удовлетворяет Р. Может быть указан элемент (7 системы Х такой, что (11) [(/А ХМ [ $ ы! СИСТЕМЫ СЛОВ пз к (7 есть вхождение однозначно определенного атома 7 7 В ВХ. Здесь !7 — слово в алфавите А.
Обозначая буквами У и В' левое и правое крылья вхождения (7, имеем (12) Х Х Уу!)7)Р. Так как У вЂ” левое крыло (7, имеем по определению номера элемента (13) [(7'~ ЦУ" 1 Имеем далее (14) М ЩУ Ц13), (и), 4 17.5.1], (15) ЦХтьлсМ[[Цйэ™ [(12), ф 19.4.1, (14), ф 19.4.3, 3 19.4.5], (16) [Х»~М[Ц(рте [(15), ~ 18.!0.11, 4(1), 3 17.5.1].
Так как, по предположению, М < ([Х' — ~) имеем М! < [Х ' Следовательно, ЦВ'ть.!Е Л [(16), ~ 18.6.12], УР~Л [Ц 19,4.4] И (17) 7(У лг 7 [$ !?.5.2]. 7И' является концом системы Х [(12)] и, следовательно, системой [1.2]. В силу (17) ТВ' начинается атомом, т. е. имеется слово 77 в алфавите А такое, что 7)су есть начало слова 7В' [2.4]. Имеем (18) 7%' ~су)77 (7777 - 7В') В 18 8 4] (19) Х Х Уу Ду Я у (7Я7 7(У) [(12), (18)]. Положим по определению (20) Т УТЯокуйу*(7)77 7" ) ° Т есть вхождение атома 7)су в систему Х [( ), ( )1„ 19,20, т. е. элемент системы Х. Левым крылом Т является слово 7 для которого имеем ЦУТЯтэХ[У»э~ Ц 19,4.1, $19.4.3, ~ 19.4.5] ль М [ [(14)].
Отсюда по определению номера элемента [ТА тг ЦУ7()ть [ хМ[]. $20 СИСТЕМЫ СЛОВ !!4 СЕМИОТИКА [гл. и [(24), (25)], [(31), (30), % 17.5.2], [(3», % 22.1.1], [(32), ф 22.1.1], [(22), (23), (зо), (зз), (з4)] и, следовательно, [у' < [г', (2) и, следовательно, ~<Л [з 1?.5.2], Таким образом, число М) удовлетворяет предикату Р. Им- пликация (10) тем самым доказана Ц 13.6,2].
Применяя метод ограниченной арифметической индукции, мы видим, что каждое натуральное число М такое, что м < ([х — 1), удовлетворяет предикату Р. Если же число ?т' удовлетворяет условию (5), то (Ас — 1) < ([Х вЂ” [). и потому (А! — () удовлетворяет предикату Р. Это означает, что существует элемент системы Х с номером Ас„что и тре- бовалось доказать. 5.4. Если У и 17 — элементы одной и той жс систел!ы и [У Х[(?А, УХи. Действительно, пусть У и (7 — элементы системы Х, и пусть (21) [У х[(?А. 1' и Н суть вхождения некоторых атомов ТРт и ТЯ? соот- ветственно в Х. Р и 4С являются здесь словами в алфавите А. Обозначая левое и правое крылья (7 через У и Т, левое и правое крылья У через г и В', имеем (22) 1 х г 'Ф 7 Ру Ф 97, (23) иху худу кт, (24) Ххгуру)У, (25) ххУ? дут, (26) [уа:- Пгта ) (27) [ца — ПУта ( (28) Пгта о ПУта [(21) (27)] Если бы слово УТ было началом слова г, то мы имели бы ПУута<Пг а [4 в.4.2], т.
е. (20) П [<Пгт Ц В.4 1, % В.4.З], откуда П1"'! < П1' [(28), (29)] что абсурдно. Таким образом, слово УТ не есть начало слова г. А так как Уу и г суть начала одного и того же слова Х, то г есть начало У [3 18.4,6]. Аналогичным образом доказывается, что У вЂ нача г. Следовательно, (зо) г о У Ц 18,3,3].
Имеем далее (З1) гурууухУТОТТ (32) РуьР хЯТ (33) Р хЯ (34) 1(2" х Т Ухи что и требовалось доказать. 6. Мы будем говорить, что злелсент У предшествует элементу г, если У и г суть элементы одной и той же системы и левое крыло 1' есть собственное начало левого крыла г. 6.1. Никакой элелсент нс предшествует самол!у себе [Ц 18.4.17].
6.2. Если злсменпс У пред!4!еспсвует элементу г, !по [1'А < [гА. В самом деле, пусть элемент У предшествует элементу г (У и г суть элементы одной и той же системы). Обозначим буквой (7 левое крыло У, буквой У вЂ” левое крылог. (7 есть собственное начало У, так как У предшествует г. Поэтому (7 фУ и, следовательно, У,а.г. Так как (7 — начало У, имеем Пг?та < Пута [6 в 4 2] и потому, согласно определению номера элемента, (1) [УА( [га Ц 18.6.10, ~ 18.10.11].
Если бы имело место равенство [УАХ [га, то мы имели бы равенство УХ г [5,4], а мы видели, что У 'ф г. Таким образом, [у' ~ [г' что и требовалось доказать. 6.3. Если У и г — элементы одной и спой же системы и [У" < [г'", то У предшествует г. 117 СХЕМЪ| . «»»1 1|6 [гл. || СЕМИОТИКА Действительно, пусть У и 3 — элементы системы Х, и пусть имеет место (2).
У и Я являются тогда вхождениями в Х. Обозначим через (7 левое крыло вхождения У, через У— левое крыло вхождения Я. (7 и У являются началами слова Х [3 23.3.81, в силу чего У есть начало (7 или (7 есть собственное начало 1' [3 18.4,51. Но если бы У было началом (7, то мы имели бы [[У э[([[(у>э[ [4 18.4.2, 6 18.6.16, 4 18.16.111, т. е. [2 ([УА, что несовместимо с (2) [3 18.6.131. Следовательно, У не есть начало У, и потому У есть собственное начало У. Зто означает, что У предшествует 2. Это и требовалось доказать.
6.4. Элемент У тогда и только тогда предшествует элементу 2, когда У и 2 суть элементы одной и той же системы и [УА < [ЕА [6.2, 6,31. 6.5. Если элемент У предшествует элементу 2, то 2 не предшествует У [6.41. 7. Следующее высказывание непосредственно вытекает из определения элемента; 7.1. Всякий элемент есть слово вида (1) У*уру жг.
Имеем также 7.2. Всякий элемент представляется в виде (1) единственным образом [3 22.1.1, 2 22.1,21, В силу 7.1 и 7.2 законно следующее определение: Слово Р в представлении (1) элемента Х мы называем ядром элемента Х. Следующее высказывание легко следует из определений. 7.3. Слово Р тогда и только тогда есть ядро некоторого элемента системы Х, когда Р есть член Х, 8.
Пусть Х вЂ” система, а Ф вЂ” натуральное число такое, что [~ (А1~ ([Х". А1-м членом сис|пемы Х мы будем называть ядро такого элемента У системы Х, что [Уьл|.А|. Если [< А1 < [Х', то А1-й член системы Х мы будем называть внутренним членом Х. $25. Схемы 1. В этом параграфе А означает некоторый алфавит, а, 3, 7 и ж — некоторые попарно различные буквы, не входящие в А. Мы введем в рассмотрение алфавит Б, положив по определению Б = Аи[). Буквы Р н Я будут применяться как вербальные переменные ' в алфавите А; буквы Х, У и 2 — как вербальные переменные в алфавите Бу; буквы Т, (7, У, В' — как вербальные переменные в алфавите Б. Буквой 7 мы будем пользоваться для построения 7-систем в алфавите Б.
Как и в 3 24, мы будем называть их просто системами. Буквой я| мы будем пользоваться для построения ' |К-вхождений в алфавите Бу, которые мы будем называть просто вхождениями. 2. Слова вида Р$Я, где $ — буква алфавита ар, мы будем называть формулами подстановок (в алфавите А); слова вида Рй«г — простыми формулами подстановок, слова вида Рр|'„|в заключительными формулами подстановок.
Очевидным образом имеем 2.1. Всякая формула подспшновки является простой или заключительной. 2.2. Никакая простая формула подсп|ановки не является заключительной. 2.3. Всякая формула подстановки единственным образом представляется в виде РЩ где $ — буква алфавита ар [3 22.1.3[. Слово Р будет называться левой частью формулы подстановки Р~~д; слово 9 — правой частью этой формулы подстановки.
Имеем 2.4. Левая и правая части всякой формулы подстановки суть слова в алфавип|е А. 31 Нетрудно видеть, что следующие вербальные предикаты разрешимы: «Х есть формула подстановки>, «Х есть простая формула подстановки», «Х есть заключительная формула подстановки», «Х есть формула подстановки и Р— левая часть Х», «Х есть формула подстановки н Я вЂ” правая часть Х». 13. Мы будем говорить, что формула подстановки Р действует на слово Р, если левая часть Р входит в Р. В этом случае мы будем под результатом действия Р на Р подразумевать результат подстановки правой части формулы подстановки Р вместо первого вхождения ее левой части в слово Р.
Имеем 3.1. Резулыпот действия формулы подстановки Р на слово Р определен тогда и толька тогда, когда Г действует на Р. Он является тогда словом в алфавите А [$ 23.8.2]. 11В СЕМИОТИКА 1гл. и 4. Мы будем говорить о у-системе Х в алфавите Б, что она есть схема (точнее — у-схема в алфавите Б), если все ее члены суть формулы подстановок. Нетрудно видеть, что вербальный преднкат «Х — схема» разрешим. Мы будем говорить, что схема Х действует на слово Р, если хотя бы один член схемы Х действует на Р.
Это определение осмысленно ввиду того, что члены схемы Х суть формулы подстановок. Мы будем говорить, что элемент )' действует на слово Р, если ядро этого элемента действует на Р. В этом случае результат действия ядра )' на Р мы будем считать результатом действия 1' на Р. 4.1. Если схема Х действует на слово Р, то имеется единственныи злел5ент схемы Х, действующий на Р и предшествую- и(ий всякому другому элементу схемы Х, действующему на Р. Действительно, допустим, что схема Х действует на слово Р. Построим одноместный арифметический предикат 6 «У есть номер некоторого элемента схемы Х, действующего на Р», где Х и Р фиксированы, а Ж вЂ свободн натуральная переменная.
Этот предикат очевидно разрешим. Поскольку Х действует на Р, имеется член 1е схемы Х, действующий на Р. Я является ядром некоторого элемента )' схемы Х 9 24.7.31. [)ль есть положительное натуральное число 9 24.5.1], )' действует на Р, так как ядро Я элемента г' действует на Р. Таким образом, [)'А удовлетворяет предикату 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
