Thread: Uncountbility: can be thought of as "layers" of countability?

Over on physicsforums we were discussing the different types of infinity. I only knew of uncountable and countable before this discussion and learned a lot, but I want to know if any of you can relate to how I've come to view uncountable sets of higher order. Our discussion stemmed from the idea that P(N) (I am using this to denote the power set of the natural numbers) is uncountable. A proof was provided but being new to the topic it wasn't something that I could quite "aha!" at.

However, upon truly thinking about P(N), I see clearly that it must be the case that is uncountable, by, well, trying to count it.

I thought of different ways to try to count the members of P(N) but they all are equivalent, I think this is my favorite method:

Consider the members of P(N) that is not N (proper subsets) and is not the empty set.

There are two qualities that these member (sets) have:

1.) Their cardinality
2.) Their elements

We will attempt to count the member of P(N) in the following way:

1.) Choose a cardinality to start with
2.) List all possible sets with that cardinality
3.) Move to the next cardinality, repeat


Immediately it becomes clear that as a whole, this cannot be counted. The reason for this is that their are countably infinite choices of set size, and countably infinite choices for the elements of that set. Therefore "counting" to the next set size can never be done because it is already a countably infinite process to list the possible elements of a specific set size. I am "stuck" at whatever set size I choose to start at, because their are countably infinite elements to consider for that set.

I further realized that this is the exact same concept as trying to count the real numbers. I am "stuck" at whatever real number I choose to start at because their are countably infinite decimal places to consider before the "next" one comes. The next one in fact doesn't exist.
_______________

This leads me to conceptually think of something that is uncountably infinite (aleph-1) as 2 "layers." What I mean by that is that attempting to "count" requires you to attempt count a "substep" first, and that substep is countably infinite, so the attempt to count as a whole is in vain.

Considering P(R) in the same way, this would be 3 layers of countability.

Since P(R) contains all subsets of R, as before, the subsets can be of any size.

So there are countably infinite choices of set size. However, since R is uncountable, there are uncountably many choices of elements, as opposed to the elements of the members of P(N). Following the idea that the real numbers contain 2 "layers" of countability, this would make P(R) 3 "layers" - the "layer" of set size, then the 1st "layer" of the reals, then the second "layer" of the reals.

Attempting to count from one member of P(R) to the next (1st layer) requires attempting to count something else (2nd layer), of which requires to attempt to count something else (3rd layer) that is infinite. So not only can you not count, but you can't even count a "substep", you can only count the substep of a substep, and this process in itself is infinite.



So in short, my view of the different types of infinite sets is that for any attribute of the members of this set that is countable, it is always a subsubsubsub....substep of counting the actual objects themselves, and in itself is infinite, with the number of "subs" I wrote there being equal to the aleph number of the set. (I should also mention that what we consider a step and substep is arbitrary, there is no reason why I can't "first" consider the elements of a member of P(N) and then the cardinality, it just doesn't feel as natural)

Can anyone relate to this thinking?

Keep in mind it IS 4:40 AM :P

Originally Posted by OneMileCrash

Over on physicsforums we were discussing the different types of infinity. I only knew of uncountable and countable before this discussion and learned a lot, but I want to know if any of you can relate to how I've come to view uncountable sets of higher order. Our discussion stemmed from the idea that P(N) (I am using this to denote the power set of the natural numbers) is uncountable. A proof was provided but being new to the topic it wasn't something that I could quite "aha!" at.

However, upon truly thinking about P(N), I see clearly that it must be the case that is uncountable, by, well, trying to count it.

I thought of different ways to try to count the members of P(N) but they all are equivalent, I think this is my favorite method:

Consider the members of P(N) that is not N (proper subsets) and is not the empty set.

There are two qualities that these member (sets) have:

1.) Their cardinality
2.) Their elements

We will attempt to count the member of P(N) in the following way:

1.) Choose a cardinality to start with
2.) List all possible sets with that cardinality
3.) Move to the next cardinality, repeat


Immediately it becomes clear that as a whole, this cannot be counted. The reason for this is that their are countably infinite choices of set size, and countably infinite choices for the elements of that set. Therefore "counting" to the next set size can never be done because it is already a countably infinite process to list the possible elements of a specific set size. I am "stuck" at whatever set size I choose to start at, because their are countably infinite elements to consider for that set.

I further realized that this is the exact same concept as trying to count the real numbers. I am "stuck" at whatever real number I choose to start at because their are countably infinite decimal places to consider before the "next" one comes. The next one in fact doesn't exist.
_______________

This leads me to conceptually think of something that is uncountably infinite (aleph-1) as 2 "layers." What I mean by that is that attempting to "count" requires you to attempt count a "substep" first, and that substep is countably infinite, so the attempt to count as a whole is in vain.

Considering P(R) in the same way, this would be 3 layers of countability.

Since P(R) contains all subsets of R, as before, the subsets can be of any size.

So there are countably infinite choices of set size. However, since R is uncountable, there are uncountably many choices of elements, as opposed to the elements of the members of P(N). Following the idea that the real numbers contain 2 "layers" of countability, this would make P(R) 3 "layers" - the "layer" of set size, then the 1st "layer" of the reals, then the second "layer" of the reals.

Attempting to count from one member of P(R) to the next (1st layer) requires attempting to count something else (2nd layer), of which requires to attempt to count something else (3rd layer) that is infinite. So not only can you not count, but you can't even count a "substep", you can only count the substep of a substep, and this process in itself is infinite.



So in short, my view of the different types of infinite sets is that for any attribute of the members of this set that is countable, it is always a subsubsubsub....substep of counting the actual objects themselves, and in itself is infinite, with the number of "subs" I wrote there being equal to the aleph number of the set. (I should also mention that what we consider a step and substep is arbitrary, there is no reason why I can't "first" consider the elements of a member of P(N) and then the cardinality, it just doesn't feel as natural)

Can anyone relate to this thinking?

Keep in mind it IS 4:40 AM :P

A countable union of countable sets is countable.

Originally Posted by zzephod

A countable union of countable sets is countable.

Who is talking about unions?

Originally Posted by OneMileCrash

Who is talking about unions?

My mistake.

You might want to consider what happens at step 2 when the cardinality is

.

.

Yes, because you are describing a subset of an uncountable set.

What I'm saying is that say you have a countable set

{A1, A2, A3,....}

And for each element, there corresponds another countable set

{A1B1, A1B2, A1B3,...}

The set of all AnBk is uncountable. Thus "layers" of countable sets.

Originally Posted by zzephod

My mistake.

You might want to consider what happens at step 2 when the cardinality is

.

.

Those steps are for counting the elements of P(N) which is aleph one. Wwhy would you need steps to count something that is aleph 0 (countable)?

Just bumping this over the spam