20 replies to this topic

[mmiguel]

choice

Spoiler for

It is an axiom - the axiom of choice (well... maybe it is)...!

Here is my attempt at connecting the two ideas.

http://en.wikipedia....Axiom_of_choice
Here is a variant:
"Given any set X of pairwise disjoint non-empty sets, there exists at least one set C that contains exactly one element in common with each of the sets in X."

Treating a triplet of digits at positions (k,k+1,k+2) for k = floor(n/3)+1 (where the 10^0 decimal is at position 0) in bushindo's e as the C above and X as the set containing the nth digits of x,y, and z, the axiom of choice guarantees bushindo's construction exists.

I'm not sure how to prove that if the axiom of choice is not taken, that bushindo's construction cannot certainly be constructed... so maybe i am wrong here.
i am assuming ordered sets (tuples), so that is slightly different than the statement of the axioms of choice i have.
but if i am right, then the title of this thread is actually relevant



http://en.wikipedia....ki/Ordered_pair

"In 1921 Kazimierz Kuratowski offered the now-accepted definition^[4] of the ordered pair (a, b): "

let x be the set of ordered pairs (v,n) where n is an integer indicating the position of a digit, and v is the digit itself.

an ordered triplet (a,b,c) can be defined as (a,(b,c)) = {{a},{a,(b,c)}} = {{a},{a,{{b},{b,c}}}}

so given n, to construct the triplet C_n = (x_n,y_n,z_n) = {{x_n},{x_n,{{y_n},{y_n,z_n}}}}, we must be able to select:
{{x_n},{x_n,n}} from x
{{y_n},{y_n,n}} from y
{{z_n},{z_n,n}} from z

i.e. elements from x,y,z where the second value in the ordered pair equals n.
by the way we have defined things, such an element must always exist for x,y, and z and any n, so i don't see why we wouldn't be able to select it.
the only time i have seen (in my limited experience) where the axiom of choice actually plays a useful role is when there is some sort of indistinguishability between multiple things, and the axiom of choice kicks in to say, even though these things are indistinguishable, you can still pick one.

by the way we defined this, i don't see any indistinguishability.
we could even guarantee that x,y, and z distinguishable, by making them ordered pairs themselves and putting some identifier (e.g. 1 for x, 2 for y, 3 for z) as the first element of the ordered pair, and then previously described countably infinite set of natural numbers as the second element of the pair.

so maybe the axiom of choice doesn't apply here....

on the other hand... the AC is equivalent to the well-ordering theorem in first order logic, and perhaps we somehow implicitly assumed that in our construction of these real numbers.

i think i've probably reached the limit in what i know about this topic (as well as the limit of the time i have to spend on this tonight), so hopefully someone else can step in and show the light.

Edited by mmiguel, 18 October 2012 - 05:08 AM.

[EventHorizon]

Spoiler for A few more thoughts

Let Z be the set of all integers and Q be the rationals. We know that |Z| = |Q| and that |Q|-|Z| is undefined since |Q| and |Z| are both infinity. But isn't it true that Q contains more than just integers? Since Q is a superset of Z and the extra elements of the set Q are still numbers, can't it be said Q contains more numbers than the numbers contained in the set Z... even though the cardinality of the sets are equal?

In other words the number of elements in each is the same, and yet one set contains more elements in addition to those contained in the other.



Let C be the set of points in the cube.
Let E be the set of points in the edge.

We know |C| = |E|. I've shown they're the same degree of infinity and others have given one-to-one mappings. So we know the number of points in each is the same. But does that necessarily mean one doesn't contain more points than are contained in the other?

We know |C| - |E| is undefined since both |C| and |E| are infinity. However, |C-E| is infinity. So if we wait to abstract away the actual sets, we can have an answer that isn't just undefined.


So I guess what I'm saying is that if the question was "is the number of points in the cube greater than the number of points in the edge", the answer would be no since both are infinity. But if the question isn't outright asking about the cardinalities and comparing their values, it could be different. If it is only asking about the points not contained in the edge, then the answer is yes. We have the sets and know their difference. So we know what points are contained in the cube in addition to those contained in the specified edge.

So just like I would say Q contains more than just the numbers contained in Z (even though they both contain the same number of numbers), the cube contains more points in addition to those contained in the edge.


So, yes, we all agree the cardinality is the same. The question now is whether the original question is asking "|C|>|E|" or "|C-E|>0?"

