Решить задачи по математической логике

1. Пусть M — произвольное множество. Покажите, что (S(M), ?) является группой.
Указание. Проверьте, что выполняются все аксиомы.
2. Докажите, что для любого натурального числа n > 2 группа Sn не
является абелевой.
3. Докажите, что любая группа из двух элементов изоморфна группе
({a, b}, ?), где a ? a = b ? b = a, a ? b = b ? a = b.
6. * Сколько существует попарно неизоморфных групп из четырёх
элементов?
7. Докажите, что в кольце Zn делители нуля есть в том и только том
случае, когда n–– составное число.
8. Даны n, a ? N. Определите минимальное такое m ? N, что
m · [a]n = [a]n + . . . + [a]n = [0]n
(сумма содержит m слагаемых).
9. * Докажите, что элемент [k]n кольца Zn имеет обратный относительно умножения, если и только если числа k и n взаимно простые.
10. Напишите формулу языка арифметики, выражающую предикат
x = ?(a, b, i)
(здесь ? — бета-функция Гёделя).
11. Напишите формулу языка арифметики, выражающую предикат
?n(x = n!)
(x является факториалом некоторого n).
13. Напишите формулу языка арифметики, выражающую предикат
x = y
z
.
14. Докажите, что множество всех замкнутых арифметических формул, истинных в стандартной интерпретации, неперечислимо.
Указание. Используйте теорему 2 из теоретического материала и
теорему Поста о связи перечислимости и разрешимости.