Velordningsprinsippet - aksiom eller teorem?

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

I tallteorikurset jeg hadde i høst antok vi velordningprinsippet, og viste derifra at matematisk induksjon "fungerer". Jeg havnet i en diskusjon her i dag, angående nettopp dette. Meddebattanten mente at å $\text{WOP} \implies \text{induksjon}$ er sirkulært da man må bruke ulikhetsegenskaper i beviset. Og disse ulikhetene må man ha induksjon for å vise. Diskusjonen gikk litt videre og etter hvert fikk jeg vite at det er mye bedre å anta induksjon og detter vise at $\text{induksjon} \implies \text{WOP}$. WOP er jo noe vi tross alt trenger for mye i tallteorien, men ved å anta induksjon som et aksiom så blir jo heller WOP et teorem istedenfor et aksiom eller "prinsipp".

Etter litt googling fant jeg ut at Peano aksiomene tydeligvis antar induksjon som et aksiom, så der er jo saken grei. Allikevel lurer jeg på hvorfor forfatteren av tallteoriboken har valgt å anta WOP og å vise induksjon utifra det. Er det feil? Er det rett? Hvor står vi sånn samlet sett som et matematisk samfunn på hvilke aksiomer vi antar i dag?

Jeg er litt av den typen som egentlig tenker så mye på aksiomene. Jeg tenker at noe bare er åpenbart (altså veldig åpenbart - aksiomatisk åpenbart), og at mye av matematikken kan bygges på disse åpenbare antakelsene uten å gå helt til bunns i hvilke byggesteiner man skal bygge matematikken på. Selvfølgelig er det viktig å bygge matematikken på aksiomer, men jeg tror ikke man trenger å være ekstremt rigorøs i hvilke aksiomer man har. Hva er den generelle konsensus blant matematikere rundt akkurat dette spørsmålet?
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Jeg havnet i en induksjon her i dag, angående nettopp dette.
Altså hvis påstanden holder for Markus-1, så må den også holde for Markus.
Bilde
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Aleks855 skrev:
Jeg havnet i en induksjon her i dag, angående nettopp dette.
Altså hvis påstanden holder for Markus-1, så må den også holde for Markus.
Haha, er det mulig? :oops: Tror den diskusjonen gikk litt oppi hodet på meg. Uansett, håper noen har noe klokt å komme med her! Vi får vel nesten vente på Gustav og Dennis enn så lenge :D

Sånn forresten, har du noen tanker om dette Aleks? Alle innspill er gode innspill.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Det blir spekulasjon fra min side, men jeg var alltid av det inntrykket at WOP er det som ligger til grunn for at induksjon skal fungere. Hva er poenget med å vise at en påstand holder for "neste heltall" hvis vi ikke er gitt en definisjon av "neste heltall"?

Nå mangler jeg sannsynligvis veldig mye kunnskap her, men la oss si vi induserer over $S = \{0, 1, 2, 3, \ldots\}$, og vi beviser grunntilfellet $n = 0$, da får vi "neste heltall" som $\min\left(S\setminus \{0\}\right) = 1$, og slik fortsetter det.
Bilde
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

WOP og matematisk induksjon på $\mathbb{N}$ er ekvivalente påstander, og begge kan bevises fra hverandre. Innen ZF trenger vi ikke å anta noen av disse som aksiomer, de kan bevises kun ved å bruke egenskapene til $\mathbb{N}$. Vi trenger derimot blant annet aksiomet som erklærer eksistensen til $\mathbb{N}$ (axiom of infinity).

En langt sterkere påstand er det såkalte Well-Ordering Theorem (WO) som hevder at alle mengder kan utstyres med en well-order. Det er blitt bevist (Gödel, Cohen) at WO ikke lar seg bevise innen ZF, og må derfor betraktes som et ekstra aksiom. En mer velkjent, men ekvivalent formulering av WO kalles Axiom of Choice (AC), som du muligens allerede har lest litt om. En annen ekvivalent formulering er det såkalte Zorn’s Lemma, som blir hyppig brukt blant annet innen kommutativ algebra.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Det er riktig at velordningsprinsippet og induksjon er ekvivalente. I den gamle boka jeg brukte i algebra på NTNU i sin tid, Basic abstract algebra av Bhattacharya, Jain og Nagpaul, viste de dette begge veier, i et av de tidligste kapitlene viste de at velordningsprinsippet impliserer induksjon, og mot slutten av boka viste de at Peanos aksiomer impliserer velordningsprinsippet.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Takk for gode svar Dennis og Gustav! Jeg så litt på Well-Ordering theorem. Som du nevner Dennis så er den ikke beviselig innen ZF, men må betraktes som et ekstra aksiom. Et aksiom er jo noe vi tar for å være åpenbart sant, så vidt jeg har forstått det. Men, Well-Ordering theorem er definitivt ikke noe som er åpenbart for meg. Jeg kan fint være enig i at det er en åpenbar egenskap for $\mathbb{N}$. Men hva med $\mathbb{R}$, hva er det minste elementet i en slik mengde? Eller et enda lettere eksempel: $\mathbb{Z}$ - hva er det minste elementet her? Axiom of Choice er hvertfall langt mer rimelig intuitiv, i mine øyne.

