Axiomschema för ersättning

I mängdteori är axiomschemat för ersättning ett schema av axiom i Zermelo–Fraenkels mängdteori ( ZF) som hävdar att bilden av vilken mängd som helst under en definierbar mappning också är en mängd. Det är nödvändigt för konstruktionen av vissa oändliga uppsättningar i ZF.

Axiomschemat motiveras av tanken att huruvida en klass är en mängd beror bara på klassens kardinalitet , inte på rangen av dess element. Således, om en klass är "tillräckligt liten" för att vara en mängd, och det finns en övergång från den klassen till en andra klass, säger axiomet att den andra klassen också är en mängd. Men eftersom ZFC bara talar om uppsättningar, inte riktiga klasser, anges schemat endast för definierbara surjektioner, som identifieras med sina definierande formler .

Påstående

Axiomschema för ersättning: bilden $F[A]$ av domänuppsättningen $A$ under den definierbara klassfunktionen $F$ är själv en uppsättning, $B$ .

Antag att $P$ är en definierbar binär relation (som kan vara en riktig klass ) så att det för varje mängd $P(x,y)$$\displaystyle x}$ finns en unik mängd $y$ så att gäller. Det finns en motsvarande definierbar funktion $F_{P}$ , där $F_{P}(x)=y$ om och endast om ${\ displaystil P(x,y)}$ . Betrakta (möjligen korrekt) klass $B$ definierad så att för varje uppsättning $y$ , $y\in B$ om och endast om det finns ett $x\in A$ med $F_{P}(x)=y$ . $B$ kallas bilden av $A$ under $F_{P}$ , och betecknas $F_{P}[A]$ eller (med hjälp av set-builder notation ) $\{F_{P}(x):x\in A\}$ .

Axiomschemat för ersättning anger att om $F$$] {\displaystyle F[A]}$ klassfunktion, som ovan, och ${\displaystyle A} är vilken uppsättning som helst, då$ är bilden också ett set. Detta kan ses som en princip för litenhet: axiomet säger att om $A$ är tillräckligt liten för att vara en mängd, så är $F[A]$ också tillräckligt liten för att vara en mängd . Det antyds av det starkare axiomet för storleksbegränsning .

Eftersom det är omöjligt att kvantifiera överdefinierbara funktioner i första ordningens logik, ingår en instans av schemat för varje formel $w_{1},\dotsc ,w_{n},A,x,y$$\displaystyle \phi }$ i mängdteorin med fria variabler bland ; men $B$ är inte ledig i $\phi$ . I det formella språket för mängdteorin är axiomschemat:

${\begin{aligned}\forall w_{1},\ldots ,w_{n}\,\forall A\,([ \forall x\i A&\,\exists !y\,\phi (x,y,w_{1},\ldots ,w_{n},A)]\ \Longrightarrow \ \exists B\,\forall y\ ,[y\in B\Leftrightarrow \exists x\in A\,\phi (x,y,w_{1},\ldots ,w_{n},A)])\end{aligned}}$

För betydelsen av $\exists !$ , se unikhetskvantifiering .

För tydlighetens skull, i fallet med inga variabler $w_{i}$ , förenklas detta till:

