Cont: Deeper than primes - Continuation 2

[doronshadmi]

Are you trying to say that f: S -> P(S) where f(a) = {a}? You could save us all a lot of trouble trying to decipher your posts if you just used, you know, math to express your math.

Ok, what of it? It is an injection, but not a surjection, from S to P(S). It provides an example of something that isn't a bijection between S and P(S).

How does this triviality relate to Cantor's Theorem? It certainly has nothing to do with the proof of the theorem since the proof does not consider any mapping from S to P(S) that isn't surjective.

Please keep reading my post until its end.

 

[jsfisher]

Please keep reading my post until its end.

I did read to the end. It stopped making sense well before that, and that is why a commented the way I did.

So, I ask again: Why do you bring up this function, f, at all? It doesn't relate to Cantor's Theorem (nor its proof) in any way.

 

[doronshadmi]

I did read to the end. It stopped making sense well before that, and that is why a commented the way I did.

So, I ask again: Why do you bring up this function, f, at all? It doesn't relate to Cantor's Theorem (nor its proof) in any way.

You still missing the example (without loss of generality) of {}, which is the
result of

1 --> {1}
2 --> {2}
3 --> {3}
...

and yet {} can't be used in order to show that it is beyond f range, since it is (in the first place) not a member of one of the |P(S)| proper subsets of P(S) that is in bijection with P(S) even without {}.

So no matter what members like {} Cantor's theorem provides, they are always missing from any one of the |P(S)| proper subsets of P(S) that is in bijection with P(S), and as a result Cantor's theorem can't prove that there are more P(S) members than S members, in case of infinite sets (where only infinite sets can be in bijection with their proper subsets).

 

[jsfisher]

You still missing the example (without loss of generality) of {}, which is the
result of

1 --> {1}
2 --> {2}
3 --> {3}
...

Yeah, great. You are repeating what you said before. What does this have to do with Cantor's Theorem? You have yet to show any connection whatsoever from your non-surjective mapping to the theorem or its proof.

 

[doronshadmi]

Yeah, great. You are repeating what you said before. What does this have to do with Cantor's Theorem? You have yet to show any connection whatsoever from your non-surjective mapping to the theorem or its proof.

Once again you are missing my argument, which is not about the injective map, but it is about the missing P(S) {} member from a given proper subset of P(S) that is in bijection with P(S) even if {} is not its member (and in this case we can't provide the needed contradiction that enables to conclude that there is no surjection).

In case of infinite sets it is not enough to show that the attempt to define a mapping between S member and, for example, {} (which is some P(S) member) is involved with contradiction with some member of set P(S), since such member can be omitted from P(S), and yet we get a proper subset of P(S) which is in bijection with P(S) (this is Dedeking-infinite property).

Since there are at least |P(S)| proper subsets of set P(S) that are in bijection with set P(S), Cantor's theorem has to prove that there is injection but not surjection among at least |P(S)| (proper) subsets with P(S) members, where set P(S) itself is only one case of such subsets.

EDIT:

Since Cantor's theorem is limited only to P(S) itself (where any given P(S) members that are constructed by Cantor's theorem can be omitted from set P(S) (for example: {})) it is insufficient in order to prove that indeed |S| < |P(S)|.

 

[jsfisher]

Once again you are missing my argument, which is not about the injective map, but it is about the missing P(S) {} member from a given proper subset of P(S) that is in bijection with P(S)

So what? Yes, there are subsets of P(S)\{} that are equi-numerous with P(S), but you have yet to show where that has any bearing on Cantor's Theorem.

...even if {} is not its member (and in this case we can't provide the needed contradiction that enables to conclude that there is no surjection).

Since neither the empty set, your function f, nor proper subsets of P(S) is a factor in Cantor's Theorem, why do you keep referring to them?

You must think there is some connection, otherwise you wouldn't keep bringing it up. You must think it is an obvious connection; the rest of us do not. So, whatever it is you think is there, you need to point out the connection to the rest of us in clear and direct language. The standard proof of Cantor's Theorem is short and simple; surely you can point out where in the proof there is a dependency on {} or your function f or proper subsets of P(S).

 

[jsfisher]

EDIT:

Since Cantor's theorem is limited only to P(S) itself (where any given P(S) members that are constructed by Cantor's theorem can be omitted from set P(S) (for example: {})) it is insufficient in order to prove that indeed |S| < |P(S)|.

Cantor's Theorem does not construct members of P(S), nor does its proof which is probably what you meant to refer to.

 

[ctamblyn]

This is the core of Cantor's argument, AIUI (please forgive any lapses in rigour):

CLAIM:

Let f be any mapping whatsoever from a set S to its subsets. I.e. for every x in S, f(x) is a subset of S. Then there is at least one subset of S which is not the image of any element of S under f.

PROOF:

1. For each element x of S, either the subset f(x) contains x (perhaps among other elements) or it does not.

2. Let T be the subset of S defined by T = { all x in S such that x is not contained in f(x) }.

3. Then for all y in S, y is an element of f(y) if and only if y is not an element of T.

4. Therefore, for all y in S, f(y) is not the same set as T. QED.
​

Short and sweet. Which step, exactly, does doronshadmi doubt?

 

[jsfisher]

In case of, for example:

1 --> {1}
2 --> {2}
3 --> {3}
4 --> {4}
5 --> {5}
...

the given P(S) member that is not in f range is {}.

I return to this earlier post for a clarification. Doron, did you really mean that, "the given P(S) member that is not in f range is {}"?

"The member", not "a member"?

 

[doronshadmi]

I return to this earlier post for a clarification. Doron, did you really mean that, "the given P(S) member that is not in f range is {}"?

"The member", not "a member"?

I clearly use the words "in case of" and "for example", which means that {} can be replaced by any other P(S) member that is in the first place, not a member of some proper subset of set P(S) (out of at least |P(S)| proper subsets of set P(S)) that is in bijection with set P(S).

So, jsfisher your questions and last replies clearly demonstrate the "glass ceiling" in your mind that prevents the understanding of what is actually written in http://www.internationalskeptics.com/forums/showpost.php?p=11582977&postcount=2245.

Here is a more detailed version of the last part of my argument:

Let S be the set of all natural numbers, and let P(S) be the powerset of S.

This is the core of Cantor's argument, AIUI (please forgive any lapses in rigour):

CLAIM:

Let f be any mapping whatsoever from a set S to its subsets. I.e. for every x in S, f(x) is a subset of S. Then there is at least one subset of S which is not the image of any element of S under f.

PROOF:

1. For each element x of S, either the subset f(x) contains x (perhaps among other elements) or it does not.

2. Let T be the subset of S defined by T = { all x in S such that x is not contained in f(x) }.

3. Then for all y in S, y is an element of f(y) if and only if y is not an element of T.

4. Therefore, for all y in S, f(y) is not the same set as T. QED.
​

Short and sweet. Which step, exactly, does doronshadmi doubt?

Since Cantor's theorem is limited only to P(S) itself (where any given P(S) members that are constructed by Cantor's theorem and used to show the needed contradiction, actually can be omitted from set P(S) (for example: {}, which can be replaced by any other P(S) member), without preventing the bijection between set P(S) and any one of its at least |P(S)| proper subsets, because of Dedekind-infinite property) it is insufficient in order to prove that indeed |S| < |P(S)|.

Since there are at least |P(S)| proper subsets of set P(S) that are in bijection with set P(S), Cantor's theorem has to prove that there is injection but not surjection among at least |P(S)| (proper) subsets with P(S) members, where set P(S) itself is only one case of such subsets (Cantor's theorem is limited only to P(S) itself).

 

[doronshadmi]

Let f be any mapping whatsoever from a set S to its subsets. I.e. for every x in S, f(x) is a subset of S. Then there is at least one subset of S which is not the image of any element of S under f.

Any such subset of S (which is used to provide the needed contradiction) is omitted from set P(S), without harming the bijection between set P(S) and any one of its at least |P(S)| proper subsets (this is exactly Dedekind-infinite property, which can't be found among finite sets).

Since there are at least |P(S)| proper subsets of set P(S) that are in bijection with set P(S), Cantor's theorem has to prove that there is injection but not surjection among at least |P(S)| (proper) subsets with P(S) members, where set P(S) itself is only one case of such subsets (Cantor's theorem is limited only to P(S) itself).

Since Cantor's theorem is limited only to P(S) itself it is insufficient in order to prove that indeed |S| < |P(S)|.

 

[doronshadmi]

To those who still can't follow my argument (which is actually its weak version), here is again an example that can be used without loss of generality (which means that this particular case can be replaced by any other example, without harming the common notion at the basis if these examples).

Let S be the set of all natural numbers, and let P(S) be the powerset of S.

Here is some example of an injective map between S and P(S)

1 --> {1}
2 --> {2}
3 --> {3}
...

where in this case (this example) the member of set P(S) that is claimed not to be in the range of all the members of set S, is member {}.

Since {} can be ommited from set P(S), we get a proper subset of set P(S) which is defiantly in bijection with set P(S), exactly because of Dedekind-infinite property.

