Математическая логика

Теория множеств ZFC

Вся современная математика строится на 9 аксиомах. Числа, функции, пространства, группы - всё это множества, и все их свойства выводятся из этих 9 утверждений. Теория множеств Цермело-Френкеля с аксиомой выбора (ZFC) - стандартный фундамент математики.

Аксиома выбора эквивалентна лемме Цорна - используется в каждом доказательстве теоремы о существовании базиса в произвольном векторном пространстве
Теоремы об измеримости в теории меры зависят от ZFC
Вопрос P = NP, возможно, независим от ZFC

Споры об аксиоме выбора

Аксиому выбора (AC) сформулировал Цермело в 1904 году для доказательства теоремы о хорошей упорядоченности. Она вызвала бурные споры: одни математики считали её само собой разумеющейся, другие - неприемлемо неконструктивной. Горан Банах и Альфред Тарский показали в 1924 году: из AC следует парадоксальное разложение шара (теорема Банаха-Тарского).

Аксиомы ZFC

ZFC строится на едином отношении принадлежности ∈. Все математические объекты кодируются как множества: число 0 = ∅, число 1 = {∅}, число 2 = {∅, {∅}} и т.д.

Аксиома выделения ограничена: из множества x можно выделить подмножество {z ∈ x : φ(z)}. Но нельзя собрать {z : φ(z)} для произвольного φ - это привело бы к парадоксу Рассела. Именно это разграничение сделал Цермело, исправив наивную теорию Кантора.

Почему в ZFC аксиома выделения ограничена формулой вида {z ∈ x : φ(z)}, а не {z : φ(z)}?

Ординалы

Ординал - это транзитивное множество, хорошо упорядоченное ∈. Ординалы обобщают натуральные числа на бесконечность: 0 = ∅, 1 = {∅}, 2 = {∅,{∅}}, ..., ω = ℕ, ω+1 = ω∪{ω}, ω+2, ..., ω·2, ..., ω², ..., ωω, ..., ε₀, ...

Чем ω+1 отличается от ω в теории ординалов?

Кардиналы

Кардинал - ординал, не находящийся в биекции ни с каким меньшим ординалом. Кардиналы измеряют «размер» множеств: |A| = |B| тогда и только тогда, когда существует биекция между A и B.

Почему ℵ₀ · ℵ₀ = ℵ₀ (счётное × счётное = счётное)?

Аксиома выбора

Аксиома выбора позволяет «произвольно» строить любые множества

AC гарантирует существование функции выбора, но не говорит, как её построить. Она неконструктивна: мы знаем, что выбор существует, но не можем его описать явно в общем случае.

Именно эта неконструктивность вызвала споры. Конструктивные математики (Бишоп, Мартин-Лёф) разрабатывают математику без AC, где любой объект строится явно.

Аксиома выбора?

Review the concept above.