23
$\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$
  • 5
    $\begingroup$ The set of subsets of N. $\endgroup$ – Keshav Srinivasan Oct 2 '13 at 2:46
  • $\begingroup$ The set of all sets? $\endgroup$ – naught101 Oct 2 '13 at 5:22
  • 12
    $\begingroup$ @naught101 The set of all sets doesn't exist $\endgroup$ – Daniela Diaz Oct 2 '13 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$ – Simon Nickerson Oct 2 '13 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$ – Andrés E. Caicedo Oct 9 '13 at 16:19
42
$\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$
  • 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$ – Peter LeFanu Lumsdaine Oct 2 '13 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$
  • $\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$ – Peter LeFanu Lumsdaine Oct 2 '13 at 14:52
  • 1
    $\begingroup$ Would the person who downvoted this post mind clarifying why they think this answer is not useful? $\endgroup$ – Michael Albanese Oct 9 '13 at 22:28
15
$\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$
  • 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 '13 at 8:41
11
$\begingroup$

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

$\endgroup$
  • 10
    $\begingroup$ (This is cheating! =D) $\endgroup$ – Pedro Tamaroff Oct 2 '13 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$ – Bruno Joyal Oct 2 '13 at 4:11
  • 3
    $\begingroup$ How do you show this set is uncountable? $\endgroup$ – Michael Albanese Oct 2 '13 at 10:28
  • $\begingroup$ @MichaelAlbanese Good question. I admit that I'd have a hard time doing it while respecting Daniela's conditions. $\endgroup$ – Bruno Joyal Oct 2 '13 at 16:24
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$
6
$\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$
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$
  • 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$ – Trevor Wilson Oct 2 '13 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$ – John Gowers Oct 2 '13 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$ – Trevor Wilson Oct 2 '13 at 15:34
  • $\begingroup$ Also in some topoi $2^{\mathbb{N}}$ and $\mathcal{P}(\mathbb{N})$ can fail to be isomorphic, I believe. $\endgroup$ – Trevor Wilson Oct 2 '13 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$
  • $\begingroup$ Hardly "everyone". $\endgroup$ – Asaf Karagila Oct 2 '13 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$ – Zafer Sernikli Oct 4 '13 at 7:06
1
$\begingroup$

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

$\endgroup$
  • 11
    $\begingroup$ But that is basically $\Bbb R$, which OP didn't want to use. $\endgroup$ – Ross Millikan Oct 2 '13 at 2:46

protected by Jared Oct 4 '13 at 14:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.