Preuve de bijection.

Question

Laisser $A$ et $B$ être des ensembles finis, prouvez que $|A\times B|=|A||B|$.

Depuis $A$ et $B$ sont des ensembles finis, alors il peut être représenté comme suit, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Puis j'ai défini une fonction $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ donné par $$\varphi(a_i,b_j)=(i-1)n+j$$ Qui m'aide à prouver ou comment prouver que cette fonction est bien bijective.

Answer 1

Je pense que vous devriez prouver que:

Étant donné les nombres naturels $m$ et $n$ et laissez $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, par $$f(i,j)=(i-1)n+j$$Alors, $f$ est une bijection.

Vous pouvez utiliser le théorème de division, par exemple, vous devrez peut-être gérer des nombres $\mathbb{N}_{mn}$ qui sont divisibles par $n$ comme cas séparé.

Une autre approche [1]: vous pouvez prouver que si$A$ et $B$ sont des ensembles finis, alors $A\times B$ est un ensemble fini et $$|A\times B|=|A||B|$$ en suivant les étapes suivantes:

1. Si $\{b\}$ est un singleton, alors $|A\times \{b\}|=|A|$.
2. Si $B=\{b_{1},b_{2},\ldots,b_{n}\}$, puis $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Enfin, vous pouvez conclure que $$|A\times B|=mn=|A||B|$$

Une autre approche [2]: vous pouvez utiliser l'induction sur$|B|$. C'est pour dire, prouver 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

Pour toute $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ avec $0 \leq r \lt n$ et $q \in \Bbb N$. Notez que$q, r$sont uniques avec ces propriétés. Si$r=0$, carte $f: k \mapsto (q-1, r)$. Si$r \neq 0$, carte $f: k \mapsto (q, r)$. Ce$f$ est la bijection que vous voulez.