Let's suppose that I have only defined $\mathbb{N}$ and then I define the terms finite and infinite set, and also countable and uncountable set.
I can think of some examples of finite, infinite and countable sets, but what about uncountable sets? I think the simplest example is $\mathbb{R}$. But as I don't have it defined yet then I cannot use it.
What may be a good and simple example in this case?. By simple I mean easy to verify without knowing anything about ordinals, cardinals or $\mathbb{R}$.
$\endgroup$ 69 Answers
$\begingroup$The set of all subsets of $\mathbb N$, also called the powerset of $\mathbb N$. It is denoted by $P(\mathbb N)$ and has a cardinality of $\beth_1=2^{\aleph_0}$ which is uncountably infinite.
$\endgroup$ 1 $\begingroup$The set of functions from $\mathbb{N}$ to $\mathbb{N}$, often denoted $\mathbb{N}^{\mathbb{N}}$, is uncountable. This follows from using an adapted Cantor's diagonalisation argument (or by using cardinal arithmetic, but you want to avoid that).
$\endgroup$ 2 $\begingroup$The set of infinite sequences consisting of $0$'s and $1$'s is uncountable. There are, in fact, easily constructed bijections between this set and $(0, 1)$.
$\endgroup$ 1 $\begingroup$The set of subsets of $\mathbf Q$ which have no greatest element is uncountable.
$\endgroup$ 4 $\begingroup$The set of all partitions of $\Bbb N$. In fact, the set of all partitions of $\Bbb N$ into two parts is already enough.
$\endgroup$ $\begingroup$One common proof technique to show that a set is uncountable is Cantor's diagonal argument. You can apply this to the example T. Bongers gave with infinite sequences of 0's and 1's.
Also, the powerset of any set is of a larger cardinality than the set. There is a good argument on Wikipedia.
$\endgroup$ $\begingroup$The power set $2^{\mathbb N}$ is uncountable.
Of course, this is exactly the same as the set of infinite binary sequences.
$\endgroup$ 4 $\begingroup$As everyone said, P(N), which is the set of all subsets of N is uncountable. I'm just gonna add the proof.
You can first use this theorem 3.3 and its proof in the link below:
As there is not any surjective map between any set A and P(A) from the theorem above, then there is no surjective map between N and P(N).
And as "countable set" is defined as "If a set C is a countable set, then there exist a map between C and N which is 1-1 and onto (surjective)"; then P(N) is not countable, as there is no surjective map from N to P(N).
q.e.d.
$\endgroup$ 2 $\begingroup$The open interval $(0,1)$ is uncountable.
$\endgroup$ 1
