Jämlikhet

I matematik är två uppsättningar eller klasser A och B lika många om det finns en en-till-en-överensstämmelse (eller bijektion) mellan dem, det vill säga om det finns en funktion från A till B så att för varje element y av B , det finns exakt ett element x i A med f ( x ) = y . Lika många uppsättningar sägs ha samma kardinalitet (antal element). Studiet av kardinalitet kallas ofta equinumerosity ( equalness-of-number ). Begreppen equipollens ( equalness-of-force ) och equipotence ( equalness-of-power ) används ibland istället.

Jämställdhet har de karakteristiska egenskaperna hos en ekvivalensrelation . Påståendet att två uppsättningar A och B är lika många betecknas vanligtvis

A\approx B\,

eller

A\sim B

, eller

|A|=|B|.

Definitionen av equinumerosity med hjälp av bijektioner kan tillämpas på både finita och oändliga mängder , och låter en ange om två mängder har samma storlek även om de är oändliga. Georg Cantor , uppfinnaren av mängdläran , visade 1874 att det finns mer än en sorts oändlighet, särskilt att samlingen av alla naturliga tal och samlingen av alla reella tal , även om de båda är oändliga, inte är lika många (se Cantors första oräknelighet). bevis ). I sin kontroversiella uppsats från 1878 definierade Cantor uttryckligen begreppet "kraft" av mängder och använde det för att bevisa att mängden av alla naturliga tal och mängden av alla rationella tal är lika många (ett exempel där en riktig delmängd av en oändlig mängd är lika många i förhållande till den ursprungliga uppsättningen), och att den kartesiska produkten av till och med ett oräkneligt oändligt antal kopior av de reella talen är lika många till en enda kopia av de reella talen.

Cantors teorem från 1891 antyder att ingen mängd är lika stor med sin egen potensmängd (mängden av alla dess delmängder). Detta tillåter definitionen av större och större oändliga mängder med början från en enda oändlig mängd.

Om valets axiom gäller, kan kardinalnumret för en mängd betraktas som det minsta ordningstalet för den kardinaliteten (se initial ordningsföljd ). Annars kan det betraktas (av Scotts trick ) som uppsättningen av uppsättningar av minimal rang som har den kardinaliteten.

Påståendet att två uppsättningar antingen är lika många eller att den ena har en mindre kardinalitet än den andra är ekvivalent med valets axiom .

Kardinalitet

Lika många uppsättningar har en en-till-en-överensstämmelse mellan dem och sägs ha samma kardinalitet . Kardinaliteten för en mängd X är ett mått på "antalet element i mängden". Equinumerosity har de karakteristiska egenskaperna hos en ekvivalensrelation ( reflexivitet , symmetri och transitivitet ):

Reflexivitet: Givet en mängd A , är identitetsfunktionen på A en bijektion från A till sig själv, vilket visar att varje mängd A är lika många med sig själv: A ~ A .
Symmetri: För varje bijektion mellan två mängder A och B finns det en invers funktion som är en bijektion mellan B och A , vilket innebär att om en mängd A är jämnårig med en mängd B så är B också lika med A : A ~ B innebär B ~ A .
Transitivitet: Givet tre uppsättningar A , B och C med två bijektioner f : A → B och g : B → C , är sammansättningen g ∘ f av dessa bijektioner en bijektion från A till C , så om A och B är lika många och B och C är lika många då är A och C lika många: A ~ B och B ~ C betyder tillsammans A ~ C .

Ett försök att definiera en mängds kardinalitet som ekvivalensklassen för alla mängder som är lika många för den är problematiskt i Zermelo–Fraenkel mängdteori, standardformen för axiomatisk mängdlära , eftersom ekvivalensklassen för alla icke-tom mängder skulle vara för stor att vara en uppsättning: det skulle vara en riktig klass . Inom ramen för Zermelo–Fraenkel-mängdteorin relationer per definition begränsade till mängder (en binär relation på en mängd A är en delmängd av den kartesiska produkten A × A ), och det finns ingen mängd av alla mängder i Zermelo–Fraenkel-mängden teori. I Zermelo–Fraenkels mängdteorin försöker man istället för att definiera en mängds kardinalitet som ekvivalensklassen för alla mängder lika många till den att tilldela en representativ mängd till varje ekvivalensklass ( kardinaltilldelning ). I några andra system av axiomatisk mängdlära, till exempel i Von Neumann–Bernays–Gödel mängdlära och Morse–Kelley mängdlära , utvidgas relationer till klasser .

En mängd A sägs ha kardinalitet som är mindre än eller lika med kardinaliteten för en mängd B , om det finns en en-till-en-funktion (en injektion) från A till B . Detta betecknas | A | ≤ | B |. Om A och B inte är lika många, sägs kardinaliteten hos A vara strikt mindre än kardinaliteten hos B . Detta betecknas | A | < | B |. Om valets axiom gäller, så gäller trikotomilagen för kardinaltal , så att två uppsättningar antingen är lika många, eller så har den ena en strikt mindre kardinalitet än den andra. Lagen om trikotomi för kardinaltal innebär också valets axiom .

Schröder –Bernsteins sats säger att alla två uppsättningar A och B för vilka det finns två en-till-en-funktioner f : A → B och g : B → A är lika många: if | A | ≤ | B | och | B | ≤ | A |, sedan | A | = | B |. Detta teorem förlitar sig inte på valets axiom .

