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
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
First:
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:
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.
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.