${\begin style$

Så närhelst $\phi$ anger en unik $x$ -to- $y$ -överensstämmelse, besläktad med en funktion $F$ på $A$ , sedan alla $y$ som nås på detta sätt kan samlas i en uppsättning $B$ , liknande $F[A]$ .

Ansökningar

Axiomschemat för ersättning är inte nödvändigt för bevisen för de flesta satser i vanlig matematik. Zermelos mängdteori (Z) kan faktiskt redan tolka andra ordningens aritmetik och mycket typteori i finita typer, vilket i sin tur är tillräckligt för att formalisera huvuddelen av matematiken. Även om axiomschemat för ersättning är ett standardaxiom i mängdteorin idag, utelämnas det ofta från system av typteori och grundsystem i topos -teorin.

I vilket fall som helst ökar axiomschemat drastiskt styrkan hos ZF, både när det gäller de satser det kan bevisa - till exempel de mängder som visat sig existera - och även i termer av dess bevisteoretiska konsistensstyrka, jämfört med Z. Några viktiga exempel följer:

• Genom att använda den moderna definitionen på grund av von Neumann , för att bevisa förekomsten av någon gränsordinal som är större än ω krävs ersättningsaxiom. Ordningstalet ω·2 = ω + ω är det första sådana ordningstalet . Oändlighetens axiom hävdar att det finns en oändlig mängd ω = {0, 1, 2, ...}. Man kan hoppas att definiera ω·2 som föreningen av sekvensen {ω, ω + 1, ω + 2,...}. Men godtyckliga sådana klasser av ordningstal behöver inte vara mängder - till exempel är klassen för alla ordningstal inte en mängd. Ersättning tillåter nu att man ersätter varje ändligt tal n i ω med motsvarande ω + n , och garanterar därmed att denna klass är en mängd. Som ett förtydligande, notera att man enkelt kan konstruera en välordnad mängd som är isomorf till ω·2 utan att tillgripa ersättning – ta helt enkelt den disjunkta föreningen av två kopior av ω, med den andra kopian större än den första – men att detta är inte en ordinal eftersom den inte är helt ordnad genom inkludering.
• Större ordtal är beroende av utbyte mindre direkt. Till exempel kan ω ₁ , den första oräkneliga ordinalen , konstrueras enligt följande – uppsättningen av räknebara brunnsorder existerar som en delmängd av $P({\mathbb {N} }\times {\ mathbb {N} })$ genom separation och potensmängd (en relation på A är en delmängd av $A\times A$ , och alltså ett element i potensmängden $P (A\ gånger A)$ En uppsättning relationer är alltså en delmängd av ${\displaystyle P(A\times A)} ))$ . Byt ut varje välordnad set med dess ordningsföljd. Detta är uppsättningen av räknebara ordinaler ω ₁ , som i sig kan visas vara oräkneliga. Konstruktionen använder utbyte två gånger; en gång för att säkerställa en ordningstilldelning för varje välordnad uppsättning och återigen för att ersätta välordnade uppsättningar med sina ordtal. Detta är ett specialfall av resultatet av Hartogs nummer , och det allmänna fallet kan bevisas på liknande sätt.
• Mot bakgrund av ovanstående kräver förekomsten av en tilldelning av en ordinal till varje välordnad uppsättning även utbyte. På liknande sätt von Neumanns kardinaluppgift, som tilldelar ett kardinalnummer till varje uppsättning, utbyte, såväl som valfrihet .
• För uppsättningar av tupler rekursivt definierade som $A^{n}=A^{n-1}\times A$ och för stor $A$ , uppsättningen $\{A^{n}\mid n\in {\mathbb {N} }\}$ har för hög rang för att dess existens ska kunna bevisas utifrån mängdteorin med bara axiomet av kraftuppsättning, valfritt och utan ersättning.
• På samma sätt visade Harvey Friedman att utbyte krävs för att visa att Borel-set är bestämda . Det bevisade resultatet är Donald A. Martins Borels bestämningssats .
• ZF med ersättning bevisar konsistensen av Z, eftersom mängden V _ω·2 är en modell av Z vars existens kan bevisas i ZF. Kardinaltalet $\aleph _{\omega }$ är det första som kan visas existera i ZF men inte i Z. För förtydligande, notera att Gödels andra ofullständighetsteorem visar att var och en av dessa teorier innehåller en mening, "uttrycka" teorins egen konsistens, vilket är obevisbart i den teorin, om den teorin är konsekvent - detta resultat uttrycks ofta löst som påståendet att ingen av dessa teorier kan bevisa sin egen konsistens, om den är konsekvent.

Relation till andra axiomscheman

Samling

Axiomschema för samling: bilden $f[A]$ av domänuppsättningen $A$ under den definierbara klassfunktionen $f$ faller inuti en uppsättning $B$ .

Axiomschemat för insamling är nära relaterat till och förväxlas ofta med axiomschemat för ersättning. Över resten av ZF-axiomen är det ekvivalent med axiomschemat för ersättning. Samlingens axiom är starkare än ersättning i avsaknad av kraftuppsättningsaxiomet eller dess konstruktiva motsvarighet till ZF men svagare inom ramen för IZF, som saknar lagen om utesluten mitt .

Medan ersättning kan läsas för att säga att bilden av en funktion är en mängd, talar samling om bilder av relationer och säger då bara att någon superklass av relationens bild är en mängd. Med andra ord har den resulterande mängden $B$ inget minimalitetskrav, dvs denna variant saknar också unikhetskravet på $\phi$ . Det vill säga, relationen som definieras av $\phi$ behöver inte vara en funktion – vissa $x\in A$ kan motsvara många $y$ i ${\ displaystil B}$ . I det här fallet måste bilduppsättningen $B$ vars existens hävdas innehålla minst en sådan $y$ för varje $x$ i originaluppsättningen, utan garanti att den endast kommer att innehålla ett.

