[bonanova]

You can count things like the people in a room, apples in a basket and letters in this sentence. These are examples of finite sets - their cardinality is just the number of objects they contain.

If a dinner party has 13 guests, and there are 13 place settings at the table, we can say the cardinality of the guests is the same as the cardinality of the dinner plates or of the soup spoons. When the guests are seated, each guest has a plate and a soup spoon. If one of the guests does not show up, the cardinalities would then differ.

You can also count the positive integers. In fact you use the positive integers to do the counting, so they're sometimes called the counting numbers. There are an infinite number of them. So their cardinality can't be a number like 43 or 125. So we give this cardinality a symbol instead: Aleph_o Any collection [set] whose elements can be placed in a one-to-one correspondence to the counting numbers has the cardinality Aleph_o We call such collections countably infinite. That might sound like a contradiction.

Other collections are infinite in "number" [cardinality] but are not countable. An example is the real numbers. Their cardinality is given the symbol Aleph₁. They cannot be placed in a 1-1 correspondence to the counting numbers. Other sets have even higher cardinality.

So we've mentioned four classes of sets:

.

1. finite sets,
2. the positive integers [countable] Aleph_o
3. the real numbers [uncountable] Aleph₁
4. higher infinities Aleph_2...
   .

Just for fun, classify the following ten sets by cardinality: 1, 2, 3 or 4.

.

• Unicorns
• Negative integers
  
• Odd integers
• Neurons in your brain
  
• Rational numbers [p/q where p and q are integers]
  
• Atoms in the universe
• Functions of real numbers
  
• Points in the line segment [0, 1]
• Points in the square having diagonally opposite corners [0,0] and [1,1]
• Points in infinite 3-space.
  .

Remember, if you can construct a 1-1 correspondence, you can say two sets have the same cardinality. And here's a clue - the list has at least one of each type.

[araver]

1 - Finite - but not equal in cardinality - listed in ascending order

- Unicorns (probably 0)

- Neurons in your brain

- Atoms in the universe (since 1 neuron has more than 1 atom .... and there are other brains as well )

2 - Aleph_O - Countable

