Пеанове аксиоме

У математичкој логици, Пеано аксиоми такође познати као Дедекинд-Пеано аксиоми или Пеано постулати, су аксиоми за природне бројеве које је у 19 веку издао Ђузепе Пеано, италијански математичар. Ови аксиоми су се користили непромењени у бројевима математичких истраживања, укључујући истраживање фундаменталних питања да ли је теорија бројева конзистентна и потпуна.

Потреба да се формализује аритметика није добро цењена све до рада Херман Грасмана који је показао 1860. да многе чињенице у аритметици могу да се изведу из више основних чињеница о операцији успешности и индукцији.^[1] Године 1881, Чарлс Сандерс Перс обезбедио је аксиоматизацију природних бројева аритметике.^[2] 1888. Дедекинд је предложио још једну Аксиоматизацију природних бројева аритметике, и 1889. године, Пеано објављује прецизније формулисану верзију од њих као скуп аксиома у својој књизи, Принципи аритметике представљени уз помоћ нове методе (латински: Arithmetices principia, nova methodo exposita). 

Пеано аксиоми садрже три врсте изјава. Први аксиом тврди постојање најмање једног члана низа природних бројева. Следеће четири су опште изјаве о равноправности; у модерним третманима они се често не узимају као део Пеано аксиома, већ као аксиома "логике".^[3] Наредне три аксиоме су првог реда изјаве о природним бројевима које изражавају основне особине операције наследника. Девети, коначни аксиом је друга изјава реда принципа математичке индукције током природних бројева. Слабији систем првог реда се зове Пеано аритметика и добија се експлицитним сабирањем и множењем оперативних симбола и заменом индукционих аксиома другог реда са првим редом аксиоме шеме. 

Формулација

Када је Пеано формулисао његове аксиоме, језик математичке логике био је у раном детињству. Систем логичких нотација је направљен да презентује аксиоме што се није показало популарним, иако је била модерна нотација за скуп чланства (∈, који долази од Пеанове ε) и импликација (⊃, која долази од обрнутог 'C'.) Пеано уводи јасну разлику између математичких и логичких симбола, што тада није било често у математици; такво раздвајање је први пут уведено у часопису ''Begriffsschrift'' од стране Готлоба Фрегеа, издатог 1879.^[4] Пеано је био свестан рада Фрега и независно је поновио свој логички апарат заснован на раду Џорџа Була и Ернста Шредера.^[5]

Пеанови аксиоми дефинишу аритметичка својства природних бројева, најчешће представљена као скуп N или ${\displaystyle \mathbb {N} .}$ Потпис ( не-логички симболи формалног језика) за аксиоме укључују сталан симбол 0 и унарни симбол S.

Константа нула, се испоставила да јесте број

1. О је природан број

У наредне четири аксиоме описује се релација једнакости. Пошто су логично важећи у првом реду логике са једнакостима, они се не сматрају као део "Пеанових аксиома" у модерним третманима.^[4]

2. За сваки природан број х, х=x. Ta једнакост је рефлексивна
3. За сваки природан број x и y, ако је x=y, онда је y=x. Та једнакост је симетрична
4. За сваки природан број x,y и z ако је x=y и y=z и x=z. Онда је једнакост прелазна
5. За све a и b ако је b природан број а a=b и a је природан број. Онда су природни бројеви затворени у неједнакости

Преостале аксиоме дефинишу аритметичка својства природних бројева. Природни се претпоставља да буду затворени под једном вредношћу "наследника" функције S.

6. За сваки природан број n, S(n) је природан број

Пеанова првобитна формулација аксиома користи 1 уместо о за "први" природан број.^[6] Овај избор је произвољан, пошто аксиом 1 не додељује броју 0 никаква додатна својства. Међутим, пошто је 0 адитивни идентитет у аритметици, већина модерних формулације Пеанових аксиома почињу од 0. Аксиоме 1 и 6 дефинишу унарну операцију природних бројева: број 1 може бити дефинисан као S(0), 2 као S(S(0)) (што је исто S(1)), и уопште било који природан број као резултат -струке примене S на 0. Наредна два аксиома дефинишу особине овог представљања.

