Exploring Natural Number-Aleph Zero Correspondence

[cragar]

I was reading in George Gamow's book and he talks about drawing a one-to-one correspondence between the natural numbers and their squares and how these sets have the same size.
But could I take each natural number to $\aleph_{0}$
like $1^{\aleph_0}, 2^{\aleph_0}$ and draw a one-to-one correspondence between these 2 sets? This is probably ill defined or wrong, but just wondering.

 

[Integral]

$\aleph_{0}$ is the cardinality of the natural numbers. I do not believe that you can use it as if it were real.

Any set which can be but into 1 to 1 correspondecne with the natural numbers has cardinality of $\aleph_{0}$

 

[Deveno]

I was reading in George Gamow's book and he talks about drawing a one-to-one correspondence between the natural numbers and their squares and how these sets have the same size.
But could I take each natural number to $\aleph_{0}$
like $1^{\aleph_0}, 2^{\aleph_0}$ and draw a one-to-one correspondence between these 2 sets? This is probably ill defined or wrong, but just wondering.

in set theory, the notation B^A usually means the set of all possible mappings from A to B. the reason for this notation, is that if |A| and |B| are finite:

|B^A| = |B|^|A|.

note that there is only one possible mapping A→1, everything goes to the only possible image.

however, the set of mappings A→{0,1} is equivalent to the power set of A (a in A maps to 1 if a is in a given subset S of A, and 0 if it is not).

in particular: $2^{\aleph_0}$ is uncountable, but $1^{\aleph_0}$ is FINITE (it has cardinality 1).

 

[cragar]

ok interesting, can I ask a side question. If I multiply all the real numbers together do I get one. Multiply all of them except 0. because what ever large number, its reciprocal exists.

 

[Deveno]

ok interesting, can I ask a side question. If I multiply all the real numbers together do I get one. Multiply all of them except 0. because what ever large number, its reciprocal exists.

that depends on "how you multiply them".

infinite products (like infinite sums) only make sense when they converge. if you always pair a real number with its inverse BEFORE you multiply anything else, you will get 1. but if you multiply all the real numbers > 1 FIRST, you'll get a divergent product, and from there, you could wind up with ANYTHING.

see, our notion of "pairing" only works with countable things (at least only works well). there's a LOT of real numbers. there's just as many real numbers between 0 and 1, as there are in the entire set. so "how" you "group" them, is going to affect any potential "product", drastically. in other words, you can re-arrange the groupings, to come up with any desired "product" you like, because there's so many of them, you can always grab a "few infinite more" to compensate.

you can't even say if the "end product" will be positive, or negative (without being very careful about the "grouping").

in the face of uncountably infinite sets, our ordinary intuitions about what happens if we do something with "all" of them, just break down.

you see, each real number is actually an infinite set of rational numbers. it's really a wonder we can add and multiply them at all, because of the difficulties involved.

 

[SteveL27]

I was reading in George Gamow's book and he talks about drawing a one-to-one correspondence between the natural numbers and their squares and how these sets have the same size.
But could I take each natural number to $\aleph_{0}$
like $1^{\aleph_0}, 2^{\aleph_0}$ and draw a one-to-one correspondence between these 2 sets? This is probably ill defined or wrong, but just wondering.

Absolutely. Bearing in mind the meaning of $n^{\aleph_0}$. It denotes the set of functions from the set $\aleph_0$ to the set n.

There is certainly a 1-1 correspondence between the natural numbers {1, 2, 3, ...} and the set {$1^{\aleph_0}, 2^{\aleph_0}$, ... }

In fact even though each of the sets $n^{\aleph_0}$ is an uncountable set (can you prove that? Try it for $2^{\aleph_0}$ with the definition I gave) there are only countably many such sets ... one for each n. You are correct.

 

[cragar]

I was using $2^{\aleph_0}$ as a very large number.
why would a really large number be uncountable?

 

[SteveL27]

I was using $2^{\aleph_0}$ as a very large number.
why would a really large number be uncountable?

$2^{\aleph_0}$ has a very specific meaning in set theory. It's the set of all functions from ${\aleph_0}$ to 2.

Since ${\aleph_0}$ is the set {0, 1, 2, 3, 4, ...}; and the set 2 = {0, 1}; a function from ${\aleph_0}$ to 2 is just a binary sequence. The collection of all binary sequences is uncountable.