- Negative integers (1-to-1: for every negative integer, consider it's positive counterpart)

- Odd integers (1-to-1: for every odd integer 2p+1, consider p it's counterpart)

- Rational numbers [p/q where p and q are integers] (1-to-1: only actual way of counting rational numbers that I know of is a small distortion of Cantor's diagonal proof - reordering positive rational numbers so that p+q increases from left to right, all elements with the same sum p+q>0 are neighbors, and p and q are co-prime: 1/1, (1/2, 2/1,) (1/3, 3/1), (1/4, 2/3, 3/2, 4/1), (1/5, 5/1),.... Once you have positive rational numbers counted the same as positive integers, it's easy to think of the negative counterparts. If one counts all p+q as in the original diagonal argument, without the coprime condition, it is simpler to prove that the sequence covers all rational numbers at least once, has an infinite number of repetitions therefore there is an injective function from rational numbers to integers. Since integers are rational numbers, one gets two opposing injective functions needed by the Cantor-Bernstein-Schroeder theorem to deduce equality of cardinalities).

3 - Aleph₁ - Real numbers

- Points in the line segment [0, 1]

- Points in the square having diagonally opposite corners [0,0] and [1,1]

- Points in infinite 3-space

All these can be shown through the same theorem (two injections). Not sure if there is a simple bijection.

4 - Aleph₂

- Functions of real numbers

Besides the clue stating that at least one is in set 4, there's the old argument that the power-set of an Aleph_n set cannot be Aleph_n itself.

Generalized continuum hypothesis would make 2^Aleph₁ = Aleph_2.

EDIT: That would show all function of real numbers with output 0 and 1 are Aleph₂ . To finish, for each such function f( ) consider g_f (x,y)=1 if y=f(x) and 0 otherwise. This is an injection from functions of real numbers to the powerset of 2-dim space (and 2-dim space is the same cardinal as the 1-space).

Edited November 21, 2010 by araver

[Guest]

Just to start...

unicorns-1

neurons in brain-1

atoms in the universe-1

negative integers-2

odd integers-2

rational numbers-2

points in the line segment [0,1]-3

That's as far as i can go off the top of my head... If anyone wants explanations for them, I can give them.

[Guest]

I had an argument with the lecturer on this.

You say that if there exists a one-to-one relation between two groups then they are the same size, there was an example of all the positive numbers and all the positive even numbers, he claimed that those two groups were the same size cause you can have a one-to-one relation between them (multiplication/division by 2) but I said that for every number n in the even numbers group you have n and n+1 in the first group...

I thought the way to settle this was to see it in the practical application this had in real life, I sat down and didn't bother with it again...

Edited November 21, 2010 by Anza Power

[bonanova]

I had an argument with the lecturer on this.

You say that if there exists a one-to-one relation between two groups then they are the same size, there was an example of all the positive numbers and all the positive even numbers, he claimed that those two groups were the same size cause you can have a one-to-one relation between them (multiplication/division by 2) but I said that for every number n in the even numbers group you have n and n+1 in the first group.

Simpler than multiplication / division is to just count:

2 4 6 8 10 12 14 16 ...

1 2 3 4  5  6  7  8 ...

[/code]

Now does anyone care to place the real numbers in a 1-1 correspondence with the points in a unit square, or infinite 3-space? 

Assuming we accept they both are all Aleph[sub]1[/sub].


[/font]

[Guest]

Simpler than multiplication / division is to just count:

2 4 6 8 10 12 14 16 ...

1 2 3 4  5  6  7  8 ...

Now does anyone care to place the real numbers in a 1-1 correspondence with the points in a unit square, or infinite 3-space?

Assuming we accept they both are all Aleph₁.

That's dividing by two...

Points in a unit square should be Aleph₂ not 1 since points in a 1cm line are Aleph₁...

[araver]

Points in a unit square should be Aleph₂ not 1 since points in a 1cm line are Aleph₁...

Not really. There are as may points in a unit square as in a segment. Similarly a plane has as many points as a plane.

I know it sounds counter-intuitive but it's really not that absurd.

I can convince you with the interleaving digits argument which basically is an extension of the odd/even argument.

I am assuming that you believe that there is a correspondence between even numbers and odd numbers (f(x)=x+1 for every even integer x). Now if you shuffle back the evens and the odds putting one even then one odd, and so forth, you get all integers again.

Long story short:

For every real number x between 0 and 1 (your 1cm line) you can write an infinite sequence of decimal digits:

x=0.x₁x₂x₃ ...

This can be written as an infinite sum: x = sum_i>0 (x_i /10ⁱ).

The same applies for every real number, adding it's integer part to the left of the decimal point.

The problem is that this digit decomposition is not unique as seen for 1 for example:

1=0.99999999999999999999999999...

=1.00000000000000000000000000....

(there are several proofs for this result, not directly relevant to this discussion)

However, this non-uniqueness only occurs when you get an infinite sequence of 0's. This is the case only for rational numbers, more precisely for rational x = p/q where q is of the form 2ⁿ5^m, where n and m are positive integers (m,n>=0).

So, you may get an unique decimal representation by simply banning an infinite sequence of 9's and choosing the other possible representation, ok?

Back to the square. For every a and b real numbers you have two such unique-sequences as seen above (not ending in infinite 9's):

a=0.a₁a₂a₃ ...

b=0.b₁b₂b₃ ...

By interleaving the two sequences you create an infinite decimal representation and therefore a real number x:

x=0. a₁b₁a₂b₂a₃b₃ ...

The beauty lies in the fact that for every point in that unit square, you get exactly one point on the unit segment (your 1cm line) and conversely each point on that unit segment can be split into (a,b) giving a point in the unit square.

Convinced?

Now does anyone care to place the real numbers in a 1-1 correspondence with the points in a unit square, or infinite 3-space?

Assuming we accept they both are all Aleph₁.

Yes, I'll think of a nice (=geometric) 1-to-1 correspondence and post it.

Simplest way I know has multiple steps square-rectangle-ray and so forth.

P.S. I don't really like the interleaving digits or Cantor-Bernstein-Schroeder proofs either, but accept them

Edited November 22, 2010 by araver

[araver]

Well, geometrically, one can show very nicely continuous 1-to-1 correspondences (continuous in almost every point).

E.g. a visual representation of why a segment has the same number of points as a ray (half a line if you prefer).

1. Take a segment [C,D) (That is with C but without D)

2. Consider a circle tangent to CD that contains D.

3. Construct a parallel line to CD over the other side of the circle

4. Let G be a moving point on the green segment CD.

5. Construct another tangent to the circle from G (as one tangent always follows line CD).

6. Denote H the point of intersection between this tangent and the parallel line.

As G moves inside the green segment [C,D), H describes a red "ray" (-inf, I]. This 1-to-1 correspondence is seen in the following animation:

Cannot find a simple geometrical way to get from 1-D space to 2D space (that would replace the interleaving proof in my previous post).

A 1-to-1 correspondence between 2-dimensional space and 1-dimensional space has to "distort" that space a lot ... spreading two near points in a plan in very distant places on the line. So it's very hard to show it in a geometrical way.

I know of infinite curves that can fill an unit square, but there not so easy to explain in an animation using GeoGebra.

bonanova, is this (curves filling nD objects) what you were thinking about?

I'm slowly running out of uploading space, so I'll probably need to delete some previously added images/posts.

[Guest]

1 - Finite - but not equal in cardinality - listed in ascending order

- Unicorns (probably 0)

- Neurons in your brain

- Atoms in the universe (since 1 neuron has more than 1 atom .... and there are other brains as well )

2 - Aleph_O - Countable

- Negative integers (1-to-1: for every negative integer, consider it's positive counterpart)

- Odd integers (1-to-1: for every odd integer 2p+1, consider p it's counterpart)

- Rational numbers [p/q where p and q are integers] (1-to-1: only actual way of counting rational numbers that I know of is a small distortion of Cantor's diagonal proof - reordering positive rational numbers so that p+q increases from left to right, all elements with the same sum p+q>0 are neighbors, and p and q are co-prime: 1/1, (1/2, 2/1,) (1/3, 3/1), (1/4, 2/3, 3/2, 4/1), (1/5, 5/1),.... Once you have positive rational numbers counted the same as positive integers, it's easy to think of the negative counterparts. If one counts all p+q as in the original diagonal argument, without the coprime condition, it is simpler to prove that the sequence covers all rational numbers at least once, has an infinite number of repetitions therefore there is an injective function from rational numbers to integers. Since integers are rational numbers, one gets two opposing injective functions needed by the Cantor-Bernstein-Schroeder theorem to deduce equality of cardinalities).

3 - Aleph₁ - Real numbers

- Points in the line segment [0, 1]

- Points in the square having diagonally opposite corners [0,0] and [1,1]

- Points in infinite 3-space

All these can be shown through the same theorem (two injections). Not sure if there is a simple bijection.

4 - Aleph₂

- Functions of real numbers

Besides the clue stating that at least one is in set 4, there's the old argument that the power-set of an Aleph_n set cannot be Aleph_n itself.

Generalized continuum hypothesis would make 2^Aleph₁ = Aleph_2.

EDIT: That would show all function of real numbers with output 0 and 1 are Aleph₂ . To finish, for each such function f( ) consider g_f (x,y)=1 if y=f(x) and 0 otherwise. This is an injection from functions of real numbers to the powerset of 2-dim space (and 2-dim space is the same cardinal as the 1-space).

I think that "Points in infinite 3-space" is Aleph₅

Edited November 23, 2010 by :-)

[Guest]

Sorry, Araver, you're right.

[araver]

I think that "Points in infinite 3-space" is Aleph₅

Every point in a 1-unit cube in 3-dimensional space is in a 1-to-1 correspondence with a 1-unit segment.

The same interleaving-digits proof described can be used to show just that. Shuffling (a,b,c) to get an unique x.

And from a 1-unit cube in 3D to the whole infinite 3D you can expand in a very very similar way you can expand from a 1-unit segment to a line.

See more

So real numbers and "points in infinite 3-space" share the same Aleph.

... can't really argue with Aleph₅. Only because you might choose to not accept Riemann's Continuum Hypothesis and actually give aleph₅ for real numbers in your own set theory.

To clarify:

- the set of Aleph cardinal numbers covers by definition all possible cardinal numbers. Aleph₀ < Aleph₁<Aleph₂<... and there is no cardinal number between Aleph _n and Aleph _n+1

- the set of Beth cardinal numbers are constructed from natural numbers:

-- Beth₀ is the cardinal number of natural numbers (countable infinity)

-- Beth₁ is the cardinal number of powerset of natural numbers and the set of real numbers (uncountable infinity). Also covers any infinite but finite-dimensional space.

-- Beth₂ is the cardinal number of the powerset of real numbers or the set of functions of real numbers (which is in bonanova's list).

So the numbers in bonanova's list are aleph₀, aleph₁, aleph₂ if and only if one accepts the Generalized continuum hypothesis

Edited November 23, 2010 by araver

[bonanova]

bonanova, is this (curves filling nD objects) what you were thinking about?

Actually I was thinking of the interleaved digits approach.

It demonstrates the 1-1 correspondence most clearly I think.

Even though it is monstrously discontinuous.

Aside: (line segment cardinality = ray cardinality)

I don't have photoshop on this machine, but this is an easy sketch to make.

Draw the point P at (-1, 1)

Draw the unit line segment from (0,1) to the origin.

Rays drawn from P through the line segment give 1-1 correspondences of its points to the points in the ray which is the positive x-axis.

[Guest]

Araver, the Aleph5 was a misprint for Aleph2.

I can't imagine anything that is an Aleph3.

[araver]

I can't imagine anything that is an Aleph3.

Well, powerset of an Aleph_2 :-) E.g. sets of functions of real numbers.

[Guest]

Well, powerset of an Aleph_2 :-) E.g. sets of functions of real numbers.

So, powersets of an Aleph_n is an Aleph_n+1. Is it correct?

[araver]

So, powersets of an Aleph_n is an Aleph_n+1. Is it correct?

It is generally accepted, although strictly not true.

- As I said, Beth numbers are defined like so: powerset of Beth_n is Beth_n+1; Beth_0 is countable infinity (natural numbers).

- Aleph's are defined as "consecutive" cardinal numbers (i.e. there's no cardinal number in between) with Aleph_0=Beth_0 (natural numbers).

If one believes there's nothing between Beth_0 (natural numbers) and Beth_1 (real numbers) then Beth_1 is the next in the sequence so Beth_1=Aleph_1.

But it's not necessarily true. It's called the Continuum Hypothesis and it cannot be proved or disproved by the current accepted set theory (which resembles the set theory we teach since kindergarden).

So, strictly from this point of view, one should use Beth numbers when reasoning with powersets and cardinal numbers.

EDIT: So, my previous post, was again, biased towards accepting the Generalized Continuum Hypothesis (Aleph_n=Beth_n), like bonanova's OP.

Edited November 27, 2010 by araver