Sizes of Infinity: Countable vs Uncountable

[EvLer]

So we talked about this in class but there's nothing in the textbook. Basically I want to make sure I get this:

Reals are uncountable, while natural numbers, integers, and rationals are countable. So really the cardinality: |Z| = |R| = |Q| < |R|
then there are only 2 sizes of infinity: inifinitely countable and infinitely uncountable. Right?
Another question I have is this: can someone give an example when Cantor's diagonalization is applied to countable sets and how it works out...
thanks

 

[0rthodontist]

There are an infinite number of "sizes" of infinity. For example the power set of any set is of strictly greater cardinality, even if the original set is uncountable.

Cantor's diagonalization is used only to show that sets are NOT countable. On a countable set you wouldn't be able to find a suitable diagonal not included in the listing. For example if you try the integers, any such diagonalization would be an "infinite digit" integer which doesn't exist. On the rational numbers written as decimals, such a diagonal would be nonrepeating. (Can you prove it directly?)

 

[EvLer]

but what about if the prof on exam asks: is this (whatever) set countable or uncountable.
How do I start? try to make it countable? how do I know when and if to use Cantor's method if the question does not explicitly asks for that?

 

[0rthodontist]

If it's countable, then probably your proof should be that you actually give a way to count it in some order. If it's uncountable then Cantor's diagonalization method would work, or if you can recognize it or put it in 1-1 correspondence with some other uncountable set, that would work too.

 

[Office_Shredder]

then there are only 2 sizes of infinity: inifinitely countable and infinitely uncountable. Right?

Wrong. In fact, there is no "biggest" infinity. Take a set. Then, make a new set composed of every subset of the initial set. That new set will be larger than the old one. The same holds for infinite sets.

The interesting question is whether there is an infinity BETWEEN countable and continuum

 

[Mk]

Doesn't it seem like in any given space, there would be more points than possible lines?

 

[Office_Shredder]

Doesn't it seem like in any given space, there would be more points than possible lines?

Why?

If you're thinking "There are infinite points per line", keep in mind that each point is used by infinite lines also

 

[0rthodontist]

The interesting question is whether there is an infinity BETWEEN countable and continuum

The continuum hypothesis is undecidable.
http://en.wikipedia.org/wiki/Continuum_hypothesis#Impossibility_of_proof_and_disproof

 

[Data]

only 2 sizes of infinity: inifinitely countable and infinitely uncountable

well in some sense this is right. Every infinite set is either countable or uncountable (a countable set is by definition any set that can be put into 1-1 correspondence with some subset of the natural numbers, and if a set isn't countable then it is uncountable). But as others have pointed out, given any set it is always possible to construct a "larger" set (in the sense that you can't have a bijection between them), so there are infinitely many "sizes of infinity."

 

[Hurkyl]

Just to clarify, any infinite cardinal (it's not right to call it an "infinity") is either countable or uncountable. It's just that there are many different sizes of uncountable cardinals.

Doesn't it seem like in any given space, there would be more points than possible lines?

Only if you are using your finite intuition.

 

[EvLer]

Wrong. In fact, there is no "biggest" infinity. Take a set. Then, make a new set composed of every subset of the initial set. That new set will be larger than the old one. The same holds for infinite sets.

but I can still ORDER them by cardinality, right? i.e. |P(N)| < |P(R)|
and |P(N)| < |R|
where P is power set;actually what I need to make sure is that this is correct, as far as cardinality:
N < Z = Q < R

 

[Data]

$|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}|$

 

[Data]

