Grunnleggende mengdeoperasjoner

En mengde er en samling distinkte objekter uten rekkefølge. Vi skriver \(x\in A\) for medlemskap. Med universalmengde \(U\) defineres operasjonene slik:

\(A\cup B=\{x : x\in A \lor x\in B\}\) (union)
\(A\cap B=\{x : x\in A \land x\in B\}\) (snitt)
\(A\setminus B=\{x : x\in A \land x\notin B\}\) (differanse)
\(\overline{A}=U\setminus A=\{x\in U : x\notin A\}\) (komplement)
\(A\oplus B=(A\setminus B)\cup(B\setminus A)\) (symmetrisk differanse)

Merk konvensjonen i dette kurset: \(\mathbb{N}\) inkluderer 0. Husk derfor å ta med 0 i komplement og mengdebygger-uttrykk der det er aktuelt.

Eksempel 1: La \(A=\{1,2,3,4,5\}\), \(B=\{2,4,6,8\}\), \(U=\{0,1,\dots,10\}\). Finn de fem operasjonene.

\(A\cup B=\{1,2,3,4,5,6,8\}\) (alt i minst én)

\(A\cap B=\{2,4\}\) (i begge)

\(A\setminus B=\{1,3,5\}\) (i A, ikke i B)

\(\overline{A}=\{0,6,7,8,9,10\}\) (NB: 0 er med)

\(A\oplus B=\{1,3,5\}\cup\{6,8\}=\{1,3,5,6,8\}\)

Mengdelovene

De Morgan: \(\overline{A\cup B}=\overline{A}\cap\overline{B}\), \(\overline{A\cap B}=\overline{A}\cup\overline{B}\)
Distributiv: \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\), og dualt med \(\cup,\cap\) byttet
Absorpsjon: \(A\cup(A\cap B)=A\), \(A\cap(A\cup B)=A\)
Komplement: \(A\cap\overline{A}=\emptyset\), \(A\cup\overline{A}=U\), \(\overline{\overline{A}}=A\)
Idempotens: \(A\cup A=A\), \(A\cap A=A\)

Potensmengde og kardinalitet

Potensmengden \(\mathcal{P}(A)\) er mengden av ALLE delmengder av \(A\), inkludert \(\emptyset\) og \(A\) selv.

\(|\mathcal{P}(A)|=2^{|A|}\). For hvert element velges uavhengig «med» eller «uten» (2 valg), så totalt \(2^n\) delmengder. Antall \(k\)-elements delmengder er \(\binom{n}{k}\), og \(\sum_{k=0}^n\binom{n}{k}=2^n\).

Eksempel 2: List opp \(\mathcal{P}(\{a,b,c\})\) og bekreft kardinaliteten.

Størrelse 0: \(\emptyset\) — 1 stk

Størrelse 1: \(\{a\},\{b\},\{c\}\) — 3 stk

Størrelse 2: \(\{a,b\},\{a,c\},\{b,c\}\) — 3 stk

Størrelse 3: \(\{a,b,c\}\) — 1 stk

Totalt: \(1+3+3+1=8=2^3\) ✓

Kartesisk produkt og ordnede par

Et ordnet par \(\langle a,b\rangle\) har rekkefølge: \(\langle a,b\rangle=\langle c,d\rangle\) hvis og bare hvis \(a=c\) og \(b=d\). Det kartesiske produktet er mengden av alle slike par:

\(A\times B=\{\langle a,b\rangle : a\in A \land b\in B\}\), med \(|A\times B|=|A|\cdot|B|\). Generelt er \(A\times B\neq B\times A\). Videre \(A\times\emptyset=\emptyset\).

Eksempel 3: \(A=\{1,2\}\), \(B=\{x,y\}\). Finn \(A\times B\).

Fra \(1\): \(\langle1,x\rangle,\langle1,y\rangle\)

Fra \(2\): \(\langle2,x\rangle,\langle2,y\rangle\)

\(A\times B=\{\langle1,x\rangle,\langle1,y\rangle,\langle2,x\rangle,\langle2,y\rangle\}\), \(|A\times B|=2\cdot2=4\)

Bevis av mengdelikheter (element-argument)

For å vise \(A\subseteq B\): ta vilkårlig \(x\in A\) og utled \(x\in B\). For å vise \(A=B\): vis begge inklusjonene (dobbel inklusjon), eller bruk en kjede av logiske ekvivalenser (\(\Leftrightarrow\)) på medlemskapsbetingelsen.

Eksempel 4: Bevis at \(\overline{A\cup B}=\overline{A}\cap\overline{B}\).

\(x\in\overline{A\cup B}\Leftrightarrow x\notin A\cup B\)

\(\Leftrightarrow \neg(x\in A\lor x\in B)\)

\(\Leftrightarrow x\notin A\land x\notin B\) (de Morgan i logikk)

\(\Leftrightarrow x\in\overline{A}\land x\in\overline{B}\)

\(\Leftrightarrow x\in\overline{A}\cap\overline{B}\). Ekvivalens begge veier gir likhet. ∎

Venn-diagram og mengdebygger-notasjon

Venn-diagram visualiserer operasjoner; tre overlappende mengder deler \(U\) i \(2^3=8\) regioner. Mengdebygger-notasjon \(\{x : P(x)\}\) angir alle \(x\) som oppfyller predikatet \(P\), og bildemengde-form \(\{f(x):x\in S\}\) angir verdiene \(f\) tar over \(S\).

Studieguide: Mengdelære