Dowód Bijection.

Question

Pozwolić $A$ i $B$ być zbiorami skończonymi, udowodnij to $|A\times B|=|A||B|$.

Od $A$ i $B$ są zbiorami skończonymi, to można je przedstawić następująco: $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Następnie zdefiniowałem funkcję $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ podane przez $$\varphi(a_i,b_j)=(i-1)n+j$$ Kto pomaga mi udowodnić lub jak udowodnić, że ta funkcja jest rzeczywiście bijektywna.

Answer 1

Myślę, że powinieneś to udowodnić:

Biorąc pod uwagę liczby naturalne $m$ i $n$ i pozwól $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, przez $$f(i,j)=(i-1)n+j$$Więc, $f$ jest bijection.

Możesz użyć twierdzenia o dzieleniu, na przykład możesz mieć do czynienia z liczbami $\mathbb{N}_{mn}$ które są podzielne przez $n$ jako oddzielny przypadek.

Inne podejście [1]: Możesz to udowodnić, jeśli$A$ i $B$ są więc zbiorami skończonymi $A\times B$ jest zbiorem skończonym i $$|A\times B|=|A||B|$$ wykonując następujące kroki:

1. Gdyby $\{b\}$ jest więc singletonem $|A\times \{b\}|=|A|$.
2. Gdyby $B=\{b_{1},b_{2},\ldots,b_{n}\}$, następnie $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Wreszcie możesz to stwierdzić $$|A\times B|=mn=|A||B|$$

Inne podejście [2]: Możesz użyć indukcji na$|B|$. To znaczy, udowodnij to$$\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

Dla każdego $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ z $0 \leq r \lt n$ i $q \in \Bbb N$. Zauważ, że$q, r$są wyjątkowe pod względem tych właściwości. Gdyby$r=0$, mapa $f: k \mapsto (q-1, r)$. Gdyby$r \neq 0$, mapa $f: k \mapsto (q, r)$. To$f$ jest bijection, którego chcesz.