Beyond infinity

[Xerxes]

This thread attempts to address (albeit in a somewhat oblique way) some issues in elementary set theory that have emerged here. I promise you will enjoy it, but first let me freely confess I have posted this elsewhere. I dare say it is against the "rules", but then......

 

Before the fun starts, we have to do a bit of homework.

 

The cardinality of a set is simply its number of elements.

 

If [math]S[/math] is a set, then its powerset [math]\mathcal{P}(S)[/math] is simply the set formed from all its subsets. Thus, bearing in mind that [math]S, \,\,\, \O[/math] are always subsets of [math]S[/math] ([math]\O[/math] is the empty set, btw) then, when [math]S=\{a,b,c\}[/math], we will have that

 

[math]\mathcal{P}(S) = \{\{a\},\{b\},\{c\},\{a,b\},\{a,c\}, \{b,c\}, \{a,b,c\},\O\}[/math].

 

Note that the elements in the powerset are subsets of the set - this will be important. Note also I am abusing notation slightly - I am slightly conflating sets with elements - this is standard. The context is clear enough however, I trust

 

There is a Theorem of Cantor that says that the cardinality of [math]\mathcal{P}(S)[/math] is always strictly greater than the cardinality of [math]S[/math]. Let's see......

 

In the example above, this is not hard to see; the cardinality of [math] S[/math] is 3, that of [math]\mathcal{P}(S)[/math] is [math]8 = 2^3[/math]. In fact, using all available fingers and toes, and those of our wives and girlfriends (assuming they are different), it is not hard to see that, in general, for any set [math]S[/math] of finite cardinality [math]n[/math], then the powerset [math]\mathcal{P}(S)[/math] has cardinality [math]2^n[/math]

 

But what if the cardinality of our set is infinite? What do we make of the assertion, say, that [math]2^{\infty} > \infty[/math]? Surely this is madness?

 

One last thing, of MAJOR importance (sorry for shouting).

 

