Bằng chứng sinh đôi.

Question

Để cho $A$ và $B$ là tập hợp hữu hạn, chứng minh rằng $|A\times B|=|A||B|$.

Từ $A$ và $B$ là các tập hợp hữu hạn, sau đó nó có thể được biểu diễn như sau, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Sau đó, tôi đã xác định một hàm $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ được cho bởi $$\varphi(a_i,b_j)=(i-1)n+j$$ Ai giúp tôi cách chứng minh hoặc làm thế nào để chứng minh rằng chức năng này thực sự là bijective.

Answer 1

Tôi nghĩ bạn nên chứng minh rằng:

Đã cho số tự nhiên $m$ và $n$ và để $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, bởi $$f(i,j)=(i-1)n+j$$Vì thế, $f$ là một từ chối.

Bạn có thể sử dụng định lý chia, chẳng hạn như bạn có thể phải xử lý các số $\mathbb{N}_{mn}$ chia hết cho $n$ như trường hợp riêng biệt.

Một cách tiếp cận khác [1]: Bạn có thể chứng minh rằng nếu$A$ và $B$ là tập hợp hữu hạn, sau đó $A\times B$ là tập hợp hữu hạn và $$|A\times B|=|A||B|$$ bằng các bước sau:

1. Nếu $\{b\}$ là một singleton, sau đó $|A\times \{b\}|=|A|$.
2. Nếu $B=\{b_{1},b_{2},\ldots,b_{n}\}$, sau đó $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
3. Cuối cùng, bạn có thể kết luận rằng $$|A\times B|=mn=|A||B|$$

Một cách tiếp cận khác [2]: Bạn có thể sử dụng cảm ứng trên$|B|$. Nó để nói, chứng minh rằng$$\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

Bất cứ gì $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ với $0 \leq r \lt n$ và $q \in \Bbb N$. Lưu ý rằng$q, r$là duy nhất với những thuộc tính đó. Nếu$r=0$, bản đồ $f: k \mapsto (q-1, r)$. Nếu$r \neq 0$, bản đồ $f: k \mapsto (q, r)$. Điều này$f$ là sự phản đối mà bạn muốn.