Cantor's Proof (for the abstract-concept impaired)

Got a great idea? Tell the world about it here.

Moderators: mvs_staff, forum_admin, Marilyn

Cantor's Proof (for the abstract-concept impaired)

Postby JeffJo » Mon May 01, 2017 11:56 am

  1. The Axiom of Infinity.
    1. The number 1 is defined to be a natural number.
    2. If n is a natural number, then the number n+1 is defined to be a natural number.
    3. By the deductive process known as Mathematical Induction, this defines every possible natural number in an endless collection.
    4. The Axiom is not that these numbers are defined (which they are), are or need to be "produced" (which is not defined but seems to require an end), or have an end. It is that you can call the collection, as a whole, the "set" that we call N. And that other infinite sets can be now defined from N.
    5. Such sets have some non-intuitive properties that the abstract-concept impaired refuse to accept. Most are related to the fact that the non-deductive process they know as "inductive inference" cannot be used to extend properties of finite portions of these sets to the infinite sets. The inferences apply only to the members of the set, not the set itself.
    6. For example, if you list a finite set, the size/cardinality of the set is always the index of the last element listed. Since there can be no "last element" of an infinite set, its size/cardinality can't be defined that way.
  2. Countable sets.
    1. A 1:1 correspondence is a mapping that matches each element of two sets with one, and only one, member of the other.
    2. Sets that can be put into a 1:1 correspondence have the same size/cardinality.
    3. A countable set is one that can be put into a 1:1 correspondence - or "list" - with a sequential set of natural numbers starting with 1. It can be represented like a function, L(*), whose domain is the sequential set of natural numbers.
    4. If the domain is N itself, the listed set is called infinitely-countable. Again, it is not "produced," but it is defined.
    5. One property that the abstract-concept impaired try to avoid, is that every infinitely-countable set can be put into a 1:1 correspondence with any and every infinite subset of N. So all infinitely-countable sets, no matter how many elements seem to be "missing" to the abstract-concept impaired, have the same cardinality.
    6. As an example, the set N2={1,4,9,16,...} is in a 1:1 correspondence with N, as defined by the relationship n2=n^2. After looking at the finite subset of N2 up to n2=n^2, the abstract-concept impaired notice the list seems to be "missing" n^2-n elements. The two sets are still the same size/cardinality, and any "inductive inference" made about the relative sizes is irrelevant, because there is a valid 1:1 correspondence with N.
  3. Cantor Strings.
    1. It is possible to define function that describes a character for each n in N. This function is called a "string." If only two characters are produced, I call it a "Cantor String," and the characters "opposites" of each other. An example is S(n)=char(mod(n,2)), which produced the string "10101010...", demonstrating that Cantor Strings "exist" without the need to explicitly "produce" each character in the string.
    2. A countably-infinite set of such strings is defined by the binary representation of each n in N. Again, this set "exists" without the need to explicitly "produce" each n in N, or each string.
  4. Cantor Diagonalization.
    1. Assume T is the set of all Cantor Strings.
    2. Assume S is a countably-infinite set of Cantor Strings. We know that such sets exist, because one was defined in step 3B.
    3. Let S(*) be a list of the set S (please note that the set S is represented in bold-italic, and the listing S(*) is not).
    4. Define the function D(S(*),n) to be the opposite character of the nth character of S(n). Note that this defines an infinite string, even though (yet again) it doesn't "produce" anything.
    5. D(S(*),n) is a Cantor String, so it must be in T.
    6. D(S(*),n) cannot be in S, because for every n its nth character is different than the nth character of S(n).
    7. This proves the lemma "If S is countable, then it is not all of T.
    8. By Contraposition, if S is all of T, then it is not countable.
  5. The set T cannot be counted.
  6. The set T has a greater cardinality then N.
JeffJo
Intellectual
 
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby Gofer » Mon May 01, 2017 4:04 pm

JeffJo wrote:The set T has a greater cardinality then N.
Just to clarify, and according to the definition of cardinality below, Cantor's theorem never proves that; the proof is trivial though, and left as an exercise.

The cardinality of A is said to be less than the cardinality of B, written |A|<|B|, if there exists an injective, but not bijective, map from A to B.

----
In terms of maps, Cantor's Lemma may be stated as follows: If f is an injective map from ℕ to T, then f is no bijection.

And its contrapositive: If f is a bijection, then f is not ℕ to T.

An exercise is to find a surjective map from T to ℕ, or prove that none exists.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby JeffJo » Tue May 02, 2017 9:30 am

Gofer wrote:Just to clarify, ...
Maybe you didn't notice, but I was trying to be informal for clarity's sake. So I said "1:1 correspondence" where I could have said "bijection," "subset" where I could have said "a trivial injection," "some are unmatched" where I could have said "surjection," and referred to size and cardinality as having similar meanings.