Antag att de fria variablerna för $\phi$ är bland $w_{1},\dotsc ,w_{n},x,y$ ; men varken $A$ eller $B$ är fria i $\phi$ . Då är axiomschemat:

$\forall w_{1},\ldots ,w_{n}\,[(\forall x\,\exists \,y\phi (x,y,w_{1}, \ldots ,w_{n}))\Högerpil \forall A\,\exists B\,\forall x\in A\,\exists y\i B\,\phi (x,y,w_{1},\ ldots ,w_{n})]$

Axiomschemat anges ibland utan föregående begränsningar (förutom att $B$ inte förekommer fritt i $\phi$ ) på predikatet, $\phi$ :

$\forall w_{1},\ldots ,w_{n}\,\forall A\,\exists B\,\forall x\in A\,[\exists y\phi (x,y ,w_{1},\ldots ,w_{n})\Högerpil \exists y\i B\,\phi (x,y,w_{1},\ldots ,w_{n})]$

I det här fallet kan det finnas element $x$ i $A$ som inte är associerade med några andra uppsättningar av $\phi$ . Axiomschemat kräver dock att om ett element $x$ av $A$ är associerat med minst en uppsättning $y$ , då bilduppsättningen $B$ kommer att innehålla minst en sådan $y$ . Det resulterande axiomschemat kallas också axiomschemat för begränsning .

Separation

Axiomschemat för separation , det andra axiomschemat i ZFC, antyds av axiomschemat för ersättning och axiomet för tom uppsättning . Kom ihåg att axiomschemat för separation inkluderar

$\forall A\,\exists B\,\forall C\,(C\in B\Leftrightarrow [C\] i A\land \theta (C)])$

för varje formel $\theta$ på språket för mängdteorin där $B$ inte är fri.

Beviset är som följer. Börja med en formel $\theta (C)$ som inte nämner $B$ , och en mängd $A$ . Om inget element $E$ i $A$ uppfyller ${\displaystyle \theta (E)},$ så är den mängd $B$ som önskas av den relevanta instansen av separationsaxiomschemat är den tomma uppsättningen. Välj annars en fast $E$ i $A$ så att $\theta (E)$ gäller. Definiera en klassfunktion $F$ så att, för alla element $D$$) {\displaystyle \theta ( D)}$ F $\displaystyle F(D)=D}$ om håller och $F(D)=E$ om $\theta (D)$ är falsk. Sedan bilden av $A$ under $F$ , dvs mängden ${\displaystyle B=F''A:=\{F(x):x\in A\}=A\cap \{x:\theta (x)\}} , existerar (genom axiomet för ersättning)$ och är just mängden $B$ som krävs för separationsaxiomet.

Detta resultat visar att det är möjligt att axiomatisera ZFC med ett enda oändligt axiomschema. Eftersom minst ett sådant oändligt schema krävs (ZFC är inte ändligt axiomatiserbart), visar detta att axiomschemat för ersättning kan stå som det enda oändliga axiomschemat i ZFC om så önskas. Eftersom axiomschemat för separation inte är oberoende, utelämnas det ibland från samtida uttalanden av Zermelo-Fraenkels axiom.

Separation är dock fortfarande viktig för användning i fragment av ZFC, på grund av historiska överväganden, och för jämförelse med alternativa axiomatiseringar av mängdteorin. En formulering av mängdteori som inte inkluderar axiomet för ersättning kommer sannolikt att inkludera någon form av separationsaxiomet, för att säkerställa att dess modeller innehåller en tillräckligt rik samling av mängder. I studien av modeller för mängdteori är det ibland användbart att överväga modeller av ZFC utan ersättning, såsom modellerna $V_{\delta }$ i von Neumanns hierarki.

Beviset ovan använder lagen om utesluten mitt i antagandet att om $A$ är icke-tom så måste den innehålla ett element (i intuitionistisk logik är en mängd "tom" om den inte innehåller ett element, och "icke-tom" är den formella negationen av detta, som är svagare än "innehåller ett element"). Separationens axiom ingår i intuitionistisk mängdlära .