A set is said to be countable iff it is isomorphic to a subset of the natural (i.e. "counting") numbers [math]\mathbb{N}[/math]. Since, from the above, [math]\mathbb{N}[/math] is always a subset of itself, and is infinite, we have the brain-curdling expression "countably infinite". (That's yet another reason to love mathmen).

 

Let's assume our set [math]S[/math] is countably infinite in this sense.

 

Let's also assume that [math]\mathcal{P}(S)[/math] is countably infinite in the same sense, that is, in accord with intuition, [math] 2^{\infty} = \infty[/math]. We will find a contradiction

 

So, since [math]S[/math] is countable, we can index each and every element by an element of [math]\mathbb{N}[/math] (this is due to our isomorphism). Call the [math]n[/math]-th element [math]s_n \,\,\,\,(n \in \mathbb{N})[/math]. (Note that the choice of ordering is arbitrary, but, having chosen, we had jolly well better stick with it)

 

Assuming that [math]\mathcal{P}(S)[/math] is also countably infinite, then, to each element here we can also assign an index. So let's write a list of these elements (subsets of [math]S[/math], remember) and call the [math]n[/math]-th member of this list as [math]l_n[/math].

 

Now form the set [math]D[/math] by the rule that [math] s_n \in D[/math] iff [math]s_n \in l_n[/math]

 

Now [math]D[/math] is obviously a subset of [math]S[/math], an element in [math]\mathcal{P}(S)[/math], so is eligible to be in our list. Let's call this list element as [math]l_p[/math], so by our rule we have that [math]s_p \in D[/math] iff [math] s_p \in l_p[/math].

 

But hey! [math] l_p = D[/math] so we arrive at the breath-taking conclusion:

 

[math] s_p \in D [/math] iff [math]s_p \in D[/math].

 

 

Wow! Let's write to mother about that. But wait....

 

For every subset in [math]S[/math] (that is every element in [math]\mathcal{P}(S)[/math]) I can find its complement, that is, there is the element in [math]\mathcal{P}(S)[/math] comprising those elements in [math]S[/math] that are not in [math]D[/math] Let's call it as [math]D^c[/math].

 

Under the assumption that our powerset is countable, I can add [math]D^c[/math] to our list, call it the [math]q[/math]-th member, and apply the same rule as before: [math] s_q \in D[/math] iff [math] s_q \in l_q[/math].

 

But [math]l_q = D^c[/math], so we conclude that

 

[math]s_q \in D[/math] iff [math]s_q \not\in D[/math]. This is clearly nuts, so the assumption that the powerset is countable must be false. Cantor's Theorem is thereby proved.

 

 

A really sweet result, wouldn't you say?

Edited January 30, 2011 by Xerxes

[Mr Skeptic]

In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A (the power set of A) has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can be seen to be true by a much simpler proof than that given below, since in addition to subsets of A with just one member, there are others as well, and since n < 2ⁿ for all natural numbers n. But the theorem is true of infinite sets as well. In particular, the power set of a countably infinite set is uncountably infinite. The theorem is named for German mathematician Georg Cantor, who first stated and proved it.

 

It's already been proven, of course.

[Xerxes]

It's already been proven, of course.

Of course, by Cantor himself, whose proof I outlined in the OP.

 

Did my post give the impression I was claiming this proof as mine own? If so, I apologize.

 

Only a madman would do that, as it is one of the most celebrated proofs in all mathematics

[ajb]

Only a madman would do that...

 

And we do get a few passing through this forum.

Edited January 31, 2011 by ajb

[Xerxes]

No shit?

 

Anyway, here's something weird (or wonderful, depending on how you hang) that emerges when you consider different "sizes" of infinity. The idea is not mine, but the execution is, as far as I know.

 

The set of elements that make up an alphabet, as it is commonly understood, is of finite cardinality. In English this cardinality is 26. Let's now assign to the letter A the natural number 10, to B the number 20 etc. and concatenate these numbers to form a word. So that DOG = 4015070 (I use A = 10 rather than A = 1 to remove the ambiguity: is 12 = AB or is 12 =L) If we like, we can chuck in for good measure another 26 elements to capitalize, and another few for spaces and punctuation.

 

We see that there is no word, no sentence, no book, no library, no collection of libraries that cannot be represented as a natural number, however humongous. And by definition, the set of natural numbers is countably infinite.

 

Now any complete theory of the numbers [math]\mathbb{N}[/math] MUST include at least one true statement for each subset of [math]\mathbb{N}[/math].

 

But by Cantor's argument, the set of all subsets of [math]\mathbb{N}[/math] which I called [math]\mathcal{P}(\mathbb{N})[/math] is uncountable, so, by the above, there is no set of words, sentences, books etc (all elements in [math]\mathbb{N}[/math] recall) however large that will allow a true statement to made of each and every subset of the natural numbers. Thus our theory can never be complete

 

This is an example of one of Gödel's incompleteness theorems

[DrRocket]

Now any complete theory of the numbers [math]\mathbb{N}[/math] MUST include at least one true statement for each subset of [math]\mathbb{N}[/math].

 

This is not at all clear and at the very least requires proof.

 

 

 

But by Cantor's argument, the set of all subsets of [math]\mathbb{N}[/math] which I called [math]\mathcal{P}(\mathbb{N})[/math] is uncountable, so, by the above, there is no set of words, sentences, books etc (all elements in [math]\mathbb{N}[/math] recall) however large that will allow a true statement to made of each and every subset of the natural numbers. Thus our theory can never be complete

 

You are making the unwarranted assumption that to each subset there must correspond a unique true statement expressed with a finite number of symbols from your countable set of symbols.

 

This is an example of one of Gödel's incompleteness theorems

 

Yes, but the proof doesn't quite work. There is a reason why Godel's proof is more subtle and complicated. However, he did use a numbering scheme so you are sort of on the right track.

[Xerxes]

Yes, but the proof doesn't quite work. There is a reason why Godel's proof is more subtle and complicated. However, he did use a numbering scheme so you are sort of on the right track.

 

Ya, agreed, but my post was not intended as a "proof", rather some light entertainment. Likewise the entire thread (the clue is in its title!).

[khaled]

I don't suggest playing with the infinity in mathematics .. but you should know something about infinity,

 

when the infinity has a direction it's an ultima, when it doesn't have a direction it's an ultimatum ...

 

means when we means by infinity a huge number uncountable it's an ultimatum, but when we refer

to infinity as the unlimited, the endless number that is always greater than any number then it's an ultima ...

 

ultima a: [math] a > x[/math], where [math]x \in \mathbb{R}[/math]

 

ultimatum b: [math] y > b >> x[/math], where [math]x \in \mathbb{R}[/math] and [math]y \in \mathbb{R}[/math]

 

for any two ultima(s) a and b [math]a = b[/math]

 

for any ultima a, expressions such as [math]C \times a[/math], [math]C + a[/math], .. [math]C^{a}[/math]

will all result in an ultima that is and "endless infinity" which is a constant value that is greater than any,

and any two ultima(s) will be equal because they all refer to the endlessness ...

 

So, if S = { S0, S1, S2, ... } an infinite set, where |S| = infinity, it means that |S| = infinity (endlessness),

and [math]2^{\infty} = \infty[/math] (endlessness) ...

 

it's not mad, and it requires logic ...

 

1000000000..0 ~ this number would be an ultimatum (huge uncountable number)

 

1000000000... ~ this would be an ultima (an endless number)

Edited February 24, 2011 by khaled

[DrRocket]

I don't suggest playing with the infinity in mathematics .. but you should know something about infinity,

 

when the infinity has a direction it's an ultima, when it doesn't have a direction it's an ultimatum ...

 

means when we means by infinity a huge number uncountable it's an ultimatum, but when we refer

to infinity as the unlimited, the endless number that is always greater than any number then it's an ultima ...

 

ultima a: [math] a > x[/math], where [math]x \in \mathbb{R}[/math]

 

ultimatum b: [math] y > b >> x[/math], where [math]x \in \mathbb{R}[/math] and [math]y \in \mathbb{R}[/math]

 

for any two ultima(s) a and b [math]a = b[/math]

 

for any ultima a, expressions such as [math]C \times a[/math], [math]C + a[/math], .. [math]C^{a}[/math]

will all result in an ultima that is and "endless infinity" which is a constant value that is greater than any,

and any two ultima(s) will be equal because they all refer to the endlessness ...

 

So, if S = { S0, S1, S2, ... } an infinite set, where |S| = infinity, it means that |S| = infinity (endlessness),

and [math]2^{\infty} = \infty[/math] (endlessness) ...

 

it's not mad, and it requires logic ...

 

1000000000..0 ~ this number would be an ultimatum (huge uncountable number)

 

1000000000... ~ this would be an ultima (an endless number)

 

This is nonsense.

[khaled]

This is nonsense.

 

define infinity then ...

[DrRocket]

define infinity then ...

 

Read the OP.

 

A set [math] A [/math]is finite if it can be put in 1-1 correspondence with the set [math] S_N = \{ x \in \mathbb N: x \le N \}[/math] for some [math] N \in \mathbb N [/math]. [math]A[/math] is infinite if it is not finite.

 

An equivalent characterization of an infinite set is a set that can be put into 1-1 correspondence with a proper subset of itself.

 

Two sets have the same cardinality if they can be put into 1-1 correspondence. A cardinal number is an equivalence class under this relation. A cardinal number is infinite if any representative of its equivalence class is infinite.

[Xerxes]

khaled: I have made mistakes - even posted nonsense - on more one forum more than once. While embarrassing, it is a forgiveable "offence". But to claim as you did that your gibberish "requires logic" looks like arrogance. Arrogance plus mistakes are not an easy mix to digest. Please don't post if you do not really know what you are talking about.

 

An equivalent characterization of an infinite set is a set that can be put into 1-1 correspondence with a proper subset of itself.

Yes. Readers notice the a here, that is, not any. As I recall this is famous corollary (due to Dedekind?) to an easy thm that states that every set, finite, infinite, countable or otherwise, has a countable proper subset.

 

So let us assume as discussed that the set of all positive integers is countably infinite, and assign a symbol to the cardinality of any set that can be placed in 1-1 correspondence with this set as [math]\aleph_0[/math] (say "aleph-null"). Let's refer to this as the first transfinite cardinal, for want of a better term. So the question arises, what is the next transfinite cardinal? Since we don't yet know (or possibly care) let's call it [math]\aleph_1[/math]. How are these two cardinal numbers related?

 

Now, as shown by Cantor, using an argument identical to the one in the OP, the set [math] \mathbb{R}[/math] of real numbers is uncountably infinite (the term "infinite" is, of course redundant), and let's assign a symbol to its cardinality, say [math]\mathfrak{c}[/math]. Then it can be shown that [math]\mathfrak{c} = 2^{\aleph_0}[/math] as I hinted in the OP.

 

Question: is it truly the case that [math]\mathfrak{c} = \aleph_1 \Rightarrow \aleph_1 =2^{\aleph_0}[/math]? That is, is there or is there not a cardinal that "lies between" [math]\mathfrak{c}[/math] and [math]\aleph_0[/math]? As far as I am aware, nobody knows for sure. Poor old Cantor literally went bonkers trying for a proof of the negative.

 

PS This is the celebrated "continuum hypothesis". Anyone know if it has been proven?

[khaled]

khaled: I have made mistakes - even posted nonsense - on more one forum more than once. While embarrassing, it is a forgiveable "offence". But to claim as you did that your gibberish "requires logic" looks like arrogance. Arrogance plus mistakes are not an easy mix to digest. Please don't post if you do not really know what you are talking about.

 

Yes. Readers notice the a here, that is, not any. As I recall this is famous corollary (due to Dedekind?) to an easy thm that states that every set, finite, infinite, countable or otherwise, has a countable proper subset.

 

So let us assume as discussed that the set of all positive integers is countably infinite, and assign a symbol to the cardinality of any set that can be placed in 1-1 correspondence with this set as [math]\aleph_0[/math] (say "aleph-null"). Let's refer to this as the first transfinite cardinal, for want of a better term. So the question arises, what is the next transfinite cardinal? Since we don't yet know (or possibly care) let's call it [math]\aleph_1[/math]. How are these two cardinal numbers related?

 

Now, as shown by Cantor, using an argument identical to the one in the OP, the set [math] \mathbb{R}[/math] of real numbers is uncountably infinite (the term "infinite" is, of course redundant), and let's assign a symbol to its cardinality, say [math]\mathfrak{c}[/math]. Then it can be shown that [math]\mathfrak{c} = 2^{\aleph_0}[/math] as I hinted in the OP.

 

Question: is it truly the case that [math]\mathfrak{c} = \aleph_1 \Rightarrow \aleph_1 =2^{\aleph_0}[/math]? That is, is there or is there not a cardinal that "lies between" [math]\mathfrak{c}[/math] and [math]\aleph_0[/math]? As far as I am aware, nobody knows for sure. Poor old Cantor literally went bonkers trying for a proof of the negative.

 

PS This is the celebrated "continuum hypothesis". Anyone know if it has been proven?

 

I never write something I do not fully understand,

 

But what if the cardinality of our set is infinite? What do we make of the assertion, say, that ? Surely this is madness?

 

I was saying that if you make a power set of an infinite set you get another infinite set, but in a higher degree ...

 

we only can address the difference in degree, but both are infinite to us ...

 

Sorry about my "gebbrish" ...

[DrRocket]

 

PS This is the celebrated "continuum hypothesis". Anyone know if it has been proven?

 

 

Paul Cohen proved that the Continuum Hypothesis is independet of the Zermelo-Fraenkel axioms plus the Axiom of Choice.

[Trestone]

Hello,

the results of Cantor and Gödel are astonishing.

But we still can ask, what we can do to avoid the consequences
(and perhaps expulse some mathematicans from Hilbert`s paradise).

As physics has showed us with time, space and matter,
a small change in basic concepts may alter a lot.

In mathematics we have the complex numbers that show
how to solve unsolvable equations like x*x= -1.

As (classical) logic is used in the proofs of Cantor and Gödel,
I looked for alterations in logic,
that would influence these proofs and give us other results.

As I always was doubtful to indirect proofs (where there are two branches),
I experimented with different “views” in logic,
where every “view” has its own truth value for a proposition.
(For example “the liar” is “true” from view1 and false “from” view2).

Later I called the views “layers” and used (inductive) natural numbers t = 0,1,2,3,…

Now a proposition or statement is not longer “true” (ex-)or false”,
but has a truth value only in combination with a layer t,
and the truth values in different layers can be different.

The layers have some hierarchical order,
but the whole is quite different to the “Hierarchy o Types” by Russel,
as self reference is fully allowed.

Of course this is not classic logic any more,
but it has nice effects to set theory:

In Cantor`s diagonalization proof we can see, that different layers are implied
and therefore there is no contradiction.

We therefore need no different kinds of infinity,
the “set of all sets” is without paradoxes (and is its own powerset),
even “Russell´s set” is existing witout contradiction.

We even need less axioms than ZFC to form a set theory.

More Details are in the neighbouring thread:

 

http://www.scienceforums.net/topic/59914-layer-logic-a-new-dimension/

 

The Peano axioms and an arithmetic can be defined with layer logic
(but the uniqness of the prime factorization might not hold),
I suppose that Gödels proof for incompletness does not hold for layer logic and layer set theory,
but beeing no professional mathematican I did not look deeply up to now.

Perhaps someone might do this? (And formalize my more intuitive settings).

Yours
Trestone

Edited August 16, 2013 by Trestone

[HalfWit]

The cardinality of a set is simply its number of elements.

 

 

 

I seem to remember this essay from somewhere else. I see you haven't taken the trouble to improve it. But you should.

 

The above statement is unsupportable. First, it only applies to finite sets. Secondly, if you are building up math from first principles, sets are logically prior to numbers. So I don't know what you mean by "number of elements."

 

If you are going to take the trouble to lay out an overview of set theory for general readers, the least you could do is try for a bit of accuracy. You can't say that cardinality is a "number" without saying what you mean by number; and you can't then start waving your hands at the cardinality of infinite sets, having given a misleading and incorrect definition of cardinality in the first place.

 

I remember being annoyed by these problems the first time I read this, and your repeating it doesn't make it any better. People who take the trouble to lay out general purpose overviews of technical subjects have a responsibility to try to be accurate within the limits of understandability. Making a false statement early on and then introducing additional confusion based on your faulty statement is poor pedagogy.

 

Why not rewrite your essay based on the well-understood and accepted notion of one-to-one correspondence? That is both accurate math and good pedagogy. What you have here is neither.

Edited August 19, 2013 by HalfWit

[nellythedog]

Could you explain the bit about Godel's theorem of incompleteness?

[Someguy1]

Could you explain the bit about Godel's theorem of incompleteness?

 

Xerxes' reference was nonsense, as is most of his clever-sounding but incorrect exposition. DrRocket already made this point in post #6 above.

 

Also note that this is a three year old thread.

 

You'd be far better off just looking these topics up on Wikipedia and then asking specific questions.

Edited May 1, 2014 by Someguy1