Mängder, funktioner och relationer

En mängd bestäms av sina element, inte av deras ordning eller hur många gånger de räknas upp. En funktion tilldelar varje element i definitionsmängden exakt ett värde. Injektivitet förbjuder sammanfallande värden för olika argument; surjektivitet kräver att hela målmängden nås. En relation kan däremot koppla ett element till flera andra. En ekvivalensrelation är reflexiv, symmetrisk och transitiv och delar mängden i disjunkta klasser.

$$[a]_R=\{x\in A:xRa\}$$

En partialordning är en relation som är reflexiv, antisymmetrisk och transitiv. Antisymmetri betyder att $aRb$ och $bRa$ tillsammans tvingar $a=b$; det förbjuder alltså inte att ett element är relaterat till sig självt. Om varje par dessutom är jämförbart kallas ordningen total. Symmetri och antisymmetri är olika egenskaper, inte varandras negationer.

På heltalen relaterar vi två tal när deras skillnad är delbar med tre. Varje tal är relaterat till sig självt eftersom differensen är noll. Byter vi ordning ändras bara tecknet, och summerar vi två delbara differenser är summan fortfarande delbar. Relationens tre klasser representeras därför av noll, ett och två.

$$aRb\iff3\mid(a-b),\qquad\mathbb Z/R=\{[0],[1],[2]\}$$

På $A=\{1,2,3,6\}$ definierar vi $aRb$ genom $a\mid b$. Varje tal delar sig självt, så relationen är reflexiv. Om två positiva heltal delar varandra är de lika, vilket ger antisymmetri. Om $b=ar$ och $c=bs$ med heltal $r,s$, så är $c=a(rs)$ och relationen transitiv. Därför är detta en partialordning. Den är inte total: varken $2\mid3$ eller $3\mid2$ gäller.

För ändliga mängder räcker antalet element för att jämföra storlek. För oändliga mängder använder vi bijektioner. Att en mängd innehåller en annan bevisar inte att den har strikt större kardinalitet. Funktionen som fördubblar ett naturligt tal ger en bijektion mellan de naturliga talen och de jämna naturliga talen. För att motbevisa injektivitet behövs två olika argument med samma bild, och för att motbevisa surjektivitet räcker ett målelement utan urbild.

$$f:\mathbb N\longrightarrow2\mathbb N,\qquad f(n)=2n$$

På en produkt av två partialordnade mängder kan par jämföras koordinatvis: $(x_1,y_1)\preceq(x_2,y_2)$ när $x_1\le x_2$ och $y_1\le y_2$. Reflexivitet, antisymmetri och transitivitet ärvs då i varje koordinat. Det är en annan ordning än lexikografisk ordning, där första olika koordinaten avgör. För mängdidentiteter är ett motsvarande arbetssätt att följa ett godtyckligt elements medlemskap genom båda leden. Med samma universalmängd ger de Morgans lagar $A\setminus(B\cup C)=A\cap B^c\cap C^c=(A\setminus B)\cap(A\setminus C)$.