TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/7. VO 27.10.2005

ISBN (Fortsetzung)

Wir zeigen: Jeder Fehler an genau einer Stelle wird erkannt

Wir definieren: $x_{1}0:=p\qquad x\in \{0,1,...9,10\}\qquad X{\text{ entspricht }}10$

$\sum _{j=1}^{10}x_{j}(11-j)\equiv 0{\text{ mod 11 }}$

2 ISBN-Codes unterscheiden sich an der Stelle j

$\sum _{j=1}^{10}x_{j}(11-j)\equiv 0{\text{ mod 11 }}\qquad |\qquad \sum _{j=1}^{10}y_{j}(11-j)\equiv 0{\text{ mod 11 }}$

$s:=\sum _{j=1}^{10}x_{j}(11-j)\qquad =\qquad \sum _{j=1}^{10}y_{j}(11-j)$

ISBN: Summe $s+(11-j)+x_{j}\equiv 0{\text{ mod 11 }}$
ISBN: Summe $s+(11-j)+y_{j}\equiv 0{\text{ mod 11 }}$

Es gilt: $1\leq j\leq 10\qquad \Rightarrow \qquad 1\leq 11-j\leq 10$

Wir subtrahieren:

$(11-j)*(x_{j}-y_{j})\equiv 0{\text{ mod 11 }}$

$ggT(11-j,11)=1{\text{ f. }}1\leq j\leq 10\qquad \Rightarrow \qquad x_{j}-y_{j}\equiv 0{\text{ mod 11 }}$

$0\leq x_{j}\leq 10,0\leq y_{j}\leq 10$

$-10\leq x_{j}-y_{j}\leq 10$

$x_{j}-y_{j}\equiv 0{\text{ mod 11 }}$

$\Rightarrow 11|x_{j}-y_{j}$

d.h. $x_{j}-y_{j}\in \{0,11,-11,22,-22\}$

$\Rightarrow x_{j}-y_{j}=0\qquad \Rightarrow \qquad x_{j}=y_{j}$

Nachtrag Komplexe Zahlen: Konjugation

Operation der Konjugation:

$z=a+b*i$

${\overline {z}}=a-b*i$ ... konjugiert komplexe Zahl

Mengen

Mengenlehre

Naive Mengenlehre: "Zusammenfassung wohlunterscheidbarer Objekte in einem Ganzen" $\Rightarrow$ NICHT WIDERSPRUCHSFREI!

Russel's Paradoxon:

$\mathbb {M} :=$ Menge aller Mengen, die sich selbst nicht als Element enthalten

Frage: $\mathbb {M} \in \mathbb {M}$ ?

Definiert ist aber: $\mathbb {M} \in \mathbb {M} \Rightarrow \mathbb {M} \notin \mathbb {M}$ und $\mathbb {M} \notin \mathbb {M} \Rightarrow \mathbb {M} \in \mathbb {M}$ - WIDERSPRUCH!

Axiomatische Mengenlehre: Sie definiert durch Axiome, wie eine Menge gestaltet sein sollte.

ZFC: Zermelo-Fränkel-Axiome (Auswahlaxiom, "C" steht für "Axiom of Choice")

Beispiele:

$\varnothing$ ... leere Menge
endliche Mengen, z.B. ASCII-Code
$\mathbb {N} ,\mathbb {Z} ,\mathbb {Q} ,\mathbb {R} ,\mathbb {C}$
$\mathbb {P}$ ... Menge der Primzahlen
Potenzmenge einer Menge M (Menge aller Teilmengen von M): $P(M):\{A:A\subseteq M\}$

Operationen auf Mengen

$A\cap B,A\cup B$
$A\diagdown B$ ... $\{x:x\in A\wedge x\notin B\}$ ... Differenz
$A\bigtriangleup B$ ... $\{x:(x\in A\wedge x\notin B)\vee (x\notin A\wedge x\in B)\}$ ... "symmetrische Differenz"
Grundmenge G, $G\subseteq A$ ... $A'...\{x\in G:x\notin A\}$ ... Komplement
Binäre Relation: ${\overline {A}}\subseteq B$

Mächtigkeit der Potenzmenge endlicher Mengen

Gegeben sei eine Menge A, und A sei endlich.

Nun stellt sich die Frage: |P(A)| = ?

  n    |P(A)|
  0    1
  1    2
  2    4
  3    8
  ...  ...
  n     $2^{n}$

n = |A|

$n=0\qquad \Rightarrow A=\varnothing \qquad P(\varnothing )=\{\varnothing \}$

$n=1\qquad \Rightarrow A=\{a\}\qquad P(a)=\{\varnothing \,\{a\}\}$

$n=2\qquad \Rightarrow A=\{a,b\}\qquad P(a)=\{\varnothing \,\{a\},\{b\},\{a,b\}\}$

Beweis durch vollständige Induktion nach $n:=|A|$

Behauptung: $|A|=n\qquad \Rightarrow \qquad |P(A)|=2^{n}\qquad \forall n\geq 0$

Induktionsanfang:

$n=0$ ... OK

Induktionsschluss:

$n\rightarrow n+1$

$A=\{a_{1},a_{2},a_{3},...,a_{n+1}\}\qquad |A|=n+1$

$P(A)=\{B:B\subseteq \{a_{1},...a_{n}\}\}\cup \{C:C=B\cup \{a_{1},...a_{n}\}\}\wedge B\subseteq \{a_{1},...,a_{n}\}\}$

$\{B:B\subseteq \{a_{1},...a_{n}\}\}$ Teilmenge $a_{n+1}$ nicht enthalten
$\{C:C=B\cup \{a_{1},...a_{n}\}\}\wedge B\subseteq \{a_{1},...,a_{n}\}\}$ Teilmenge $a_{n+1}$ enthalten