But if you feel the need to insert the unnecessary, pedantic definitions that you like to look up, without demonstrating that you understand them, and hint at trivial proofs without ever providing them (or any new information at all for that matter) yourself, I hope you have satisfied those needs.
JeffJo
Intellectual
 
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby Gofer » Tue May 02, 2017 11:12 am

BEWARE! Near the end of this post, I provide answers to the exercises I posted earlier!

Aside from Jeff's unwarranted hostility, perhaps he hasn't noticed that it is entirely possible to be informal yet still refer to the actual definitions, provided unfamiliar terms are explained.

And he obviously missed the part where I gave new information in terms of interpreting Cantor's proof in respect to the theory of maps.

Does Jeff need new glasses?

answer to exercise 1: Cantor's Lemma already shows that there exists no bijection from ℕ to T, so we only need to find an injection from ℕ to T to show |ℕ|<|T| according to the definition. The function (s n)≝(n 1's followed by infinite zeroes) suffices, so that every n gets assigned a unique infinite string.

answer to exercise 2: we need to find a way to assign arbitrary infinite strings to the natural numbers, and make sure all numbers get covered:
return the position of the first occurring 1; if the string has no 1's, return 1. Note that this mapping is not constructive because there's no way for an algorithm to know if an arbitrary string contains a 1.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby JeffJo » Wed May 03, 2017 6:38 am

Aside from Jeff's unwarranted hostility, perhaps he hasn't noticed that it is entirely possible to be informal yet still refer to the actual definitions, provided unfamiliar terms are explained.
Aside from Gofer's customary condescension, and perhaps due to his need for continuous one-upsmanship, he hasn't noticed that I didn't use any unfamiliar terms. And in fact, I substituted familiar and acceptable terms for the unfamiliar ones that he thinks need more formal definitions.

Or notice how I described them in a way that points to his trivial proof, but uses familiar concepts instead of unnecessary (to non-mathematicians) theories like the theory of mapping; or complex-sounding, yet easy to understand if expressed in more familiar terms instead of "***jection."

The assumption that S is a subset of T is an injection. The proof that S is not all of T shows there isn't a surjection if S is countable. A surjective map from T to N is unnecessary to construct unless you believe in an overly-strict requirement.
JeffJo
Intellectual
 
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby Gofer » Fri May 05, 2017 6:26 pm

Isn't it funny how my OP was perfectly civil and informative, yet Jeff decided to go on a diatribe, bashing it, and then accusing me of exactly what he himself was doing!

---
There is absolutely nothing advanced about the theory of maps; one just needs to put in the effort to learn the definitions.

---
The assumption that S is a subset of T is an injection. The proof that S is not all of T shows there isn't a surjection if S is countable.
Since S was the set under injection from N, it is already defined to be countable, making your statement "if S is countable" very strange.

The lemma merely shows that any injection from N to T can't also be a surjection, and hence not a bijection, a bijection being defined as being both a surjection and an injection, thus immediately proving the main theorem, without invoking contraposition.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby JeffJo » Sat May 06, 2017 9:17 am

Isn't it funny Gofer's original reply was completely irrelevant to my original post; it's only possible purpose being to obfuscate it? Yet Gofer feels he was justified to do so.

There is absolutely nothing about the theory of maps that is needed to understand my points. Mentioning it can serve only to confuse the vast majority of potential readers who have never encountered the theory before.
JeffJo
Intellectual
 
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby Gofer » Tue May 09, 2017 11:07 am

Isn't it funny how my OP was NOT irrelevant to Jeff's, seeing how it brought new theory into the discussion, theory that wasn't too hard to comprehend for the vast majority, had they bothered to look it up.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby JeffJo » Tue May 09, 2017 3:44 pm

Isn't it funny that Gofer seems to admit that "brought new theory into the discussion" is a euphemism for "theory that wasn't necessary to begin with;" and "not too hard to comprehend for the vast majority" is a euphemism for "they won't understand what I said, and need to look it up, but I won't give them a hint where to do so."
JeffJo
Intellectual
 
Posts: 2609
Joined: Tue Mar 10, 2009 11:01 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby Gofer » Thu May 11, 2017 6:16 am

Isn't it funny how Jeff's last post is euphemism for "I can't be bothered to precisely quote Gofer, so I'm just going to interpret it in a way that would make him seem wrong.".

Besides, your OP doesn't discuss how Cantor's proof relates to the actual definition of countability:

A set S is said to be countable if there exists an injection from S to N, the natural numbers.


Oh look, Jeff, it says "injection" - guess my OP had some value after all.
Gofer
Intellectual
 
Posts: 283
Joined: Mon May 09, 2016 8:24 am

Re: Cantor's Proof (for the abstract-concept impaired)

Postby romanze7 » Mon May 15, 2017 11:12 pm

I think it not really funny. :cry: Tmaxbet mobileT
romanze7
Thinker
 
Posts: 9
Joined: Wed Nov 23, 2016 4:44 am


Return to Great Ideas

Who is online

Users browsing this forum: No registered users and 2 guests