Proof of cardinality inequality: $m_1\le m_2$, $k_1\le k_2$ implies $k_1m_1\le k_2m_2$

Question

I have this homework question I am struggling with:

Let k1,k2,m1,m2 be cardinalities. prove that if $${{m}_{1}}\le {{m}_{2}},{{k}_{1}}\le {{k}_{2}}$$ then $${{k}_{1}}{{m}_{1}}\le {{k}_{2}}{{m}_{2}}$$

Can anyone please help me prove this? thanks

Answer 1

First:

• What does that mean that $k_1\le k_2$? It means there exists a one-to-one function $f\colon k_1\to k_2$.
• What does that mean $k_1 m_1$? It is the cardinality of $A\times B$ where $|A|=k_1$ and $|B|=m_1$.

Suppose $k_1\le k_2$ and $m_1\le m_2$, we abuse the notation and assume that $k_i,m_i$ are also the sets given in the cardinalities at hand.

Now we need to find a function from $k_1\times m_1$ which is one-to-one, into $k_2\times m_2$. Since $k_1\le k_2$ there exists a one-to-one $f\colon k_1\to k_2$, and likewise $g\colon m_1\to m_2$ which is one-to-one.

Let $h\colon k_1\times m_1\to k_2\times m_2$ be defined as: $$h(\langle k,m\rangle) = \langle f(k),g(m)\rangle$$

$h$ is well-defined, since for every $\langle k,m\rangle\in k_1\times m_1$ we have that $f(k)\in k_2$ and $g(m)\in m_2$, therefore $h(\langle k,m\rangle)\in k_2\times m_2$.

We need to show that $h$ is injective. Suppose $h(\langle a,b\rangle) = h(\langle c,d\rangle)$, then $\langle f(a),g(b)\rangle=\langle f(c),g(d)\rangle$. Therefore $f(a)=f(c)$ and $g(b)=g(d)$.

Since $f,g$ are both injective, we have that $a=c, b=d$ that is $\langle a,b\rangle=\langle c,d\rangle$.

It is a very standard exercise to prove the basics properties of the cardinals order, for example:

$A\le B$ and $C\le D$, then:

1. $A+C\le B+D$,
2. $A\cdot C\le B\cdot D$,
3. $A^C\le B^D$.

And so forth. It is easily proved by the above method, of composing the injective functions witnessing $A\le B$ and $C\le D$ into functions witnessing these properties.

Answer 2

Do it in three steps, each of which should be straightforward:

(i) $k_1m_1 \le k_2m_1$;

(ii) $k_2m_1 \le k_2m_2$;

(iii) Therefore by transitivity $k_1m_1 \le k_2m_2$.

Given the way homework questions are usually designed, each step is likely to be justifiable by quoting appropriate results given in the course. If not, justification is still not difficult.