Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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$... –  Zhen Lin Aug 13 '11 at 14:31

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
The two points you wrote are correct those are my definitions. And this is a great answer exactly like I'm looking for thanks a lot :) –  Jason Aug 13 '11 at 14:59
    
@Jason: They are the usual definitions. I added them for sake of having my answer self contained. –  Asaf Karagila Aug 13 '11 at 15:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.