| Съдържание |
Забележка 1. В точка 2 на горната дефиниция скобите и запетаите фигурират в означението ω(τ1,…,τn) като формални символи и не означават нищо друго освен самите себе си (за разлика от останалите запетаи в същата точка, които изпълняват присъщата им в българския език и в математиката пунктуационна роля).
Пример. Думата difference(difference(one,one),one)) е затворен терм при сигнатурата Σ′ от пример 3 в текста „Сигнатури и структури“.
Забележка 2. За да съществува поне един затворен терм при дадена сигнатура Σ, необходимо и достатъчно е тази сигнатура да притежава поне една константа. И наистина, по смисъла на дадената индуктивна дефиниция, всеки затворен терм при сигнатура Σ може да бъде построен, като за една или повече константи на Σ чрез точка 1 от дефиницията се получи, че те са затворени термове при сигнатура Σ, и след това някакъв (евентуално нулев) брой пъти се приложи точка 2 от дефиницията, а същевременно точка 1 от нея гарантира, че при наличието на поне една константа на Σ ще съществува и поне един затворен терм при Σ.
Забележка 3. В съгласие със забележка 3 от текста „Сигнатури и структури“ вместо „затворен терм при сигнатура Σ“, „константа на Σ“ и „функционален символ на Σ“ често ще пишем само „затворен терм“, „константа“ и „функционален символ“. В частност така ще постъпваме по-нататък в настоящия текст.
Дадената индуктивна дефиниция позволява да доказваме общи свойства на затворените термове с помощта на индукция, съобразена с нея. А именно, за да докажем, че всеки затворен терм има дадено свойство, достатъчно е да покажем от една страна, че то е налице за константите (това е тъй наречената база на индукцията), и от друга, че то се запазва при прилагането на втората точка от дефиницията (т.е. винаги, когато n е положително цяло число, ω e n-местен функционален символ и τ1, …, τn са затворени термове, притежаващи даденото свойство, затвореният терм ω(τ1,…,τn) също го притежава – това е тъй наречената индуктивна стъпка). По такъв начин може да се докаже например следното твърдение, което да се разбира в смисъла на текста „Осигуряване на еднозначен прочит с помощта на скоби и разделители“ при азбука Α, съвпадаща с основната, и азбука Β, получена от нея чрез добавяне на скобите и запетаята.
Лема за силна приемливост на затворените термове. Всеки затворен терм е силно приемлива дума.
Доказателство. Константите са силно приемливи думи, защото са думи над основната азбука, а от забележка 1 в споменатия по-горе текст е ясно, че силната приемливост се запазва при прилагането на втората точка от дефиницията за затворен терм. □
Ще използваме току-що доказаното твърдение, за да докажем, че при дадената дефиниция за затворен терм е налице еднозначен прочит на затворените термове, т.е. всеки затворен терм може да бъде получен само по една от двете точки на дефиницията, и то само по един начин (това свойство се нарича още еднозначност на синтактичния анализ на затворените термове).
Ако една дума е затворен терм въз основа на едната измежду двете точки на горната дефиниция, тази дума не може да бъде затворен терм и въз основа на другата. Действително, ако една дума е терм въз основа на първата точка, то всички знаци в тази дума са от основната азбука и следователно думата не може да бъде терм въз основа на втората точка.
Остава да видим, че не може една дума по два различни начина да се окаже затворен терм въз основа на втората точка, т.е. не може при два различни избора на цялото положително число n, на n-местния функционален символ ω и на термовете τ1, …, τn съответната дума ω(τ1,…, τn) да се окаже една и съща. Лесно е да се види, че функционалният символ ω се определя еднозначно по тази дума – той е най-дългото измежду нейните начала, в които всички знаци са от основната азбука. Оттук е ясно, че числото n и думата τ1,…,τn също се определят еднозначно по ω(τ1,…, τn). Като използваме лемата за силна приемливост на затворените термове и приложим лемата за еднозначния прочит, получаваме, че и затворените термове τ1, …, τn се определят еднозначно по ω(τ1,…, τn).
Последно изменение: 23.10.2008 г.