Cantor and the Omniscience of God

[Brian]

Hello Everyone!

George Cantor in the 19th century paved the way for the mathematics of the 20th century with his proof concerning the uncountability of real numbers. This theorum is the only basis for all set theory and meta-mathematics concerning the Transfinite. Recent attacks on God’s omniscience employ a metaphysical application of Cantor’s theorem. The basic idea is that if R is uncountable, then God cannot be omniscient. Rather than attack the validity of the implication, I would like to discuss the validity of Cantor's proof. I claim that Cantor was wrong, and that all mathematics based on Transfinite numbers (which encompasses most of the mathematical breakthroughs of the 20th century) is built on a foundation of sand. I say the storm has come, and great was Cantor's fall! Therefore, the implication concerning God's omniscience is moot.

All of you philosophy buffs out there who believe R is uncountable, step up to the plate!

Sincerely,

Brian

[Tim Holt]

Hi Brian,

I've been looking for statements of this argument, so if you could give some references for you statement "Recent attacks on God's omniscience employ a metaphysical application of Cantor's theorem" then I'd appreciate it. I have access to a good philosophy library, journals and all, so don't worry about whether the sources referred to are widely available. Thanks,

Tim

[Brian]

Hello Tim!

I briefly took a look at your website and thought it was great. I would love to pick your brain. To be more specific with the argument against God's omniscience:

1. If God exists, then God is omniscient.
2. If God is omniscient, then, by definition, God knows [the set of] all truths.
3. If Cantor’s theorem is true, then there is no set of all truths.
4. But Cantor’s theorem is true.
5. Therefore, God does not exist.

You could argue against this in 2 ways. #1 You could assume Cantor's proof is true, and then argue that 5 does not follow from 2 and 3. Or, #2 You could argue against premise 4.

There are two things that motivated this post. #1 is that most modern logicians and mathematicians readily accept the idea of the Transfinite. So, strickly from a mathematics perspective it would be a hoot to show that some of the greatest thinkers of the 20th century (Russell, Goedel, etc...) were wrong. Parenthetically, most of these mathematicians, Cantor, Russell, Goedel, etc..., were atheists, and I think their atheistic bias played a part in there seach for the Transfinite. It is almost as if they tried to build a tower that reached into the heavens...a second Babel if you will. Which leads us to #2, which is that the espitemological and theological consequences of the Transfinite must be delt with by Christians.

Here is an article that motivated this post: www.sunysb.edu/philosophy/faculty/gmar/cantor.txt

I claim that I am able to refute Cantor's proof. Let me know what you think.

Sincerely,

Brian

[John Powell]

POWELL:
Partly so that my own "outrageous" philosophical claims receive better response and fewer arguments by assertion, appeals to ignorance, and appeals to authority by my critics, I strongly encourage the same be done about Brian's claim. If we wish to consider ourselves to be competent to discuss philosophy then WE should be able to present and defend the arguments that support our view whichever side it might be. Although using those "fallacious" arguments above is a sensible way to deal with most claims during the normal course of our day, I DON'T think it is appropriate in this forum.

I am not too familiar with this issue, but I'm willing to become more informed, especially if it's a good argument against God's omniscience.

John Powell
An athe-ist or strong atheist

[John Powell]

Brian:

Hello Tim!

I briefly took a look at your website and thought it was great. I would love to pick your brain. To be more specific with the argument against God's omniscience:

1. If God exists, then God is omniscient.
2. If God is omniscient, then, by definition, God knows [the set of] all truths.
3. If Cantor’s theorem is true, then there is no set of all truths.
4. But Cantor’s theorem is true.
5. Therefore, God does not exist.

You could argue against this in 2 ways. #1 You could assume Cantor's proof is true, and then argue that 5 does not follow from 2 and 3. Or, #2 You could argue against premise 4.


POWELL:
Yes. Even if Cantor's theorem were true it would not mean that the creator God could not exist nor even that an "omniscient" God could not exist (provided the definition of "omniscient" was properly understood).

This argument is flawed, I think, in a number of ways. First is that some God-concepts do not entail omniscience. Secondly, omniscience does not necessarily mean "Know everything, even the unknowable" just like "omnipotent" does not necessarily mean "able to do anything, even the impossible." God CANNOT do certain actions that the mind of man can phrase into sensible words. For example, Brian, wouldn't you concede that God cannot create a being more powerful than He is or create triangular shaped circles? God can at most do what is logically possible. Isn't that right, Brian?

So, the definition of "omniscience" might NOT be "knows everything," but might mean "knows everything logically possible to know." I am in a discussion / debate in which it is argued that God CANNOT know the future if we have free will. If this were true then "knowing the future" would be something that God cannot know if we have free will, similar to "creating a God more powerful than He is" is not something possible for God to do.

I think you need to specify that it is YOUR current concept of God or something like that THAT is omniscient in a certain way. If you change what attributes you give to God, such as taking from Him knowledge of the set of all truths, then your God might still exist, but the old concept of God no longer matches the God that exists.

Consider an example.

1. If Michael Jordan exists, then Michael Jordan is the best basketball player in the world.
2. Michael Jordan is not the best basketball player in the world.
3. Therefore, Michael Jordan does not exist.

It might be true that right now everyone agrees that Michael Jordan is the best basketball player in the world. However, if a new player were to outdo Mike, then that fact would not cause Michael Jordan to disappear into nonexistence. Our concept of Michael would change, but Michael would not fail to exist.

Likewise, if it turns out that Cantor is correct, then it would not mean that the creator God does not exist, it might only mean that the creator God does NOT have the attribute or the knowledge that some people thought He did. It would NOT even mean that God is not omniscient, just possibly that He's not omniscient in the way people may have previously thought.

Does this make sense, Brian?

John Powell

[Tim Holt]

Hi Brian,

Think of the version of the web-site that's up at the moment as a first draft. I have an updated version on my hard-drive, but won't upload until I've written some more content for it. Thanks for the comments; I encourage you to check back in a month or so when the site should be much improved. Bear in mind that introductory material will appear first, followed by more technical material later.

As for the argument: I appreciate the reference. All I had on this so far was a page in a book on paradoxes. I've skimmed the article, but will have to read it more carefully before I reach a settled view. I have a regular pub meet with an agnostic physics graduate and an atheist maths graduate on Wednesday evenings, so will see if they have anything to say about it later.

Thanks again,

Tim

[Brian]

Hello Tim and John!

Tim, I will check out your site in a month or so. I am sure your physics and math buddies will have much to say! They might better understand it as there being "infinities" larger than "infinite", i.e. aleph_0, aleph_1, etc...

John, I agree that we could argue against the argument by defining omniscient, etc...However, that is what I am specifically trying to aviod in the thread. I want to attack premise 4, i.e., Cantor's proof for the uncountability of R. What I would like is for someone who thinks Cantor is correct to challenge me on it.

As to your discussion concerning Free Will, I have read just a little of it. I think your position is that if man has free will, then God cannot know the future. Correct me if I am wrong. I do not want to discuss this in this thread, but will risk a comment about it since you brought it up. It seems you are trying to preserve an idea of God being omniscient without knowing the real choices man makes because God cannot logically know them. That is, your point is that it is logically impossible for God to know our free-will choices. Therefore, God can still be omniscient because omniscience does not require God to know "logically impossible to know" things.

The flaw I see immediately in your argument is that you assume what it means for man to have free-will. You seem to define free-will as "the ability to make choices that God cannot know." That is fine. But to build an argument from this assumption proves nothing until you establish your assumption, which you have not done. To quote you...


Partly so that my own (Powell's)"outrageous" philosophical claims receive better response and fewer arguments by assertion...

Arguments by assertion are not arguments. However, you are doing the very thing you wish others would not do. You seem to assert a definition of "free-will" but do not argue for it, but instead argue from it. These are just my thoughts from your other thread. Of course you may have argued for your assumption, but from what I have read you have not established it. If I am wrong, my bad, and chalk it up to my cursory glance at the thread.


If we wish to consider ourselves to be competent to discuss philosophy then WE should be able to present and defend the arguments that support our view whichever side it might be.

Well said. I agree.


I am not too familiar with this issue, but I'm willing to become more informed, especially if it's a good argument against God's omniscience.

I think it can be a good argument against God's omniscience, if you assume Cantor's proof to be true, and you identify what omniscient means. When Cantor speaks of R being uncountable, he is speaking of a set that does exist. It is not some hypothetical round square or rock too big to lift thing. It is a real set (pardon the pun :-)), that is completely logical, whatever that means. The epistemelogical implications of this are far reaching.

Sincerely,

Brian

[BrianB]

Hi Brian,

For background, you may want to read the thread "POE arg - for John"

John rejects some of the common rules of argumentation, and if you are unaware of this going forward in your discussions with him it could lead to some serious miscommunication and frustration.

Basically, he wants to make assertions and require that the opposite side take some burden of proof to disprove his unsupported assertions.

Hope this helps,
BrianB

[John Powell]

Brian:

Hello Tim and John!

Tim, I will check out your site in a month or so. I am sure your physics and math buddies will have much to say! They might better understand it as there being "infinities"; larger than "infinite", i.e. aleph_0, aleph_1, etc...

John, I agree that we could argue against the argument by defining omniscient, etc...However, that is what I am specifically trying to aviod {avoid} in the thread. I want to attack premise 4, i.e., Cantor's proof for the uncountability of R. What I would like is for someone who thinks Cantor is correct to challenge me on it.


POWELL:
That seems fine then. We would take as given that God has the attributes YOU personally claim Him to have and focus on whether Cantor's arguments disqualify that PARTICULAR definition of God. I could be game for that. I need to understand Cantor's argument / proof first.


BRIAN:
As to your discussion concerning Free Will, I have read just a little of it. I think your position is that if man has free will, then God cannot know the future. Correct me if I am wrong. I do not want to discuss this in this thread, but will risk a comment about it since you brought it up. It seems you are trying to preserve an idea of God being omniscient without knowing the real choices man makes because God cannot logically know them. That is, your point is that it is logically impossible for God to know our free-will choices. Therefore, God can still be omniscient because omniscience does not require God to know "logically impossible to know" things.


POWELL:
That sounds like you understand my argument pretty well.


BRIAN:
The flaw I see immediately in your argument is that you assume what it means for man to have free-will. You seem to define free-will as "the ability to make choices that God cannot know." That is fine. But to build an argument from this assumption proves nothing until you establish your assumption, which you have not done.


POWELL:
I see.


BRIAN:
To quote you...

Arguments by assertion are not arguments.


POWELL:
That would be absurd if I said that, which I didn't. How can arguments not be arguments? Whoever thinks this surely means that arguments by assertion are fallacious arguments or something like that.


BRIAN:
However, you are doing the very thing you wish others would not do. You seem to assert a definition of "free-will" but do not argue for it, but instead argue from it. These are just my thoughts from your other thread. Of course you may have argued for your assumption, but from what I have read you have not established it. If I am wrong, my bad, and chalk it up to my cursory glance at the thread.


POWELL:
I'm trying to use the definition of free will that others use or will accept phrased in such a way that it supports my argument. I think you're right that we should focus on Cantor's argument and leave this discussion to the debate in progress


BRIAN:
Well said. I agree.


POWELL:
About what?


