3
$\begingroup$

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

  • 0
    What are your definitions of cardinal arithmetic, and what have you tried? For instance, under some definitions, all this amounts to is showing that from any pair of injective maps $M_1 \to M_2$ and $K_1 \to K_2$, you can get an injective map $K_1 \times M_1 \to K_2 \times M_2$...2011-08-13

2 Answers 2

4

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.

  • 0
    @Jason: They are the usual definitions. I added them for sake of having my answer self contained.2011-08-13
4

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.