Prova de bijetora.

Question

Deixei $A$ e $B$ sejam conjuntos finitos, prove que $|A\times B|=|A||B|$.

Desde a $A$ e $B$ são conjuntos finitos, então ele pode ser representado da seguinte forma, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Então eu defini uma função $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ dado por $$\varphi(a_i,b_j)=(i-1)n+j$$ Quem me ajuda a provar ou como provar que essa função é realmente bijetiva.

Answer 1

Eu acho que você deve provar que:

Dados números naturais $m$ e $n$ e deixar $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, de $$f(i,j)=(i-1)n+j$$Então, $f$ é uma bijeção.

Você pode usar o teorema da divisão, por exemplo, você pode ter que lidar com números $\mathbb{N}_{mn}$ que são divisíveis por $n$ como caso separado.

Outra abordagem [1]: você pode provar que se$A$ e $B$ são conjuntos finitos, então $A\times B$ é um conjunto finito e $$|A\times B|=|A||B|$$ usando as seguintes etapas:

1. E se $\{b\}$ é um singleton, então $|A\times \{b\}|=|A|$.
2. E se $B=\{b_{1},b_{2},\ldots,b_{n}\}$, então $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Finalmente, você pode concluir que $$|A\times B|=mn=|A||B|$$

Outra abordagem [2]: você pode usar a indução em$|B|$. É para dizer, provar que$$\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 qualquer $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ com $0 \leq r \lt n$ e $q \in \Bbb N$. Observe que$q, r$são únicos com essas propriedades. E se$r=0$, mapa $f: k \mapsto (q-1, r)$. E se$r \neq 0$, mapa $f: k \mapsto (q, r)$. este$f$ é a bijeção que você deseja.