BRIAN:
I think it can be a good argument against God's omniscience, if you assume Cantor's proof to be true, and you identify what omniscient means. When Cantor speaks of R being uncountable, he is speaking of a set that does exist. It is not some hypothetical round square or rock too big to lift thing. It is a real set (pardon the pun :-)), that is completely logical, whatever that means. The epistemelogical implications of this are far reaching.

Sincerely,

Brian


POWELL:
Perhaps.

So, are you arguing that Cantor's set exists outside of his mind, but my concepts of "a rock too big for God to lift" and "a being more powerful than God" only exist in my mind? I find it interesting that someone who thinks a concept that, apparently to me, only exists in the minds of mankind actually exists in the real universe would argue in this way.

I suspect you're overemphasizing the persuasive power of Cantor's argument and underestimating the persuasive power of "can God create a rock so large that He can't lift it" type arguments. These both go to show that God cannot be an Omnibeing if omnipotent means "can do anything, even that which a human might think to be impossible" and if "omniscient" means "knows everything, even that which a human might think to be impossible."

Nevertheless, I'm very interested in Cantor's argument. It could prove to be another weapon in the atheist's arsenal of persuasive arguments, especially suited for those of a more mathematical mind set.

John Powell.

[mattbballman19]

Hey Powell,

I apologize for not reciprocating on the modens ponnens thread with more expeditiousness! I request that you glance at my last post due to the potential amelioration we could draw out of that discussion concerning that particular logical question.

thanx

matt

[Brian]

Hello John!


That seems fine then. We would take as given that God has the attributes YOU personally claim Him to have and focus on whether Cantor's arguments disqualify that PARTICULAR definition of God. I could be game for that. I need to understand Cantor's argument / proof first.

No offense John, but I wish to argue this with someone who understands Cantor's proof, and thinks it is valid. Since you are not familiar with it, I will wait for another. By the way, Cantor's proof in and of itself has nothing to do with the attributes of God.


That would be absurd if I said that, which I didn't. How can arguments not be arguments? Whoever thinks this surely means that arguments by assertion are fallacious arguments or something like that.

You are misrepresenting me. Please go back and read my previous post more carefully.


POWELL: About what?

Once again, please go back and read my post. It is obvious.


So, are you arguing that Cantor's set exists outside of his mind, but my concepts of "a rock too big for God to lift" and "a being more powerful than God" only exist in my mind? I find it interesting that someone who thinks a concept that, apparently to me, only exists in the minds of mankind actually exists in the real universe would argue in this way.

No. All I said is that the concept of real numbers, which are immaterial, are logically consistent. A round triangle is immaterial as well, but is not logically consistent. Cantor's proof deals with the logically consistent concept of R (i.e. real numbers), and does not fall into the "four corners of the round table" type category.


Nevertheless, I'm very interested in Cantor's argument. It could prove to be another weapon in the atheist's arsenal of persuasive arguments, especially suited for those of a more mathematical mind set.

I think it might be persuasive if it were valid. But, because Cantor's proof for the uncountability of R is not valid, then the whole argument based on it is moot. Sorry John, your search for something to validate your world-view continues.

Sincerely,

Brian

[Brian]

Hello Everyone!

A challenge has ben put forth. Are there any philosophy geeks out there ready to defend Cantor's proof for the uncountability of R?

Sincerely,

Brian

[John Powell]

BrianB:

Hi Brian,

For background, you may want to read the thread "POE arg - for John"

John rejects some of the common rules of argumentation, and if you are unaware of this going forward in your discussions with him it could lead to some serious miscommunication and frustration.


POWELL:
Prove it, BrianB. You just made a claim. According to your understanding of this principle you should support your claim with sufficient support and I don't have to support my criticism of your claim. Reading the text might be helpful, but it doesn't prove your case. It demonstrates that you and I disagree.

More seriously, I reject what is commonly claimed to be one of the common rules of argumentation concerning who has the burden of proof. It is my contention that what has been claimed to be the rule, namely that the claimant has 100% of the burden of proof and the critic has 0% of the burden of proof is an exaggeration of what is actually meant by the rule and usually done in debates / discussions. What is really meant is that the claimant has the burden of proof commensurate with the acceptance-level of the claim. If it is an outrageous claim then the claimant has the vast majority of the burden of proof. If the claim is almost universally accepted, however, then the claimant has very little burden of proof.

For example, the outrageous claim "I have an invisible fire breathing dragon in my garage" would put nearly all the burden of proof on the claimant.

On the other hand, the almost universally accepted claim "Japan still exists" would put nearly all the burden of proof on anyone denying that claim.

If I am wrong and you are right, BrianB, then I suggest that I am justified as a critic to rebut with a single word even the best-defended mathematical proof:

"Denied."


BRIANB:
Basically, he wants to make assertions and require that the opposite side take some burden of proof to disprove his unsupported assertions.


POWELL:
Again, BrianB, prove it. If you won't do that then you seem to be violating your own principle of burden of proof.

More seriously, not quite. I expect the opposition to take some burden of proof commensurate with the acceptance level of my claim.

If I make a claim that you don't feel is sufficiently supported and you say that the claim is wrong, but you don't have to support your criticism at all because I didn't support my original assertion to your satisfaction, then I feel justified to ask you to live up to your own standard and support your criticism or I don't have to more fully support my original assertion. Either both sides must take some burden of proof or an unnecessary impasse might result.

Something you seem to fail to realize, BrianB, is that a person's say-so is a form of at least implied support, so "an unsupported assertion" implies "insufficient support" not "no support." Or, it means "no more support" other than things like the person's mere say-so.


BRIANB:
Hope this helps,
BrianB


POWELL:
I'm sorry if I've frustrated you, BrianB. That wasn't my goal.

John Powell

[John Powell]

BRIAN:
Hello John!


POWELL:
Hello, Brian.


POWELL:
That seems fine then. We would take as given that God has the attributes YOU personally claim Him to have and focus on whether Cantor's arguments disqualify that PARTICULAR definition of God. I could be game for that. I need to understand Cantor's argument / proof first.

BRIAN:
No offense John, but I wish to argue this with someone who understands Cantor's proof, and thinks it is valid. Since you are not familiar with it, I will wait for another.


POWELL:
Fair enough. If no one else is interested, perhaps you'll want me to try.


BRIAN:
By the way, Cantor's proof in and of itself has nothing to do with the attributes of God.

POWELL:
That would be absurd if I said that, which I didn't. How can arguments not be arguments? Whoever thinks this surely means that arguments by assertion are fallacious arguments or something like that.

BRIAN:
You are misrepresenting me. Please go back and read my previous post more carefully.


POWELL:
Oops. Things look different than I remember them. It would have helped me to avoid the confusion if you had used my tag over my words and your tag over your own as I will do.


BRIAN:
That is fine. But to build an argument from this assumption proves nothing until you establish your assumption, which you have not done. To quote you...

POWELL:
“ Partly so that my own (Powell's)"outrageous" philosophical claims receive better response and fewer arguments by assertion... ”

BRIAN:
Arguments by assertion are not arguments. However, you are doing the very thing you wish others would not do.


POWELL:
Your statement (that I thought you were attributing to me) "Arguments by assertion are not arguments" is absurd on the face, Brian. It is claiming that arguments are not arguments. Don't you mean that arguments by assertion aren't GOOD arguments or something like that?

Also, your earlier statement "But to build an argument from this assumption proves nothing until you establish your assumption," is absurd on the face unless by "proves nothing" you mean something like "doesn't prove enough" or "doesn't prove the assumption" since verbalizing an argument will likely prove SOMETHING to the listener even if it's just that the claimant still exists.


POWELL:
About what?

BRIAN:
Once again, please go back and read my post. It is obvious.


POWELL:
Oops again. I don't understand why it didn't make sense before. I must have missed the quote formatting or something like that.


POWELL:
So, are you arguing that Cantor's set exists outside of his mind, but my concepts of "a rock too big for God to lift" and "a being more powerful than God" only exist in my mind? I find it interesting that someone who thinks a concept that, apparently to me, only exists in the minds of mankind actually exists in the real universe would argue in this way.

BRIAN:
No. All I said is that the concept of real numbers, which are immaterial, are logically consistent.


POWELL:
I'm beginning to get frustrated with your exaggerations, Brian. It is surely NOT true that ALL you said was that "the concept of real numbers, which are immaterial, are logically consistent." Where did you say those exact words and nothing else?

I suggest you avoid the use of words like "all" and "nothing" unless you really mean them since you seem to equivocate too often when you use them. This sloppiness in your writing leads me to doubt your abilities to effectively rebut Cantor's theorem which has something to do with concepts like "all" or "nothing."


BRIAN:
A round triangle is immaterial as well, but is not logically consistent. Cantor's proof deals with the logically consistent concept of R (i.e. real numbers), and does not fall into the "four corners of the round table" type category.


POWELL:
Yes, "four corners of the round table" is not logically consistent, but I'm not so sure about "a being more powerful than God" or similar logically-sounding statements being logically inconsistent. It depends on the definition of God. My former belief in God allowed for the existence of a being to be more powerful than the supreme God of this Earth and for Jesus to one day surpass His Father.


POWELL:
Nevertheless, I'm very interested in Cantor's argument. It could prove to be another weapon in the atheist's arsenal of persuasive arguments, especially suited for those of a more mathematical mind set.

BRIAN:
I think it might be persuasive if it were valid.


POWELL:
If all you require is a valid argument to be persuaded, Brian, then how about the following?

1. If Grim's argument is sound then God doesn't exist.
2. Grim's argument is sound.
3. therefore, God doesn't exist.

Is that a valid argument? It has the modus ponens form, does it not?


BRIAN:
But, because Cantor's proof for the uncountability of R is not valid, then the whole argument based on it is moot. Sorry John, your search for something to validate your world-view continues.

Sincerely,

Brian


POWELL:
Perhaps I'll just have to keep searching for validation.

John Powell

[John Powell]

POWELL:
I'm beginning to get frustrated with your exaggerations, Brian. It is surely NOT true that ALL you said was that "the concept of real numbers, which are immaterial, are logically consistent." Where did you say those exact words and nothing else?


POWELL:
I should mention that I was not only frustrated by BrianB's exaggerations, but perhaps more so because of my own apparent inability to properly quote him. :argh:

Imperfection is sometimes difficult to live with.

John Powell

[mengenlehre]

I propose the following two statements and there consistency in an unknown universe of statements.
1) god exists
2) ~(god exists)

Maybe contradictions don't matter??????

"It is a puzzling thing. The truth knocks on the door and you say, "Go away, I'm looking for the truth," and so it goes away. Puzzling. "

R M Pirsig






POWELL:
Yes. Even if Cantor's theorem were true it would not mean that the creator God could not exist nor even that an "omniscient" God could not exist (provided the definition of "omniscient" was properly understood).

This argument is flawed, I think, in a number of ways. First is that some God-concepts do not entail omniscience. Secondly, omniscience does not necessarily mean "Know everything, even the unknowable" just like "omnipotent" does not necessarily mean "able to do anything, even the impossible." God CANNOT do certain actions that the mind of man can phrase into sensible words. For example, Brian, wouldn't you concede that God cannot create a being more powerful than He is or create triangular shaped circles? God can at most do what is logically possible. Isn't that right, Brian?

So, the definition of "omniscience" might NOT be "knows everything," but might mean "knows everything logically possible to know." I am in a discussion / debate in which it is argued that God CANNOT know the future if we have free will. If this were true then "knowing the future" would be something that God cannot know if we have free will, similar to "creating a God more powerful than He is" is not something possible for God to do.

