Задачи към "Индуктивни дефиниции"

    1. Покажете, че множеството на достижимите числа, дефинирано в пример 1, няма да се промени, ако заменим условията в) и г) със следните:
    вў) когато едно число t е достижимо, всяко положително цяло число, което е делител на t и е различно от 1 и от t, също е достижимо;
    г') произведението на всеки две достижими числа, различни от 1, също е достижимо.

    2. В множеството на простите числа да дефинираме един индуктивен механизъм M по следния начин: една наредена двойка (T,u) причисляваме към M тогава и само тогава, когато за някое положително цяло число t е вярно, че T е множеството на простите делители на t, а u е прост делител на числото t2+1. Докажете, че M-достижими са точно онези прости числа, които са достижими в смисъла на пример 1. 
    Упътване. За да докажете, че простите числа, достижими в смисъла на пример 1, са M-достижими, покажете, че простите делители на всяко число, достижимо в смисъла на пример 1, са M-достижими.

    3. Нека a и b са две различни букви от дадена азбука и нека някои думи над тази азбука са наречени специални, като за целта е използвана следната индуктивна дефиниция: а) празната дума е специална; б,в) за всяка специална дума w думите awb и bwa са също специални; г,д) при всеки избор на специалните думи x, y и z думите axbybza и bxayazb са също специални. Докажете, че една дума над дадената азбука е специална точно тогава, когато в тази дума не участват други букви освен a и b, а те пък участват в нея равен брой пъти.

    4. Нека M е такъв индуктивен механизъм в дадено множество U, че за всеки индуктор T/u от M множеството T е празно или има точно един елемент. Да наречем канонична M-пътека такава непразна крайна редица u0, u1, ..., um от елементи на U, че индукторът Ж/u0 и индукторите {ui}/ui+1, i=0,1,...,m-1, принадлежат на M. Покажете, че един елемент на U е M-достижим точно тогава, когато е последен член на някоя канонична M-пътека.

 

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