25
$\begingroup$

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$
6
  • 5
    $\begingroup$ The set of subsets of N. $\endgroup$ Oct 2, 2013 at 2:46
  • $\begingroup$ The set of all sets? $\endgroup$
    – naught101
    Oct 2, 2013 at 5:22
  • 13
    $\begingroup$ @naught101 The set of all sets doesn't exist $\endgroup$ Oct 2, 2013 at 5:28
  • 1
    $\begingroup$ @ARi: most reasonable definitions of 'program' would require the program to be finite in length over some finite alphabet, and therefore at most countably infinite. $\endgroup$ Oct 2, 2013 at 21:46
  • 2
    $\begingroup$ An example of a different nature from the ones mentioned below is the first uncountable ordinal, $\omega_1=\aleph_1$. Its existence can be established without any reference to the reals (or any appeal to the axiom of choice). See here. $\endgroup$ Oct 9, 2013 at 16:19

9 Answers 9

43
$\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
  • 6
    $\begingroup$ This is the canonical example, and its proof is pretty much the cleanest form of Cantor’s diagonalisation. Given any function $\varphi : \mathbb{N} \to \mathcal{P}(\mathbb{N})$, define the set $D(\varphi) = \{n \in \mathbb{N}\ |\ n \notin \varphi(n) \}$. Then $D(\varphi)$ can’t be in the image of $\varphi$, since if $D(\varphi)=\varphi(m)$, then $m \in D(\varphi) \Leftrightarrow m \notin D(\varphi)$, which is contradictory. So $D(\varphi)$ shows that $\varphi$ is not surjective, and in particular, is not a bijection. $\endgroup$ Oct 2, 2013 at 17:45
17
$\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$ “or by using cardinal arithmetic” — this isn’t really a different option; the proof of this property of cardinal arithmetic uses exactly that diagonalisation argument. $\endgroup$ Oct 2, 2013 at 14:52
  • 1
    $\begingroup$ Would the person who downvoted this post mind clarifying why they think this answer is not useful? $\endgroup$ Oct 9, 2013 at 22:28
16
$\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
  • 22
    $\begingroup$ Actually it's not very "easily". The obvious way [binary expansions] fails to be a bijection (it is not injective). $\endgroup$
    – Asaf Karagila
    Oct 2, 2013 at 8:41
12
$\begingroup$

The set of subsets of $\mathbf Q$ which have no greatest element is uncountable.

$\endgroup$
4
  • 11
    $\begingroup$ (This is cheating! =D) $\endgroup$
    – Pedro
    Oct 2, 2013 at 4:05
  • 5
    $\begingroup$ @PedroTamaroff I initially wanted to say "the set of Dedekind cuts", but I felt that would be pushing it ;) $\endgroup$ Oct 2, 2013 at 4:11
  • 3
    $\begingroup$ How do you show this set is uncountable? $\endgroup$ Oct 2, 2013 at 10:28
  • $\begingroup$ @MichaelAlbanese Good question. I admit that I'd have a hard time doing it while respecting Daniela's conditions. $\endgroup$ Oct 2, 2013 at 16:24
7
$\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$
6
$\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$
5
$\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
  • 1
    $\begingroup$ I don't think it's quite right to call $2^\mathbb{N}$ the power set of $\mathbb{N}$, although it is naturally isomorphic to it. $\endgroup$ Oct 2, 2013 at 4:02
  • 4
    $\begingroup$ @Trevor I think a natural isomorphism is definitely a good enough reason to call two objects the same thing! (Please don't give me any silly counterexamples...) $\endgroup$ Oct 2, 2013 at 10:03
  • $\begingroup$ @Donkey_2009 Not in the context of set theory (and the question is tagged "elementary-set-theory".) And in any case it would only make sense to call them the same thing after one has seen a bijection between them, and the OP may not have seen one yet. $\endgroup$ Oct 2, 2013 at 15:34
  • $\begingroup$ Also in some topoi $2^{\mathbb{N}}$ and $\mathcal{P}(\mathbb{N})$ can fail to be isomorphic, I believe. $\endgroup$ Oct 2, 2013 at 15:39
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:

http://www.math.psu.edu/wysocki/M403/Notes403_3.pdf

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$ Hardly "everyone". $\endgroup$
    – Asaf Karagila
    Oct 2, 2013 at 15:03
  • 1
    $\begingroup$ @AsafKaragila yeah you're right, hardly everyone. I just tried to mention that it was the most common example. $\endgroup$ Oct 4, 2013 at 7:06
1
$\begingroup$

The open interval $(0,1)$ is uncountable.

$\endgroup$
1
  • 12
    $\begingroup$ But that is basically $\Bbb R$, which OP didn't want to use. $\endgroup$ Oct 2, 2013 at 2:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .