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.

Which of the statements regarding cardinality of sets are always correct

Let $X$ be an infinite set then

(1)$|\{F|F \subseteq X \;\text {and} \;X \; \text {is finite}\}| > $|X|$

(2) $A \in P(X) $ and $ X\setminus A $ is infinite $\rightarrow |A|<|X|$

(3) $A \subseteq X $ and $|A|<|X| \Rightarrow |X\setminus A|=|X|$


(5) $|X*X|>|X|$

and $P(X)$ indicates the power set of X. I think 4 is correct but I am not sure of the rest please provide help since we have not been covered cardinality in the course properly

share|improve this question
In the future, please post only one question in one post. Posting several questions in the same post is discouraged and such questions may be closed, see meta. –  Cameron Buie Jul 3 '13 at 3:52
For #2, consider "nice" uncountable subsets of the reals. To answer #5, we need more information (in particular, what axioms are you working with?) #3 has been answered on this site before, and I suspect that #1 has, as well. –  Cameron Buie Jul 3 '13 at 3:56
Are you assuming the axiom of choice? –  Andres Caicedo Jul 3 '13 at 4:00
@AndresCaicedo Yes I am –  user83369 Jul 3 '13 at 4:02
(3) is the only statement whose truth value could change in the absence of choice. (It is always true under choice, and there are models where choice fails, and there are counterexamples.) –  Andres Caicedo Jul 3 '13 at 5:49

2 Answers 2

up vote 2 down vote accepted

You are right about (4): this is Cantor’s theorem, a very important basic result about cardinalities. Assuming the axiom of choice, (5) is false: it is a general fact about infinite sets that $|X\times X|=|X|$. Unless you’re taking a course that goes into well-orderings in some detail, you could not reasonably be asked to prove this; I imagine that you’re simply expected to learn it as a fact. The same goes for (1): if $X$ is an infinite set, and $\mathscr{F}$ is the set of finite subsets of $X$, then $|\mathscr{F}|=|X|$. (3), on the other hand, is true; again, this is probably something that you’re expected simply to learn as a fact, unless you’re taking a fairly serious elementary set theory course.

Syd Henderson has given a nice, straightforward example showing that (2) is not necessarily true.

share|improve this answer
@user14111: True, and I didn’t say otherwise: it’s the general fact that is beyond the scope of a really elementary course. –  Brian M. Scott Jul 3 '13 at 4:54

To see #2 is false, let X be the set of integers and A the set of odd integers. Then X, A and X\A all have the same cardinality.

share|improve this answer

Your Answer


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.