Bijeksiyon kanıtı.

Question

İzin Vermek $A$ ve $B$ sonlu kümeler olun, kanıtlayın $|A\times B|=|A||B|$.

Dan beri $A$ ve $B$ sonlu kümelerdir, bu durumda aşağıdaki gibi temsil edilebilir, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Sonra bir fonksiyon tanımladım $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ veren $$\varphi(a_i,b_j)=(i-1)n+j$$ Bu işlevin aslında önyargılı olduğunu kanıtlamama kim yardım ediyor ya da nasıl kanıtlayabilirim?

Answer 1

Bence bunu kanıtlamalısın:

Doğal sayılar verildiğinde $m$ ve $n$ ve izin ver $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, tarafından $$f(i,j)=(i-1)n+j$$Yani, $f$ bir bijection.

Bölme teoremini kullanabilirsiniz, örneğin sayıları işlemeniz gerekebilir $\mathbb{N}_{mn}$ ile bölünebilen $n$ ayrı durum olarak.

Başka bir yaklaşım [1]: Şunu kanıtlayabilirsiniz :$A$ ve $B$ sonlu kümelerdir, o zaman $A\times B$ sonlu küme ve $$|A\times B|=|A||B|$$ aşağıdaki adımları kullanarak:

1. Eğer $\{b\}$ bir singleton ise $|A\times \{b\}|=|A|$.
2. Eğer $B=\{b_{1},b_{2},\ldots,b_{n}\}$, sonra $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Son olarak, şu sonuca varabilirsiniz: $$|A\times B|=mn=|A||B|$$

Başka bir yaklaşım [2]: Tümevarımı$|B|$. Bunu kanıtlamak demek$$\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

Herhangi $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ ile $0 \leq r \lt n$ ve $q \in \Bbb N$. Bunu not et$q, r$bu özelliklerle benzersizdir. Eğer$r=0$, harita $f: k \mapsto (q-1, r)$. Eğer$r \neq 0$, harita $f: k \mapsto (q, r)$. Bu$f$ istediğiniz bijeksiyondur.