That's the only definition of $2^{\aleph_0}$. It is of course "a really large number," but its not a natural number. It's a transfinite number.

 

[cragar]

ok, now that I think of it, isn't $2^{\aleph_0}$ and
$10^{\aleph_0}$ the same thing, so this function would not be one-to-one and onto.

 

[micromass]

ok, now that I think of it, isn't $2^{\aleph_0}$ and
$10^{\aleph_0}$ the same thing, so this function would not be one-to-one and onto.

It can be proven that $2^{\aleph_0}$ and $10^{\aleph_0}$ are indeed equal.

Much of the confusion in this thread comes from the fact that you don't know what $\aleph_0$ really IS. Thinking of it as a really large number is very wrong.

If you have the time, read "Introduction to Set theory" by Hrbacek and Jech.
Or if you don't have that much time: at least read our FAQ on infinity: https://www.physicsforums.com/showthread.php?t=507003
There are 3 parts of the FAQ.

 

[cragar]

how should I think of $\aleph_0}$

 

[micromass]

how should I think of $\aleph_0}$

Did you read the FAQ?? What was not clear about it??

 

[SteveL27]

It can be proven that $2^{\aleph_0}$ and $10^{\aleph_0}$ are indeed equal.

They have equal cardinalities, so if you interpret them as cardinal numbers they are equal.

But as sets they are not equal. For example the function that maps every natural number to 3 is an element of $10^{\aleph_0}$ but not $2^{\aleph_0}$.

There's some ambiguity in the notation $n^{\aleph_0}$. You can interpret it as a set of functions; or you can interpret it as the cardinality of that particular set of functions.

The map that assigns to n the set $n^{\aleph_0}$ is injective; but the map that assigns to n the cardinality $n^{\aleph_0}$ is not injective.

Perhaps I should have been more clear earlier about the distinction.

 

[micromass]

They have equal cardinalities, so if you interpret them via cardinal arithmetic they are equal.

But as sets they are not equal. For example the function that maps every natural number to 3 is an element of $10^{\aleph_0}$ but not $2^{\aleph_0}$.

There's some ambiguity in the notation $n^{\aleph_0}$. You can interpret it as a set of functions; or you can interpret it as the cardinality of that particular set of functions.

The map that assigns to n the set $n^{\aleph_0}$ is injective; but the map that assigns to n the cardinality $n^{\aleph_0}$ is not injective.

Perhaps I should have been more clear earlier about the distinction.

There is no ambiguity. If you write $\aleph_0$, then you obviously mean this as a cardinal number. So obviously cardinal arithmetic applies.
If you want to discuss sets, then you write $2^\mathbb{N}$ and not $2^{\aleph_0}$.
If you want to discuss ordinals, then you write $2^\omega$.

There is no ambiguity.

 

[Char. Limit]

There is no ambiguity. If you write $\aleph_0$, then you obviously mean this as a cardinal number. So obviously cardinal arithmetic applies.
If you want to discuss sets, then you write $2^\mathbb{N}$ and not $2^{\aleph_0}$.
If you want to discuss ordinals, then you write $2^\omega$.

There is no ambiguity.

So what is $2^\omega$ then?

 

[micromass]

So what is $2^\omega$ then?

It is ordinal exponentiation. http://en.wikipedia.org/wiki/Ordinal_arithmetic

We actually have $2^\omega=\omega$.

 

[SteveL27]

There is no ambiguity. If you write $\aleph_0$, then you obviously mean this as a cardinal number. So obviously cardinal arithmetic applies.
If you want to discuss sets, then you write $2^\mathbb{N}$ and not $2^{\aleph_0}$.
If you want to discuss ordinals, then you write $2^\omega$.

There is no ambiguity.

Interesting point. So the notation $A^B$ may mean two different things. If A and B happen to be cardinals, then it means the cardinality of the set of functions from B to A. If A and B happen to not both be cardinals, then it means the set of functions from B to A.

I'd never thought of it that way before; and I've never seen an explicit discussion of this overloading of the set exponentiation operator.

In your opinion is this a generally understood convention? Or is there a formal definition somewhere that set exponentiation has two different meanings depending on whether the arguments are cardinals?