I think you need to specify that it is YOUR current concept of God or something like that THAT is omniscient in a certain way. If you change what attributes you give to God, such as taking from Him knowledge of the set of all truths, then your God might still exist, but the old concept of God no longer matches the God that exists.

Consider an example.

1. If Michael Jordan exists, then Michael Jordan is the best basketball player in the world.
2. Michael Jordan is not the best basketball player in the world.
3. Therefore, Michael Jordan does not exist.

It might be true that right now everyone agrees that Michael Jordan is the best basketball player in the world. However, if a new player were to outdo Mike, then that fact would not cause Michael Jordan to disappear into nonexistence. Our concept of Michael would change, but Michael would not fail to exist.

Likewise, if it turns out that Cantor is correct, then it would not mean that the creator God does not exist, it might only mean that the creator God does NOT have the attribute or the knowledge that some people thought He did. It would NOT even mean that God is not omniscient, just possibly that He's not omniscient in the way people may have previously thought.

Does this make sense, Brian?

John Powell

[mengenlehre]

Well, I would like to come at you from below. At some point in mathematics, we have to come to a separation of truth and consistency. Lets assume your right and that Cantor's proof of the cardinality of the continuum is inherently flawed. Now, forget about Cantor all together. "ALL" of set theory is constructed from nothing i.e. the empty set and nothing more using very basic methods from logic. So we construct our way up to the rationals which are countable. Then we find new numbers (doesn't matter how many) that are not elements of the rationals.
Hence there exists a set of size STRICTLY greater than the rationals. Here in lies the problem because we can collect the elements of this new set, call it S, together with everything "below" it to get a set of larger cardinality, call it S', and then we can construct the power set using the powerset axiom to get a new set, S", of larger cardinality. This is simply a quasi-meta-construction of something that turns out to be of some size much bigger than the rationals. But it keeps on going... Now we simply give it a nice-name and do some forcing. We have constructed a set without any mention of anything but rationals and "other numbers" not in the rationals which we know to exist and have produced of set with the desired property i.e. transfiniticity. Call the set and its size whatever you like.








Hello Everyone!

George Cantor in the 19th century paved the way for the mathematics of the 20th century with his proof concerning the uncountability of real numbers. This theorum is the only basis for all set theory and meta-mathematics concerning the Transfinite. Recent attacks on God’s omniscience employ a metaphysical application of Cantor’s theorem. The basic idea is that if R is uncountable, then God cannot be omniscient. Rather than attack the validity of the implication, I would like to discuss the validity of Cantor's proof. I claim that Cantor was wrong, and that all mathematics based on Transfinite numbers (which encompasses most of the mathematical breakthroughs of the 20th century) is built on a foundation of sand. I say the storm has come, and great was Cantor's fall! Therefore, the implication concerning God's omniscience is moot.

All of you philosophy buffs out there who believe R is uncountable, step up to the plate!

Sincerely,

Brian

[Seasanctuary]

Ok, Brian, I'll bite. I understand Cantor's proof, find it convincing, and am quite willing to argue the point with you. To be clear, I'm speaking about his diagonalization proof showing that R is uncountable.

Please point out how you think Cantor's proof is flawed.

[mengenlehre]

i agree with you. the proof is not flawed unless proof by contradiction is invalid.

[Brian]

Hello Guys,

I have not posted to this board in a long time. However, this is a topic that I find very fascinating. As such, I will be happy to pick this thread back up.


To be clear, I'm speaking about his diagonalization proof showing that R is uncountable.

I am going to begin with my version of Cantor's proof. Note: the symbol "<>" means "is an element of," and it's negation is indicated by the symbol "~<>".


Step 1) Prove A: R is uncountable.
Step 2) Assume ~A: R is countable.
Step 3) ~A-->B(1): N can index R.
Step 4) B(1)-->B(2): There exists an enumeration of R, say X, such that if r <> R, then r <> X.
Step 5) B(2)-->~B(2): By the diagonal method, y1 is created such that y1<>R, but y1 ~<> X.
Step 6) ~B(1) by Modus Tollens.
Step 7) ~~A by Modus Tollens.
Step 8) A by law of negation.
Q.E.D.

In order to show that R is not countable, we must show that N cannot index R. In the above proof this is proved indirectly by MT from step 5 to step 6. But does this really follow? I submit that the implication from step 3 to step 4 is not sufficient, and as a result when y1 is created in step 5, it says nothing about N's ability to index R.

The transitive law of equality says that if A=B, and if B=C, then A=C. Notice that the relation established between A and C is completely dependent upon B. Also notice that the relationship of A and C to B must be clearly defined in order to make any necessary conclusions concerning the relationship between A and C. In Cantor's proof we have three sets under consideration: N, X, and R. The relationship between N and R is established by the relationship of N to X, and X to R. In order to demonstrate that N cannot index R, the relationship between N and X, and X and R must be sufficient to necessarily draw this conclusion. Are these relationships sufficiently defined to establish the conclusion that N cannot index R? The answer is no. The relationship between X and R is that every element in R is an element in X. This relationship is sufficiently clear to draw the necessary conclusions of Cantor's proof, IF the relationship between N and X is the same, i.e. X is a listing utilizing every element of N as the index. However, this does not necessarily follow from the assumption that R is countable.

In order to show that R is countable X only needs to contain |N| elements. That is, the relationship between N and X is defined to be that X utilizes |N| elements from the set N, but not necessarily every element from the set N! (If you need all of the elements N, then you do not need them all.) We can enumerate R utilizing only the even numbers, and this would be sufficient to show a complete enumeration that is countable because the even numbers have |N| elements. This would leave us with an infinite number of elements in N (i.e. the odd numbers) that are still available for further indexing. That is to say, the relationship between N and X is such that if there is an element y1 not contained in X but contained in R it says nothing about N's ability to index R! This means that the needed relationship between X and N for Cantor's proof to be valid is NOT a necessary consequence (implication) from the assumption ~A or B(1). Therefore, since the relationship between N and X is insufficient, we cannot conclude anything about the relationship between N and R in terms of indexing.

If all of the implications drawn from Cantor's proof follow, then by MT we should be able to conclude that N cannot index R. However, it has been shown that the relationship between N and X is not sufficient for these implications to follow. What is the problem? The problem with Cantor's proof starts right at the beginning with its use of a definition that is not consistent with itself (or at least has not been proven consistent with itself). The following ideas are taken from the non-published paper, Hinged Sets and the Answer to the Continuum Hypothesis (http://pages.sbcglobal.net/webster.kehr/files/Continuum.pdf), by R. Webster Kehr.

Countable: A set is countable if and only if its cardinality is either finite or equal to Ào.

This leads us to another definition for countablilty namely...

The Standard Definition of Countable (SD): A set is countable iff it can be placed into bijection with N.

Because our standard definition is a material implication (i.e. an if and only if statement), then it can be broken down in to the following 2 implications:

(1) If a set can be placed into bijection with N, then it is countable.
(2) If a set it countable, then it can be placed into bijection with N.

Statement (1) I find to be obviously true. For the sake of distinction, I would like to call (1) the "Definition of Countable (DOC)." Statement (2) is logically independent of (1). In other words, the validity of DOC does not imply the validity of (2). The contrapositive of A-->B is ~B-->~A, and is logically equivalent to A-->B. The contrapositive of (2) is "if a set cannot be placed into bijection with N, then it is uncountable." Again, for the sake of distinction, I would like to refer to this as the "Definition of Uncountable (DOU)." That would make (2) the contrapositive of DOU, i.e. CDOU. Therefore, SD consists of 2 logically independent implications, DOC and DOU. From this we now have a definition that provides a sufficient condition to determine a set to be countable or uncountable. That is, DOC establishes a sufficient condition to determine that a set is countable, and DOU establishes a sufficient condition to determine that a set is uncountable.

DOC: If a set can be placed into bijection with N, then it is countable.
DOU: If a set cannot be placed into bijection with N, then it is uncountable.

The question that arises is if we have 2 sets that have vastly different properties and they cannot be placed into bijection, is this a proof that the two sets have different cardinal numbers? Is it possible for two sets to have the same cardinal number and there not be a bijection between them? The DOU assumes that it is not possible. However, DOC and DOU are logically independent of one another, therefore it must be shown that these 2 definitions are consistent with each other before we can say that SD is a valid definition. There is no proof that I am aware of that demonstrates the absolute consistency of the DOC and DOU with respect to all mapping techniques and all possible infinite sets no matter what the differences in properties between the 2 sets. Therefore, we have a definition that may or may not be valid.

Let’s look at this a little deeper. Cantor’s Proof starts out with an arbitrary countable listing of R. It then places N into bijection with R. Why does it do this? DOU states: If a set cannot be placed into bijection with N, then it is uncountable. The contrapositive of this is CDOU: If a set is countable, then it can be placed into bijection with N. Notice that the Cantor’s Proof relies on CDOU and not DOC. Once this list has been compiled we ask the question, “Is every element of R in this countable listing?” To answer this Cantor creates his CDN (Cantor's Diagonal Number) that is an element of R, but which is not mapped to by any element in N. Since no specific element of N maps to the CDN, and because the CDN is an element of R, then R cannot be placed into bijection with N. At this point Cantor uses the DOU and concludes that R is uncountable. Note that Cantor’s proof relies entirely on DOU (CDOU and DOU are logically equivalent). Cantor uses CDOU to set up the original assumption that if R were countable, then it could be placed into bijection with N. It then uses the DOU when it is determined that no specific element of N maps to the CDN. If DOU were not available to Cantor’s proof, then diagonalization by itself is not sufficient to prove that R is uncountable.

If we consider this initial listing of R, then diagonalization divides R into 2 disjoint sets: 1) the set of all elements that maps to N, and 2) the compliment of (1) that makes up the rest of R. The CDN is in the second set. Notice this second set is not empty (it includes the CDN), and we also know this set to be infinite. However, infinite does not mean uncountable. The key to determine the cardinality of R lies in determining the cardinality of the second set! If the second set is uncountable, then obviously R is uncountable. However, if the second set is countable, then by Cantor’s Countable Union Theorem (CUT) all of R is countable. Here is the interesting thing, the CUT is based on the DOC which is obviously true! It is a variation of the CUT that I use above in my argument for why there is not a proper relationship defined between N and X. However, Cantor's proof is based solely on the DOU.

Here is the point to all of this. Given any countable listing of R elements, a CDN can be constructed. But the question is, “By using different algorithms, how many unique CDNs can be constructed?” The DOU says that an uncountable number can be created. However, the DOU is a definition and not a mapping technique! The DOU by itself does not prove anything. The DOU must be paired with a mapping technique. Cantor’s proof pairs the DOU with diagonalization. Thus the combination of DOU and diagonalization must be valid. By using the DOU/diagonalization combination, Cantor assumes that this combination cannot “work” (i.e. prove the lack of a bijection with N) on any countable set. But this has never been proved! The DOC and DOU/diagonalization combination are clearly logically independent and it has never been proven that the set of all sets that are the same “size” as N and the set of all sets in bijection with N are the same set. There is no proof that the DOC and DOU/diagonalization combination are consistent. Cantor’s proof depends heavily on a definition that has never been shown to be logically or mathematically consistent with the obviously valid definition of the DOC. Cantor assumes that it is true, and this assumption leads to the assumption that when R is indexed by N, N must use every element in N to index it (i.e. there exists a bijection between N and R). However, this does not follow from the DOC and CUT, which allows us to say, "If you need every element of N, then you don't need them all."

