# Homework Help: Sizes of infinity

1. Jul 25, 2006

### 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

2. Jul 25, 2006

### 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?)

3. Jul 25, 2006

### 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?

4. Jul 25, 2006

### 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.

5. Jul 25, 2006

### Office_Shredder

Staff Emeritus
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

6. Jul 25, 2006

### Mk

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

7. Jul 25, 2006

### Office_Shredder

Staff Emeritus
Why?

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

8. Jul 25, 2006

### 0rthodontist

9. Jul 25, 2006

### Data

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."

10. Jul 25, 2006

### Hurkyl

Staff Emeritus
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.

Only if you are using your finite intuition.

11. Jul 25, 2006

### EvLer

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

Last edited: Jul 25, 2006
12. Jul 25, 2006

### Data

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

13. Jul 25, 2006

### 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

Last edited: Jul 25, 2006
14. Jul 25, 2006

### 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...

Last edited: Jul 25, 2006
15. Jul 25, 2006

### 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.

16. Jul 25, 2006

### BoTemp

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.

17. Jul 26, 2006

### 0rthodontist

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.

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

Last edited: Jul 26, 2006
18. Jul 26, 2006

### Hurkyl

Staff Emeritus
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.

19. Jul 26, 2006

### Hurkyl

Staff Emeritus
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)

20. Jul 26, 2006

### 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!

Last edited: Jul 26, 2006
21. Jul 26, 2006

### EvLer

thanks, i'll try the questions, but if I make a mistake, could someone please correct?
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

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....

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

22. Jul 26, 2006

### 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|.$

23. Jul 27, 2006

### 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 text book.

Last edited: Jul 27, 2006
24. Jul 27, 2006

### HallsofIvy

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.)

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?

25. Jul 27, 2006

### Hurkyl

Staff Emeritus
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)

Last edited: Jul 27, 2006