# cardinality

• April 15th 2008, 07:00 PM
sfitz
cardinality
I have two problems:

1. Let A, B, and C be sets. Suppose that card A < card B and card B < card C. Prove that card A < card C.

Can I do this by contradiction?:
Assume card A < card B, card B < card C, and by contradiction, that card A > C.
We are give that card A < card B.
By transitivity of the relation <, card B < card C and card C < card A implies that card B < card A.
Contradiction, because card A < card B and card B < card A can't both be true.

Is this right or am I missing something?

2. Let K be any set, and let F be the set of all functions with domain K. Then card K < card F.

I don't know how to start with this one. It makes sense, because there are infinitely many functions for each possibility of the codomain... But I don't know how to say that. Any hints?

Thank you!
• April 15th 2008, 07:11 PM
ThePerfectHacker
Quote:

Originally Posted by sfitz
1. Let A, B, and C be sets. Suppose that card A < card B and card B < card C. Prove that card A < card C.

The first step is to note that $|A| \leq |C|$ because we know there exists injective maps $\mu: A\mapsto B$ and $\eta: B\mapsto C$ so $\eta \circ \mu : A\mapsto C$ is injective. Which means $|A|\leq |C|$. Now you argue that it is not possible to have $|A| = |C|$. Assume that if $\phi: A\mapsto C$ is bijection. Then $\eta^{-1} \circ \phi :A\mapsto B$ is a bijection contradicting the fact that $|A| < |B|$.

Quote:

2. Let K be any set, and let F be the set of all functions with domain K. Then card K < card F.
This is not a good set. $F$ is a set of all function from $K$ to where?
• April 15th 2008, 07:18 PM
sfitz
The first one makes sense, thank you! What is the problem with what I did? Or does it make sense, but just not as good a proof?

For the second one, that's all the problem said. I think from K to anything, all the different possibilities. There's no other information.

Thank you!