but whether |P(N)|<|R| seems nontrivial (I don't know anything about set theory, so it's quite likely that someone else can tell you whether this is true or not). But P(N) is definitely uncountable (since there's never a bijection between a set and its power set).

Edit: A quick wikipedia search will tell you that in fact |P(N)| = |R| - http://en.wikipedia.org/wiki/Cardinality

 

[EvLer]

so among countable sets there is no ordering of cardinality except the power set (that is the only one I have heard about); and so power set of a countable set is also countable, right?
sorry for all the questions: have exam coming up...
edit:
oh, so power set of a countable set is not countable?
Could someone provide a proof sketch? I have been searching, but can't find much relevant stuff...

 

[Data]

The power set of a countably infinite set is not countable (the power set of a finite set is always still finite and countable), precisely because a set always has smaller cardinality than its power set.

 

[BoTemp]

but what about if the prof on exam asks: is this (whatever) set countable or uncountable.
How do I start? try to make it countable? how do I know when and if to use Cantor's method if the question does not explicitly asks for that?

Say you're given two sets and asked to determine which is larger. Most direct way is to try and find a bijection. If you can find one, they're equal, otherwise you need to prove that one cannot exist.
Try and find some practice problems. I'll list the few that I know.

1. Let A be the set of real numbers between 0 and 1 (inclusive), and let B be the set of real numbers between 0 and 2. Which set has a higher cardinality? If they are equal, construct a bijection.

2. Let C be the number of points on a line segment of unit length, and let D be the number of points on a line segment of infinite length. Which cardinality larger? If equal, find bijection.

3. Prove that the total number of subsets of a set with N elements is 2^n. A bit pedestrian, but a fundamental.

 

[0rthodontist]

so among countable sets there is no ordering of cardinality except the power set (that is the only one I have heard about); and so power set of a countable set is also countable, right?
sorry for all the questions: have exam coming up...
edit:
oh, so power set of a countable set is not countable?
Could someone provide a proof sketch? I have been searching, but can't find much relevant stuff...

Assume there existed a bijection f between a set A and its power set B. Then let S be the set of all a$$\in$$A such that a $$\not\in$$ f(a). S is a subset of A, so it is an element of B, so consider c = f^-1(S). Is c in S or isn't it? Well, if it is, c $$\not\in$$ f(c) by the definition of S. But f(c) = S, so there is a contradiction. On the other hand if c is not in S, then c $$\in$$ f(c) by the definition of S. But again f(c) = S so there is a contradiction here too. So there cannot be a bijection between a set and its power set. Also there does exist an injection from a set to its power set, for example the function given by f(a) = {a}, so a set's power set has greater cardinality than the set itself.

Edit: A quick wikipedia search will tell you that in fact |P(N)| = |R| - http://en.wikipedia.org/wiki/Cardinality

This is also undecidable. Apparently it is equivalent to the continuum hypothesis.

 

[Hurkyl]

I'm quite sure that R ~ P(N) is a decidable fact. The bijection is given by:

P(N)
<-->
binary sequences
<-->
nonterminating binary sequences
<-->
(0, 1]
<-->
R

It's easy to explicitly construct the first, third, and fourth of these bijections. The second follows from the fact that there are only countably many terminating binary sequences -- I don't think you need the axiom of choice to prove that A = A+B where A is infinite, and A > B.

 

[Hurkyl]

I like the form of the diagonal argument that uses characteristic functions instead of the power set; it seems much cleaner.

Suppose there was a surjection:
f : (elements of A) ---> (characteristic functions on A)

Then, we define g(x) := 1 - f(x)(x).

g is a characteristic function on A. So, there must exist some c such that f(c) = g. Then:

f(c)(c) = g(c) = 1 - f(c)(c)

which is a contradiction.

 

[Data]

My (fairly limited) understanding is that |R| = |P(N)| is decidable and proved (probably fairly easily if Hurkyl's analysis is correct). The continuum hypothesis is that $|\mathbb{R}| = \aleph_1,$ ie. that there's nothing "between" countable and continuum, and this is undecidable (as Office_Shredder was hinting at). Unless someone has proved that $P(\aleph_0) = \aleph_1$ then there's no way that those are equivalent. I'm pretty sure that no one has proved that!

 

[EvLer]

Try and find some practice problems. I'll list the few that I know.

thanks, i'll try the questions, but if I make a mistake, could someone please correct?

1. Let A be the set of real numbers between 0 and 1 (inclusive), and let B be the set of real numbers between 0 and 2. Which set has a higher cardinality? If they are equal, construct a bijection.

both are uncountable, so there isn't a way to establish a ranking, even though intuitively |0-2| > |0-1|
0-1 is uncountable by Cantor's argument

2. Let C be the number of points on a line segment of unit length, and let D be the number of points on a line segment of infinite length. Which cardinality larger? If equal, find bijection.

number of points on unit length line is uncountable, while number of points on an infinite line can be paired with natural numbers. although I am not sure since infinite line includes unit length line...

3. Prove that the total number of subsets of a set with N elements is 2^n. A bit pedestrian, but a fundamental.

assume |S| = n then each element may or may not be present in some particular subset => 2^n subsets

 

[Data]

For the first question you need to work a bit harder. What's does it mean for two sets to have the same cardinality? Can you prove that this holds or doesn't hold for those two sets?

For the second question your answer is wrong. I don't know how you decided that "the number of points on an infinite line can be paired with the natural numbers," but that can easily be disproven using a diagonal argument. In general if $S \subset S^\prime$ then $|S| \leq |S^\prime|.$

 

[matt grime]

You want to decide whether [0,1], and [0,2] have the same cardinality. There is a rather obvious bijection between them.

There are several rules you should know, including, but not limited to:

1. If $\alpha_1,..,\alpha_n$ is a finite collection of infinite sets then the cardinality of the union is the maxmimum of the cardinalities of the $\alpha_i$.

2. The countable union of countable sets is countable.

3. If X is in bijection with a subset of Y and Y is in bijection with a subset of X, then they have the same cardinality.All of these should be proven in your textbook.

 

[HallsofIvy]

so among countable sets there is no ordering of cardinality except the power set (that is the only one I have heard about); and so power set of a countable set is also countable, right?
sorry for all the questions: have exam coming up...
edit:
oh, so power set of a countable set is not countable?
Could someone provide a proof sketch? I have been searching, but can't find much relevant stuff...

I'm not sure what you mean by "no ordering of cardinality except the power set". The power set is a set, not an "ordering". It is true that the cardinality of of the power set of set A is always strictly larger than that of A itself. However, given any two sets, A, B, one and only one of these three must be true:
1) Cardinality of A is larger than Cardinality of B.
2) Cardinality of A is smaller than Cardinality of B.
2) Cardinality of A is equal to Cardinality of B.
(In other words, order by cardinality is a linear order.)

