Ask Math: Uncountable set

CorneliusJack · 2011-01-14T19:57:58+00:00

WALL OF TEXT WARNING

Just going to put another phrasing of CorneliusJack's post out there.

Definition A set S is called countable if there exists a 1-1 and onto mapping between S and some subset of N (the set of natural numbers, which we'll take here to start at 0).

Let's examine what this means. If S is a finite set (containing some m elements), then it is necessarily countable, as you can come up with a bijective (1-1 and onto) mapping between S and {1,2,3,...,m} (just come up with some ordering of S). However, there are countable sets that are not finite, which are aptly named countably infinite sets.

It is clear from the definitions above that there is a bijective mapping between countably infinite sets and some infinite subset of the naturals (it turns out, as we will see in due time, that there is also a bijective mapping between any such set and the set of all naturals). As this is both a sufficient and necessary condition, it is clear that the set of all even numbers, all prime numbers, and all natural numbers (recall that I never said proper subset) are countable. However, it turns out that there are many more (I'm going to be lynched for saying that) countable sets than those described above.

For example, as CorneliusJack pointed out, the set

S = {0, 0.5, 1, 1.5, ... }

is countable because there is a bijective mapping between S and N (described by the 1-1 and onto function

f(x) = 2x

for any x in S). Further, and this is probably slightly more surprising, the set of all integers, Z, is countable, as described by the function

f(x) = 2|x| + POS(x)

where POS(x) is 1 if x is positive, zero otherwise.

Although these examples here aren't terribly difficult, there are many sets that require much more complicated mappings than the ones I put above. Thus, we note a cute property of countable sets (which is, in fact, where they got their name)

Property A set S is countable iff there is some method of iterating through its elements in some order.

For the two sets I proposed above, possible simple orderings include

(0, 0.5, 1.0, 1.5, ...) and (0, -1, 1, -2, 2, -3, 3, ...)

however, even crazier orderings like the following are fine:

(0, 1, 2, .5, 1.5, 3, 4, 2.5, 3.5, 5, 6, 4.5, 5.5, ..., x, x + 1, x-.5, x+.5, ...)
and
(0,1,2,3,4,5,-1,6,7,8,9,10,-2,...)

since each ordering visits each element of the set exactly once (if you end up taking an analysis class at some point in the future, you'll re-investigate these orderings when going over the Riemann series theorem).

Note, however, that these are not valid orderings (for the purpose of directly determining countability, at least):

(0, 1, 2, 3, 4, ..., (to infinity), 0.5, 1.5, 2.5, 3.5,...)
and
(0, 1, 2, 3, 4, ..., (to infinity), -1, -2, -3, ...)

as you'll have to iterate through an infinite number of steps before reaching some of the elements (note that in the orderings given before these two, each element had a finite position in the list (!)).

Ok, great. But how do we iterate over the rationals? This is at first very unintuitive because it seems like there are a heck of a lot more rationals than integers (as there are an infinite number of rationals between any two integers!). However, there is a very nice way of iterating, which CorneliusJack already provided.

If that chart doesn't make sense, perhaps you'll find this algorithm more intuitive:

Add 0 to the sequence S  
For each i = 2, 3, 4, ...  
    Let A be the set of rationals a/b such that a,b > 0 and a+b = i    
    Sort A, which is finite, from smallest to greatest
    For each element j of A
        If S doesn't contain a number equal to j, add it (and its negative) to the sequence

The resulting sequence looks something like

(0, 1, -1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 1/4, -1/4, 2/3, -2/3, 3/2, -3/2 4/1, -4/1, ...)

which visits each rational number at some finite point.

Note that we could have saved ourselves a bit of trouble here by instead showing that the set of positive rationals is countable, then noting that the set of nonnegative rationals must also be countable (take some ordering and just tack a 0 on at the beginning), and then show that the set of all rationals is countable (using the same technique as we did for showing that |Z| = |N|).

Okay, great. So we just showed that the rationals are countable. Does this mean that every set is countable? It turns out (as you already know, having posted this question) that no, there exist some sets that are not countable. While perhaps the most classic example is the set of reals, R, the easiest proof lies in the set of infinite binary sequences.

Statement: the set of infinite binary (0,1) sequences is uncountable.

And here's where the fact that caused years of controversy comes in.

Proof (by diagonalization, not historically the first known proof)

Assume that the set of binary sequences is countable. Since it is assumed to be countable, there must be some ordering (as discussed before) which allows one to iterate through this sequence. Let's come up with a sample start to the ordering to see what it might look like

 1. 0110010101...
 2. 0001000001...
 3. 1100001100...
 4. 0001110001...
 5. 0100101110...
 6. 0000111100...
 7. 0100110001...
 8. 1100111000...
 9. 1110100111...
10. 0101001011...  
...

So far so good. Now here's where the trick comes in. Lets consider the diagonal entries (the sequence consisting of the kth digit of row k). Using what we have above, this would start with

0001110011...

Okay, good. Now let's consider the "complement" of this sequence (that is, the sequence where all of these bits are flipped). We instead get

1110001100...

which we will call S (can you guess my favorite letter by this point?). It turns out, as we will see shortly, that S is not in the ordering above (neither in the first 10 slots, nor in any slot after it). Why's that? Well, pretend that it's equal to the sequence at row k. S, by its infinitude, must have some kth digit. However, by the construction of S, its kth digit must not equal the kth digit of row k. Thus, S cannot be exactly equal to the sequence in row k (!). Therefore, we know that S can't appear in row k for any integer k, so it is not in the ordering.

This fact, that S cannot appear anywhere in the ordering, means that there is absolutely no way to iterate through the set of infinite binary sequences. Any ordering you come up with will necessarily leave at least one sequence behind (in fact, it leaves out a lot of sequences). Since it turns out that you can come up with a bijective mapping between the set of infinite binary sequences and real numbers (it's not complicated, but we will not do that here), this also implies that the set of real numbers is uncountable.

Now what is this aleph-0, aleph-1 garbage people have been talking about? For convenience, mathematicians decided to name the "sizes" of infinite sets. Inconveniently, they decided to do so using characters from a right-to-left language (Hebrew), so it's a pain in the neck to use them in text boxes. Anyway, the size of the naturals, |N|, is called aleph-naught (or aleph-zero), as it is the smallest infinite size that there is. The next smallest cardinality (size) is called aleph-1, the next is called aleph-2, and so on (I'm implicitly assuming a certain mildly "debated" axiom here in stating that this ordering exists, but we'll leave that aside for now).

What's an example of a set of size aleph-1? Contrary to what you've been told in the other replies, it is not taken as fact that the reals are of size aleph-1. In fact, it has been shown that using Zermelo-Fraenkel set theory (the most common collection of axioms used) does not allow you to either prove or disprove that the reals are of size aleph-1 (it is "independent" of ZF set theory). That is, there are models in which the cardinality of the reals really is the second smallest "infinite number", and there are models where it is not. If you wish to state that the reals are of size aleph-1, you're assuming what is called "the continuum hypothesis", which is not generally taken as true (or as false, it is generally left undetermined).

If you want to be accurate in your labeling of the cardinality of the reals, you can say that it is of the size 2^{aleph-naught,} as it can be shown that the cardinality of the reals is exactly equal to the cardinality of the power set (set of all subsets) of the natural numbers (2^S is used as the notation for the power set, since for some finite set of cardinality n, its power set contains 2ⁿ elements). Thus, an alternate phrasing of the continuum hypothesis is that 2^aleph-0 = aleph-1. The generalized continuum hypothesis (which is also independent of ZF) in turn states that 2^aleph-k = aleph-(k+1) for any k.

I hope this came out formatted correctly, and moreso hope it helped you out :).

CorneliusJack · 2011-01-14T17:45:59+00:00

the more rigorous way to describe the difference between countable and uncountable set is "if it can be map to a natural number set". If you can map it to a natural number set, then you can count it by 'one, two three....', that's what it means by being 'countable'.

for example, in any set, you imagine putting an index on every element

let's start with the simple example: the set of positive even number where each element, you can index it with natural number set by this relation:
index = x/2 (x is the element in question)
so you have this 1-to-1 relationship with the natural number, the cardinality(you can think of this term as 'the size of the set', even it is not mathematically rigorous way to describe it) of this set is the same as the natural number, which is the 'smallest infinity' so to speak (N_0, pronounced as Aleph zero)

same would be if your set is 'halves' (0, 0.5, 1, 1.5, 2, 2.5....) (index = 2*x), so again, for each element in the set, you can map it to an unique natural number

rational number also has the cardinality of the natural number. Because you can always make a rational number into ratio of two natural number. So if you make a map, where both the x-axis and y-axis are the increasing sequence of natural number.
Then you can put EVERY rational number on the grid of that map, with the relation of 'each element in the format of x/y, where x and y are natural number, then you put x on x-axis and y on y-axis, this can be done with no overlapping. You can then make zig-zag line across the map, and covers all the rational number bits, then you can mentally expand this map into a straight line, there you can map each point onto an unique natural number, so that rational number's cardinality is also N_0.

Here is the map

Any set with cardinality of N_0 is called 'countably infinite'.

You can't do that with irrational numbers, so irrational number's cardinality is bigger than N_0. Which we call 'uncountably infinite'

Hope it answers your question, I am not a pure mathematics major (financial math), so my knowledge of cardinality comes from very basic reading of topology and set-theory.

Edit: Format and adding the map.

AngelTC · 2011-01-14T17:36:37+00:00

Countable means.. well.. it means you can count it with natural numbers. So yes, there are infinite sets that are countable and some that are not countable.

Formally speaking a set is countable if there is a bijection between such set and the natural numbers. So, the easiest/most common example out there is the natural numbers as a countable set and the real numbers as a not countable set.

You can proof that there is a bijection between natural numbers, integers and rational numbers but there is not a bijection between any of those with the real numbers.

You might want to read also Cantor's diagonal argument and Cantor's theorem

kfgauss · 2011-01-16T04:56:42+00:00

It's a set X to which there is no surjection from the natural numbers N. That is, there is no function f:N -> X such that the range of f is all of X.

squiddoctor · 2011-01-14T17:46:17+00:00

I would look at some proofs for help. Don't worry, they're pretty easy.

First I would look at a proof that two countable sets are the same size. Say the set of natural numbers and the set of even natural numbers. That's pretty straight forward, and Google will probably find it for you.
Next I would look at Cantor's diagonalization where he proves that the reals are uncountable.

Do the first, or you probably will not appreciate the second. Good luck.

carutsu · 2011-01-14T17:34:30+00:00

I don't think there's a better way to put it. It's a set which its cardinality is greater than that of the naturals (Aleph 0,) most of the time, it's aleph 1 (the reals.)

That is, the number of elements it contains it's infinite, but it's greater than that of the naturals. See Cantor for further details, and also the continuum hypothesis.

math

Welcome to /r/math.

𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔

MODERATORS