2

Let $A$ and $B$ be finite sets, prove that $|A\times B|=|A||B|$.

Since $A$ and $B$ are finite sets, then it can be represented as follows, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Then i defined a function $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ given by $$\varphi(a_i,b_j)=(i-1)n+j$$ Who helps me to prove or how to prove that this function is indeed bijective.

James A.
  • 824
  • I wouldn't recommend trying to prove this by attempting to create a bijection. However the second answer here provides a proof: https://math.stackexchange.com/questions/1060219/basic-set-theory-proof-about-cardinality-of-cartesian-product-of-two-finite-sets – Alias K Oct 15 '20 at 06:26

2 Answers2

1

I think you should to prove that:

Given natural numbers $m$ and $n$ and let $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, by $$f(i,j)=(i-1)n+j$$So, $f$ is a bijection.

You can use the division theorem, for example you might have to handle numbers $\mathbb{N}_{mn}$ that are divisible by $n$ as separate case.

Another approach [1]: You can prove that if $A$ and $B$ are finite sets, then $A\times B$ is finite set and $$|A\times B|=|A||B|$$ using the following steps:

  1. If $\{b\}$ is a singleton, then $|A\times \{b\}|=|A|$.
  2. If $B=\{b_{1},b_{2},\ldots,b_{n}\}$, then $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$
  3. Finally, you can conclude that $$|A\times B|=mn=|A||B|$$

Another approach [2]: You can use induction on $|B|$. It's to say, prove that $$\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$$

0

For any $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ with $0 \leq r \lt n$ and $q \in \Bbb N$. Note that $q, r$ are unique with those properties. If $r=0$, map $f: k \mapsto (q-1, r)$. If $r \neq 0$, map $f: k \mapsto (q, r)$. This $f$ is the bijection you want.

Robert Shore
  • 23,332