7. За све природне бројеви m и n, m=n ако је и само ако S(m)=S(n). S је инјекција
8. За сваки природан број n,S(n)=0 је нетачно ако нема ниједног броја чији је наследник 0

Ланац лаких домина, почевши од најближе, може представљати N, међутим, аксиоми 1-8 су такође задовољени скуп свих, светлих и тамних, домина.^[7] Девети аксиом ограничава ланац светлих комада по индукцији тако да једно светло домина ће пасти када се најближе сруши.^[8]

Аксиоми 1, 6, 7 и 8 значе да скуп природних бројева садржи различите елементе 0, и даље да. Ово показује да је скуп природних бројева бесконачан. Међутим, да би показали да = {0, S(0), S(S(0)), …}, мора бити показано да мора бити показано да сваки природан број је садржан у Да би се то урадило, захтева се додатни аксиом, који се понекад назива аксиом индукције. Овај аксиом обезбеђује метод за расуђивање о скупу свих природних бројева 

9. Ако је K скуп такав да:
   • 0 је у К и
   • за сваки природан број n, ако n је у K, онда S(n) је у K,
   онда K садржи сваки природан број.

Индукован аксиом се понекад наводи у следећем облику: |9=Ако φ је унарни предикат такав да:

• φ(0) је тачно, и
• за сваки природан број , ако φ() је тачно, онда је тачно,

онда је тачно за сваки природан број . }}

У оригиналној формулацији Пеана, индукциони аксиом је аксиом другог реда. Сада је уобичајено заменити овај принцип другог реда са слабијом шемом индукције првог реда. Постоје значајне разлике између другог реда и првог реда формулације, као што је речено у одељку Модели испод. 

Аритметика

Пеано аксиоми се могу повећати са операцијама сабирања и множења и уобичајеном сумом (линеарном) редоследом N. Одговарајуће функције и односи се граде у другом реду логике, и показало се да је јединствено користећи Пеано аксиоме. 

Сабирање

Сабирање је функција која спаја два природна броја (два елемента Н) један се додаје на други. Дефинисано је као рекурзивно:

На пример,

a + 1 = a + S(0) = S(a + 0) = S(a).

Структура (N, +) је комутативна семигрупа са елементом 0. (N, +) је такође опозивна магма, и такво уграђена у групи. Најмања група уграђивања  N су Цео број.

Множење

Слично, множење је функција која множи два цела броја један са другим. Као додатак може се дефинисати рекурзивно:

Лако се види да постављање б једнако 0 даје мултипликациони идентитет: 

a · 1 = a · S(0) = a + (a · 0) = a + 0 = a

Осим тога, множење дистрибуира преко тога: 

a · (b + c) = (a · b) + (a · c).

Ово, (N, +, 0, ·, 1) је комутативни прстен

Неједнакости

Обично коришћење правила релације ≤ на природне бројеве може бити дефинисано као следеће, укључујући 0 као природан број.

За свако a, b ∈ N, a ≤ b ако и само ако постоји неко c ∈ N такво да a + c = b.

Ова релација је стабилна за сабирање и множење: за ${\displaystyle a,b,c\in N}$, ако a ≤ b, онда:

• a + c ≤ b + c, и
• a · c ≤ b · c.

Структура (N, +, ·, 1, 0, ≤) је одређен прстен јер не постоји број између 0 и 1.

Аксиом индукције понекад има јаку форму правећи ≤ ред:

За било који исказ φ, ако

• φ(0) је тачно и
• за свако n, k ∈ N, ако k ≤ n имплицира φ(k) је тачно, онда φ(S(n)) је тачно,

онда за свако n ∈ N, φ(n) је тачно.

Ова форма аксиоме индукције је једноставна косенквенција стандардне формулације, али често више одговара за расуђивање ≤ реда. На пример, да покаже да су природни борјеви добро одређени—сваки непразни подскуп N има најмањи елемент. Нека непразни X ⊆ N буде дат и  претпостављен да X нема најмањи елемент.

• Зато што је 0 последњи елемент N, мора бити 0 ∉ X.
• За било који n ∈ N, претпостављајући за свако k ≤ n, k ∉ X. Онда S(n) ∉ X, у другом случају би био последњи елемент X.

Ово, уз помоћ јаких принципа индукције, за свако  n ∈ N, n ∉ X. Ово, X ∩ N = ∅, што је супротно X који је подскуп непразни N. Тако X има најмањи елемент.