Historia

Axiomschemat för ersättning var inte en del av Ernst Zermelos 1908 axiomatisering av mängdteorin ( Z ). En viss informell approximation till det fanns i Cantors opublicerade verk, och det dök upp igen informellt i Mirimanoff (1917).

Abraham Fraenkel, mellan 1939 och 1949

Thoralf Skolem, på 1930-talet

Dess publicering av Abraham Fraenkel 1922 är det som gör den moderna mängdläran Zermelo- Fraenkels mängdlära ( ZFC ). Axiomet upptäcktes självständigt och tillkännagavs av Thoralf Skolem senare samma år (och publicerades 1923). Zermelo själv införlivade Fraenkels axiom i sitt reviderade system som han publicerade 1930, vilket också inkluderade som ett nytt axiom von Neumanns grundaxiom . Även om det är Skolems första ordningsversion av axiomlistan som vi använder idag, får han vanligtvis ingen kredit eftersom varje enskilt axiom utvecklades tidigare av antingen Zermelo eller Fraenkel. Frasen "Zermelo-Fraenkel set theory" användes först i tryck av von Neumann 1928.

Zermelo och Fraenkel hade korresponderat tungt 1921; axiomet för utbyte var ett viktigt ämne för detta utbyte. Fraenkel inledde korrespondens med Zermelo någon gång i mars 1921. Hans brev före det daterade den 6 maj 1921 är dock förlorade. Zermelo erkände först att han hade en lucka i sitt system i ett svar till Fraenkel daterat den 9 maj 1921. Den 10 juli 1921 färdigställde Fraenkel och skickade in en artikel (publicerad 1922) för publicering som beskrev hans axiom som att tillåta godtyckliga ersättningar: "Om M är en mängd och varje element i M ersätts med [en mängd eller ett urelement] sedan förvandlas M till en mängd igen" (komplettering och översättning av parentes av Ebbinghaus). Fraenkels publikation från 1922 tackade Zermelo för användbara argument. Före denna publikation meddelade Fraenkel offentligt sitt nya axiom vid ett möte i German Mathematical Society som hölls i Jena den 22 september 1921. Zermelo var närvarande vid detta möte; i diskussionen efter Fraenkels tal accepterade han axiomet om ersättning i allmänna termer, men uttryckte reservationer beträffande dess omfattning.

Thoralf Skolem offentliggjorde sin upptäckt av luckan i Zermelos system (samma lucka som Fraenkel hade hittat) i ett föredrag som han höll den 6 juli 1922 vid den 5:e kongressen för skandinaviska matematiker, som hölls i Helsingfors ; handlingarna från denna kongress publicerades 1923. Skolem presenterade en resolution i termer av första ordningens definierbara ersättningar: "Låt U vara en bestämd proposition som gäller för vissa par ( a , b ) i domänen B ; anta vidare att för varje a existerar högst ett b så att U är sant. Då, när Mb _a sträcker sig över elementen i en mängd _Ma , sträcker sig b över alla element i en mängd ." Samma år skrev Fraenkel en recension av Skolems tidning, där Fraenkel helt enkelt konstaterade att Skolems överväganden motsvarar hans egna.

Zermelo själv accepterade aldrig Skolems formulering av axiomschemat för ersättning. Vid ett tillfälle kallade han Skolems tillvägagångssätt för "uppsättningsteori om de fattiga". Zermelo föreställde sig ett system som skulle tillåta stora kardinaler . Han invände också starkt mot de filosofiska implikationerna av räknebara modeller för mängdteori, som följde av Skolems första ordningens axiomatisering. Enligt biografin om Zermelo av Heinz-Dieter Ebbinghaus , markerade Zermelos ogillande av Skolems tillvägagångssätt slutet på Zermelos inflytande på utvecklingen av mängdteori och logik.

•   Ebbinghaus, Heinz-Dieter (2007), Ernst Zermelo: An Approach to His Life and Work , Springer Science & Business Media, ISBN 978-3-540-49553-6 .
•   Halmos, Paul R. (1974) [1960], Naive Set Theory , Springer-Verlag, ISBN 0-387-90092-6 .
•   Jech, Thomas (2003), Set Theory: The Third Millennium Edition, Revised and Expanded , Springer, ISBN 3-540-44085-2 .
•   Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs , Elsevier, ISBN 0-444-86839-9 .