ИНДУКТИВНИ ДЕФИНИЦИИ

    Както коя да е явна дефиниция, всяка индуктивна дефиниция също въвежда някакво наименование - за някои измежду обектите от даден вид или за някои измежду системите от определен брой обекти от даден вид или дадени видове. Можем да приемем, че първият от тези два случая обхваща и втория, защото всяка система от обекти може да се разглежда като един по-сложен обект. Затова ще се занимаем с първия от случаите - въвеждане на наименование за някои измежду обектите от даден вид. При една индуктивна дефиниция посочването на съвкупността на обектите, които да се наричат по съответния начин, най-често се прави като се използват два вида приемания: едните посочват известна част от въпросната съвкупност, а другите дават начини от едни елементи на тази съвкупност при определени условия да се получават други (понякога могат да се използват и такива приемания, които съдържат като подслучаи приемания както от първия, така и от втория вид). Освен това негласно се приема още, че в съвкупността, която се определя по този начин, попадат точно онези елементи, за които това произтича от споменатите вече приемания, включени в дефиницията. Ще илюстрираме казаното с един пример.

    Пример 1. Някои измежду положителните цели числа временно ще наречем достижими и това ще направим чрез индуктивна дефиниция, състояща се от следните приемания:
    а) числото 1 е достижимо;
    б) за всяко достижимо число t числото t²+1 е също достижимо;
    в) когато едно число е достижимо, всяко положително цяло число, което е негов делител, също е достижимо;
    г) произведението на всеки две достижими числа е пак достижимо.