"Does the cube contain a greater quantity of points than the quantity contained in one of its edges?" - Answer: No.
"Does the cube contain more points than the quantity of points contained in one of its edges?" - Answer: No.
"Does the cube contain more points than just those points contained in one of its edges?" - Answer: Yes.
"Does the cube contain extra points in addition to those contained in one of its edges?" - Answer: Yes.
"Does a cube contain more points than those contained in one of its edges?" - I'd still answer yes.

Actual question: "Does a cube contain more points than are contained in one of its edges?"

It does sound slightly vague to me as to which it is asking, but I'm still leaning towards the latter interpretation (ie, answer is yes).

I'm sure if I ask bonanova which interpretation he meant... he'll say "I can't or I won't say."

[bonanova]

Spoiler for A few more thoughts

Let Z be the set of all integers and Q be the rationals. We know that |Z| = |Q| and that |Q|-|Z| is undefined since |Q| and |Z| are both infinity. But isn't it true that Q contains more than just integers? Since Q is a superset of Z and the extra elements of the set Q are still numbers, can't it be said Q contains more numbers than the numbers contained in the set Z... even though the cardinality of the sets are equal?

In other words the number of elements in each is the same, and yet one set contains more elements in addition to those contained in the other.



Let C be the set of points in the cube.
Let E be the set of points in the edge.

We know |C| = |E|. I've shown they're the same degree of infinity and others have given one-to-one mappings. So we know the number of points in each is the same. But does that necessarily mean one doesn't contain more points than are contained in the other?

We know |C| - |E| is undefined since both |C| and |E| are infinity. However, |C-E| is infinity. So if we wait to abstract away the actual sets, we can have an answer that isn't just undefined.


So I guess what I'm saying is that if the question was "is the number of points in the cube greater than the number of points in the edge", the answer would be no since both are infinity. But if the question isn't outright asking about the cardinalities and comparing their values, it could be different. If it is only asking about the points not contained in the edge, then the answer is yes. We have the sets and know their difference. So we know what points are contained in the cube in addition to those contained in the specified edge.

So just like I would say Q contains more than just the numbers contained in Z (even though they both contain the same number of numbers), the cube contains more points in addition to those contained in the edge.


So, yes, we all agree the cardinality is the same. The question now is whether the original question is asking "|C|>|E|" or "|C-E|>0?"

"Does the cube contain a greater quantity of points than the quantity contained in one of its edges?" - Answer: No.
"Does the cube contain more points than the quantity of points contained in one of its edges?" - Answer: No.
"Does the cube contain more points than just those points contained in one of its edges?" - Answer: Yes.
"Does the cube contain extra points in addition to those contained in one of its edges?" - Answer: Yes.
"Does a cube contain more points than those contained in one of its edges?" - I'd still answer yes.

Actual question: "Does a cube contain more points than are contained in one of its edges?"

It does sound slightly vague to me as to which it is asking, but I'm still leaning towards the latter interpretation (ie, answer is yes).

I'm sure if I ask bonanova which interpretation he meant... he'll say "I can't or I won't say."

Spoiler for I would say

If extra, or better, other, were used in OP, the answer would be Yes.
But with more, as in OP, the answer is No.

But it's best to say the points in the cube and its edge have the same cardinality. That gets us off the hook a little, because cardinality is a well behaved algebraic number only for finite sets. For infinite sets, Aleph0, Aleph1, Aleph2, are symbols that are not like algebraic symbols. Specifically, they are invariant to addition, multiplication, squaring, cubing ...

Aleph1 == Aleph1 + 1 == Aleph1 x Aleph1 == ... And so forth.

That's why asking questions about the Alephs that include words like "more than" lead to counterintuitive results.

But 2^Aleph1 == Aleph2.

That is, the set of all subsets [power set] of an infinite set jumps up to the next higher cardinality. The proof that the elements of any set can not be paired 1-1 with the elements of its power set is both simple and elegant.