In conclusion, Cantor's Proof assumes DOU is true (a definition that has not been proved), ignores DOC (a definition that obviously is true), and assumes that all sets are actual. This is in addition to his original assumption that R is countable. According to the rules of Reductio Ad Absurdum, Cantor can make no claim one way or the other concerning the countability of R because of his multiple assumptions. Because of DOC and CUT, it does not necessarily follow that if N can index R, there exists a bijection between N and R. This is the assumption made from step 3 to step 4 of the Cantor's proof. Disregarding the assumption that all sets are actual, what Cantor does prove is that DOU and R being countable cannot both be true.

Sincerely,

Brian

[HRG_new]

Hello Guys,

I have not posted to this board in a long time. However, this is a topic that I find very fascinating. As such, I will be happy to pick this thread back up.



I am going to begin with my version of Cantor's proof. Note: the symbol "<>" means "is an element of," and it's negation is indicated by the symbol "~<>".


Step 1) Prove A: R is uncountable.
Step 2) Assume ~A: R is countable.
Step 3) ~A-->B(1): N can index R.
Step 4) B(1)-->B(2): There exists an enumeration of R, say X, such that if r <> R, then r <> X.
Step 5) B(2)-->~B(2): By the diagonal method, y1 is created such that y1<>R, but y1 ~<> X.
Step 6) ~B(1) by Modus Tollens.
Step 7) ~~A by Modus Tollens.
Step 8) A by law of negation.
Q.E.D.

In order to show that R is not countable, we must show that N cannot index R. In the above proof this is proved indirectly by MT from step 5 to step 6. But does this really follow? I submit that the implication from step 3 to step 4 is not sufficient, and as a result when y1 is created in step 5, it says nothing about N's ability to index R.

The transitive law of equality says that if A=B, and if B=C, then A=C. Notice that the relation established between A and C is completely dependent upon B.

Not so. This is just one way to establish the equality of A and C; there may be others, not dependent on B.-



Also notice that the relationship of A and C to B must be clearly defined in order to make any necessary conclusions concerning the relationship between A and C. In Cantor's proof we have three sets under consideration: N, X, and R.


Careful here: X is a set of ordered pairs which establishes a mapping, aka function of N into
R.
[quote]
The relationship between N and R is established by the relationship of N to X, and X to R. In order to demonstrate that N cannot index R, the relationship between N and X, and X and R must be sufficient to necessarily draw this conclusion. Are these relationships sufficiently defined to establish the conclusion that N cannot index R? The answer is no. The relationship between X and R is that every element in R is an element in X.
[quote]
Not at all. X is a function with domain N into R. Cantor's proof shows that whatever X, its image cannot be all of R - by establishing a contradiction from the contrary assumption.
[quote]
This relationship is sufficiently clear to draw the necessary conclusions of Cantor's proof, IF the relationship between N and X is the same, i.e. X is a listing utilizing every element of N as the index. However, this does not necessarily follow from the assumption that R is countable.

If a set S is countable, by definition there is a function from N onto the whole of S.


In order to show that R is countable X only needs to contain |N| elements. That is, the relationship between N and X is defined to be that X utilizes |N| elements from the set N, but not necessarily every element from the set N!

(If you need all of the elements N, then you do not need them all.) We can enumerate R utilizing only the even numbers, and this would be sufficient to show a complete enumeration that is countable because the even numbers have |N| elements. This would leave us with an infinite number of elements in N (i.e. the odd numbers) that are still available for further indexing.

Quite irrelevant. Assign any elements of R to the odd numbers, and you get a function on the whole of N. The construction works as above and shows that its image cannot be R.



That is to say, the relationship between N and X is such that if there is an element y1 not contained in X but contained in R it says nothing about N's ability to index R! This means that the needed relationship between X and N for Cantor's proof to be valid is NOT a necessary consequence (implication) from the assumption ~A or B(1). Therefore, since the relationship between N and X is insufficient, we cannot conclude anything about the relationship between N and R in terms of indexing.

I'm sorry, but you are simply wrong, as demonstrated above. You misunderstand the concept of "indexing"; what Cantor's proof is about is simply functions from N into R.



If all of the implications drawn from Cantor's proof follow, then by MT we should be able to conclude that N cannot index R. However, it has been shown that the relationship between N and X is not sufficient for these implications to follow.

Since you misunderstand the relationship, your conclusion is wrong.



What is the problem? The problem with Cantor's proof starts right at the beginning with its use of a definition that is not consistent with itself (or at least has not been proven consistent with itself). The following ideas are taken from the non-published paper, Hinged Sets and the Answer to the Continuum Hypothesis (http://pages.sbcglobal.net/webster.kehr/files/Continuum.pdf), by R. Webster Kehr.

Countable: A set is countable if and only if its cardinality is either finite or equal to Ào.

This leads us to another definition for countablilty namely...

The Standard Definition of Countable (SD): A set is countable iff it can be placed into bijection with N.

Because our standard definition is a material implication (i.e. an if and only if statement), then it can be broken down in to the following 2 implications:

(1) If a set can be placed into bijection with N, then it is countable.
(2) If a set it countable, then it can be placed into bijection with N.

Statement (1) I find to be obviously true. For the sake of distinction, I would like to call (1) the "Definition of Countable (DOC)." Statement (2) is logically independent of (1).

Why do you break down a definition ? (2) is still part of the definition of "countable".


In other words, the validity of DOC does not imply the validity of (2). The contrapositive of A-->B is ~B-->~A, and is logically equivalent to A-->B. The contrapositive of (2) is "if a set cannot be placed into bijection with N, then it is uncountable." Again, for the sake of distinction, I would like to refer to this as the "Definition of Uncountable (DOU)." That would make (2) the contrapositive of DOU, i.e. CDOU. Therefore, SD consists of 2 logically independent implications, DOC and DOU. From this we now have a definition that provides a sufficient condition to determine a set to be countable or uncountable. That is, DOC establishes a sufficient condition to determine that a set is countable, and DOU establishes a sufficient condition to determine that a set is uncountable.

DOC: If a set can be placed into bijection with N, then it is countable.

And: if a set S is countable, then by definition, there is a bijection between N and S.


DOU: If a set cannot be placed into bijection with N, then it is uncountable.

And, if there exists no bijection between N and an infinite S, then by definition, S is not countable.

There is nothing to be "assumed" or "logically independent". We are simply talking about the definitions of "countably infinite" and "uncountably infinite".


The question that arises is if we have 2 sets that have vastly different properties and they cannot be placed into bijection, is this a proof that the two sets have different cardinal numbers?

Yes, by the definition of "cardinal number". Two sets have the same cardinal if and only if there is a bijection between them.



Is it possible for two sets to have the same cardinal number and there not be a bijection between them? The DOU assumes that it is not possible.

A definition doesn't "assume" anything. It defines a term; and you cannot split it into the "if" and the "only if" part.

Example: We define a set S to be countable if and only if there is a bijection between S and N.



However, DOC and DOU are logically independent of one another, therefore it must be shown that these 2 definitions are consistent with each other before we can say that SD is a valid definition. There is no proof that I am aware of that demonstrates the absolute consistency of the DOC and DOU with respect to all mapping techniques and all possible infinite sets no matter what the differences in properties between the 2 sets. Therefore, we have a definition that may or may not be valid.

Let’s look at this a little deeper. Cantor’s Proof starts out with an arbitrary countable listing of R.

Better: with any function f of N into R.


It then places N into bijection with R.

No, it doesn't. Quite the contrary. It constructs a y which is not in the image of f. Thus f cannot be a bijection.

Are you sure that you understand the concept of a proof by reductio ad absurdum ?

<rest snipped, for being based on the same misunderstanding>

Regards,
HRG.

[Brian]

Hello HRG,
Brian said… The transitive law of equality says that if A=B, and if B=C, then A=C. Notice that the relation established between A and C is completely dependent upon B.