Hmmm ... now it occurs to me that if the arguments are ordinals, then the meaning IS different and I'm aware of that difference ... so I shouldn't have too much trouble accepting the difference between sets of functions and cardinal arithmetic.

 

[micromass]

Interesting point. So the notation $A^B$ may mean two different things. If A and B happen to be cardinals, then it means the cardinality of the set of functions from B to A. If A and B happen to not both be cardinals, then it means the set of functions from B to A.

I'd never thought of it that way before; and I've never seen an explicit discussion of this overloading of the set exponentiation operator.

In your opinion is this a generally understood convention? Or is there a formal definition somewhere that set exponentiation has two different meanings depending on whether the arguments are cardinals?

Hmmm ... now it occurs to me that if the arguments are ordinals, then the meaning IS different and I'm aware of that difference ... so I shouldn't have too much trouble accepting the difference between sets of functions and cardinal arithmetic.

I think it's just a convention that most people are aware of. It's usually clear from the context which convention is used.

 

[jgens]

If you want to discuss sets, then you write $2^\mathbb{N}$ and not $2^{\aleph_0}$

If you want to discuss the set of all mappings $\aleph_1 \rightarrow \{0,1\}$, then how would you suggest to do this using your convention? Your convention rules out $2^{\aleph_1}$ so this seems problematic.

 

[micromass]

If you want to discuss the set of all mappings $\aleph_1 \rightarrow \{0,1\}$, then how would you suggest to do this using your convention? Your convention rules out $2^{\aleph_1}$ so this seems problematic.

Let A be a set of cardinality $\aleph_1$. Look at $2^A$.

That wasn't very hard.

 

[micromass]

If you want to discuss the set of all mappings $\aleph_1 \rightarrow \{0,1\}$, then how would you suggest to do this using your convention? Your convention rules out $2^{\aleph_1}$ so this seems problematic.

Oh wait, I see what you mean. The thing is that you actually don't ever want to do that.

The philosophy of set theory is that a cardinal is an invariant of a set which satisfies: the cardinals of two sets are equal if and only if there is a bijection between the two sets.

How exactly we define the cardinals doesn't matter at all. Using the axiom of choice, we like to define them using ordinals. Without the axiom of choice, but using a foundation axiom, we might define them with the rank function.

The philosophy is that we shouldn't see $\aleph_1$ as a set (although it IS a set) because it can be defined in many equivalent ways.

From set-theoretic point-of-view, we should never want to work with the functions $\aleph_1\rightarrow \{0,1\}$. It always suffices to take a set A of cardinality $\aleph_1$ and look at $2^A$.

 

[cragar]

ok so I should think of $2^{\aleph_0}$ as the set of reals. that's pretty clear.

 

[SteveL27]

ok so I should think of $2^{\aleph_0}$ as the set of reals. that's pretty clear.

Well no, that's the opposite of what micromass said.

When you look at $2^{\aleph_0}$, you should say to yourself: "2 is a cardinal. And $\aleph_0$ is a cardinal. Therefore we are doing cardinal exponentiation. The answer is whatever cardinal $2^{\aleph_0}$ happens to be. [In the presence of the Continuum Hypothesis that's $\aleph_1$; without CH, we have no idea what $2^{\aleph_0}$ is.]

If you wanted the set of binary sequences (which is essentially identical to the set of reals), you would denote that as $2^\mathbb{N}$.

And if you specifically wanted to denote the set of functions from $\aleph_0$ to 2, you would still write $2^{\aleph_0}$, but then you would have to add a note to indicate that you mean the set of functions and not the cardinal. Because micromass certainly convinced me that mathematicians would implicitly apply the convention he described.

Now, my question is regarding the logical status of what in programming would be called operator overloading. An arithmetic operator, namely set exponentiation, has different semantics depending on the data type of the arguments.

My question is, is that legal in terms of set theory? In other words, how would a set theorist (or perhaps logician) convince me that we can still do cardinal exponentiation properly starting from ZFC? I thought that when you define an operator, you can't change its meaning. It seems to me that if your operators can become variables, you are out of the realm of standard logic. I know computer scientists have been thinking about these kinds of things but I'm not familiar with how operator overloading is handled by the theorists.

So: What is the logical status of operator overloading in set theory?