24. Арифметика Пеано. Теорема Геделя о неполноте (1158031), страница 2
Текст из файла (страница 2)
Но тогда придется создать «кодекс теории множеств»,в котором должно быть указано, какие именно конструкциипризнаются множествами, и какими свойствами они должныобладать.Попытку создания такого «кодекса теории множеств» —аксиоматической теории множеств — предприняли в ЭрнестЦермело в 1908 г.. Аксиоматику Цермело пополнили АбрахамФренкель, Торальф Сколем, Джон фон Нейман.Теория множеств Цермело–ФренкеляПонятие множества и свойства множеств можно описать сиспользованием единственного предикатного символа ∈ ,обозначающего отношение принадлежности одного множествав качестве элемента другого множества.Представим себе математический мир, состоящий только измножеств.
Этот мир может быть описан следующимиаксиомами.Теория множеств Цермело–Френкеля1) ∀x, y , u, v (x = y & u = v ) → (x ∈ u ≡ y ∈ v )(Аксиома равенства множеств)2) ∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y )(Аксиома объемности)3) ∀x∀u1 , . . . , un ∃y ∀z (z ∈ y ≡ (z ∈ x & ϕ(z, u1 , . . . , un )))(Схема аксиом выделения)здесь ϕ(x, u1 , . . . , un ) — произвольная формулалогики предикатов сигнатуры σ = h∈i .Теория множеств Цермело–ФренкеляПримеры применения аксиомы выделения1.
Существует единственное пересечение двух множествоСуществование пересечения двух множеств следует из аксиомывыделения∀x1 , x2 ∃y ∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 )),а единственность пересечения следует из аксиомы объемности∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y ).Теория множеств Цермело–ФренкеляПримеры применения аксиомы выделения2. Существует единственное пустое множествоСуществование пустого множества следует из аксимывыделения∀x ∃y ∀z(z ∈ y ≡ (z ∈ x & z 6= z)),а единственность пустого множества следует из аксиомыобъемности∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y ).Но здесь есть один нюанс.
А откуда берется множество X наосновании которого определяется пустое множество?Теория множеств Цермело–ФренкеляПримеры применения аксиомы выделения2. Существует единственное пустое множествоСуществование пустого множества следует из аксимывыделения∀X ∃y ∀z(z ∈ y ≡ (z ∈ X & z 6= z)),а единственность пустого множества следует из аксиомыобъемности∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y ).Но здесь есть один нюанс. А откуда берется множество X наосновании которого определяется пустое множество?Теория множеств Цермело–ФренкеляПримеры применения аксиомы выделенияПоэтому приходится вводить специальную аксиому.4).
∃y ∀z ¬(z ∈ y )(Аксиома пустого множества)Введем специальный символ ∅ для обозначения пустогомножества, а запись y = ∅ будем рассматривать каксокращенное обозначение формулы∀z ¬(z ∈ y ) .Теория множеств Цермело–ФренкеляПримеры применения аксиомы выделения3. Существует единственное объединение двух множествКазалось бы, объединение множеств легко ввести так же, какэто было сделано для пересечения:∀x1 , x2 ∃y ∀z (z ∈ y ≡ (z ∈ x1 ∨ z ∈ x2 )) .Но эта формула не подпадает под схему аксиом выделения∀x∀u1 , .
. . , un ∃y ∀z (z ∈ y ≡ (z ∈ x & ϕ(z, u1 , . . . , un ))) .Можно было бы записать определение объединения так:∀X, x1 , x2 ∃y ∀z (z ∈ y ≡ (z ∈ X & (z 6= x1 ∨ z ∈ x2 ))) .Но совершенно непонятно, откуда взять подходящее множествоX . Может быть, в качестве X взять x1 ∪ x2 ? Но мы ведь еще неТеория множеств Цермело–ФренкеляПримеры применения аксиомы выделения3. Существует единственное объединение двух множеств.Поэтому приходится вводить две специальные аксиомы.5). ∀y , z ∃x ∀u (u ∈ x ≡ (u = y ∨ u = z))(Аксиома пары)Множество x, существование которого утверждает аксиомапары, традиционно обозначается {y , z}.6). ∀y ∃x ∀u (u ∈ x ≡ ∃z (z ∈ y & u ∈ z))(Аксиома объединения)Множество x, существование которого утверждаетаксиомаSобъединения, традиционно обозначаетсяz или болееz∈yкоротко ∪y .
Таким образом x1 ∪ x2 — это ∪{x1 , x2 }.Теория множеств Цермело–ФренкеляПримеры применения аксиомы выделения4. А что делать, если нам нужно множество, состоящее изодного-единственного элемента?Для этого достаточно выделения и аксиомы пары:множество, состоящее из одного элемента u — это множество{u,u}.5. А что делать, если нам нужны упорядоченные наборыэлементов?Для этого достаточно аксиомы выделения и аксиомы пары:упорядоченная пара hy , zi — это множество {y , {y , z}}.Далее аналогично можно определять упорядоченные наборы(кортежи), функции, инъективные отображения, биективныеотображения, отношения включения, равномощности и т. д.Теория множеств Цермело–ФренкеляНо таким образом из пустого множества ∅, — единственногомножества, существование которого гарантируют аксиомы, —можно получить только конечные множества.
А откудавозьмутся бесконечные множества?7). ∃x (∅ ∈ x & ∀y (y ∈ x → y ∪ {y } ∈ x))(Аксиома бесконечности)Фактически, аксиома бесконечности определяет множествонатуральных чисел:no∅,{∅},{∅,{∅}},∅,{∅},{∅,{∅}},...|{z} |{z} | {z } |{z}0123Теория множеств Цермело–ФренкеляА откуда возьмутся несчетные множества?8). ∀y ∃x ∀z (z ∈ x ≡ ∀u (u ∈ z → u ∈ y ))(Аксиома степени)Аксиома степени определяет множество всех подмножествзаданного множества (множество-степень, powerset). Значит,множества могут нарастать неограниченно «высоко».Теория множеств Цермело–ФренкеляА являются ли множествами образы множеств относительнозаданных функций, определяемых при помощи формул логикипредикатов?9).
∀x ∀y , z, u (y ∈ x & ϕ(y , z) & ϕ(y , u) → z = u) →→ ∃v ∀w (w ∈ v ≡ ∃t (t ∈ x & ϕ(t, w )))(Схема аксиом замены)Теория множеств Цермело–ФренкеляА насколько «глубоко» могут опускаться множества? Не могутли у нас образовываться такие множества, которые входят всостав самих себя в качестве элементов?10).
∀x (x 6= ∅ → ∃y (y ∈ x & x ∩ y = ∅))(Аксиома фундирования (регулярности))Эта аксиома играет роль предохранителя, оберегающеготеорию множеств от парадоксов. Аксиома фундированияобъявляет, что семейства множеств видаnoX1 , X2 , X3 , . . . ,у которых X2 ∈ X1 , X3 ∈ X2 , . . . , Xn+1 ∈ Xn , · · · и т. д.множествами не являются .Теория множеств Цермело–ФренкеляПримеры применения аксиомы фундированияZF ` ∀u(u ∈/ u)Из аксиомы фундирования∀x (x 6= ∅ → ∃y (y ∈ x & x ∩ y = ∅))следует (если в качестве x выбрать {u})ZF ` ∃y (y ∈ {u} & u ∩ y = ∅) .Поскольку единственным элементом y в множестве {u}является u, получаемZF ` {u} ∩ u = ∅ .Следовательно, ZF ` u ∈/ u.Теория множеств Цермело–ФренкеляПримеры применения аксиомы фундированияПопробуйте самостоятельно убедиться, что из аксиом теориимножеств Цермело–Френкеля следует невозможностьсуществования «парадоксальных множеств»:ZF ` ∀u, v (u ∈/ v ∨v ∈/ u)ZF ` ¬∃x ∀y (y ∈ x ≡ y ∈/ y)Нужны ли еще какие-нибудь другие аксиомы?Теория множеств Цермело–ФренкеляК сожалению, для решения некоторых задач приходитсявводить дополнительные аксиомы.Например, интуиция подсказывает, что любые два множествадолжны быть сравнимы по мощности.
Два множества A и Bназываются равномощными (A ∼ B), если существуетбиективная функция, отображающая одно множество надругое. Справедливо ли следующее утверждение?Теорема трихотомии. Для любых двух множеств A и B верноодно из трех:IIIлибо A ∼ B,либо A ∼6 B, но существует такое A0 , A0 ⊂ A, что A0 ∼ B,либо A ∼6 B, но существует такое B 0 , B 0 ⊂ B, что A ∼ B 0 .Эту теорему можно доказать, но лишь при том условии, если унас есть хоть какой-нибудь способ, позволяющий выбрать изпроизвольного непустого множества хоть какой-нибудь элемент.Чтобы этот способ выбора стал легальным средствомдоказательства, нужно ввести специальную аксиому выбора .Теория множеств Цермело–ФренкеляАксиома выбора (CA)Каково бы ни было множество попарно непересекающихсямножеств U = {X1 , X2 , .
. . }, существует множество Y ,содержащее в точности по одному представителю из каждогомножества X1 , X2 , . . . семейства U.Аксиома выбора используется при доказательстве оченьбольшого числа теорем математики. С ее помощью можнодоказать весьма неожиданные утверждения. К их числуотноситсяТеорема ЦермелоЛюбое множество можно вполне упорядочить, т.
е. определитьна этом множестве такое отношение линейного порядка, прикотором не существует бесконечно убывающихпоследовательностей элементов.Теория множеств Цермело–ФренкеляА не привнесет ли аксиома выбора какое-нибудь противоречиев теорию ZF? Этот вопрос остается открытым и по сей день.Есть в теории множеств и другие задачи, для решения которыхнедостаточно аксиом теории множеств ZF.Континуум-гипотеза (CH)Любое подмножество множества вещественных чисел либоявляется счетным, либо равномощно множеству вещественныхчисел (является континуальным).В 1939 г. К.
Гедель доказал теорему:Если теория множеств ZF+CA непротиворечива, то теорияZF+AC+CH также непротиворечива .В 1963 г. П. Коэн доказал теорему:Если теория множеств ZF+CA непротиворечива, то теорияZF+AC+¬CH также непротиворечива .Формальная арифметикаА можно ли полностью аксиоматизировать арифметикунатуральных чисел?В 1889 г.
итальянский математик Д. Пеано предложил списокаксиом, при помощи которых можно доказывать утверждения освойствах натуральных чисел.Арифметика Пеано (PA) образуется за счет добавления к ИПРсигнатуры h0, s, +, ×i следующих аксиом.Здесь s(x) нужно рассматривать как одноместную операцию,реализующую функцию вычисления следующего натуральногочисла x + 1.Формальная арифметика1. ∀x, y (s(x) = s(y ) → x = y );2.
∀x (s(x) 6= 0);3. ∀x ∃y (x 6= 0 → x = s(y ));4. ∀x (x + 0 = x);5. ∀x, y (x + s(y ) = s(x + y ));6. ∀x (x × 0 = 0);7. ∀x, y (x × s(y ) = x × y + x);8. ϕ(0) & ∀x (ϕ(x) → ϕ(s(x))) → ∀x ϕ(x).Вопрос о непротиворечивости и полноте этой аксиоматическойтеории долгое время оставался центральной проблемойматематики. В 1931 г. К. Гедель доказал теорему, которая даласовершенно неожиданный ответ на этот вопрос.Формальная арифметикаНумералы и арифметизуемые отношенияНумералом n̄ натурального числа n называется термs(s(. . . s( 0) .
. . ))| {z }n разНапример, 4̄ — это терм s(s(s(s(0)))) .Отношение P (k) на множестве натуральных чисел называетсяарифметизуемым , если существует такая формулаϕ(x1 , x2 , . . . , xk ) , что для всякого набора натуральных чисел(n1 , n2 , . . . , nk ) верны соотношенияIP (k) (n1 , n2 , . . . , nk ) = true ⇐⇒ PA ` ϕ(n̄1 , n̄2 , . . . , n̄k ) ,IP (k) (n1 , n2 , . . . , nk ) = false ⇐⇒ PA ` ¬ϕ(n̄1 , n̄2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