HRG responded… Not so. This is just one way to establish the equality of A and C; there may be others, not dependent on B.You need to help me here. Here is a quote taken from an online encyclopedia ( http://encyclopedia.thefreedictionary.com/Transitive%20property%20of%20equality).
The transitive property states: For any quantities a, b, and c, if a = b and b = c, then a = c.Is this what the Transitive Property/Law says or is it not? Also, you seem to be missing my point. I am not making the point that two sets have to be identical to establish a bijection. Rather, I am saying that there must be a specific minimum relationship between N and X, as well as X and R to conclude anything about N’s ability to index R. X is critical in this regard.
Brian said…The relationship between X and R is that every element in R is an element in X.

HGR responded… Not at all. X is a function with domain N into R. Cantor's proof shows that whatever X, its image cannot be all of R - by establishing a contradiction from the contrary assumption.Then what does step 4 in the proof mean? Surely, r is supposed to be an element common to two sets. When y1 is created, it is by definition an element of R, but it is not an element contained in the listing of R. This listing of R is by definition the set X. You seem to realize this yourself when you speak of the image of X not being all of R. This presupposes that X is a set.
If a set S is countable, by definition there is a function from N onto the whole of S.I realize this, but your point is moot. I have shown that going from step 3 to step 4 in the proof does not establish the needed relationship between N and X. If I do not need all the elements of N to set up this countable index (and I don’t), then when y1 is created it is not enough to establish N’s inability to index R. Of course you go on to say…
Quite irrelevant. Assign any elements of R to the odd numbers, and you get a function on the whole of N. The construction works as above and shows that its image cannot be R.Cantor’s diagonal method only shows that one element in R, namely y1, is not in the listing of X. This listing of X does not ever have to contain every element in N, thus allowing N to easily index y1. This is quite relevant.
You misunderstand the concept of "indexing"; what Cantor's proof is about is simply functions from N into R. Cantor constructs a set made up of R that has |N| elements, and demonstrates that there exists y1 that is not in this set. This set is the set X. What do you think the diagonal method is applied to? It is appied to set X!
Why do you break down a definition ? (2) is still part of the definition of "countable".I broke down the definition to observe the fact that Cantor’s proof relies solely on (2).
And: if a set S is countable, then by definition, there is a bijection between N and S.I realize this. But just declaring something a definition does not make it valid. A definition must be shown to be consistent with all of the other axioms in the system. As such, there is no proof that the DOC and DOU/diagonalization combination are consistent, especially in relation to Cantor’s countable union theorem.
A definition doesn't "assume" anything. It defines a term; and you cannot split it into the "if" and the "only if" part. Example: We define a set S to be countable if and only if there is a bijection between S and N.This completely ignores other axioms in the system such as Cantor’s countable union theorem. Again, you just can't define something as being true without making sure it is consistent with the rest of the system. I can’t define the sum of the angles of a triangle to be 180° in hyperbolic geometry even though it is true in Euclidean geometry. Why? Because it would not be consistent with the other axioms. You just assume the Standard Definition is consistent. Well if it is, then prove it is consistent. Give me a proof that shows that there exists a bijection between N and every countable set. This is what (2) assumes. Just to say it is so is not enough. Could it be possible that there exists a set that cannot be put into bijection with N, yet be shown to be countable by Cantor’s countable union theory? If you say no, then why? If you say because of SD, then you are just arguing in circles. This is precisely what needs to be proved in order to establish the validity of SD.
Are you sure that you understand the concept of a proof by reductio ad absurdum ?Here is my analysis of Reductio Ad Absurdum (http://www.theologyforums.com/forums/showthread.php?s=&threadid=6320). Would you say that I understand it?

Sincerely,

Brian

[mengenlehre]

OK I hear alot about contradiction and cardinality but no one has even mention order. Order is a very important part of this proof. These functions can be made order isomorphic and that changes the whole argument. An order isomorphisms is defined as follows; Let f mapping A to B be a bijection. Then f is order isomorphic provided a<b iff f(a)<f(b). So now you can't play around with sets and create different sizes from the same set.

[mengenlehre]

Our sets are well-ordered. Maybe an example is in order here. First, let N={0,1,2,3,...}.
Next, let k(N)=omega where k(N) is the cardinality of N.
That is, there exists a bijection f from N to omega where omega={0,{0},{0,{0}},...} and omega is an ordinal which is ordered by set inclusion (ie like A iis a subset of B) and N has the usual order less than (<). Here satisfies k
(alpha)=alpha where alpha is an ordinal and this is what makes k(N) a cardinal. Note: omega is the collection all transitive subsets of the empty set=0. Also, we are not using numbers just transitive sets, that is, our sets are ordered by inclusion.

Next, we can write N as the disjoint union of sets as follows
N={0}U{1,3,5,...}U{2,4,6,...}. Let E={2,4,6...} and let O={1,3,5,...}. Then, E is order isomorphic to omega, so
k(E)=omega, and O is order isomorphic to omega, so k(O)=omega as well. Here we are using the order less than < on elements of N but this is really the ordering of transitives sets of omega by inclusion which gets hidden this deep into the proof. And this is my point; We are using several different orders in this example. Size depends on order. Now we just add using ordinal arithmetic to get; k(E)+k(O)=omega+omega=omega*2 (where * is ordinal multiplication and 2={0,1}) and
k(N)=k(E)+k(O) where + is ordinal arithmetic in both cases (see Intro to idependence proofs by Kunen or set theory by Jech). Next, "=" is an equvalence relation for cardinality of sets so omega=k(N)=K(E)+k(O)=omega*2. But, ordinals are ordered by set inclusion so this can never happen. Note that I am using the definitions of both ordinals and cardinals as well as ordinal arithmetic (see Kunen, Jech, or Suppes) and everything is ordered. So, if you don't use the fact that ordinals are ordered sets and cardinals are defined in terms of ordinals in the proof you can proof almsot anything. In mathematics, there are many many details that are not explicity stated in the "simplified" proofs you might find on the internet or even a book. It takes years to understand much less prove complicated theorems. Another comment; There is no mention of the particular model of set theory you are using like ZFC=Zermelo Frankel+Axiom of Choice, or NBG=von Neumann-Bernays-Godel (ortography on the O). You must decide this because it will change the sizes of sets in reference to each other. That is you can construct a model of set theory where k(PP(N))=k(PPPPP(N)) where P(N) is the powerset of N and PP(N) is the powerset of the P(N). Note above that k(P(N))=k(R) where R is the set of reals and this is the ACTUAL statement of Cantor's Theorem (it uses much set theory). There is much more happening in Cantor's proof than just a simple bijection although it may seem that way. I have a final question for Brian. Do you think that R has cardinality greater than N ie is k(R)>k(N)?

[mengenlehre]

As a different approach examine the Cantor set or the complete binary tree. The tree illuminates the fact that the interval [0,1] is uncountable because any path down has k(N) many nodes but at the n'th level (stage) there are 2^n nodes and each of these has k(N) many nodes below it. So I guess you really are saying that k(N)=k(R). So I have just found k(N) many nodes below the n'th level and this is only one path. There are k(P(N)) many paths in all because at each level there are 2^n nodes. This is just common sense really, No math just a picture ie the Cantor Tree. Remember we are just looking at [0,1] but [0,1]~R.

[mengenlehre]

All mathematics to date occurs in ZFC and the continuum hypothesis is independent of this. So there simply is no inconsistency.

The "thing" your missing is the way things were defined (by Cantor) to begin with. See my example below.
This transitive law you speak of is an equivalence relation on cardinals which is defined in terms of order-types of ordinals (ie transitive well-ordered sets that is they are ordered by inclusion).




Hello Guys,

I have not posted to this board in a long time. However, this is a topic that I find very fascinating. As such, I will be happy to pick this thread back up.



I am going to begin with my version of Cantor's proof. Note: the symbol "<>" means "is an element of," and it's negation is indicated by the symbol "~<>".


Step 1) Prove A: R is uncountable.
Step 2) Assume ~A: R is countable.
Step 3) ~A-->B(1): N can index R.
Step 4) B(1)-->B(2): There exists an enumeration of R, say X, such that if r <> R, then r <> X.
Step 5) B(2)-->~B(2): By the diagonal method, y1 is created such that y1<>R, but y1 ~<> X.
Step 6) ~B(1) by Modus Tollens.
Step 7) ~~A by Modus Tollens.
Step 8) A by law of negation.
Q.E.D.

In order to show that R is not countable, we must show that N cannot index R. In the above proof this is proved indirectly by MT from step 5 to step 6. But does this really follow? I submit that the implication from step 3 to step 4 is not sufficient, and as a result when y1 is created in step 5, it says nothing about N's ability to index R.

The transitive law of equality says that if A=B, and if B=C, then A=C. Notice that the relation established between A and C is completely dependent upon B. Also notice that the relationship of A and C to B must be clearly defined in order to make any necessary conclusions concerning the relationship between A and C. In Cantor's proof we have three sets under consideration: N, X, and R. The relationship between N and R is established by the relationship of N to X, and X to R. In order to demonstrate that N cannot index R, the relationship between N and X, and X and R must be sufficient to necessarily draw this conclusion. Are these relationships sufficiently defined to establish the conclusion that N cannot index R? The answer is no. The relationship between X and R is that every element in R is an element in X. This relationship is sufficiently clear to draw the necessary conclusions of Cantor's proof, IF the relationship between N and X is the same, i.e. X is a listing utilizing every element of N as the index. However, this does not necessarily follow from the assumption that R is countable.

In order to show that R is countable X only needs to contain |N| elements. That is, the relationship between N and X is defined to be that X utilizes |N| elements from the set N, but not necessarily every element from the set N! (If you need all of the elements N, then you do not need them all.) We can enumerate R utilizing only the even numbers, and this would be sufficient to show a complete enumeration that is countable because the even numbers have |N| elements. This would leave us with an infinite number of elements in N (i.e. the odd numbers) that are still available for further indexing. That is to say, the relationship between N and X is such that if there is an element y1 not contained in X but contained in R it says nothing about N's ability to index R! This means that the needed relationship between X and N for Cantor's proof to be valid is NOT a necessary consequence (implication) from the assumption ~A or B(1). Therefore, since the relationship between N and X is insufficient, we cannot conclude anything about the relationship between N and R in terms of indexing.

If all of the implications drawn from Cantor's proof follow, then by MT we should be able to conclude that N cannot index R. However, it has been shown that the relationship between N and X is not sufficient for these implications to follow. What is the problem? The problem with Cantor's proof starts right at the beginning with its use of a definition that is not consistent with itself (or at least has not been proven consistent with itself). The following ideas are taken from the non-published paper, Hinged Sets and the Answer to the Continuum Hypothesis (http://pages.sbcglobal.net/webster.kehr/files/Continuum.pdf), by R. Webster Kehr.

Countable: A set is countable if and only if its cardinality is either finite or equal to Ào.

This leads us to another definition for countablilty namely...

The Standard Definition of Countable (SD): A set is countable iff it can be placed into bijection with N.

Because our standard definition is a material implication (i.e. an if and only if statement), then it can be broken down in to the following 2 implications:

(1) If a set can be placed into bijection with N, then it is countable.
(2) If a set it countable, then it can be placed into bijection with N.

Statement (1) I find to be obviously true. For the sake of distinction, I would like to call (1) the "Definition of Countable (DOC)." Statement (2) is logically independent of (1). In other words, the validity of DOC does not imply the validity of (2). The contrapositive of A-->B is ~B-->~A, and is logically equivalent to A-->B. The contrapositive of (2) is "if a set cannot be placed into bijection with N, then it is uncountable." Again, for the sake of distinction, I would like to refer to this as the "Definition of Uncountable (DOU)." That would make (2) the contrapositive of DOU, i.e. CDOU. Therefore, SD consists of 2 logically independent implications, DOC and DOU. From this we now have a definition that provides a sufficient condition to determine a set to be countable or uncountable. That is, DOC establishes a sufficient condition to determine that a set is countable, and DOU establishes a sufficient condition to determine that a set is uncountable.

DOC: If a set can be placed into bijection with N, then it is countable.
DOU: If a set cannot be placed into bijection with N, then it is uncountable.

The question that arises is if we have 2 sets that have vastly different properties and they cannot be placed into bijection, is this a proof that the two sets have different cardinal numbers? Is it possible for two sets to have the same cardinal number and there not be a bijection between them? The DOU assumes that it is not possible. However, DOC and DOU are logically independent of one another, therefore it must be shown that these 2 definitions are consistent with each other before we can say that SD is a valid definition. There is no proof that I am aware of that demonstrates the absolute consistency of the DOC and DOU with respect to all mapping techniques and all possible infinite sets no matter what the differences in properties between the 2 sets. Therefore, we have a definition that may or may not be valid.

Let’s look at this a little deeper. Cantor’s Proof starts out with an arbitrary countable listing of R. It then places N into bijection with R. Why does it do this? DOU states: If a set cannot be placed into bijection with N, then it is uncountable. The contrapositive of this is CDOU: If a set is countable, then it can be placed into bijection with N. Notice that the Cantor’s Proof relies on CDOU and not DOC. Once this list has been compiled we ask the question, “Is every element of R in this countable listing?” To answer this Cantor creates his CDN (Cantor's Diagonal Number) that is an element of R, but which is not mapped to by any element in N. Since no specific element of N maps to the CDN, and because the CDN is an element of R, then R cannot be placed into bijection with N. At this point Cantor uses the DOU and concludes that R is uncountable. Note that Cantor’s proof relies entirely on DOU (CDOU and DOU are logically equivalent). Cantor uses CDOU to set up the original assumption that if R were countable, then it could be placed into bijection with N. It then uses the DOU when it is determined that no specific element of N maps to the CDN. If DOU were not available to Cantor’s proof, then diagonalization by itself is not sufficient to prove that R is uncountable.

If we consider this initial listing of R, then diagonalization divides R into 2 disjoint sets: 1) the set of all elements that maps to N, and 2) the compliment of (1) that makes up the rest of R. The CDN is in the second set. Notice this second set is not empty (it includes the CDN), and we also know this set to be infinite. However, infinite does not mean uncountable. The key to determine the cardinality of R lies in determining the cardinality of the second set! If the second set is uncountable, then obviously R is uncountable. However, if the second set is countable, then by Cantor’s Countable Union Theorem (CUT) all of R is countable. Here is the interesting thing, the CUT is based on the DOC which is obviously true! It is a variation of the CUT that I use above in my argument for why there is not a proper relationship defined between N and X. However, Cantor's proof is based solely on the DOU.

