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

(преусмерено са Peano axioms)

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

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

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

Формулација

уреди

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

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

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

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

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

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

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

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

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

  1. За све природне бројеви m и n, m=n ако је и само ако S(m)=S(n). S је инјекција
  2. За сваки природан број n,S(n)=0 је нетачно ако нема ниједног броја чији је наследник 0
 
Ланац лаких домина, почевши од најближе, може представљати N, међутим, аксиоми 1-8 су такође задовољени скуп свих, светлих и тамних, домина.[7] Девети аксиом ограничава ланац светлих комада по индукцији тако да једно светло домина ће пасти када се најближе сруши.[8]

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

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

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

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

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

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

Аритметика

уреди

Пеано аксиоми се могу повећати са операцијама сабирања и множења и уобичајеном сумом (линеарном) редоследом 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, bN, ab ако и само ако постоји неко cN такво да a + c = b.

Ова релација је стабилна за сабирање и множење: за  , ако ab, онда:

  • a + cb + c, и
  • a · cb · c.

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

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

За било који исказ φ, ако
  • φ(0) је тачно и
  • за свако n, kN, ако kn имплицира φ(k) је тачно, онда φ(S(n)) је тачно,
онда за свако nN, φ(n) је тачно.

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

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

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

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

уреди

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

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

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

  • xN. 0 ≠ S(x)
  • x,yN. S(x) = S(y) ⇒ x = y
  • xN. x + 0 = x
  • x,yN. x + S(y) = S(x + y)
  • xN. x ⋅ 0 = 0
  • x,yN. xS(y) = xy + x

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

 

где је   скраћеница за y1,...,yk. Први ред индуцкијске шеме укључује сваки пример првог реда индукцијског аксиома, који укључује аксиому индукције за сваку формулу φ.

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

уреди

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

  1.  .  , додатак је асоцијативан.
  2.  .  , додатак је комутативан.
  3.  .  , множење је асоцијативно.
  4.  .  , множење је комутативно.
  5.  .  , дистрибутивни закон.
  6.  .  , нула је идентитет елемента за сабирање.
  7.  .  ,  један је идентитет елемента за множење.
  8.  .  ,  '<' операција је транзитивна.
  9.  .  ,  '<' операција је ирефлексивна.
  10.  .  .
  11.  .  .
  12.  .  .
  13.  .
  14.  .  .
  15.  .  .

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

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

Модели

уреди

Модел Пеано аритметике је тродупла (N, 0, S), где N је (нужно бесконачан) скуп, 0 ∈ N и S : NN задовољава аксиоме изнад. Дедекинд је доказао у његовој књизи 1888k, Шта су бројеви и шта би требало да буду (нем: Was sind und was sollen die Zahlen) да било која два модела Пеано аксиома (укључујући други ред аксиоме индукције) су изоморфна. Практично, дата два модела (NA, 0A, SA) и (NB, 0B, SB) Пеано аксиома, постоји јединствени хомоморфизам f : NANB који задовољава

 

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

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

уреди

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

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

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

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

уреди

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

s(a) = a ∪ { a }.

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

 

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

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

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

уреди

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

  • Објекти US1(C) су триплети (X, 0X, SX) где X је објекат C, и 0X : 1CX и SX : XX су C-морфизми.
  • Морфизам φ : (X, 0X, SX) → (Y, 0Y, SY) је C-морфизам φ : XY са φ 0X = 0Y и φ SX = SY φ.

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

 

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

Доследност

уреди

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

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

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

Види још

уреди

Референце

уреди
  1. ^ Grassmann 1861.
  2. ^ Peirce 1881; also see Shields 1997
  3. ^ Van Heijenoort 1967, стр. 94.
  4. ^ а б Van Heijenoort 1967, стр. 3
  5. ^ Van Heijenoort 1967, стр. 83.
  6. ^ Peano 1889, стр. 1.
  7. ^ N ote: The non-contiguous set satisfies axiom 1 as it has a 0 element, 2-5 as it doesn't affect equality relations, 6 & 8 as all pieces have a successor, bar the zero element and axiom 7 as no two dominos topple, or are toppled by, the same piece.
  8. ^ Note: Though the ring of dark pieces would itself satisfy axiom 9, it wouldn't satisfy axiom 8, as its zero element would have a predecessor.
  9. ^ Partee et al. (2012), стр. 215
  10. ^ Harsanyi 1983
  11. ^ Mendelson 1997, стр. 155
  12. ^ Kaye 1991, стр. 16–18
  13. ^ Kaye 1991, sec. 11.3
  14. ^ Suppes 1960; Hatcher 1982
  15. ^ Tarski & Givant 1987, sec. 7.6
  16. ^ Hilbert 1900.
  17. ^ Godel 1931.
  18. ^ Godel 1958.
  19. ^ Gentzen 1936.

