# Continuity and uncountability

## Recommended Posts

Analysis of the proof of Cantor's theorem
Cantor's theorem states that the power set of ℕ is uncountable. This article carefully analyzes this proof to clarify its logical reasoning

##### Share on other sites

Testing latex - nothing to do with posts.

Edited by mathematic
testing

##### Share on other sites
On 9/16/2018 at 4:51 AM, pengkuan said:

Analysis of the proof of Cantor's theorem
Cantor's theorem states that the power set of ℕ is uncountable. This article carefully analyzes this proof to clarify its logical reasoning

I don't particularly need to read that article, since I know this proof very well and can reproduce it at will. It's so beautiful. One of my favorite proofs.

What I think is missing here is evidence that YOU understand the proof. I know you can link it, but you haven't convinced me that you appreciate it. Until you say, "Aha line n of the proof is wrong because ..." you will have no credibility with me.

Edited by wtf

##### Share on other sites
18 hours ago, wtf said:

I don't particularly need to read that article, since I know this proof very well and can reproduce it at will. It's so beautiful. One of my favorite proofs.

What I think is missing here is evidence that YOU understand the proof. I know you can link it, but you haven't convinced me that you appreciate it. Until you say, "Aha line n of the proof is wrong because ..." you will have no credibility with me.

The proof is correct. But the premise is apparently wrong. The theorem states: the power set of ℕ etc.

Does the power set of ℕ exist at all? If it exists, its cardinality would be aleph 1. But the existence of cardinality aleph 1 is proved by the uncountability of the power set of ℕ.

##### Share on other sites
6 minutes ago, pengkuan said:

The proof is correct. But the premise is apparently wrong. The theorem states: the power set of ℕ etc.

Does the power set of ℕ exist at all? If it exists, its cardinality would be aleph 1. But the existence of cardinality aleph 1 is proved by the uncountability of the power set of ℕ.

The cardinality of the power set of N is $|\mathbb R|$. It is not known if this is equal to $\aleph_1$ or not. (https://en.wikipedia.org/wiki/Cardinality_of_the_continuum)

But I don't see where you think the problem is. Why do you think this is wrong?

Edited by Strange

##### Share on other sites
28 minutes ago, Strange said:

The cardinality of the power set of N is |R| . It is not known if this is equal to 1  or not. (https://en.wikipedia.org/wiki/Cardinality_of_the_continuum)

But I don't see where you think the problem is. Why do you think this is wrong?

If A is Proven by B, B should not be consequence of A. But apparently, that the power set is uncountable is consequence of the existence of uncountability. But uncountability is proved by the existence of uncountable the power set. Before Cantor, uncountability did not exist.

Also, I have shown in Analyze of the proof of Cantor's theorem.pdf that, not using Cantor's theorem, the ℕ is smaller than the power set. So, before using Cantor's theorem, this is already a proven fact.

Below is a short summary of the first error I have found in Cantor’s theorem. Cantor  uses a proof by contradiction, which is the following. The proposition to be proved P: A list cannot contain all subsets of ℕ.

1.      Assume that P is false. That is: a list L contains all subsets of .

2.      A subset K is created. It is shown that K is not in L, which shows P is true.

3.      P cannot be true and false at the same time, So, P is true.

See section “Recall of the proof” of « Analysis of the proof of Cantor's theorem »

The scheme of logic is:

1.      P is assumed false

2.      P is shown true.

3.      Then P must be true.

This logic holds if P is correctly stated. What if the statement of P is incorrect? In this case, will the proof fall apart? The error I have found is that the used list in P is limited in length by the creation of K.

In section “Case of infinite set” of « Analysis of the proof of Cantor's theorem » I have shown that for a subset to be selfish or non selfish, the binary string of the subset must have the diagonal bit which equals 1 or 0. As the list L contains only subsets that are selfish or non selfish, the binary list L’ contains the diagonal.

The length of the diagonal equals the length of the list L’ and the length of which is the width of the list L. So, the length of L equals the length of . In this case, the proposition “A list cannot contain all subsets of ” is not correct, because in the derivation the use of the property “selfish or non selfish” imposes the length of the list L to equal the length of . So, the length of the list in the proposition P is not free of constraint, but is imposed by another element in the same context.

One can argue that because all subsets of cannot be put in the list L with the length of , subsets of are uncountable. But is countable? is created by one in x-axis and another in y-axis. In this case, is a list whose length is a free variable not limited by of its axis. Must the length of equal the length of its axis?

Edited by pengkuan

##### Share on other sites
2 minutes ago, pengkuan said:

If A is Proven by B, B should not be consequence of A. But apparently, that the power set is uncountable is consequence of the existence of uncountability. But uncountability is proved by the existence of uncountable the power set. Before Cantor, uncountability did not exist.

I don’t understand. There are not two things here (A and B). Just one: the proof of the uncountability of the power set.

##### Share on other sites
32 minutes ago, pengkuan said:

Below is a short summary of the first error I have found in Cantor’s theorem. Cantor  uses a proof by contradiction, which is the following. The proposition to be proved P: A list cannot contain all subsets of ℕ.

1.      Assume that P is false. That is: a list L contains all subsets of .

I see two problems here already.

1) The diagonal argument is NOT Cantor's theorem. There is no "list" in Cantor's theorem. Cantor's theorem says that any set has strictly smaller cardinality than its powerset. https://en.wikipedia.org/wiki/Cantor's_theorem. This is why you need to be more clear.

2) Neither Cantor's theorem nor his diagonal argument need to be framed as proofs by contradiction. The diagonal argument is a direct proof that any arbitrary list of reals is missing at least one real. Cantor's theorem is a direct proof that an arbitrary map from a set to its powerset fails to hit at least one set. Any complaints about proof by contradiction are misplaced here.