Први ред теорије аритметике

Сви Пеамови аксиоми осим деветог сучињеница првог реда логике.^[9] Аритметичке операције са сабирањем и множењем и релације редова могубити дефинисане користећи аксиому првог реда. Аксиома индукције је другог реда, али може бити трансформисана у први ред аксиоме шеме индукције. Таква шема укључује један аксиом по предикту дефинисан у првом реду језика Пеано аритметике, правећи је слабијим од аксиоме другог реда.^[10]

Аксиномизација првог реда Пеанове аритметике имају битну ограниченост. Међутим у другом реду логике, могуће је дефинисати сабирање и мнозење операција од наследника операција али ово не може бити урађено у рестриктивнијим постављањима првог реда логике  Тако сад сабирање и множење су директно повезане са потписом Пеанове аритметике, и аксиоми су укључени да односе три операције једну ка другој.

Следћа листа аксиома, која садржи 6 од 7 аксиома Робинсонове аритметике, је довољна за ову сврху^[11] 

• ∀x∈N. 0 ≠ S(x)
• ∀x,y∈N. S(x) = S(y) ⇒ x = y
• ∀x∈N. x + 0 = x
• ∀x,y∈N. x + S(y) = S(x + y)
• ∀x∈N. x ⋅ 0 = 0
• ∀x,y∈N. x ⋅ S(y) = x ⋅ y + x

Као додатак овој листи бројчаних аксиома, Пеано аритметика садржи шему индукције, која се састоји од пребројиво много скупова аксиома. За сваку формулу φ(x,y₁,...,y_k) у језику Пеано аритметике, први ред аксиоме индукције за φ је реченица.

${\displaystyle \forall {\bar {y}}(\varphi (0,{\bar {y}})\land \forall x(\varphi (x,{\bar {y}})\Rightarrow \varphi (S(x),{\bar {y}}))\Rightarrow \forall x\varphi (x,{\bar {y}}))}$

где је ${\displaystyle {\bar {y}}}$ скраћеница за y₁,...,y_k. Први ред индуцкијске шеме укључује сваки пример првог реда индукцијског аксиома, који укључује аксиому индукције за сваку формулу φ.

Еквивалент аксиомизације

Има много различитих, или еквивалентних аксомизација Пеанове аритметике. Док неке аксиомизације, као што је описано, користе потпис који користи симболе за 0 као наследник, додатак, је множење, друге аксиомизације користе језике одређених полупрстена, укључујући и додатак одређеном релацијом симбола. Аксиомизација почиње са праћењем аксиома који описују дискретне одређене полупрстенове^[12]

1. ${\displaystyle \forall x,y,z\in N}$. ${\displaystyle (x+y)+z=x+(y+z)}$, додатак је асоцијативан.
2. ${\displaystyle \forall x,y\in N}$. ${\displaystyle x+y=y+x}$, додатак је комутативан.
3. ${\displaystyle \forall x,y,z\in N}$. ${\displaystyle (x\cdot y)\cdot z=x\cdot (y\cdot z)}$, множење је асоцијативно.
4. ${\displaystyle \forall x,y\in N}$. ${\displaystyle x\cdot y=y\cdot x}$, множење је комутативно.
5. ${\displaystyle \forall x,y,z\in N}$. ${\displaystyle x\cdot (y+z)=(x\cdot y)+(x\cdot z)}$, дистрибутивни закон.
6. ${\displaystyle \forall x\in N}$. ${\displaystyle x+0=x\land x\cdot 0=0}$, нула је идентитет елемента за сабирање.
7. ${\displaystyle \forall x\in N}$. ${\displaystyle x\cdot 1=x}$,  један је идентитет елемента за множење.
8. ${\displaystyle \forall x,y,z\in N}$. ${\displaystyle x<y\land y<z\Rightarrow x<z}$,  '<' операција је транзитивна.
9. ${\displaystyle \forall x\in N}$. ${\displaystyle \neg (x<x)}$,  '<' операција је ирефлексивна.
10. ${\displaystyle \forall x,y\in N}$. ${\displaystyle x<y\lor x=y\lor y<x}$.
11. ${\displaystyle \forall x,y,z\in N}$. ${\displaystyle x<y\Rightarrow x+z<y+z}$.
12. ${\displaystyle \forall x,y,z\in N}$. ${\displaystyle 0<z\land x<y\Rightarrow x\cdot z<y\cdot z}$.
13. ${\displaystyle \forall x,y\in Nx<y\Rightarrow \exists z\in Nx+z=y}$.
14. ${\displaystyle 0<1\land \forall x\in N}$. ${\displaystyle x>0\Rightarrow x\geq 1}$.
15. ${\displaystyle \forall x\in N}$. ${\displaystyle x\geq 0}$.