Mulig et forferdelig dumt spørsmål, men hvorfor antar man et aksiom som Well-Ordering når det virker veldig vanskelig å visualisere seg det, nesten "counter-intuitive" at det i det hele tatt bør være sant? Jeg regner med at grunnen til at jeg ikke helt klarer å godta det er fordi jeg ser på et aksiom som noe som bør være åpenbart, men at man her ikke bør se på det fra den synsvinkelen.

Apropos boka du nevner Gustav så skal jeg ha den i faget Ringer og moduler til høsten. Den ser veldig bra ut. Husker du fra din tid på NTNU om det var noen fag som gikk på formell logikk? Jeg finner ingen som omhandler nettopp dette med aksiomer, og formell mengdeteori. Det nærmeste man kommer er diskret matematikk, men det er fortsatt langt unna.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Jeg benytter muligheten til å kanskje få et oppfølgingsspørsmål besvart, selv om det kanskje er litt under nivået.
Eller et enda lettere eksempel: $\mathbb{Z}$ - hva er det minste elementet her?
Er det ikke slik at WOP hevder at $\mathbb Z$ er velordnet fordi enhver ikke-tom delmengde av $\mathbb Z$ har et minste element?

WOP hevder vel ikke at $\mathbb Z$ i seg selv har et? Eller er det AoC som gjør det?
Bilde
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

Markus skrev:Takk for gode svar Dennis og Gustav! Jeg så litt på Well-Ordering theorem. Som du nevner Dennis så er den ikke beviselig innen ZF, men må betraktes som et ekstra aksiom. Et aksiom er jo noe vi tar for å være åpenbart sant, så vidt jeg har forstått det. Men, Well-Ordering theorem er definitivt ikke noe som er åpenbart for meg. Jeg kan fint være enig i at det er en åpenbar egenskap for $\mathbb{N}$. Men hva med $\mathbb{R}$, hva er det minste elementet i en slik mengde? Eller et enda lettere eksempel: $\mathbb{Z}$ - hva er det minste elementet her? Axiom of Choice er hvertfall langt mer rimelig intuitiv, i mine øyne.

Mulig et forferdelig dumt spørsmål, men hvorfor antar man et aksiom som Well-Ordering når det virker veldig vanskelig å visualisere seg det, nesten "counter-intuitive" at det i det hele tatt bør være sant? Jeg regner med at grunnen til at jeg ikke helt klarer å godta det er fordi jeg ser på et aksiom som noe som bør være åpenbart, men at man her ikke bør se på det fra den synsvinkelen.

Apropos boka du nevner Gustav så skal jeg ha den i faget Ringer og moduler til høsten. Den ser veldig bra ut. Husker du fra din tid på NTNU om det var noen fag som gikk på formell logikk? Jeg finner ingen som omhandler nettopp dette med aksiomer, og formell mengdeteori. Det nærmeste man kommer er diskret matematikk, men det er fortsatt langt unna.
Det er nok lurere å tenke på aksiomer som spilleregler enn åpenbare sannheter. Hvilket matematisk spill man ender opp med avhenger av hvilke aksiomer man aksepterer som utgangspunkt. Å definere en well-orden på $\mathbb{Z}$ er ikke vanskelig ettersom $\mathbb{Z}$ er tellbar. Vi kan eksempelvis erklære at $0 < 1 < -1 < 2 < -2 < 3 < -3 < \dots$, hvilket gir en well-orden. Cohen har bevist at ZF er konsekvent med at det ikke finnes noen well-orden på $\mathbb{R}$, så det er ikke mulig å eksplisitt produsere noen slik well-orden her. Vi må velge om vi aksepterer dens eksistens som et aksiom eller ikke.

