Prueba de biyección.

Question

Dejar $A$ y $B$ ser conjuntos finitos, demostrar que $|A\times B|=|A||B|$.

Ya que $A$ y $B$ son conjuntos finitos, entonces se pueden representar de la siguiente manera, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Entonces definí una función $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ dada por $$\varphi(a_i,b_j)=(i-1)n+j$$ ¿Quién me ayuda a probar o cómo probar que esta función es realmente biyectiva?

Answer 1

Creo que deberías demostrar que:

Dados números naturales $m$ y $n$ y deja $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, por $$f(i,j)=(i-1)n+j$$Entonces, $f$ es una biyección.

Puede usar el teorema de la división, por ejemplo, es posible que tenga que manejar números $\mathbb{N}_{mn}$ que son divisibles por $n$ como caso separado.

Otro enfoque [1]: puede demostrar que si$A$ y $B$ son conjuntos finitos, entonces $A\times B$ es un conjunto finito y $$|A\times B|=|A||B|$$ siguiendo los siguientes pasos:

1. Si $\{b\}$ es un singleton, entonces $|A\times \{b\}|=|A|$.
2. Si $B=\{b_{1},b_{2},\ldots,b_{n}\}$, luego $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Finalmente, puede concluir que $$|A\times B|=mn=|A||B|$$

Otro enfoque [2]: puede utilizar la inducción en$|B|$. Es decir, prueba eso$$\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

Para cualquier $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ con $0 \leq r \lt n$ y $q \in \Bbb N$. Tenga en cuenta que$q, r$son únicos con esas propiedades. Si$r=0$, mapa $f: k \mapsto (q-1, r)$. Si$r \neq 0$, mapa $f: k \mapsto (q, r)$. Esta$f$ es la biyección que quieres.