So from one hand we do not have {} (which in this particular case, used by Cantor's theorem in order to provide the needed contradiction and the conclusion that {} is not in the range of all S members) and on the other hand the omitted {} (which is again, no more than the result of some example that can be replaced by any other example) has no influence on the bijction (exactly because of Dedekind-infinite property) between the proper subset of P(S) (that {} is not one of its members) and set P(S).

Conclusion:

Since Cantor's theorem is limited only to P(S) itself it is insufficient in order to prove that indeed |S| < |P(S)|.

-----------------------------------

If you understand this example without loss of generality, I can provide even stronger version of my argument, which goes beyond the argument that Cantor's theorem is limited only to P(S) itself.

 

[jsfisher]

Let S be the set of all natural numbers, and let P(S) be the powerset of S.

Here is some example of an injective map between S and P(S)

1 --> {1}
2 --> {2}
3 --> {3}
...

where in this case (this example) the member of set P(S) that is claimed not to be in the range of all the members of set S, is member {}.

Is {} the only set you see left out? {1,2} is also not in the image, nor {1,2,3}, nor {17,88,103,111}, nor uncountably other members of the power set.

In no way is the empty set the member not in the image of the function you provided.

But why do you continue to bring this up? The proof of Cantor's Theorem does not rely on examples of non-surjective functions.

Since {} can be ommited from set P(S), we get a proper subset of set P(S) which is defiantly in bijection with set P(S), exactly because of Dedekind-infinite property.

Yeah, so? Your example function isn't a bijection from S to P(S)\{} either.

 

[doronshadmi]

Is {} the only set you see left out? {1,2} is also not in the image, nor {1,2,3}, nor {17,88,103,111}, nor uncountably other members of the power set.

In no way is the empty set the member not in the image of the function you provided.

But why do you continue to bring this up? The proof of Cantor's Theorem does not rely on examples of non-surjective functions.



Yeah, so? Your example function isn't a bijection from S to P(S)\{} either.

jsfisher, according to your last post(s) it is totally clear that your "glass ceiling" in your mind is permanent without any hope to break it by very clear and straightforward posts like:

http://www.internationalskeptics.com/forums/showpost.php?p=11584144&postcount=2250

http://www.internationalskeptics.com/forums/showpost.php?p=11584177&postcount=2251

and

http://www.internationalskeptics.com/forums/showpost.php?p=11584257&postcount=2252.

Since this is unfortunately your best, nobody (but you) can help you about the issue at hand.

Is {} the only set you see left out?

Not at all (as very clearly shown in the three links above) but in case of

1 --> {1}
2 --> {2}
3 --> {3}
...

(which is no more than an example)

{} is the set that is defined by Cantor's theorem, simply because the defined subset of P(S) (that Cantor's theorem claims that it is not in the range of all S members) includes exactly all the S members that do not have their image in the P(S) members that they are mapped with.

 

[jsfisher]

{} is the set that is defined by Cantor's theorem

There is no such definition in Cantor's Theorem.

 

[doronshadmi]

There is no such definition in Cantor's Theorem.

As usual, you avoid the details of the post.

 

[jsfisher]

As usual you avoid the rest of the post.

Well, since the post depends on a misstatement, focusing on the misstatement is sufficient.

 

[doronshadmi]

Well, since the post depends on a misstatement, focusing on the misstatement is sufficient.

Wrong jsfisher, {} is just an example of a member of set P(S) that is claimed by Cantor's theorem not to be in the range of all S members, and such P(S) member is constructed by Cantor's theorem as follows:

It includes exactly all the S members that do not have their image in the P(S) members that they are mapped with.

In case of the following example (which is nothing but one of at least |P(S)| possible examples)

1 --> {1}
2 --> {2}
3 --> {3}
...

I leave you for exercise to find out what is the member of set P(S) that is claimed by Cantor's theorem not to be in the range of all S members, in this example.

 

[ctamblyn]

Since there are at least |P(S)| proper subsets of set P(S) that are in bijection with set P(S), Cantor's theorem has to prove that there is injection but not surjection among at least |P(S)| (proper) subsets with P(S) members, where set P(S) itself is only one case of such subsets (Cantor's theorem is limited only to P(S) itself).

I have a question I need you to answer:

Let S be any set, and pick a particular function f: S --> P(S).

Let T_f = { all x in S such that x is not contained in f(x) }.

Do you agree that for all y in S, f(y) is not equal to T_f?

 

[doronshadmi]

Let S be any set

I disagree. In my argument (please see http://www.internationalskeptics.com/forums/showpost.php?p=11584257&postcount=2252) S is at least an infinite set, which means that it can be in bijection with at least |S| of its proper subsets.

The case of S as a finite set is trivial since no finite set can be in bijection with any of its proper subsets.