Теорија је дефинисана са овим аксиомима и позната је као ПА- : ПА је добијена додавањем индукцијске шеме првог реда.

Битна особина PA⁻ је да било која структура M задовољава теорију која има почетни сегмент (одређен са ≤) изоморфни на N. Елементи M\N су познати као нестандардни елементи.

Модели

Модел Пеано аритметике је тродупла (N, 0, S), где N је (нужно бесконачан) скуп, 0 ∈ N и S : N → N задовољава аксиоме изнад. Дедекинд је доказао у његовој књизи 1888k, Шта су бројеви и шта би требало да буду (нем: Was sind und was sollen die Zahlen) да било која два модела Пеано аксиома (укључујући други ред аксиоме индукције) су изоморфна. Практично, дата два модела (N_A, 0_A, S_A) и (N_B, 0_B, S_B) Пеано аксиома, постоји јединствени хомоморфизам f : N_A → N_B који задовољава

${\displaystyle {\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}}$

и то је бијекција. То значи да други ред Пеано аксиома је категорички. Ово није случај са било којим првим редом реформулације Пеано аксиома.

Нестандардни модели

Иако уобичајени природни бројеви задовољавају аксиоме ПА, постоје и други нестандардни модели, као што; Компактност теорема подразумева  да постојање нестандардних елемената не може искључено у првом реду логике. Навише Ловенхајм-Сколем теорема показује да постоје нестандардни модели ПА свих бесконачних кардиналности. Ово није случај за оригиналне (другог реда) Пеано аксиома, које имају само један модел, до изоморфизма. То илуструје један начин на који је првог реда система ПА слабији од другог реда Пеано аксиома.

Када се тумачи као доказ у оквиру првог реда теорије скупова, као што ЗФЦ, Дедекинд је категорисао доказ за ПА показујући да сваки модел теорије скупова има јединствен модел на Пеано аксиомима, до изоморфизма, који уграђује као иницијални сегмент све друге моделе ПА садржане у том моделу теорије скупова. У стандардном моделу теорије скупова, овај најмањи модел ПА је стандардни модел ПА; међутим, у нестандардном моделу теорије скупова, то може бити ненстандардни модел ПА. Ова ситуација не може да се избегне са било којим првим редом формализације теорије скупова . 

Природно је да се питамо да ли бројиви нестандардни модели могу бити експлицитно изграђени. Одговор је потврдан, као што је Сколем 1933. године експлицитно изградио такав нестандардни модел. С друге стране, Тененбаумова теорема, доказала је 1959. године, да не постоји пребројив нестандардни модел ПА у којој ни сабирање ни множење нису пребројиви.^[13] бројивих нестандардних модела ПА. Међутим, постоји само један могући тип реда бројивог нестандарног модела. Нека ω буде ред типа природних борјева, ζ буде ред типа целих бројева, и η буде ред тима рационалних бројева, ред типа било којег бројивог нестандардног модела ПА је ω + ζ·η, који може бити визуелисан као копија природних бројева праћена са линеарним одређењем копије целих бројева.

Теоретски модели скупа

Пеано аксиоми се могу извести из постављених теоријских конструкција природних бројева и аксиома теорије скупова, као што је ЗФ. ^[14] Стандардна конструкција природних бројева, према фон Нојману, почиње од дефиниција 0 као празног скупа, ∅, и оператора s на скуповима дефинисаг као:

s(a) = a ∪ { a }.

Скуп природних бројева N је дефинисан као пресек свих скупова затворених испод s који садржи празан скуп. Сваки природан број је еквивалентан (као скуп) скупу природних бројева мање него:

${\displaystyle {\begin{aligned}0&=\emptyset \\1&=s(0)=s(\emptyset )=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\3&=...=\{0,1,2\}\end{aligned}}}$

и тако даље. Скуп N заједно са 0 и фукција наследник s : N → N задовољава Пеано аксиоме.

Пеано аритметика је екоконзистенција са неколико слабих система теорије скупа.^[15] Један такав систем је ЗФК са аксиомом бесконачности замењен са својом негацијом. Још један такав систем се састоји од опште теорије скупова (екстенционалности, постојање празног скупа, и аксиом адјункције), увећане за аксиом шеме наводећи да је имовина која важи за празан скуп и која важи за адјункцију мора да важи за све скупове.

Интерпретација у категорији теорије

Пеано аксиоми могу такође схваћени коришћењем теорије категорије. Нека C буде категорија са терминалним објектом 1_C, и дефинише категорију тачкастог унарног система, US₁(C) као следеће::

• Објекти US₁(C) су триплети (X, 0_X, S_X) где X је објекат C, и 0_X : 1_C → X и S_X : X → X су C-морфизми.
• Морфизам φ : (X, 0_X, S_X) → (Y, 0_Y, S_Y) је C-морфизам φ : X → Y са φ 0_X = 0_Y и φ S_X = S_Y φ.

Онда C је речено да задовољи Дедекинд-Пеано аксиоме ако US₁(C) има почетни објекат; овај почетни објекат је познат као објекат природног броја у C. Ако (N, 0, S) је почетни објекат, и (X, 0_X, S_X) је било који други објекат, онда је једиствено спајање u : (N, 0, S) → (X, 0_X, S_X) такво да

${\displaystyle {\begin{aligned}u0&=0_{X},\\u(Sx)&=S_{X}(ux).\end{aligned}}}$

Ово је управо рекурзивна дефиниција 0_X и S_X.

Доследност

Када су Пеанови аксиоми прво предложени, Бертранд Русел и остали су се сложили да су ови аксиоми имплицитно дефинисани са оним на шта мислимо кад кажемо "природни број". Анри Поенкаре је био стога опрезнији и рекао је да се природни бројеви дефинишу само ако су у складу, ако постоји доказ који почиње из ових аксиома и који води ка контрадикцији  0 = 1 , онда су аксиоми недоследни, и не могу дефинисати ништа. 1900 године, Давид Хилберт поставља проблем доказивања њихове доследности користећи само методе финитизма као други својих двадесет и три проблема.^[16] 1931, Курт Гедел доказао је своју другу непотпуну теорему, која показује да таква конзистентност доказ не може бити формализован у Пеано аритметици. ^[17]

Иако је широко тврде да Годел теорема искључује могућност финитистизације доследности доказа за Пеано аритметике, то зависи од тога шта се подразумева од стране финитизма. Гедел сам указује на могућност давања финитизма конзистенције доказа Пеано аритметике или јачим системима помоћу финитизма метода које нису формализоване у Пеано аритметици, и 1958. године, Гедел је објавио метод за доказивање доследности аритметике помоћу теорије типа.^[18] 1936 године, Герхард Генцен дао је доказ конзистенције Пеано аксиома користећи трансфинт индукцију звану ε0.^[19] Генцен је објаснио: "Циљ овог рада је да се докаже конзистентност основне теорије бројева, односно да се смањи питање доследности одређених фундаменталних принципа". Генценов доказ је вероватно финитизам, од  ε₀ могу бити кодиране у смислу коначних објеката (на пример, као Тјурингова машина која описује погодне редоследе на целим бројевима, или више апстрактно која се састоји од ограничених дрвећа, погодно линеарно одређених). 

Огромна већина савремених математичара верује да Пеано аксиоми су у складу, ослањајући се на интуицију или прихватање конзистенције као доказ да је такав Генцен доказ. Мали број математичара који се залажу ултрафинитизму одбацујући Пеано аксиоме, јер аксиоми захтевају бесконачан низ природних бројева. 

Види још

• Фондације математике
• Годстајнова теорема
• Париз-Харингова теорема
• Пресбургова аритметика
• Робинсова аритметикс
• Други ред аритметике
• Нестандардни модел аритметике
• Теоретски скуп дефиниција природних бројева
• Фрејгова теорема