Det bør nevnes at WO/AC/ZL som regel ikke bare "aksepteres" som en universell sannhet. Det er heller et spørsmål om hvilke matematiske konsekvenser som følger av hvorvidt man aksepterer aksiomet. Når det er nevnt så er ikke AC ansett som særlig kontroversielt lenger, blant annet ettersom
(1) som nevnt er AC hverken beviselig eller motbeviselig innen ZF. Det vil si, dersom ZF er en konsekvent teori, så er også ZFC = ZF + AC konsekvent, og visa versa.
(2) AC er nødvendig for å bevise en rekke nyttige påstander innen matematikken, som for eksempel at alle vektorrom har en base (bevises via ZL) eller at kardinaliteten mellom to gitte mengder kan sammenliknes (cardinal comparability, CC). Faktisk er CC ekvivalent med AC.

Om du er mer interessert i logikk og aksiomatisk mengdelære har jeg to ypperlige bøker å anbefale deg, skrevet av min forhenværende tutor i disse fagene:
D. Goldrei, Propositional and Predicate Calculus: A model of argument (Springer, 2005).
D. Goldrei, Classic Set Theory (Chapman and Hall, 1996).
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

DennisChristensen skrev:Det er nok lurere å tenke på aksiomer som spilleregler enn åpenbare sannheter. Hvilket matematisk spill man ender opp med avhenger av hvilke aksiomer man aksepterer som utgangspunkt. Å definere en well-orden på $\mathbb{Z}$ er ikke vanskelig ettersom $\mathbb{Z}$ er tellbar. Vi kan eksempelvis erklære at $0 < 1 < -1 < 2 < -2 < 3 < -3 < \dots$, hvilket gir en well-orden. Cohen har bevist at ZF er konsekvent med at det ikke finnes noen well-orden på $\mathbb{R}$, så det er ikke mulig å eksplisitt produsere noen slik well-orden her. Vi må velge om vi aksepterer dens eksistens som et aksiom eller ikke.

Det bør nevnes at WO/AC/ZL som regel ikke bare "aksepteres" som en universell sannhet. Det er heller et spørsmål om hvilke matematiske konsekvenser som følger av hvorvidt man aksepterer aksiomet. Når det er nevnt så er ikke AC ansett som særlig kontroversielt lenger, blant annet ettersom
(1) som nevnt er AC hverken beviselig eller motbeviselig innen ZF. Det vil si, dersom ZF er en konsekvent teori, så er også ZFC = ZF + AC konsekvent, og visa versa.
(2) AC er nødvendig for å bevise en rekke nyttige påstander innen matematikken, som for eksempel at alle vektorrom har en base (bevises via ZL) eller at kardinaliteten mellom to gitte mengder kan sammenliknes (cardinal comparability, CC). Faktisk er CC ekvivalent med AC.

Om du er mer interessert i logikk og aksiomatisk mengdelære har jeg to ypperlige bøker å anbefale deg, skrevet av min forhenværende tutor i disse fagene:
D. Goldrei, Propositional and Predicate Calculus: A model of argument (Springer, 2005).
D. Goldrei, Classic Set Theory (Chapman and Hall, 1996).
Det angående spilleregler var noe sånt jeg mistenkte at jeg heller burde tenke på aksiomene som ja. Takk for bokanbefalingene, jeg skal definitivt se på de! Jeg ser også at jeg har misforstått hva well-orden betyr. Jeg tenkte det betydde at mengden hadde et faktisk minste element, og for $\mathbb{Z}$ burde det jo isåfall vært $-\infty$, som ikke engang er et tall. Med andre ord er vell-orden mer en måte å liste opp alle tallene i en mengde på, uten å "gå glipp av" noen? Isåfall er det jo veldig naturlig at (uendelig) tellbare mengder har en well-order. Men hva med utellbare mengder, hvordan velordner man de? Eller deler de samme skjebne som $\mathbb{R}$?
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Man må anta V=L (axiom of constructibility) for å kunne finne en eksplisitt ordning på $\mathbb{R}$ (og alle andre mengder), men det hele er relativt innfløkt.

https://en.wikipedia.org/wiki/Axiom_of_constructibility

Edit: samme spørsmål på MO: https://mathoverflow.net/questions/6593 ... -the-reals
Apropos boka du nevner Gustav så skal jeg ha den i faget Ringer og moduler til høsten. Den ser veldig bra ut. Husker du fra din tid på NTNU om det var noen fag som gikk på formell logikk? Jeg finner ingen som omhandler nettopp dette med aksiomer, og formell mengdeteori. Det nærmeste man kommer er diskret matematikk, men det er fortsatt langt unna.
Jeg likte stilen i den boka også. Konsis uten unødvendig utenomsnakk.

Kan ikke huske å ha sett noen emner på NTNU som tar for seg logikk, men UiO har jo et par ypperlige emner, som f.eks. MAT-INF 3600 Matematisk logikk
Svar