Упражнения

1. Докажите индукцией по , что

2. Докажите индукцией по , что множество из элементов имеет подмножеств.

3. Пусть А и В — конечные множества, состоящие из элементов соответственно. Докажите индукцией по , что:

число инъективных отображений множества А в В равно

число всевозможных отображений множества А в В равно

4. Докажите, что если А — подмножество множества натуральных чисел и для некоторого из А выполняется условие: если для каждого натурального числа при из следует , то каждое натуральное число принадлежит множеству А.

5. Докажите индукцией по , что композиция инъективных функций является инъективной функцией.

6. Докажите следующее утверждение (принцип Дирихле): если требуется разложить более чем предметов по местам, то по крайней мере на одно место придется положить более чем один предмет.

7. Запишите аксиомы I-VII системы натуральных чисел на языке логики предикатов (заменив аксиому VII эквивалентным ей принципом индукции).

8. Приведите пример алгебры типа (2, 2, 0, 0), которая:

удовлетворяет аксиомам II, VII и не удовлетворяет аксиоме I (системы

удовлетворяет аксиомам I, VII и не удовлетворяет аксиоме II (системы

удовлетворяет аксиомам I, II и не удовлетворяет аксиоме VII (системы