Очевидно приемането а) е от първия от споменатите два вида, а останалите три приемания са от втория вид. Като използваме приемането а) и няколкократно се възползваме от приемането б), можем последователно да заключим, че освен числото 1 са достижими например и числата 2, 5, 26. От обстоятелството, че 26 е достижимо, с помощта на приемането в) получаваме, че и 13 е достижимо. Оттук с помощта на приемането г) виждаме, че достижими ще бъдат и всички други цели положителни числа, на които простите множители са измежду числата 2, 5 и 13 (например достижими ще бъдат числата 4, 8, 10, 16, 20, 25, 32, 40, 50, 52, 64, 65 и безбройно много други). Числата 17, 29 и 37 също са достижими благодарение на равенствата 4²+1=17, 17²+1=29.10, (4.17)²+1=37.125. Като се използват разсъждения в духа на доказателството на Евклид, че простите числа са безбройно много, може да се покаже, че има безбройно много прости числа, които са достижими. И наистина, ако p₁, p₂, ...,p_k са дадени достижими прости числа, то с k-1-кратно използване на приемането г) и еднократно използване на приемането б) се получава, че числото (p₁p₂...p_k)²+1 е също достижимо. Това число има поне един прост делител (евентуално съвпадащ със самото число) и благодарение на приемането в) можем да сме сигурни, че и той е достижимо число. Ясно е обаче, че такъв делител е непременно различен от кое да е от числата p₁, p₂, ..., p_k, тъй като в противен случай той би се оказал общ делител на две числа, различаващи се с 1, и значи би трябвало да бъде делител и на тяхната разлика 1. Така по всеки намерени известен брой достижими прости числа можем да намерим още едно, различно от всяко от тях. Съществуват обаче и прости числа, които не са достижими. Такова е например числото 3. За да докажем, че 3 не е достижимо, достатъчно е да покажем, че никое достижимо число не се дели на 3. Очевидно числото 1 - единственото число, което е достижимо въз основа на приемането а), не се дели на 3. От друга страна до всяко отделно достижимо число може да се стигне, като се тръгне от числото 1 и се направят известен брой такива преходи, за каквито става дума в останалите три приемания - преход от число t към съответното му число t²+1, преход от дадено число към негов делител, преход от две числа към тяхното произведение. Поради това твърдението, че никое достижимо число не се дели на 3, със сигурност ще бъде вярно, ако се окаже, че при извършването на такива преходи винаги, когато се тръгва от числа, неделящи се на 3, пак се стига до числа, неделящи се на 3. За преходите, отговарящи на приеманията в) и г), е непосредствено ясно, че положението е наистина такова: ако едно число не се дели на 3, то и неговите делители не се делят на 3, а също произведението на две числа, неделящи се на 3, не може да се дели на 3. За прехода, отговарящ на приемането б), разсъждението може да се проведе така: ако t е положително цяло число, неделящо се на 3, то t=3k+1 или t=3k+2 за някое цяло число k, а тогава ще имаме t²+1=3l+2 за подходящо цяло число l (за l=3k²+2k или за l=3k²+4k+1), тъй че не е възможно числото t²+1 да се дели на 3. По подобен, макар и малко по-дълъг начин би могло да се докаже, че например числата 7 и 11 също не са достижими.¹

    Има общи начини за превръщане на индуктивните дефиниции в явни, т.е. за намирането на явни дефиниции, еквивалентни на тях. Два такива начина ще илюстрираме чрез тяхното прилагане към случая от горния пример.

    Пример 1ў. Временно да наречем пътека коя да е крайна редица от положителни числа, за всеки член на която е изпълнено някое от следните четири условия: аў) да бъде равен на 1; бў) да има вида t²+1, където t е някой от предхождащите го членове на редицата; вў) да бъде делител на някой от предхождащите го членове на редицата; гў) да бъде произведение на два предхождащи го члена на редицата (пътека е например редицата 1, 2, 5, 26, 13, 65). Тогава може да се твърди, че за да бъде едно положително цяло число е достижимо, необходимо и достатъчно е то да е член на някоя пътека. За да се убедим, че членовете на произволна пътека са достижими числа, можем да разсъждаваме по следния начин. Първият член на пътеката може да бъде само 1, защото за него няма как да бъде изпълнено никое от условията бў), вў), гў). Следователно, по първото приемане от дефиницията за достижимо число, първият член на пътеката е достижимо число. От друга страна, ако за някой от останалите членове на пътеката се окаже, че всички предхождащи го членове са достижими числа, той също ще бъде достижимо число благодарение на някое от четирите приемания от дефиницията за достижимо число. Значи щом първият член на пътеката е достижимо число, вторият също ще бъде, щом първият и вторият член на пътеката са достижими числа, третият също ще бъде и т.н., т.е. наистина всички нейни членове ще бъдат достижими числа. Обратно, всяко достижимо число е член на някоя пътека поради това, грубо казано, че до произволно конкретно достижимо число може да се стигне като се тръгне от числото 1 и се извършат известен брой преходи, за каквито става дума в приеманията б), в) и г) от дефиницията за достижимо число - записвайки последователно числото 1 и останалите числа, до които се стига при преходите в дадения конкретен случай, докато се стигне до въпросното число, получаваме пътека, на която то е член. По-прецизен начин на доказване на споменатото обратно твърдение е следният: показваме, че свойството да бъде член на пътека е налице за числото 1 и че това свойство се запазва при всеки от споменатите три вида преходи. Числото 1 наистина е член на пътека - например на редицата с единствен член 1. От друга страна, ако едно положително цяло число t е член на пътека, а друго положително цяло число u е числото t²+1 или е делител на t, то ние можем да получим една пътека, имаща член u, като към наличната пътека, съдържаща член t, добавим накрая като нов член числото u. Най-сетне, ако едно число u е произведение на две числа, всяко от които е член на някоя пътека, ние можем да получим една пътека, имаща член u, като напишем най-напред членовете на наличната пътека, съдържаща като член първия множител, след това членовете на наличната пътека, съдържаща като член втория множител, и накрая добавим като още един член числото u.

    Пример 1І. Временно да наречем индуктивно множество кое да е множество K от положителни цели числа, за което са изпълнени следните условия: аІ) числото 1 принадлежи на K; бІ) за всяко t от K числото t²+1 също принадлежи на K; вІ) когато едно число t принадлежи на K, всяко положително цяло число, което е делител на t, също принадлежи на K; гІ) произведението на всеки две числа от K също принадлежи на K (тези условия по същество се получават от приеманията в дефиницията за достижимо число като се замени свойството на едно число да бъде достижимо със свойството да принадлежи на K). Ето няколко примера за индуктивни множества: множеството на всички положителни цели числа, множеството на онези от тях, които са достижими, множеството на онези положителни цели числа, които не се делят на 3. Може да се твърди, че са достижими точно онези положителни цели числа, които принадлежат на всяко индуктивно множество. И наистина, дефиницията за индуктивно множество осигурява, че ако K е такова множество, то числото 1 принадлежи на K и принадлежността към K се запазва при всички преходи, чрез които се стига от 1 до останалите достижими числа, следователно всички достижими числа ще принадлежат на K. Обратно, ако едно положително цяло число принадлежи на всяко индуктивно множество, то това число ще принадлежи в частност на множеството на достижимите числа и значи ще бъде достижимо.

    Забележка. В условията на горния пример множеството на достижимите числа очевидно е най-малкото (в смисъл на включване) индуктивно множество.

    Сега ще обобщим основните неща от пример 1 и неговите продължения пример 1ў и пример 1І. Вместо множеството на положителните цели числа ще разглеждаме едно произволно множество U от какви да е обекти и ще искаме да дадем един общ начин за индуктивно дефиниране на съвкупност, състояща се от някои елементи на U. За целта да наречем индуктор в U коя да е наредена двойка (T,u), на която първият член T е подмножество на U, а вторият u е елемент на U. Интуитивно индукторът (T,u) може да се разглежда като разрешение да се премине към елемента u, ако може да се стигне до всеки елемент на T (в специалния случай, когато множеството T е празно, това трябва да се схваща като разрешение направо да се премине към елемента u). Един индуктор (T,u) ще записваме във вида T/u, като множеството T ще наричаме предпоставка на индуктора, а елемента t - негов резултат. Произволно множество от индуктори в U ще наричаме индуктивен механизъм в U. Коя да е индуктивна дефиниция от рода на дадената в пример 1 може да се представи чрез индуктивен механизъм в съответното множество от обекти, като се абстрахираме от наименованието, която тя въвежда, и всяко от приеманията в нея представим чрез подходящо множество от индуктори, а след това образуваме обединението на така получените множества. В случая на пример 1 това би изглеждало по следния начин: в качеството на U вземаме множеството на положителните цели числа, приемането а) представяме чрез множеството, имащо за единствен елемент индуктора Ж/1, приеманията б) и в) - съответно чрез множеството на всички индуктори в U от вида {t}/t²+1 и множеството на всички индуктори в U от вида {t}/u, където u е делител на t, а приемането г) - чрез множеството на всички индуктори в U, имащи вида {t₁,t₂}/t₁t₂; дадената в примера индуктивна дефиниция, разглеждана в нейната цялост, представяме чрез обединението на тези четири множества от индуктори.

    Обратно, на всеки индуктивен механизъм в едно множество може по естествен начин да се съпостави съответна индуктивна дефиниция в същото множество. Нека в едно множество U е даден един индуктивен механизъм M. Някои елементи на U ще наречем M-достижими и това ще направим чрез индуктивна дефиниция в U, състояща се от следните две приемания:
    А) за всеки индуктор от M, имащ вида Ж/u, съответният елемент u е M-достижим;
    Б) винаги, когато T/u е такъв индуктор от M, че множеството T не е празно и всичките му елементи са M-достижими, елементът u на U също е M-достижим.²

    Когато една индуктивна дефиниция в дадено множество U е представена чрез индуктивен механизъм M в U, лесно се съобразява, че съвкупността на елементите на U, определена чрез дадената индуктивна дефиниция, ще съвпада с множеството на M-достижимите елементи на U (например достижими в смисъл на пример 1 ще бъдат точно онези положителни цели числа, които са M-достижими при съответния индуктивен механизъм M, описан преди малко).

    Един индуктивен механизъм M ще наричаме финитарен, ако предпоставката на всеки индуктор от M е крайно множество (очевидно това условие е изпълнено за индуктивния механизъм, съответен на дефиницията от пример 1). Индуктивна дефиниция, която се представя чрез финитарен индуктивен механизъм, също ще наричаме финитарна. Пример 1ў допуска пълно обобщение за случая на финитарен механизъм. То може да се извърши по следния начин. За произволен индуктивен механизъм M в едно множество U да наречем M-пътека коя да е крайна редица от елементи на U, за всеки член u на която е изпълнено някое от следните две условия: Аў) индукторът Ж/u принадлежи на M; Бў) има такова непразно множество T от предхождащи u членове на редицата, че индукторът T/u принадлежи на M (бихме могли да заменим тези две условия с едно, като пропуснем първото от тях и думата "непразно" във второто). Тогава, ако механизмът M е финитарен, то разсъждавайки както в пример 1ў, виждаме, че за да бъде M-достижим един елемент на U, необходимо и достатъчно е той да е член на някоя M-пътека (това, че механизмът M е финитарен, се използва при съчетаването на налични M-пътеки, съдържащи като членове отделните елементи на предпоставката на един индуктор, с цел да се получи M-пътека, съдържаща като член резултата на този индуктор).

    За произволен индуктивен механизъм M горната характеризация на M-достижимите елементи не винаги е валидна. Ще дадем един пример за това.

    Пример 2. Нека U е множеството на всички цели числа (включително нулата и отрицателните цели числа). Да разгледаме индуктивния механизъм M в U, състоящ се от индуктора Ж/0, от всички индуктори от вида {t}/t+1, където t е неотрицателно цяло число, и от всички индуктори от вида {u+1,u+2,u+3,...}/u, където u е отрицателно цяло число. Без да има нужда да се използват индукторите от M от последния вид, лесно се показва, че всяко неотрицателно цяло число е M-достижимо. Това показва, че при u=-1 всички елементи на предпоставката на индуктора от последния вид са M-достижими. Следователно и неговият резултат -1 ще бъде M-достижим. Сега можем да твърдим, че и при u=-2 всички елементи на предпоставката на индуктора от последния вид са M-достижими, следователно и неговият резултат -2 ще бъде M-достижим. Продължавайки по същия начин, можем за всяко отрицателно цяло число да се убедим, че то е M-достижимо. От друга страна ясно е, че никоя M-пътека не може да съдържа като член отрицателно число, защото индукторите от M, които са с отрицателен резултат, имат безкрайни предпоставки.

    Възможна е модификация на характеризацията в духа на пример 1ў, като вместо крайни редици се използват по-сложни математически обекти (например подходящ вид дървета, които биха могли да бъдат и безкрайни). Чрез такава модификация може да се получи характеризация на M-достижимите елементи, която е в подобен дух, но е в сила и без ограничението механизмът M да бъде финитарен. Ние няма да се спираме на това, а ще покажем, че, за разлика от пример 1ў, пример 1І допуска непосредствено обобщение за произволен индуктивен механизъм.

    Нека M е произволен индуктивен механизъм в дадено множество U. Да наречем M-индуктивно множество кое да е подмножество K на U, за което е изпълнено следното условие: винаги, когато предпоставката на един индуктор от M се съдържа в K, резултатът на този индуктор също принадлежи на K (разбира се, понеже празното множество се съдържа във всяко множество, това условие включва в частност изискването за всеки индуктор от M, имащ празна предпоставка, резултатът на този индуктор да принадлежи на K). Тогава с разглеждания, подобни на направените в пример 1І, виждаме, че са M-достижими точно онези елементи на U, които принадлежат на всяко M-индуктивно множество (виждаме също, че множеството на M-достижимите елементи е най-малкото M-индуктивно множество).

    Обстоятелството, че M-достижимите елементи принадлежат на всяко M-индуктивно множество, дава един метод за доказване на общи свойства на M-достижимите елементи. А именно, за да докажем, че всички M-достижими елементи имат дадено свойство, достатъчно е да докажем, че множеството на елементите на U, притежаващи това свойство, е M-индуктивно. Този метод на доказване ще наричаме индукция, съобразена с индуктивния механизъм M. Когато механизмът M представя дадена индуктивна дефиниция, споменатия метод ще наричаме още индукция, съобразена с дадената индуктивна дефиниция.

    Ето един прост пример за приложение на току-що посочения метод. Да означим с K множеството на резултатите на онези индуктори от M, на които предпоставката се съдържа в множеството на M-достижимите елементи. Това множество е M-индуктивно. Оттук следва, че всички M-достижими елементи принадлежат на K, т.е. всеки M-достижим елемент е резултат на някой индуктор от M, на който предпоставката се съдържа в множеството на M-достижимите елементи (всъщност това е ясно и от смисъла на индуктивната дефиниция за M-достижимост, но лесно могат да се дадат по-интересни примери за приложение на метода - да речем доказателството от пример 1, че достижимите числа не се делят на 3, би могло да се оформи като приложение на този метод).

Задачи

  Последно изменение: 9.01.2001 г.

Previous

Next

Contents