Logik, mängder och relationer¶
Detta är språket som resten av kursen talar. Inget av det är svårt i sig, men det är det språk varje senare bevis skrivs i — så tid som läggs här betalar sig överallt. Materialet delas i tre: mängder och kardinalitet (hur man räknar och jämför samlingar, även oändliga), relationer och funktioner (hur element i mängder paras ihop) och satslogik (hur påståenden kombineras).
Mängder och kardinalitet¶
En mängd är helt enkelt en samling distinkta ting, dess element. Hela detta avsnitt handlar om två frågor: hur kombinerar vi mängder, och hur jämför vi deras storlekar?
Operationer¶
Tre sätt att bygga en ny mängd av gamla:
- Union \(A \cup B\) — allt i \(A\) eller \(B\) (eller båda). Tänk "häll ihop båda påsarna".
- Snitt \(A \cap B\) — allt i \(A\) och \(B\). Överlappet.
- Komplement \(A^c\) — allt som inte är i \(A\) (inom något överenskommet universum). Resten.
Den enda identiteten värd att lägga på minnet är De Morgans lagar, som säger hur komplement samspelar med de andra två:
Varför de gäller. Läs den vänstra i ord: "inte i (\(A\) eller \(B\))" betyder att du undvek båda \(A\) och \(B\) — du är utanför \(A\) och utanför \(B\). Det är precis \(A^c \cap B^c\). Att ta ett komplement vänder "eller" till "och". Den andra lagen är samma mening med union och snitt utbytta.
Potensmängd¶
Potensmängden \(\mathcal{P}(A)\) är varje möjlig delmängd till \(A\), samlad i en påse — inklusive tomma mängden \(\emptyset\) och hela \(A\) självt.
Storleken på potensmängden
Om \(\lvert A \rvert = n\), så är
Varför \(2^n\)? Att bygga en delmängd innebär att gå ner för de \(n\) elementen ett i taget och för varje bestämma med eller utan. Det är \(n\) oberoende ja/nej-val, och oberoende val multipliceras: \(2 \cdot 2 \cdots 2 = 2^n\).
Konkret. Ta \(A = \{a, b\}\), så \(n = 2\). Delmängderna är \(\emptyset,\ \{a\},\ \{b\},\ \{a, b\}\) — fyra stycken, och \(2^2 = 4\). ✓
\(\in\) mot \(\subseteq\) — en favoritfälla på seminarierna
De två symbolerna är inte utbytbara, och att blanda ihop dem är det enskilt vanligaste mängdteorifelet. \(\in\) betyder "är ett element i"; \(\subseteq\) betyder "är en delmängd till". Ett element är ett enda ting i påsen; en delmängd är en mindre påse.
För \(A = \{a, b, c\}\):
- \(\emptyset \subseteq A\) är sant — tomma mängden är en delmängd till allt (den kräver ingenting av \(A\)).
- \(\emptyset \subseteq \mathcal{P}(A)\) är sant, av samma skäl.
- \(\{a\} \in \mathcal{P}(A)\) är sant — elementen i \(\mathcal{P}(A)\) är delmängderna till \(A\), och \(\{a\}\) är en av dem.
- \((a, 1) \in A \times B\) är sant (ett par är ett element i produkten), men \((a, 1) \subseteq A \times B\) är falskt (ett enskilt par är inte en delsamling).
Mönstret att hålla fast vid: \(\mathcal{P}(A)\) skjuter upp allt en nivå. Delmängder till \(A\) (en "nivå 1"-idé) blir element i \(\mathcal{P}(A)\) (ett "nivå 2"-objekt).
Att jämföra storlekar: kardinalitet¶
För ändliga mängder betyder "samma storlek" bara "lika många element". Det smarta draget i den här kursen är att vi får den idén att fungera för oändliga mängder också, med en definition som aldrig räknar något:
Definition av samma kardinalitet
Två mängder har samma kardinalitet om det finns en bijektion mellan dem — en parning som matchar varje element i den ena mot exakt ett element i den andra, utan att något blir över på någondera sidan.
Läs detta noga, för det är det enda verktyg du har för oändliga mängder. Du kan inte argumentera utifrån "storlek", och du kan inte argumentera att en mängd är större för att den verkar innehålla mer. Det enda legitima draget är att bygga en bijektion (för att bevisa likhet) eller att bevisa att ingen bijektion kan finnas (för att bevisa olikhet).
De två fakta man ska kunna:
- \(\mathbb{Z}\) (heltal) och \(\mathbb{Q}\) (rationella tal) är uppräkneliga: var och en kan bijiceras med \(\mathbb{N} = \{0, 1, 2, \dots\}\). "Uppräknelig" betyder bokstavligen "kan listas i en ordning som till slut når varje element".
- \(\mathbb{R}\) (reella tal) är överuppräknelig: ingen sådan lista finns. Detta är Cantors diagonalargument — anta att du hade en fullständig lista av reella tal, och konstruera sedan ett nytt reellt tal som skiljer sig från det \(n\):te listade talet i dess \(n\):te siffra, så att det inte kan stå på listan. Motsägelse.
Oändliga mängder bryter din intuition — räkna med det
Här är ett påstående som låter uppenbart sant och i själva verket är falskt:
Om \(A\) och \(B\) är oändliga och \(B \subsetneq A\) (strikt mindre), så är \(\lvert B \rvert < \lvert A \rvert\).
Motexempel. Låt \(B = 2\mathbb{Z}\) (de jämna heltalen) sitta inuti \(A = \mathbb{Z}\). Tydligen saknar \(B\) alla udda tal, så visst måste den vara mindre? Nej: avbildningen \(n \mapsto 2n\) parar varje heltal med ett jämnt heltal, perfekt, utan att något blir över. Det är en bijektion, så \(\lvert B \rvert = \lvert A \rvert\).
Lärdomen: en äkta delmängd till en oändlig mängd kan vara precis lika stor. "Att vara en delmängd" och "att vara mindre" glider isär så snart mängder är oändliga. Lita på bijektionen, inte på bilden.
Att bevisa att en mängd är överuppräknelig¶
Detta är ett återkommande problem i del C, så det är värt en pålitlig metod. Det finns två vägar:
- Injicera \(\mathbb{R}\) in i den. Kan du bygga en injektiv (ett-till-ett) avbildning \(\varphi: \mathbb{R} \to S\), så har \(S\) minst lika många element som \(\mathbb{R}\), alltså \(\lvert S \rvert \geq \lvert \mathbb{R} \rvert\) och \(S\) är överuppräknelig.
- Kör diagonalargumentet direkt på \(S\), precis som Cantor gjorde för \(\mathbb{R}\).
Väg 1 är oftast renare när \(S\) synligt "innehåller en kopia av de reella talen".
Tentamen (maj 2024, uppgift 8): decimaler med 1:or och 5:or
Problem. Låt \(S\) vara mängden av reella tal vars decimalutveckling endast använder siffrorna \(1\) och \(5\) (så \(1{,}51151111\ldots \in S\) men \(1{,}34 \notin S\)). Är \(S\) uppräknelig?
Svar: överuppräknelig. Vi använder väg 1 och injicerar \(\mathbb{R}\) in i \(S\).
Idén. Ett reellt tal har en binär utveckling — en sträng av två symboler, \(0\) och \(1\). Ett element i \(S\) är också en sträng av två symboler, \(1\) och \(5\). Två symboler är två symboler. Så vi kan bara märka om: gör varje binär siffra till en "\(1\)-eller-\(5\)"-siffra och hamna inuti \(S\).
Konstruktionen. Låt \(\psi: \{0,1\} \to \{1,5\}\) vara \(\psi(1) = 1\), \(\psi(0) = 5\). Givet ett reellt tal med binär utveckling \(a_1 a_2 \ldots a_n . b_1 b_2 b_3 \ldots\), definiera \(\varphi\) så att det skickar talet till
Varför den är injektiv. Binära utvecklingar är entydiga så snart man förbjuder dem som slutar på idel 1:or (samma fix som stoppar \(0{,}0111\ldots = 0{,}1000\ldots\) i bas 10), så olika reella tal ger olika strängar, alltså olika element i \(S\).
Slutsats. \(\varphi\) injicerar \(\mathbb{R}\) in i \(S\), så \(\lvert S \rvert \geq \lvert \mathbb{R} \rvert\) och \(S\) är inte uppräknelig. \(\square\)
Den enda insikten att ta med sig: siffrorna \(1\) och \(5\) bär ingen aritmetisk mening i detta problem — de är bara två symboler, och två symboler är precis vad en binär utveckling behöver. Att se "detta är egentligen bara binärt i förklädnad" är hela problemet.
Relationer¶
En relation är ett sätt att säga vilka element som är kopplade till vilka. Formellt är en binär relation \(R\) på en mängd \(A\) bara en mängd ordnade par — en delmängd till \(A \times A\) — och vi skriver \(x \mathbin{R} y\) som förkortning för "\((x, y)\) ligger i den mängden", dvs. "\(x\) är relaterat till \(y\)". "Är mindre än", "delar", "är kongruent med mod \(n\)" är alla relationer.
Vi klassificerar relationer efter vilka av dessa fem egenskaper de har:
| Egenskap | Definition | I ord |
|---|---|---|
| Reflexiv | \(x \mathbin{R} x\) för alla \(x\) | allt relaterar till sig självt |
| Symmetrisk | \(x \mathbin{R} y \implies y \mathbin{R} x\) | relationen bryr sig inte om riktning |
| Antisymmetrisk | \(x \mathbin{R} y\) och \(y \mathbin{R} x \implies x = y\) | enda sättet den går åt båda hållen är \(x = y\) |
| Transitiv | \(x \mathbin{R} y\) och \(y \mathbin{R} z \implies x \mathbin{R} z\) | länkar kedjas ihop |
Två särskilda kombinationer får egna namn, eftersom de dyker upp hela tiden:
- Ekvivalensrelation = reflexiv + symmetrisk + transitiv. Fångar "dessa ting är desamma för våra syften".
- Partialordning = reflexiv + antisymmetrisk + transitiv. Fångar "detta kommer före det", där vissa par tillåts vara ojämförbara.
Ekvivalensklasser¶
Ekvivalensrelationer är viktiga på grund av en ren följd: de delar upp en mängd i disjunkta grupper. Varje grupp, kallad en ekvivalensklass, samlar allt som är ömsesidigt relaterat:
Nyckelfaktumet: varje element hamnar i exakt en klass — klasserna överlappar inte och tillsammans täcker de hela \(A\). Att dela en mängd i icke-överlappande, uttömmande bitar kallas en partition, och det är precis vad en ekvivalensrelation producerar.
Varför du ska bry dig. Denna enda idé återkommer i förklädnad genom hela kursen:
- Kongruens mod \(n\) (\(a \sim b\) när \(n \mid a - b\)) är en ekvivalensrelation. Dess klasser är de \(n\) "restklasserna" \(\{0, n, 2n, \dots\}\), \(\{1, n+1, \dots\}\), och så vidare — och de klasserna är elementen i \(\mathbb{Z}_n\). Se talteori.
- I gruppteorin partitionerar sidoklasser en grupp på samma sätt, och den partitionen är hela mekanismen bakom Lagranges sats.
Så om du förstår "ekvivalensrelation → partition" här har du redan förstått skelettet till två senare områden.
Antisymmetrisk är inte 'inte symmetrisk'
En vanlig felläsning. Antisymmetri förbjuder inte \(x \mathbin{R} y\) och \(y \mathbin{R} x\) från att båda gälla — den säger bara att när de gör det måste \(x\) och \(y\) vara lika.
Exempel. Ta delbarhet på de positiva delarna av \(100\). Om \(a \mid b\) och \(b \mid a\), så är faktiskt \(a = b\) — alltså är den antisymmetrisk, och den är en partialordning. Den är bara partiell eftersom vissa par är ojämförbara: varken \(4 \mid 5\) eller \(5 \mid 4\), så \(4\) och \(5\) är helt enkelt inte ordnade relativt varandra.
Funktioner¶
En funktion \(f: A \to B\) tilldelar varje element i definitionsmängden \(A\) exakt ett element i målmängden \(B\). De tre adjektiv du behöver beskriver hur pilarna landar i \(B\):
- Injektiv (ett-till-ett): inga två indata delar utdata — varje element i \(B\) träffas högst en gång. Ekvivalent, \(f(x) = f(y)\) tvingar \(x = y\). ("Inga kollisioner.")
- Surjektiv (på): varje element i \(B\) träffas minst en gång — inget i målmängden missas. ("Full täckning.")
- Bijektiv: båda samtidigt — varje element i \(B\) träffas exakt en gång. ("En perfekt parning.")
En användbar bild: injektiv = inga två pilar pekar på samma mål; surjektiv = inget mål lämnas opekat; bijektiv = pilar och mål matchas perfekt.
Bijektioner är precis de "perfekta parningar" som kardinalitet definieras via, vilket är varför nästan varje uppräknelighetsproblem kokar ner till att bygga en funktion och kontrollera att den är injektiv (eller bijektiv).
Satslogik¶
Satslogik är algebran för påståenden som vart och ett är helt enkelt sant eller falskt. Vi bygger sammansatta påståenden med konnektiv och frågar när de blir sanna.
Sanningstabeller¶
En sanningstabell listar varje möjlig kombination av sanningsvärden för variablerna och räknar ut resultatet. Om ett sammansatt påstående är sant på varje rad är det en tautologi; om falskt på varje rad är det en motsägelse.
Här är konnektiven. Det enda som regelbundet överraskar folk är implikation, så håll koll på dess kolumn:
| \(p\) | \(q\) | \(p \land q\) (och) | \(p \lor q\) (eller) | \(p \implies q\) (om–så) | \(p \iff q\) (omm) |
|---|---|---|---|---|---|
| S | S | S | S | S | S |
| S | F | F | S | F | F |
| F | S | F | S | S | F |
| F | F | F | F | S | S |
Varför implikation ser ut så. Läs \(p \implies q\) som ett löfte: "om \(p\), så \(q\)". Löftet bryts bara när \(p\) inträffar men \(q\) inte gör det — det är den enda F-raden. Om \(p\) aldrig inträffar (de två nedersta raderna) prövades löftet aldrig, så vi räknar det som hållet (tomt sant). Detta ställer till det eftersom vardagligt "om" ofta antyder orsakssamband; logiskt "om" gör inte det — det handlar enbart om det där brutna-löfte-fallet.
Booleska normalformer¶
Varje boolesk funktion — varje sanningstabell du kan skriva ner — kan fångas av en formel, och faktiskt av en formel i en av två standardformer. Det fina: du kan avläsa båda formerna direkt ur sanningstabellen.
- Disjunktiv normalform (DNF) — ett ELLER av OCH:n (en summa av mintermer). Titta på varje rad där funktionen är sann. Skriv en OCH-sats som är sann endast på den raden (använd \(x\) där variabeln är \(1\), \(\lnot x\) där den är \(0\)). ELLER:a ihop alla de satserna. Eftersom det hela är sant precis på de rader du valde matchar det funktionen.
- Konjunktiv normalform (KNF) — ett OCH av ELLER:n (en produkt av maxfaktorer). Samma idé från andra hållet: titta på varje rad där funktionen är falsk, skriv en ELLER-sats som är falsk endast där (den här gången negera variablerna som är \(1\)), och OCH:a ihop dem alla.
Vilken ska man använda? Den som ger färre satser. Få sanna rader → kort DNF. Få falska rader → kort KNF. Hur som helst beskriver de samma funktion — de är två kodningar av en sanningstabell.