Kantors sats

Cantors sats antyder att ingen mängd är likvärdig med sin maktmängd (mängden av alla dess delmängder ). Detta gäller även för oändliga uppsättningar . Specifikt är kraftuppsättningen för en räkningsbart oändlig uppsättning en oräknelig uppsättning .

Att anta att det finns en oändlig mängd N som består av alla P ( P naturliga P ( N ))), … tal och att anta att det finns potensmängd för en given mängd möjliggör definitionen av en sekvens N , P ( N ) , P ( P ( N )), ( av oändliga mängder där varje mängd är effektmängden för den föregående mängden. Enligt Cantors teorem överstiger kardinaliteten för varje mängd i denna sekvens strikt kardinaliteten för den föregående mängden, vilket leder till allt större oändliga mängder.

Cantors arbete kritiserades hårt av några av hans samtida, till exempel av Leopold Kronecker , som starkt anslutit sig till en finitistisk matematikfilosofi och förkastade idén att siffror kan bilda en verklig, fullbordad totalitet (en verklig oändlighet ). Emellertid försvarades Cantors idéer av andra, till exempel av Richard Dedekind , och till slut accepterades de till stor del, starkt stödda av David Hilbert . Se Kontrovers om Cantors teori för mer.

Inom ramen för Zermelo–Fraenkels mängdteorin garanterar kraftmängdens axiom existensen av kraftmängden för varje given mängd. Dessutom oändlighetens axiom att det finns minst en oändlig mängd, nämligen en mängd som innehåller de naturliga talen. Det finns alternativa mängdteorier , t.ex. " generell mängdteori " (GST), Kripke–Platek mängdteori och pocketmängdteori (PST), som medvetet utelämnar kraftmängdens axiom och oändlighetens axiom och inte tillåter definitionen av den oändliga hierarkin av oändligheter föreslagen av Cantor.

Kardinaliteterna som motsvarar mängderna N , P ( N ), P ( P ( N )), P ( P ( P ( N ))), … är beth-talen $\beth _{0}$ , $\beth _{1}$ , $\beth _{2}$ , $\beth _{3}$ , …, med det första beth-numret $\ beth _{0}$ är lika med $\aleph _{0}$ ( aleph naught ), kardinaliteten för varje räkningsbart oändlig mängd, och det andra beth-talet $\beth _{1}$ är lika med ${\displaystyle {\mathfrak {c}}} ,$ kontinuumets kardinalitet .

Dedekind-oändliga uppsättningar

I vissa tillfällen är det möjligt för en mängd S och dess rätta delmängd att vara lika många. Till exempel är mängden av jämna naturliga tal lika stor som mängden av alla naturliga tal. En mängd som är lika många till en riktig delmängd av sig själv kallas Dedekind-oändlig .

Axiomet för det räknarbara valet (AC _ω ), en svag variant av valets axiom (AC), behövs för att visa att en mängd som inte är Dedekind-oändlig faktiskt är finit . Axiomen för Zermelo–Fraenkels mängdteorin utan valets axiom (ZF) är inte tillräckligt starka för att bevisa att varje oändlig mängd är Dedekind-oändlig, utan axiomen för Zermelo–Fraenkels mängdteorin med axiomet för countable choice ( ZF + _ω AC ) är tillräckligt starka. Andra definitioner av ändlighet och oändlighet av mängder än den som ges av Dedekind kräver inte valets axiom för detta, se Finit mängd § Nödvändiga och tillräckliga villkor för ändlighet .

Kompatibilitet med inställningsoperationer

Equinumerosity är kompatibel med de grundläggande setoperationerna på ett sätt som tillåter definitionen av kardinal aritmetik . Specifikt är jämställdhet kompatibel med disjunkta fackföreningar : Givet fyra uppsättningar A , B , C och D med A och C å ena sidan och B och D å andra sidan parvis disjunkta och med A ~ B och C ~ D då A ∪ C ~ B ∪ D . Detta används för att motivera definitionen av kardinaltillägg .

Dessutom är equinumerosity kompatibel med kartesiska produkter :

Om A ~ B och C ~ D så A × C ~ B × D .
A × B ~ B × A
( A × B ) × C ~ A × ( B × C )

Dessa egenskaper används för att motivera kardinal multiplikation .

Givet två uppsättningar X och Y betecknas mängden av alla funktioner från Y till X med X ^Y . Då gäller följande uttalanden:

Om A ~ B och C ~ D så A ^C ~ B ^D .
A ^{B ∪ C} ~ A ^B × A ^C för disjunkta B och C .
( A × B ) ^C ~ A ^C × B ^C
( A ^B ) ^C ~ A ^{B × C}

Dessa egenskaper används för att motivera kardinal exponentiering .

Dessutom är effektmängden för en given mängd A (mängden av alla delmängder av A ) lika stor som mängden 2A, ^mängden av alla funktioner från mängden A till en mängd som innehåller exakt två element.

Kategoridefinition

I kategoriteori är kategorin av mängder , betecknad Mängd , den kategori som består av samlingen av alla mängder som objekt och samlingen av alla funktioner mellan mängder som morfismer , med sammansättningen av funktioner som sammansättningen av morfismerna. I Set är en isomorfism mellan två uppsättningar just en bijektion, och två uppsättningar är lika många just om de är isomorfa som objekt i Set .

Se även