In your first post you asked

can someone give an example when Cantor's diagonalization is applied to countable sets and how it works out...

It's not clear to me what you mean by that: You CAN'T apply Cantor's diagonalization to countable sets since it implies uncountability. You may mean "what goes wrong when you try to apply it".

Here's a "proof" that the set on counting numbers itself is uncountable- you often see it given by people who think they can show Cantor's method is wrong. There's an obvious error. See if you can find it.

Order the counting numbers in the obvious way: 1, 2, 3, etc. Think of each of them as an infinite string of digits by appending an infinite string of 0's : ...000000...00001, ...00000...00002, etc. Now go through the list of counting numbers creating a new number, x, by applying Cantor's method: if the nth (from the right- the ones place) digit of the nth number is a 2, write a 7 in the nth digit of x, if it is not a 2, write a 2. (I've pretty much just chosen those numbers at random.) Obviously this new number x will not be equal to any of the numbers on the list (it is different from the nth number in the list in the nth digit) and so is not on the list itself. Since, given any list of counting numbers we can produce a new number that is not on the list, it follows that the set of counting numbers is not countable!

Again, that is not a valid proof! Can you see the error?

 

[Hurkyl]

Some algebraic properties of infinite cardinals:

A+B = max(A, B)
AxB = max(A, B)

(these are still true if one of them is finite)

 

[Hurkyl]

It's not clear to me what you mean by that: You CAN'T apply Cantor's diagonalization to countable sets since it implies uncountability.

I think he means the other diagonal argument:

0 1 3 6
2 4 7
5 8
9
...

 

[EvLer]

thanks all for the input...