Bijektionssicher.

Question

Lassen $A$ und $B$ Sei endliche Mengen, beweise das $|A\times B|=|A||B|$.

Schon seit $A$ und $B$ sind endliche Mengen, dann kann es wie folgt dargestellt werden: $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Dann habe ich eine Funktion definiert $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ gegeben durch $$\varphi(a_i,b_j)=(i-1)n+j$$ Wer hilft mir zu beweisen oder wie man beweist, dass diese Funktion tatsächlich bijektiv ist.

Answer 1

Ich denke, Sie sollten das beweisen:

Gegebene natürliche Zahlen $m$ und $n$ und lass $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, durch $$f(i,j)=(i-1)n+j$$Damit, $f$ ist eine Bijektion.

Sie können den Teilungssatz verwenden, z. B. müssen Sie möglicherweise mit Zahlen umgehen $\mathbb{N}_{mn}$ das sind teilbar durch $n$ als separater Fall.

Ein anderer Ansatz [1]: Sie können beweisen, dass wenn$A$ und $B$ sind also endliche Mengen $A\times B$ ist endlich gesetzt und $$|A\times B|=|A||B|$$ Verwenden Sie die folgenden Schritte:

1. Wenn $\{b\}$ ist also ein Singleton $|A\times \{b\}|=|A|$.
2. Wenn $B=\{b_{1},b_{2},\ldots,b_{n}\}$, dann $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Schließlich können Sie daraus schließen $$|A\times B|=mn=|A||B|$$

Ein anderer Ansatz [2]: Sie können die Induktion aktivieren$|B|$. Es ist zu sagen, beweisen Sie das$$\forall n \in \mathbb{N}, \forall A,B: |A|,|B|<\infty \wedge |B|=n \implies |A\times B|<\infty \wedge |A\times B|=|A|n$$

Answer 2

Für jeden $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ mit $0 \leq r \lt n$ und $q \in \Bbb N$. Beachten Sie, dass$q, r$sind mit diesen Eigenschaften einzigartig. Wenn$r=0$, Karte $f: k \mapsto (q-1, r)$. Wenn$r \neq 0$, Karte $f: k \mapsto (q, r)$. Diese$f$ ist die Bijektion, die Sie wollen.