Here is the point to all of this. Given any countable listing of R elements, a CDN can be constructed. But the question is, “By using different algorithms, how many unique CDNs can be constructed?” The DOU says that an uncountable number can be created. However, the DOU is a definition and not a mapping technique! The DOU by itself does not prove anything. The DOU must be paired with a mapping technique. Cantor’s proof pairs the DOU with diagonalization. Thus the combination of DOU and diagonalization must be valid. By using the DOU/diagonalization combination, Cantor assumes that this combination cannot “work” (i.e. prove the lack of a bijection with N) on any countable set. But this has never been proved! The DOC and DOU/diagonalization combination are clearly logically independent and it has never been proven that the set of all sets that are the same “size” as N and the set of all sets in bijection with N are the same set. There is no proof that the DOC and DOU/diagonalization combination are consistent. Cantor’s proof depends heavily on a definition that has never been shown to be logically or mathematically consistent with the obviously valid definition of the DOC. Cantor assumes that it is true, and this assumption leads to the assumption that when R is indexed by N, N must use every element in N to index it (i.e. there exists a bijection between N and R). However, this does not follow from the DOC and CUT, which allows us to say, "If you need every element of N, then you don't need them all."

In conclusion, Cantor's Proof assumes DOU is true (a definition that has not been proved), ignores DOC (a definition that obviously is true), and assumes that all sets are actual. This is in addition to his original assumption that R is countable. According to the rules of Reductio Ad Absurdum, Cantor can make no claim one way or the other concerning the countability of R because of his multiple assumptions. Because of DOC and CUT, it does not necessarily follow that if N can index R, there exists a bijection between N and R. This is the assumption made from step 3 to step 4 of the Cantor's proof. Disregarding the assumption that all sets are actual, what Cantor does prove is that DOU and R being countable cannot both be true.

Sincerely,

Brian

[Brian]

Hello mengenlehre,