1 hour ago, pengkuan said:

The proof is correct. But the premise is apparently wrong. The theorem states: the power set of ℕ etc.

Does the power set of ℕ exist at all? If it exists, its cardinality would be aleph 1. But the existence of cardinality aleph 1 is proved by the uncountability of the power set of ℕ.

> Does the power set of ℕ exist at all?

Yes, by the axiom of powersets. https://en.wikipedia.org/wiki/Axiom_of_power_set

>  If it exists, its cardinality would be aleph 1

No, that depends on the Continuum hypothesis and is independent of the other axioms. The best we can say is that the powerset of $\mathbb N$ is $2^{\aleph_0}$. But nobody knows which Aleph that is.

Edited by wtf

##### Share on other sites
1 hour ago, Strange said:

I don’t understand. There are not two things here (A and B). Just one: the proof of the uncountability of the power set.

A: Cardinality of the power set is bigger than that of ℕ . The power set is uncountable.

B: Uncountability exists.

A is true: "the power set is uncountable", only if B is true, that is, uncountability exists.

B is true: uncountability exists, if A is true: "Cardinality of the power set is bigger than that of ℕ = the power set is uncountable".

But "Cardinality of the power set is bigger than that of ℕ" does not necessarily mean "the power set is uncountable"

##### Share on other sites
20 hours ago, pengkuan said:

But "Cardinality of the power set is bigger than that of ℕ" does not necessarily mean "the power set is uncountable"

That's exactly what it means, by definition. Any set with the same cardinality as the naturals is countable. If it's strictly smaller it's finite. If it's strictly larger it's uncountable. That's all the word uncountable means.

##### Share on other sites
28 minutes ago, wtf said:

That's exactly what it means, by definition. Any set with the same cardinality as the naturals is countable. If it's strictly smaller it's finite. If it's strictly larger it's uncountable. That's all the word uncountable means.

Short and sweet. +1

##### Share on other sites
On 23/09/2018 at 1:01 AM, wtf said:

1) The diagonal argument is NOT Cantor's theorem. There is no "list" in Cantor's theorem. Cantor's theorem says that any set has strictly smaller cardinality than its powerset. https://en.wikipedia.org/wiki/Cantor's_theorem. This is why you need to be more clear.

Correct, the diagonal argument is NOT Cantor's theorem. Cantor's theorem uses the diagonal to prove its result. Take the subset that contains the indexes of all subsets of ℕ. This means that every subset has an index, thus, is a member of a list. Then, every subset contains or not its index, qualified by selfish or not-selfish. The diagonal bit of selfish subset’s binary string is 1, otherwise is 0. The diagonal is used here.

It is correct that any set has strictly smaller cardinality than its powerset.

On 23/09/2018 at 1:01 AM, wtf said:

2) Neither Cantor's theorem nor his diagonal argument need to be framed as proofs by contradiction. The diagonal argument is a direct proof that any arbitrary list of reals is missing at least one real. Cantor's theorem is a direct proof that an arbitrary map from a set to its powerset fails to hit at least one set. Any complaints about proof by contradiction are misplaced here.

Correct. I do not complain about the contradiction, but about the sense of the theorem, that is, does it prove uncountability?

On 23/09/2018 at 1:01 AM, wtf said:

> Does the power set of ℕ exist at all?

Yes, by the axiom of powersets.

An axiom can be refuted, if the power set of ℕ is proven non existing.

On 23/09/2018 at 1:01 AM, wtf said:

