Set

Naive Verständnis

• The empty set: $\varnothing$ or $\{\}$
• $A=\{1,1\}=\{1\}$
• $A=\{x\in \mathbb{R}|x\ge 2\}$
• $A=\{M\text{Menge}||M|\ge 3\}$
  • $A\in A$
  • formal ist das kein problem However:

Question

$A=\{M\text{ Menge}|M\notin M\}$ $A\in A$? A Paradox:

• $A\in A⟹A\notin A$
• $A\notin A⟹A\in A$

Solution: Existenz und Konstruktion von Mengen reglementieren

Definition of Set

Neuanfang mit Universum:

Definition

gleiche enthaltene Elemente ($\forall x((x\in A)\leftrightarrow (x\in B))$) $⟹$ gleiche Mengen ($A=B$) Axiom: Menge, die nur aus eine Element $x$ besteht, existiert $\forall y((x\in A)\leftrightarrow (x=y))$ Schreibweise $\{x\}$ analog für $\{x_1,x_2,\dots ,x_n\}$

Lemma 3.1 Discrete Mathematics ETH, p.44

For any (sets) a and b, $\{a\}=\{b\}⟹a=b$.

Proof: $\neg (a=b)⟹\neg (\{a\}\ne \{b\})$

NOTE

Schreibe $A\subseteq B$, falls $\forall x((x\in A)\to (x\in B))$ wahr

Lemma 3.2 Discrete Mathematics ETH, p.45

$A=B⟺(A\subseteq B)\wedge (B\subseteq A)$

Proof: $(A\subseteq B)\wedge (B\subseteq A)\stackrel{\cdot }{⟹}(\forall x((x\in A)\to (x\in B)))\wedge (\forall x((x\in B)\to (x\in A)))$ Definition $\subseteq$ $\stackrel{\cdot }{⟹}\forall x(x\in A\leftrightarrow x\in B)$ Propositional Logic $\stackrel{\cdot }{⟹}A=B$ Definition $=$

Empty set

Leere Menge $\varnothing$ ist Menge mit $\forall x(x\notin \varnothing )$ wahr

Important

$\varnothing$ ist eindeutig bestimmt $\forall A(\varnothing \subseteq A)$

Warning

This does not mean $\forall A(\varnothing \in A)$

Example

• $A=\{\{\varnothing \}\}$
• $B=\{\{\varnothing \},\{\varnothing ,\varnothing \}\}$
• $C=\{\varnothing ,\{\varnothing \}\}$
• $D=\{\varnothing ,\{\varnothing ,\{\varnothing \}\}\}$

Observations: $A=B$ $C\in D$ $A\subseteq C$

Tuple

$(a,b)\stackrel{def}{=}\{a,\{a,b\}\}$

Discrete Mathematics ETH, p.47

Theorem 3.4

Alphabet

NOTE

set of all finite binary strings $\{0,1{\}}^{\ast }\stackrel{def}{=}\{\epsilon ,0,1,00,01,10,11,000,\dots \}$ $|x|\stackrel{def}{=}$ length of $x$

Power Set

$$\mathcal{P}(A)\stackrel{def}{=}\{S|S\subseteq A\}$$

Example: $\mathcal{P}(\{a,b\})=\{\varnothing ,\{a\},\{b\},\{a,b\}\}$ For a finite set with cardinality $k$, the power set has cardinality $2^k$

Cartesian Product

Definition

The Cartesian product $A\times B$ of two sets $A$ and $B$ is the set of all ordered pairs with the first component from $A$ and the second component from $B$ $A\times B=\{(a,b)|a\in A\wedge b\in B\}$

Example:

• $\varnothing \times A=\varnothing$
• $A\times B=B\times A$

$${\text{bigtimes}}_{i=1}^k{A}_i=\{(a_1,\dots ,a_k)|a_i\in A_i\text{for }1\le i\le k\}$$

Relations types

Injective

Linear Algebra ETH, p.86

For every possible output, at most one input leads to it

$$\forall a,a^{\prime }((f(a)=f(a^{\prime }))\to (a=a^{\prime }))$$

Surjective

Linear Algebra ETH, p.86

For every possible output, at least one input leads to it

$$\forall b\in B\exists a\in A(f(a)=b)$$

Bijective (undoable)

Linear Algebra ETH, p.86

For every possible output, exactly one input leads to it (There always exists an inverse)

= Injective + Surjective

$$f\circ f^{-1}=\text{id}$$