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

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!