But nobody knows which Aleph that is.

Yes

3 hours ago, wtf said:

That's exactly what it means, by definition. Any set with the same cardinality as the naturals is countable. If it's strictly smaller it's finite. If it's strictly larger it's uncountable. That's all the word uncountable means.

The validity of this definition depends on the validity  that uncountability exists. Cantor's theorem proves uncountability using uncountability. This is not allowed.

##### Share on other sites
57 minutes ago, pengkuan said:

An axiom can be refuted, if the power set of ℕ is proven non existing.

That doesn't make any sense. If you assume the powerset axiom then every set has a powerset that exists. If you reject the powerset axiom then there exists some set whose full powerset doesn't exist. It's not a matter of truth, it's a matter of which axiom you choose. There is no objective truth of the matter.

##### Share on other sites
39 minutes ago, wtf said:

That doesn't make any sense. If you assume the powerset axiom then every set has a powerset that exists. If you reject the powerset axiom then there exists some set whose full powerset doesn't exist. It's not a matter of truth, it's a matter of which axiom you choose. There is no objective truth of the matter.

The cardinality of finite sets does not have the same property than that of infinite sets. The cardinality of ℕ may be a upper limit.

There exists limits for mathematical objects that are walls that one never crosses. Like number 1 for 1/(1-x).

##### Share on other sites
32 minutes ago, pengkuan said:

The cardinality of finite sets does not have the same property than that of infinite sets. The cardinality of ℕ may be a upper limit.

There exists limits for mathematical objects that are walls that one never crosses. Like number 1 for 1/(1-x).

What are you talking about? A moment ago you were claiming there is an objective truth to whether full powersets exist. Now you're talking about something entirely different than makes no sense at all.

Edited by wtf

##### Share on other sites
22 hours ago, wtf said:

What are you talking about? A moment ago you were claiming there is an objective truth to whether full powersets exist. Now you're talking about something entirely different than makes no sense at all.

When I said “The cardinality of finite sets does not have the same property than that of infinite sets” I meant the power set of finite set is always finite set. Finite sets have finite power sets and finite sets are smaller than their power sets. This should be a theorem because this can be demonstrated. So, there is no need of axiom to finite sets.

But for ℕ it is different. ℕ is infinite and it cannot be proven that it can actually have a power set. This is why one has defined an axiom for the power set of ℕ.

I take the example of the function y=1/(1-x) to illustrate that while for any x<1, y has a value, this does not imply that for x=1, y has a value. In the same way, the fact that finite sets can have power sets does not automatically imply that ℕ has a power set. ℕ is an infinite set, and infinity can break the mechanism of creating power set. This is why, the axiom of power set maybe wrong for ℕ and its power set.

##### Share on other sites

The integers are countable (by definition) but they do not possess the property that between every pair of integers there exists another integer

Kevin Isaya

##### Share on other sites
6 hours ago, pengkuan said:

Finite sets have finite power sets and finite sets are smaller than their power sets

The same is true of infinite sets.

You must spend a lot of time coming up with such twisted “logic” to try and defend your beliefs. It is a bit sad to watch.

##### Share on other sites
13 hours ago, Strange said:

The same is true of infinite sets.

You must spend a lot of time coming up with such twisted “logic” to try and defend your beliefs. It is a bit sad to watch.

Yes, infinite sets are smaller than their power sets too. But I know that the power set of ℕ is countable.

##### Share on other sites
1 minute ago, pengkuan said:

But I know that the power set of ℕ is countable.

##### Share on other sites
15 hours ago, Kevin Mulisa Isaya said:

The integers are countable (by definition) but they do not possess the property that between every pair of integers there exists another integer

Kevin Isaya

I think you are replying my first post "Continuity and uncountability".

##### Share on other sites

Wrong formatting, sorry

Edited by Xerxes
tex wrong

##### Share on other sites

Building set and counting set
A counting set is the set of natural numbers with which a countable set is put in bijection. Is the counting set for the power set of ℕ the set that builds it?

Edited by pengkuan

##### Share on other sites

As with all your other attempts, pengkuan, this fails because you exhaust the finite subsets, then claim to have exhausted all subsets.

What natural number corresponds to the set of all even natural numbers?

##### Share on other sites
2 hours ago, uncool said:

As with all your other attempts, pengkuan, this fails because you exhaust the finite subsets, then claim to have exhausted all subsets.

Is {1,2,3,...} a finite set? This set is exhausted.

2 hours ago, uncool said:

What natural number corresponds to the set of all even natural numbers?

I think that the set of all even natural numbers corresponds to the natural number ...10101010.

## Create an account

Register a new account