Thank you for your thoughtful post.
There is no mention of the particular model of set theory you are using like ZFC=Zermelo Frankel+Axiom of Choice, or NBG=von Neumann-Bernays-Godel (ortography on the O).First off, I am trying to look at Cantor’s proof through his perspective. Certaintly, set theory was at its infancy. I think you make a valid point, so let me identify the following definitions I am using, which would be the same definitions Cantor used. (Note: this was taken from Peter Suber’s Website. (http://www.earlham.edu/~peters/writing/infapp.htm))

Set: A set is a collection of elements. So if set S contains elements A, B, and C, then we say S = {A, B, C}. The null set is the empty set or the set with no members. Therefore, Ø = {}.

Subset: Set A is a subset of set B if and only if all the members of A are also members of B.

Proper Subset: Set A is a proper subset of set B if and only if all the members of A are also members of B, but not all the members of B are members of A.

Cardinality: The cardinality of a set is the number of members it contains. The cardinality of set S is |S|. For example, if S = {A, B, C}, then |S|=3. While S is a set, |S| is a number. When S is an infinite set, |S| will be an infinite number.

One-to-one Correspondence: Two sets can be put into one-to-one correspondence if and only if their members can be paired off such that each member of the first set has exactly one counterpart in the second set, and each member of the second set has exactly one counterpart in the first set.

(Note: Putting two infinite sets into one-to-one correspondence is an infinite task, and we don't pretend that we can do it (that is, finish it) in finite time. To show that an infinite set, like the even numbers, can be put into one-to-one correspondence with another, like the odd numbers, we need only produce a rule-governed sequence for each set which runs through the members without omission or repetition, for example, 2, 4, 6... and 1, 3, 5.... If we can do so, then we know that the nth term of one sequence will have a counterpart in the nth term of the other, and vice versa, guaranteeing one-to-one correspondence all the way out.)

Same Cardinality: Two sets have the same cardinality if and only if they can be put into one-to-one correspondence; i.e., |A| = |B|.

Power Set: The power set of a set S is the set of all the subsets of S. The power set of S is *S. For example, if S = {A, B, C}, then *S = {{A,B,C}, {A,B}, {A,C}, {B,C}, {A}, {B}, {C}, Ø}. The power set of a given set always contains the given set itself and the null set.

Natural Numbers: The natural numbers are the whole positive numbers (sometimes called the "counting numbers"), including zero: 0, 1, 2, 3 .... The set of natural numbers is designated by N. The number of natural numbers is designated by Ào, called Aleph-null.

Integers: The integers are the natural numbers plus their negative counterparts, ...-3, -2, -1, 0, 1, 2, 3.... The set of integers is designated by Z.

Rational Numbers: The rational numbers are the integers plus the rational fractions (those that can be expressed as the ratio of two integers). The set of rational numbers is designated by Q. For example, 0.75 is a rational fraction because we can express it as the ratio of two integers, namely, 3/4. Therefore it is a rational number.

Irrational Numbers: The irrational numbers are the fractions that are not rational numbers, both positive and negative. For example, we can prove that pi (3.14159...) cannot be expressed as the ratio of two integers. Therefore it is an irrational number.

Real Numbers: The real numbers are the rational numbers plus the irrational numbers. The set of real numbers is designated by R.

Countable: A set is countable if and only if its cardinality is either finite or equal to Ào.

Denumerable: A set is denumerable if and only if its cardinality is exactly Ào. A denumerable set is a countable set.

Uncountable: A set is uncountable if and only if its cardinality is greater than Ào. The infinite set, N, is countable and denumerable. Sets with a larger cardinality than N are uncountable.

Real Numbers: The real numbers are the rational numbers plus the irrational numbers. The set of real numbers is designated by R.
There is much more happening in Cantor's proof than just a simple bijection although it may seem that way.I couldn’t agree more, and as such I plan on breaking down Cantor’s proof so we can see what really is going on. From this, I think I can prove that the diagonal method does not establish the uncountability of R, and that the standard definition for countability is not valid.
I have a final question for Brian. Do you think that R has cardinality greater than N ie is k(R)>k(N)?No, I don’t. I mentioned Webster Kehr’s paper to you earlier. In it he provides a proof for the countibility of R. If time permits, and we get that far I intend to explain the proof. Let me know if the folowing definitions are sufficient to continue. Note: I do not agree with all of the definitions, but will assume the burden of arguing for my position. Again, thank you for engaging me like this.

Sincerely,

Brian

[mengenlehre]

Hey Brian, I read your comments and would like to respond but first let me point out something from Peter Suber's website. It is found at the very bottom and is as follows;

Bibliographic note. Most of the theorems and proofs in this crash course were discovered by Georg Cantor (1845-1918) and published in a series of monographs starting in 1870. He published two summary statements of his results in 1895 and 1897, which have been translated into English by Philip E. B. Jourdain as Contributions to the Founding of the Theory of Transfinite Numbers, Dover Publications, 1955. My exposition of Cantor's results is indebted to three more recent authors: Stephen Cole Kleene, Introduction to Metamathematics, North-Holland Pub. Co., 1952; Abraham Fraenkel, Abstract Set Theory, North-Holland Pub. Co., 1953; and Geoffrey Hunter, Metalogic, University of California Press, 1971.

Note he says that "My exposition of Cantor's results is indebted to three more recent authors: ..."
Note also he says "a crash course."
So your definitions are not correct they are just simplified versions of the real definitions which are all stated in the formal language called symbolic logic which is a sub-branch of formal logic which is a sub-branch of logic which is a sub-branch of philosophy. There is also a branch of math called mathematical logic which uses symbolic logic to describe mathematical "stuff." Your definitions lead to contradictions and so we must use formal logic.

All known mathematics occurs within ZF which is a model of set theory. By model, I mean that a model, say M, was constructed using only formal logic which in turn uses only the following symbols; and, not, there exists, ), (, =, and a variable, say vi, with a subscript i (ie an index) which comes from N the natural numbers. Nothing else is used except logic and all axioms and definitions are stated in the formal language. Many things must be proven to produce a model like ZF. This topic belongs to the subject of model theory or MT which is related to set theory but properly belongs to philosophy/logic.

ZF and ZFC use the following axioms and you should note that Suber only mentions one. The ten axioms of ZFC are listed below. (Strictly speaking, the axioms of ZFC are just strings of logical symbols. What follows should therefore be viewed only as an attempt to express the intended meaning of these axioms in English. Moreover, the axiom of separation, along with the axiom of replacement, is actually an infinite schema of axioms, one for each formula.) Each axiom has further information in its own article.


Axiom of extensionality (http://en.wikipedia.org/wiki/Axiom_of_extensionality): Two sets are the same if and only if they have the same elements.
Axiom of empty set (http://en.wikipedia.org/wiki/Axiom_of_empty_set): There is a set with no elements. We will use {} to denote this empty set.
Axiom of pairing (http://en.wikipedia.org/wiki/Axiom_of_pairing): If x, y are sets, then so is {x,y}, a set containing x and y as its only elements.
Axiom of union (http://en.wikipedia.org/wiki/Axiom_of_union): For any set x, there is a set y such that the elements of y are precisely the elements of the elements of x.
Axiom of infinity (http://en.wikipedia.org/wiki/Axiom_of_infinity): There exists a set x such that {} is in x and whenever y is in x, so is the union y U {y}.
Axiom of separation (http://en.wikipedia.org/wiki/Axiom_of_separation) (or subset axiom): Given any set and any proposition (http://en.wikipedia.org/wiki/Predicate_(logic)) P(x), there is a subset (http://en.wikipedia.org/wiki/Subset) of the original set containing precisely those elements x for which P(x) holds.
Axiom of replacement (http://en.wikipedia.org/wiki/Axiom_of_replacement): Given any set and any mapping (http://en.wikipedia.org/wiki/Functional_predicate), formally defined as a proposition P(x,y) where P(x,y) and P(x,z) implies y = z, there is a set containing precisely the images of the original set's elements.
Axiom of power set (http://en.wikipedia.org/wiki/Axiom_of_power_set): Every set has a power set (http://en.wikipedia.org/wiki/Power_set). That is, for any set x there exists a set y, such that the elements of y are precisely the subsets of x.
Axiom of regularity (http://en.wikipedia.org/wiki/Axiom_of_regularity) (or axiom of foundation): Every non-empty set x contains some element y such that x and y are disjoint sets (http://en.wikipedia.org/wiki/Disjoint_sets).
Axiom of choice (http://en.wikipedia.org/wiki/Axiom_of_choice): (Zermelo's version) Given a set x of mutually disjoint nonempty sets, there is a set y (a choice set for x) containing exactly one element from each member of x.
ZF is 1-9
ZFC is 1-10

The axiom of choice is commonly abbreviated to AC.
In 1935 Gödel showed that ZFC is consistent if ZF is.
In 1963 Cohen showed that ZF + ¬AC is consistent if ZF is.
Therefore, AC is independent of ZF.

The model L of ZFC (Godel):
LL is a model of ZFC due to Gödel; defined as follows:-
L0 = ∅; if α is a limit ordinal then Lα = ∪β<α Lβ
L = ∪α ∈ ON Lα
The idea behind L is to build a class of "definable" sets.

Excerpt from Suber:This is not a proof in ZF!
Theorem 4. The cardinality of the power set of an arbitrary set has a greater cardinality than the original arbitrary set, or |*A| > |A|. This is called simply Cantor's Theorem. It generalizes the previous theorem, in which we proved that the power set of a particular set, N, had a greater cardinality than the original. The present theorem is trivial for finite sets, but is fundamental for infinite sets.
<LI>Proof. Let A be an arbitrary set of any cardinality, finite or infinite. Again we supply a negative proof, and assume that the members of A can be put into one-to-one correspondence with the subsets of A. Take any one of the supposed ways of pairing off the members of A with the subsets of A. Let us say that if a member of A is paired with a subset of A of which it happens to be a member, then it is happy; otherwise it is sad. Let S be the set of sad members of A. Clearly S is one of the subsets of A. Therefore S is paired off with one of the members of A, say, x. Is x happy or sad? If x is happy, then x is a member of the set to which it is paired, which is S, but that would make it sad. If x is sad, then x is not a member of the set to which it is paired, which is S, but that would make it happy. So if x is happy, then it is sad, and if it is sad, then it is happy. Our assumption implies a contradiction and is therefore false. So the members of A cannot be put into one-to-one correspondence with the subsets of A.

But if A and *A cannot be put into one-to-one correspondence, then they cannot have the same cardinality. If so, then the larger one must be *A, for A can be put into one-to-one correspondence with a proper subset *A. For example, if the members of A are A1, A2, A3..., then they can be put into one-to-one correspondence with this subset of *A: {{A1}, {A2}, {A3}...}. I can assure you Cantor's proofs look nothing like this. In proving things about sets you actually have to construction the required function then show it is well-defined, 1:1, and onto. Those indices you mention in your post are really functions. Functions are, as with everything else we do in axiomatic set theory, defined using formal language. See the definition of a function in one of the references.

Another point about Suber's website. The statement at the beginning;
Don't be surprised if this is easier than you thought. Set theory requires no algebra or calculus. It is much more primitive than those branches of mathematics, and rests on very simple notions. Moreover, the proofs will be unusually short and uncomplicated.

This is False!! I have studied mathematics and philosophy for many years and set theory is, and most experts agree, one of the more difficult abstract areas of mathematics but probably not the most difficult. I think Suber's efforts are going toward explaining something difficult in simplier terms with shortcut notation. Which is fine for a brief look at sets which sound weird to most people. It is a good website for this purpose only though. What you want to do will take years provided you do it with thoroughness and rigor. Let me state that axiomatic set theorists do not in any circumstance use shortcut notation when proving results. Shortcut notation only shows up in books for subjects mostly taught at a lower level. I have suggestions for some books and Suber has some as well listed above.
The books are listed in order of importance as follows;

1) Set Theory: An introduction to independence proofs
K. Kunen ISBN:0-444-85401-0
2) Set Theory by T. Jech 3rd edition ISBN:3-540-44085-2
3) Symbolic Logic by V. Klenk ISBN:0-13-0201142-1
Dr. Klenk is a philosopher.
4) An introduction to mathematical logic by R. Hodel
ISBN:0-534-94440-X Dr. Hodel is a mathematician.
5) Axiomatic Set Theory by P Suppes ISBN:0-486-61630-4
Dr. Suppes is a Philosopher and Statistician.
A good link to many Set Theorist:
http://www.math.ufl.edu/~jal/set_theory.html

Below are problems which arise when trying to prove results about sets without using a formal language:

Probably the best known of all problems with infinite classes (or collections or aggregates...) is that due to Bertrand Russell (http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Russell.html).

Russell pre-supposed that it is possible to construct a Class of all Classes. Clearly it can be partitioned into two subclasses:
(a) Those classes which are not members of themselves.
(b) Those classes which are members of themselves.

He then asked into which class (a) itself should be allocated. If it is placed into class (a) then (a) would be a member of itself - but class (a) is specifically reserved for classes which are not members of themselves.

However, if we place class (a) in (b) we find that the opposite is true - (a) is not a member of itself - but class (b) is specifically reserved for classes which are members of themselves.

So we have the problem that there are for classes which we cannot say whether they contain themselves - or not. This is a true logical paradox; but one way we can avoid it is to specify that we will only deal with sets as these have the property that they are never members of themselves. Non-sets (proper classes) are of strictly limited utility for other than descriptive purposes.

Of course it could be argued that a proper class is simply "too big" to be dealt with in a logical manner or that the use of the word "all" in the phrase "Class of all Classes" is flawed in the sense that it is difficult to attach a definite meaning to it.


Another use of the word "all" occuring in connection with infinite sets gives the Burali-Forti paradox.

An ordinal (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal) is a special kind of set. So the class of all ordinals (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal), Ω, must exist and it will be an ordinal (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal) itself - obviously the largest of all the ordinals (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal). However, since Ω is an ordinal (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal) we can form the ordinal (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal) Ω + 1. Since Ω + 1 > Ω, we must conclude that Ω is not the class of all ordinals (http://www.jboden.demon.co.uk/SetTheory/glossary.html#ordinal) after all.....

The main problem arises because we are trying to treat proper classes as sets. Sets have the property that they are never members of themselves. This precludes consideration of a class of "all" sets with a particular property.

[mengenlehre]

At the following link you will find the axioms of ZFC written in formal language.

http://metamath.flatline.de/mpegif/mmzfcnd.html

I will give more links as we proceed.

[Brian]

Hello mengenlehre,

I really appreciate the time and effort you have put in to your last couple of posts. I am ignorant of modern set theory, however I am a quick learner, and your 10 axioms for ZF and ZFC are most helpful. I will take the time to understand them. However, the extent of my knowledge has come from Peter's site, as well as from my subsequent studies of Cantor's diagonal theorem. I believe I have a solid understanding of the theorem as Cantor understood it. Cantor's proof was formulated prior to modern axiomatic set theory. My beef is with Cantor's diagonal proof as he formulated it. That is the play ground I want to play on. Would you be willing to go with me on this?

Sincerely,

Brian

[mengenlehre]

Yes, of course Brian, I will work within the limits you are proposing. And, don't worry, set theory is complex and I am no expert either even though I have been studying it for sometime. Necessarily, as a part of learning, each time I tackle a new subject, I am starting over in a sense and must grasp new and different ideas. Never the less, I do enjoy a challenge.

[HRG_new]

Hello HRG,You need to help me here. Here is a quote taken from an online encyclopedia ( http://encyclopedia.thefreedictionary.com/Transitive%20property%20of%20equality).Is this what the Transitive Property/Law says or is it not?

Yes, but that's not my point. Please read again what I wrote.




Also, you seem to be missing my point. I am not making the point that two sets have to be identical to establish a bijection. Rather, I am saying that there must be a specific minimum relationship between N and X, as well as X and R to conclude anything about N’s ability to index R. X is critical in this regard.

This minimal requirement is simply that X is a function with domain N and into R. Cantor's proof shows that the image of X cannot be all of R - by constructing from a given X an element of R which is not in this image.

Thus there does not exist a map of N onto the whole of R, which means that R is not countable.



Then what does step 4 in the proof mean? Surely, r is supposed to be an element common to two sets. When y1 is created, it is by definition an element of R, but it is not an element contained in the listing of R. This listing of R is by definition the set X. You seem to realize this yourself when you speak of the image of X not being all of R. This presupposes that X is a set.

A specific set: a function from N into R

I realize this, but your point is moot. I have shown that going from step 3 to step 4 in the proof does not establish the needed relationship between N and X. If I do not need all the elements of N to set up this countable index (and I don’t), then when y1 is created it is not enough to establish N’s inability to index R. Of course you go on to say…Cantor’s diagonal method only shows that one element in R, namely y1, is not in the listing of X. This listing of X does not ever have to contain every element in N, thus allowing N to easily index y1. This is quite relevant.
[/quote]
Not at all. We start by assuming that X is a map with domain N; thus, using your language, every element of N has already been used up as an index.



Cantor constructs a set made up of R that has |N| elements, and demonstrates that there exists y1 that is not in this set.

That's not all by far. He proves that for every subset of R with |N| element, there is an y1 in R which does not belong to the subset. The essential point is that the function X can be arbitrary.


This set is the set X. What do you think the diagonal method is applied to? It is appied to set X!

No. It is the image of X. X is any function from N into R, thus not a subset of R.


I broke down the definition to observe the fact that Cantor’s proof relies solely on (2).I realize this. But just declaring something a definition does not make it valid. A definition must be shown to be consistent with all of the other axioms in the system.

What do you mean by "consistent" ? A definition is consistent if there is at least one object which satisfies it. Since there are countable sets, the definition of "countable" is consistent.



As such, there is no proof that the DOC and DOU/diagonalization combination are consistent, especially in relation to Cantor’s countable union theorem.This completely ignores other axioms in the system such as Cantor’s countable union theorem.
[quote]
Since "countable union" depends on the definition of "countable", the definition is certainly consistent with it.
[quote]

Again, you just can't define something as being true without making sure it is consistent with the rest of the system. I can’t define the sum of the angles of a triangle to be 180° in hyperbolic geometry even though it is true in Euclidean geometry.

No, because "sum", "angles", "triangles" etc. have already been defined. But "countable" hasn't: its definition comes early in the presentation of set theory and just means "is the image of some function with domain N".



Why? Because it would not be consistent with the other axioms. You just assume the Standard Definition is consistent. Well if it is, then prove it is consistent. Give me a proof that shows that there exists a bijection between N and every countable set.

That's the definition of "countable" (more accurately, "countably infinite"). Asking for a proof is as ridiculous as asking for a proof that prime numbers have no non-trivial divisors; that's the definition of "prime number", after all.



This is what (2) assumes. Just to say it is so is not enough. Could it be possible that there exists a set that cannot be put into bijection with N, yet be shown to be countable by Cantor’s countable union theory?

If you refer to Cantor's theorem that a countable union of countable sets is countable, the answer is a resounding NO. You might look up the Schröder-Bernstein theorem in this context.

Regards,
HRG.

[mengenlehre]

Brian said "In order to show that R is countable X only needs to contain |N| elements. That is, the relationship between N and X is defined to be that X utilizes |N| elements from the set N, but not necessarily every element from the set N! (If you need all of the elements N, then you do not need them all.) "

I want to point out that if f maps N to X, then by the "DEFINITION" of a function Every point in N is used. This is what it means to be a function.
So in a mathematical proof if I say "Let F map N to X such that..." there is no question as to whether F is a function.

You cna't just ignore the definitions. Everything and I do mean everything depends on the definition.

[Brian]

Hello mengenlehre, (and HGR?)
Brian asked… Could it be possible that there exists a set that cannot be put into bijection with N, yet be shown to be countable by Cantor’s countable union theory?

HGR replied…If you are referring to Cantor’s theorem that a countable union of countable sets is countable, the answer is a resounding NO.

Gentlemen, this is the rub. We have a couple of ways to establish whether or not a set is countable. We have the standard definition (SD), which is made up of two logically independent implications, and Cantor’s countable union of countable sets theorem (CUT). These separate ways are assumed to be consistent. There has never been a proof showing this consistency. Forgive me for going over such a basic concept, but I want to show the logical independence of CUT and SD. As I have already stated, SD is made up of two logically independent implications…

DOC: If a set can be placed into bijection with N, then it is countable.
DOU: If a set cannot be placed into bijection with N, then it is uncountable.

Cantor’s proof relies solely on DOU. The assumption DOU makes is that there does not exist a countable set that cannot be put into bijection with N. It is fine to declare this to be the definition, but it ignores another definition or axiom already a part of the system. That specifically is CUT. CUT determines countability independently of DOU. CUT relies solely on DOC, and it does not necessarily follow that that for all countable sets, the union of these sets can be placed into bijection with N (apart from the gratuitous assumption of DOU). My ultimate purpose is to divide R into two sets, both of which can be shown to be countable by DOC, and then because of CUT, conclude R is countable.

As mengenlehre has already mentioned, there is a lot going on in Cantor’s diagonal proof. What I would like to do is break this proof down so we can see what is actually taking place. To begin, allow me to present my version of Cantor’s proof for your acceptance.

The Diagonalization Theorem (DT)

The DT starts out by stating, “Given any countable listing of R(0,1)…” It then places N in bijection with this set. The justification for doing this is CDOU (the contrapositive of DOU), which states, “If a set is countable, then the set can be placed into bijection with N.” For example:


N Symbol A Countable Subset of R(0,1)
1 π/10 .314159265…
2 5/9 .555555555…
3 1/2 .500000000…
4 1/e .367879441…
…
At this point we ask, “Can every element of R(0,1) be in this countable subset?” To answer this question DT creates (or discovers) an element of R(0,1), the NN (new number), which is not mapped to any element N. It does this with a sequence and algorithm. I will use the following algorithm: “If the nth digit of the nth element of the list is not a ‘5,’ then the nth digit of the NN will be a ‘5,’ otherwise the nth digit of the NN will be a ‘6.’” Using this algorithm we come up with a NN of .5655… Since no specific element of N taken from the listing maps to the NN, N cannot map onto all of the elements of the listing. This means that R(0,1) cannot be placed into bijection with N. At this point DT uses DOU concluding that R(0,1) is uncountable.

Once again, I want to note that DT depends entirely on DOU (CDOU). The DT uses CDOU to set up the original assumption that if R(0,1) were countable, then it could be placed into bijection with N. It then uses DOU when it is determined that no specific element of N maps to the NN. I will stop here for now. Let me know if you are ok with what has been said here.

Sincerely,

Brian

[mengenlehre]

The defintions used by Cantor
To say A is a set really means there exists a Y such that for every x in X P(x) is true. So when we define sets we must keep in mind that we can't allow values of x for which P(x) is "both" true and false at the same time.
Hence, the empty set 0 is the statement for every x, x is not equal to x. ie 0={x:x!=x} where != means not equal. Hence 0={ } ie the set with no elements. This set is unique. If A is a set then x in A means x is an element of A.

Definition: The cartesian product of any two sets A and B, denoted AxB, is the set{(x,y): x in A and y in B}.
That is AxB={(x,y): x in A and y in B}.

Definition: A relation R is a subset of AxB. Note; it does not say R=AxB but only R<AxB where < means subset. A relation is a set of ordered pairs from AxB.

Definition: A function from a set A into a set B is a relation f<AxB (ie is a set of "ordered" pairs which are elements of the set AxB) such that for every x in A there exists a y in B such that (x,y) is in f. Here, A is the domain and B is the codomain of f and < means is a subset. The range of f, denoted f(A) or ran(f) and sometimes called the image, is the set {f(x):x is in A}. Note that ran(f) is not always equal to B. This is very important for our discussion. The pre-image of V<B is the set {x: f(x) in V}.

Definition: A function f mapping A into B is called one-to-one or 1:1 (also called injective) provided: For every x,z in A if f(x)=f(z), then x=z. Note f being 1:1 means if (x,y) in f then (y,x) in f whenever A=B.

Definition: A function f mapping A into B is called onto (also called surjective) provided: For every y in B there exists an x in A such that y=f(x). Note y=f(x) is written with y first because we must let y be arbitrary in order to prove onto since it must hold for every y in B. As a short cut if we need an onto function we just say let f A map onto B. This says f is a function and f is onto but not necessarily 1:1. Note onto is just the statement if (y,x) in f, then (x,y) in f whenever A=B.

A function f from A into B is called a bijection iff f is 1:1 and onto. In this case we have a nice function with the following property. (x,y) in f iff (y,x) in f whenever A=B. Here iff has the usual meaning if and only if (ie logical eqivalence).

Finally some shortcuts; Think of functions like this if f maps A into B, then for x in A (x,f(x)) in ran(f). So we can just refer to f(x) but when we do this we understand (ie from above) that there must be an x in A for this to make sense.

Helpful properties: Let f map A into B. Then if U ,V <A and U<V, then f(U)<f(V). This one can be helpful.
I will continue to post definitions as we need them provided this is necessary.

[Brian]

Thank you for the definitions mengenlehre. I follow them. Did you get a chance to see my previous post? Are you ok with it?

Sincerely,

Brian

[HRG_new]

Hello mengenlehre, (and HGR?)

Gentlemen, this is the rub. We have a couple of ways to establish whether or not a set is countable. We have the standard definition (SD), which is made up of two logically independent implications, and Cantor’s countable union of countable sets theorem (CUT). These separate ways are assumed to be consistent. There has never been a proof showing this consistency.

False.



Forgive me for going over such a basic concept, but I want to show the logical independence of CUT and SD. As I have already stated, SD is made up of two logically independent implications…

DOC: If a set can be placed into bijection with N, then it is countable.
DOU: If a set cannot be placed into bijection with N, then it is uncountable.
[quote]
1. DOC and DOU are not independent. They are two sides of the same coin: the definition of "countably infinite":

A set is countably infinite if and only if it can be put into a bijection with N.

(It can be shown that this is the "smallest existing" infinity: every infinite set contains a countably infinite subset).

2. CUT is a theorem which can be proven by Cantor's First Diagonalization technique.
[quote]

Cantor’s proof relies solely on DOU. The assumption DOU makes is that there does not exist a countable set that cannot be put into bijection with N. It is fine to declare this to be the definition, but it ignores another definition or axiom already a part of the system. That specifically is CUT. CUT determines countability independently of DOU.

CUT is a theorem, not a definition. It is based on DOU+DOC.


CUT relies solely on DOC, and it does not necessarily follow that that for all countable sets, the union of these sets can be placed into bijection with N (apart from the gratuitous assumption of DOU). My ultimate purpose is to divide R into two sets, both of which can be shown to be countable by DOC, and then because of CUT, conclude R is countable.

And I'm afraid you won't succeed :)


As mengenlehre has already mentioned, there is a lot going on in Cantor’s diagonal proof. What I would like to do is break this proof down so we can see what is actually taking place. To begin, allow me to present my version of Cantor’s proof for your acceptance.

The Diagonalization Theorem (DT)

The DT starts out by stating, “Given any countable listing of R(0,1)…” It then places N in bijection with this set. The justification for doing this is CDOU (the contrapositive of DOU), which states, “If a set is countable, then the set can be placed into bijection with N.”

For the n-th time, this is the definition of countably infinite, not a contraposition of anything.


For example:


N Symbol A Countable Subset of R(0,1)
1 π/10 .314159265…
2 5/9 .555555555…
3 1/2 .500000000…
4 1/e .367879441…
…

At this point we ask, “Can every element of R(0,1) be in this countable subset?” To answer this question DT creates (or discovers) an element of R(0,1), the NN (new number), which is not mapped to any element N. It does this with a sequence and algorithm. I will use the following algorithm: “If the nth digit of the nth element of the list is not a ‘5,’ then the nth digit of the NN will be a ‘5,’ otherwise the nth digit of the NN will be a ‘6.’” Using this algorithm we come up with a NN of .5655… Since no specific element of N taken from the listing maps to the NN, N cannot map onto all of the elements of the listing. This means that R(0,1) cannot be placed into bijection with N. At this point DT uses DOU concluding that R(0,1) is uncountable.

Once again, I want to note that DT depends entirely on DOU (CDOU). The DT uses CDOU to set up the original assumption that if R(0,1) were countable, then it could be placed into bijection with N. It then uses DOU when it is determined that no specific element of N maps to the NN. I will stop here for now. Let me know if you are ok with what has been said here.

Fine. Now you just have to realize that DOU and DOC are not independent: together they make up the definition of "countably infinite".

("Countable" is sometimes defined as "in bijection with some subset of N" and thus includes all finite sets)

Regards,
HRG.

[Brian]

Hello Gentlemen,
Brian said...These separate ways are assumed to be consistent. There has never been a proof showing this consistency.

HRG responded...False.It really does not help the discussion by just saying I am wrong. If there is a proof showing the consistency between DOC, CUT, and DOU, then it would be a real service for you to provide it.

It seems as if HRG is OK with my formulation. He objects to my breaking up the SD into it's logically independent parts of DOU and DOC. However, because they are logically independent, and until he can provide the proof for their consistency, I will continue to do so. Why? Because DT relies solely on DOU, and it is DOU that I am going to try and demonstrate to be invalid. I am going to assume mengenlehre is OK with my formulation, and will try to post again by the end of the day.

Sincerely,

Brian

[mengenlehre]

New definition: Let f map A into B and let g map B into C. Then the composition of g and f, denoted g*f, is (g*f)(x)=g(f(x)) for every x in A for which f(x) is in B. Note: g*f maps A to C and any x in A for which f(x) is not in B is not in the domain of g*f.

Definition: Let f map A into B. the inverse of f, call it g=inv(f), is defined as follows; g is the inverse of f iff [for every a in A and every b in B (f(a)=b iff g(b)=a)]. Note: g is a function mapping B into A (actually more see below).

Theorem 1A: Let f map A into B be any function. Then the following are equivalent (TFAE).
1) f and g are inverses
2) f and g are bijections
3) f*g=i on B & g*f=i on A (called left & right inverses)
4) f(A)=B and for all X,Y<A f(X)=f(Y) iff X=Y
5) f(g(B))=B and g(f(A))=A

Proof 1A: f has an inverse iff f is a bijection.
Define f as above and suppose g=inv(f). To show f is 1:1 suppose x and z are in A. Then f(x) and f(z) are in B since f is a function. Suppose f(x)=f(z). Next, by composition, g(f(x))=g(f(z)) and g is a function by definition so we must have x=z. Restated g being a function means that any element of B cannot map to more than one point in A and must map to at least one point. Every element in the domain of a function must be used. Therefore, f is 1:1.
To show onto let y be any element of B. Then g(y) is in A since g is a function. So by the definition of the inverse f(x)=y. Therefore, f is onto. Therefore, f is a bijection. Note that every step is reversible so we have f has an ivnverse iff f is a bijection. A similar argument holds for g. Therefore we have shown that f has and inverse g iff f and g are bijections. Note we have also shown the equivalence of 3) which actually showed up inside proof of 1) iff 2) But, it should be intuitive that this is true by drawing pictures and thinking about what is happening. Also note that you must actually use the hypothesis in the proof.

Theorem 2A: From 1A when A=B, with f,g inverses iff f*g=g*f. Proof follows easily from 1A.

Theorem 3A: f is 1:1 but not onto iff f has no right inverse.

Theorem 4A: f is onto but not 1:1 iff f has no left inverse.

Theorem 5A: Suppose f maps A into B and A<B but A!=B (ie A is a proper subset of B). Then f has no inverse mapping B to A. Follows easily from above.

Note: good proofs can be found in many books but I will list several different books.
1) Set Theory with applications by Lin and Lin.
2) Discrete math with applications by Epp
3) An intro to advanced math Smith, Eggen, Et Al
4) most pre-calculus books