Литература

уреди
  • Martin Davis, 1974. Computability. Notes by Barry Jacobs. Courant Institute of Mathematical Sciences, New York University.
  • Richard Dedekind (1888). Was sind und was sollen die Zahlen? (What are and what should the numbers be?) (PDF).  (PDF). Vieweg. Приступљено 31 October 2013.. Two English translations:
    • 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
    • 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed. Oxford University Press: 787–832.
  • Gentzen, G., „Die Widerspruchsfreiheit der reinen Zahlentheorie.”. Mathematische Annalen. 112: 132—213. 1936. . Reprinted in English translation in his 1969 Collected works, M. E. Szabo, ed. Amsterdam: North-Holland.
  • Gödel, Kurt (1931). „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”. Monatshefte für Mathematik und Physik. 38-38: 173—198. S2CID 197663120. doi:10.1007/bf01700692. . See On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations.
  • --------, (1958). „Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes,”. Dialectica. 12: 280—87. . Reprinted in English translation in 1990. Gödel's Collected Works, Vol II. Solomon Feferman et al., eds. . Oxford University Press. 
  • Hermann Grassmann (1861). Lehrbuch der Arithmetik (A tutorial in arithmetic) (PDF).  Архивирано на сајту Wayback Machine (3. новембар 2013) (PDF). Enslin.
  • Hatcher, William S., 1982. The Logical Foundations of Mathematics. Pergamon. Derives the Peano axioms (called S) from several axiomatic set theories and from category theory.
  • Kaye, Richard (1991). Models of Peano arithmetic. Oxford University Press. ISBN 978-0-19-853213-2. 
  • David Hilbert,„Mathematische Probleme”. Archiv der Mathematik und Physik. 3 (1): 44—63. 1901. , 213–37. English translation by Maby Winton,. „Mathematical Problems,”. Bulletin of the American Mathematical Society. 8: 437—79. 1902. .
  • Mendelson, Elliott, 1997. Introduction to Mathematical Logic, 4th ed. Chapman & Hall.
  • Peirce, C. S. (1881). „On the Logic of Number”. American Journal of Mathematics. 4 (1): 85—95. JSTOR 2369151. doi:10.2307/2369151. .
  • Paul Shields. (1997), "Peirce's Axiomatization of Arithmetic", in Houser et al., eds., Studies in the Logic of Charles S. Peirce.
  • Hazewinkel, Michiel, ур. (2001). Peano axioms, Encyclopedia of Mathematics. Springer. ISBN 978-1-55608-010-4. 
  • Suppes, Patrick (1960). Axiomatic Set Theory. Dover. ISBN 978-0-486-61630-8. 
  • Alfred Tarski, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol. 41.
  • Edmund Landau, 1965 Grundlagen Der Analysis. AMS Chelsea Publishing. Derives the basic number systems from the Peano axioms. English/German vocabulary included. ISBN 978-0-8284-0141-8.
  • Partee, Barbara; Ter Meulen; Wall, Robert (2012). Mathematical Methods in Linguistics. Springer. 
  • van Heijenoort, Jean (1976) [1967]. From Frege to Godel: A Source Book in Mathematical Logic, 1879–1931 (3rd изд.). Cambridge, Mass: Harvard University Press. ISBN 978-0-674-32449-7. 
  • Harsanyi, John C. (1983). Mathematics, the empirical facts and logical necessity.  Недостаје или је празан параметар |title= (помоћ)Erkenntniss 19: 167 ff.
    • Richard Dedekind, 1890, "Letter to Keferstein." pp. 98–103. On pp. 100, he restates and defends his axioms of 1888.
    • Giuseppe Peano. (1889). Arithmetices principia, nova methodo exposita.  (The principles of arithmetic, presented by a new method). p. 83–97. An excerpt of the treatise where Peano first presented his axioms, and recursively defined arithmetical operations.

Спољашње везе

уреди