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 two questions about set theory and cardinals.

  1. I know that $k_1, k_2, m$ are cardinals. I also know that $k_1 \leq k_2$. I need to prove that $(k_1)^m \leq (k_2)^m$.
    I understand from what given that there is injective function between the sets of $k_1$ and $k_2$. I also know that if $|A| = |C|$, $|B|=|D|$ then $|B^A| = |D^C|$. so basically what I need to prove is that $k_2 \leq k_1$, and then with Cantor–Bernstein–Schroeder theorem say that if $k_1 \leq k_2$ and $k_2 \leq k_1$ then $k_1 = k_2$, am I correct? I don't know how to continue from here.

  2. the second question is that I need to prove that the set of relations on the set $N$ is $c$. I understand from the question that I need to prove that $|P(N \times N)|=c$, but I'm not sure and I don't know how to continue from here.

I'm just tired from all this discrete math, maybe anyone can recommend a good resource to read so I will understand it better.

Thank in advance.

share|improve this question
    
The first one is shown also in this answer. –  Martin Sleziak May 17 '12 at 19:17

1 Answer 1

For the first question: you shouldn't need the fact on equality. Instead, you can just use your injective function (say, $i$) from $k_1\to k_2$ to build an injective function $j$ from $k_1^m\to k_2^m$. Using the characterization of $A^B$ as the set of functions from $B\to A$, your $j$ is a function that will take a function from $m\to k_1$ and return a new function from $m\to k_2$. There's a very natural answer for how to build $j(f)$ given a function $f\in k_1^m$ and your injection $i$, and you should be able to prove that it works (that is, to prove that it's injective).

For the second question: do you know the notion of a pairing function? That should be all that you need to solve this problem.

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.