Cantor [can't or] originally thought Aleph1 x Aleph1 would lead to Aleph2. That is, the points in a plane would have next higher cardinality than the points in a line. And a cube would have the next higher cardinality than the plane. And so on.

But when he tried to show this, he instead proved all three cardinalities were the same. Much to his surprise, and now to ours.

So the point of this puzzle was to pause and wonder at the result that adding and multiplying, squaring or cubing do not affect the cardinality of infinite sets.

And that result can be shown, as Bushindo did, by finding a bijection between the cube and an edge.

[mmiguel]

Spoiler for I would say

If extra, or better, other, were used in OP, the answer would be Yes.
But with more, as in OP, the answer is No.

But it's best to say the points in the cube and its edge have the same cardinality. That gets us off the hook a little, because cardinality is a well behaved algebraic number only for finite sets. For infinite sets, Aleph0, Aleph1, Aleph2, are symbols that are not like algebraic symbols. Specifically, they are invariant to addition, multiplication, squaring, cubing ...

Aleph1 == Aleph1 + 1 == Aleph1 x Aleph1 == ... And so forth.

That's why asking questions about the Alephs that include words like "more than" lead to counterintuitive results.

But 2^Aleph1 == Aleph2.

That is, the set of all subsets [power set] of an infinite set jumps up to the next higher cardinality. The proof that the elements of any set can not be paired 1-1 with the elements of its power set is both simple and elegant.

Cantor [can't or] originally thought Aleph1 x Aleph1 would lead to Aleph2. That is, the points in a plane would have next higher cardinality than the points in a line. And a cube would have the next higher cardinality than the plane. And so on.

But when he tried to show this, he instead proved all three cardinalities were the same. Much to his surprise, and now to ours.

So the point of this puzzle was to pause and wonder at the result that adding and multiplying, squaring or cubing do not affect the cardinality of infinite sets.

And that result can be shown, as Bushindo did, by finding a bijection between the cube and an edge.

Spoiler for cool

using bushindo's method, we can represent n real numbers (a vector) using a single real number for any finite n.
each element of such a vector is also a real number, and can therefore represent another vector of real numbers.
following along these lines, any real tensor can be uniquely mapped to a single real number.

a single real number, therefore has the same level of complexity as a 100 by 100 by 100 tensor of arbitrary real numbers (i.e. they can be used interchangeably to communicate the same thing).

practically any set of data one could ever want to use or interact with, regardless of how large, could be encoded as a single numerical position on a number line (with higher precision required for more info).

forget about achilles passing the tortoise... what about when he passes the point on the racetrack whose real position contains all of the data in his genetic makeup under an encoding scheme like the one bushindo showed?
that is far more interesting!

[EventHorizon]

Spoiler for I would say

If extra, or better, other, were used in OP, the answer would be Yes.
But with more, as in OP, the answer is No.

But it's best to say the points in the cube and its edge have the same cardinality. That gets us off the hook a little, because cardinality is a well behaved algebraic number only for finite sets. For infinite sets, Aleph0, Aleph1, Aleph2, are symbols that are not like algebraic symbols. Specifically, they are invariant to addition, multiplication, squaring, cubing ...

Aleph1 == Aleph1 + 1 == Aleph1 x Aleph1 == ... And so forth.

That's why asking questions about the Alephs that include words like "more than" lead to counterintuitive results.

But 2^Aleph1 == Aleph2.

That is, the set of all subsets [power set] of an infinite set jumps up to the next higher cardinality. The proof that the elements of any set can not be paired 1-1 with the elements of its power set is both simple and elegant.

Cantor [can't or] originally thought Aleph1 x Aleph1 would lead to Aleph2. That is, the points in a plane would have next higher cardinality than the points in a line. And a cube would have the next higher cardinality than the plane. And so on.

But when he tried to show this, he instead proved all three cardinalities were the same. Much to his surprise, and now to ours.

So the point of this puzzle was to pause and wonder at the result that adding and multiplying, squaring or cubing do not affect the cardinality of infinite sets.

And that result can be shown, as Bushindo did, by finding a bijection between the cube and an edge.

Spoiler for Extra thoughts

One point I omitted to state outright (but meant to include) was that English (and spoken language in general) is quite subjective.

For instance, looking up "more" in the dictionary gives one definition as being "additional or further." Extra's definition sounds just like that ("beyond or more than what is usual, expected, or necessary; additional"). So I still think the question vague (if only because it is in English), and it seems I was mistaken when I thought it intentionally vague.



Also, even though it is commonplace nowadays and I'm positive I've done it before, I intentionally didn't call the cardinality of the set of reals Aleph₁ due to the generalized continuum hypothesis being unproven (unprovable with common set theory, and some have even said it is not well defined so it has no truth value).



I did point out that (2^Aleph₀)³ = 2^(Aleph₀*3) = 2^Aleph₀.
And hinted that, where n is a positive number, n^Aleph₀ = (2^{log₂ n})^Aleph₀ = 2^{(Aleph₀*log₂ n)} = 2^Aleph₀.
Since Aleph_n = Aleph_n * Aleph_n for all non-negative integer n, the same could be done for any Aleph_n.

This means, assuming GCH, that Aleph_n raised to any non-zero finite number is Aleph_n and any positive finite number raised to Aleph_n is Aleph_n+1. What is Aleph_n^Aleph_n? Since x^x grows similarly to x!, is Aleph_n! the same as Aleph_n^Aleph_n?

And is any of this math useful/valid/defined or does working with infinities mean you cannot use it so bijections are absolutely necessary?

[bonanova]

Spoiler for Extra thoughts

One point I omitted to state outright (but meant to include) was that English (and spoken language in general) is quite subjective.

For instance, looking up "more" in the dictionary gives one definition as being "additional or further." Extra's definition sounds just like that ("beyond or more than what is usual, expected, or necessary; additional"). So I still think the question vague (if only because it is in English), and it seems I was mistaken when I thought it intentionally vague.



Also, even though it is commonplace nowadays and I'm positive I've done it before, I intentionally didn't call the cardinality of the set of reals Aleph₁ due to the generalized continuum hypothesis being unproven (unprovable with common set theory, and some have even said it is not well defined so it has no truth value).



I did point out that (2^Aleph₀)³ = 2^(Aleph₀*3) = 2^Aleph₀.
And hinted that, where n is a positive number, n^Aleph₀ = (2^{log₂ n})^Aleph₀ = 2^{(Aleph₀*log₂ n)} = 2^Aleph₀.
Since Aleph_n = Aleph_n * Aleph_n for all non-negative integer n, the same could be done for any Aleph_n.

This means, assuming GCH, that Aleph_n raised to any non-zero finite number is Aleph_n and any positive finite number raised to Aleph_n is Aleph_n+1. What is Aleph_n^Aleph_n? Since x^x grows similarly to x!, is Aleph_n! the same as Aleph_n^Aleph_n?

And is any of this math useful/valid/defined or does working with infinities mean you cannot use it so bijections are absolutely necessary?

Well we've finished the discussion of the puzzle so I won't spoiler this. You made several points and raised new questions. I'll try to reply to the extent that I know.

Inarguably the cube contains points that its edge does not. For finite sets that gives a Yes answer. For infinite sets, and these sets are uncountable, we express size by cardinality. The edge has the cardinality of the reals, so the question really asks the cardinality of the cube. Bushindo's bijection expresses Cantor's finding that geometric figures of all dimensions, arbitrarily large ones, have the cardinality of the reals.

So the cube has other points, but not more points.

The power set is the set of all subsets. Is there a bijection between the elements of a set and the elements of its power set? The answer is No, and so the cardinality of the power set is greater than the cardinality of the set. For finite sets, it can be seen by inspection. The set {1,2,3} has 2³ = 8 subsets, including the empty set. No bijection exists. For infinite sets, the proof is almost as simple. It's a proof by contradiction. Suppose the elements of an infinite set have been paired with the elements of its power set. We then color the set's elements blue that are paired with a subset that contains the element, and red if they are not a member of their paired subset. Now consider the element of the set that is paired with the subset of all the red colored elements. Can it be red? No, because red elements are paired with subsets that do not contain them. Can it be blue? No, because blue elements are paired with subsets that do contain them. So the subset of all red elements cannot be paired, and this contradict the premise of a bijection.

So power sets have increasing cardinalities.

We know the integers are countably infinite, and the reals are not; and we have an understanding of both these sets. Do we have an understanding of a set that has cardinality Aleph2? One such set is the set of all functions of real numbers. Or of all curves in a plane. No one has suggested a set of cardinality Aleph3 other than the power set of the functions of a real number.

What is Aleph_n^Aleph_n? I would say it lacks any recognizable similarity with a power set or a real number raised to the power Alpha_n because the infinite cardinals are not algebraic. So it's a symbol raised to its own power. What value or significance we could thus assign to it I do not know.

[EventHorizon]

What things can I include in this post more than are contained in my previous posts?

Notice I used more in the sense of other, extra, additional, etc. We agree, except I'm harping on the various definitions of more.

Just wait until I start arguing over what the definition of is is...

I've seen those examples of sets of various degrees of infinity, and have had to come up with various bijections including them. But it doesn't say whether bijections are always necessary or if math can be used instead. Perhaps in these cases the symbolic math is just shorthand for the bijections already given. But that seems to be the way with math in general... operators are defined by previously defined operators and/or algorithms including other previously defined operators.

Spoiler for Assuming we can assign significance to a symbol raised to its own power... + realization that it can!

Aleph₀! = Aleph₀ * (Aleph₀-1) * ... * 1. Since Aleph₀ = Aleph₀ * Aleph₀, the limit seems to be Aleph₀.
But if you replace those all with 2's... it is equal to Aleph₁.

Aleph₀^Aleph₀ = x ... you'd expect it to be >= Aleph₁ since 2^Aleph₀=Aleph₁ (assuming GCH).
log(Aleph₀^Aleph₀) = log(x) ...ignoring the question of what that means.
Aleph₀ * log(Aleph₀) = log(x) ...log seems to subtract 1 from the aleph number... what is Aleph_-1?
Aleph₀ = log(x)
e^Aleph₀ = x
Aleph₁ = x = Aleph₀^Aleph₀

Since 2^Aleph₀ <= Aleph₀! <= Aleph₀^Aleph₀ and 2^Aleph₀ = Aleph₀^Aleph₀, 2^Aleph₀ = Aleph₀! = Aleph₀^Aleph₀.



SUM_i=1^Aleph₀ 0 = 0 ...additive identity
SUM_i=1^Aleph₀ 1 = Aleph₀ ...could use anything greater than the additive identity.
SUM_i=1^Aleph₀ i = Aleph₀
SUM_i=1^Aleph₀ Aleph₀ = Aleph₀ ....since Aleph₀ = Aleph₀ * Aleph₀

PROD_i=1^Aleph₀ 1 = 1 ...multiplicative identity
PROD_i=1^Aleph₀ 2 = Aleph₁ ...could use anything greater than the multiplicative identity.
PROD_i=1^Aleph₀ i = Aleph₀! = Aleph₁
PROD_i=1^Aleph₀ Aleph₀ = Aleph₀^Aleph₀ = Aleph₁

Makes perfect non-sense to me

....

Actually, if you have multiplication representing a cross product of sets (ie, all possible tuples... and the obvious/common/correct interpretation when applied to sets), then Aleph₀^Aleph₀ is the set of infinite length tuples whose elements are any integer (wlog, i'll say positive integers... easier for the bijection).

(Edit: could also interpret it as the set of all multisets of a countable set. Instead of included or not, it is how many are included.)

If the integers that are the tuple elements were bounded, it would obviously be the same cardinality as the reals (represented in the base number of the bound).

A bijection between the reals and this set would be the following.
Let the reals be given in binary.
Two 0's in a row is a sentry marking the end of the current segment.
For a 1, list a '1'. For a 0, list a '01'.
Each segment represents an integer in the infinite length tuple.
All of the set of infinite tuples are covered and the reals between 0 and 1 are used to map onto (so '0.' whatever is needed for the matching infinite length tuple).

Spoiler for example

The tuple is [1,2,3,4,5,6,7,...]
The real is 0.(1)00(101)00(11)00(10101)00(1011)00(1101)00(111)00... with the integers from the tuple marked in parenthesis.

So, assuming GCH, Aleph₀^Aleph₀ = Aleph₁ after all

[mmiguel]

So the cube has other points, but not more points.

I don't think we can say the the same about the edge with respect to the cube:
The edge does not have other points than those contained in the cube.

Do you agree?

The subset operator would still show asymetry here.
The less-than operator would not show asymmetry between the cardinalities of the two sets.

Our intuition tells us, if A is a strict subset of B, then |A| < |B|.
Our conclusion from this discussion is that this transformation, from a statement of sets, to a statement of cardinalities, does not hold when sets are infinite.

Is there some other commonly accepted mathematical construct, e.g. denoted for set A by [A], that evaluates to a number, such that if A is a strict subset of B, then [A] < [B] even for infinite sets?

Edited by mmiguel, 21 October 2012 - 04:20 AM.

[mmiguel]

I don't think we can say the the same about the edge with respect to the cube:
The edge does not have other points than those contained in the cube.

Do you agree?

The subset operator would still show asymetry here.
The less-than operator would not show asymmetry  between the cardinalities of the two sets.

Our intuition tells us, if A is a strict subset of B, then |A| < |B|.
Our conclusion from this discussion is that this transformation, from a statement of sets, to a statement of cardinalities, does not hold when sets are infinite.

Is there some other commonly accepted mathematical construct, e.g. denoted for set A by [A], that evaluates to a number, such that if A is a strict subset of B, then [A] < [B] even for infinite sets?

One more requirement for [A]: for finite sets, [A] = |A|

[mmiguel]

One more requirement for [A]: for finite sets, [A] = |A|

One more requirement:

If A is the real interval [0,1], and B = [0,0.5) U (0.5,1] U {2}
Then [A] = [B]

B is the same as A, except that 0.5 is removed, and 2 is added.
B is no longer a subset of A, but from an intuitive perspective should have the same "quantity of points".