Talk:Cantor's theorem/Archive 1

This is an archive of past discussions about Cantor's theorem. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

A SUGGESTION AND COMMENTS

1. If you have original research to present, please don't present it here. This is wikipedia policy. Wikipedia is not a place for presenting original research. That is what professional journals and publishers are for.

2. If you have mathematical or philosophical objections to Cantorian set theory, please address these in a brief descriptive section of the article itself. However, please do not turn this talk page into a debate hall. It is not our purpose here to endlessly argue over whether Cantorian set theory is "right" at all.

3. If you want to write an article on a more detailed critique, or presentation of previous critiques, or Cantorian set theory, then please create a new article for this purpose. Regardless of the bickering in here, it is an emperical fact that something on the order of 90% or so of working mathematicians accept Cantorian set theory both in theory and in practice, to some extent. (Source: The Mathematical Experience, Davis/Hersh) Thus, this should article should focus on the conventional viewpoint and mention contrary views, but a thorough hashing of intuitionism or constructivism on this topic requires a separate article.

—Preceding unsigned comment added by Revolver (talk • contribs) 27 September 2004

Beth numbers

Interesting stuff on beth numbers. I wasn't quite aware of the definition, but it seems a very natural one to make. If a bit more material on beth cardinals can be added, I think they're significant enough to warrant their own separate article. Then this article could explain some consequences of Cantor's thm, and have a link to beth cardinals within the article. How does that sound? Revolver

History

The history bit is still not quite right, since it doesn't address the main concern about the confusion over what "Cantor's Theorem" actually is. We have

the 1873-4 proof. This is a proof of non-denumerability of the reals
two proofs written in the same 1891 paper.
- The first is EXACTLY what we now call the diagonal argument. This is a proof of non-denumerability of the reals, using "diagonal" technique.
- The second is v. close to the x notin fx form which is really "Cantor's Theorem". Caveat however I believe it proves non-denumerability of the reals, whereas "Cantor's Theorem" strictly does not (only that P(M) > M).
Russell's proof - this however is about "propositional functions"
Zermelo's proof. This is called "Cantor's Theorem" (in German) and moreover does not prove non-denumerability of the reals, only that P(M) > M.

I'd write a suitably presented version of this in the main article if I was sure of the facts, but I'm not.

user: dbu

I believe that Cantor's them (P(M) > M) DOES prove non-denumerability of the reals, because it can be shown that the reals can be put in 1-1 correspondence with the set of all subsets of the positive integers, i.e. c = card(R) = 2^(card(N)) = 2^(aleph-naught). There are a couple minor details, but basically the correspondence is achieved by mapping R 1-1 onto the interval (0,1), and then using the binary representation of real numbers. (Every real number between 0 and 1 is an infinite string of 0's and 1's, and each string corresponds to a subset of N via n'th digit = 1 means n is in the set, n'th digit = 0 means n is not in the set.)

Still, there is a difference between the "diagonal argument" and the "x notin fx" argument, and this still isn't clear. Revolver

Russel's Proof is out-of-context

Quote: Russell has a very similar proof in Principles of Mathematics (1903, section 348), where he shows that that there are more propositional functions than objects. "For suppose a correlation of all objects and some propositional functions to have been affected [sic], and let phi-x be the correlate of x. Then, "not-phi-x(x)," i.e., "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value of x." He attributes the idea behind the proof to Cantor. Unquote

The above quoted paragraph --- which intentionally removed the last sentence of the paragraph where it was excerpted: But this case may perhaps be more or less met by the doctrine of types.&# --- is verily out-of-context in this article. Russel's doctrine or theory of types can be simply interpreted as any set does not contain itself as an element (that is, if S is a set then {S} is not a member of S --- even the empty set is not a member of an empty set) or the whole is not one of its parts. If one completely understands Sections 346 through 349 of "Principles of Mathematics" (1903), then he would realize that Bertrand Russel was actually expressing his reservation on the validity of Cantor's diagonalization argument.

(1) Following is Russel's complete text of Section 349 of the said book:

It is instructive to examine in detail the application of Cantor's argument to such cases by means of an actual attempted correlation. In the case of terms and classes, for example, if x be not a class, let us correlate it with {x}, i.e., the class whose only member is x, but if x be a class, let us correlate it with itself. (This is not a one-one, but a many-one correlation, for x and {x} are both correlated with {x}; but it will serve to ilustrate the point in question.) Then, the class which, according to Cantor's argument, should be omitted from the correlation, is the class W of those classes which are not members of themselves; yet this, being a class, should be correlated with itself. But W, as we saw in Chapter X, is a self-contradictory class, which both is and is not a member of itself. The contradiction, in this case, can be solved by the doctrine of types; but the case of propositions is more difficult. In this case, let us correlate every class of propositions with the proposition which is its logical product; by this means we appear to have a one-one relation of all classes of propositions to some propositions. But applying Cantor’s argument, we find that we have omitted the class W of those propositions which are logical products, but are not members of the classes of propositions whose logical products they are. This class according to the definition of our correlation, should be correlated with its own logical product, but on examining this logical product, we find that it both is and is not a member of the class W whose logical product it is.

Thus, the application of Cantor's argument to the doubtful cases yields contradictions, though I have been unable to find any point in which the argument appears faulty. The only solution I can suggest is to accept the conclusion that there is no greatest number and the doctrine of types, and to deny that there are any true propositions concerning all objects or all propositions. Yet the latter, at least, seems plainly false, since all propositions are at any rate true or false, even if they had no other common properties. In this unsatisfactory state, I reluctantly leave the problem to the ingenuity of the reader.

(2) Russel's footnote on page 55 of cited book: "I shall use the word object in a wider sense than term, to cover both singular and plural, and also cases of ambiguity, such as 'a man'. The fact that a word can be framed with a wider meaning than term raises grave logical problems."

A proposition regarding all objects or all propositions is necessarily self-contradictory or self-inconsistent [it is both true and false at the same time just like the proposition "Every rule has an exception" (if this all-encompassing proposition is a rule, then it has an exception; therefore, not all rules have exceptions) or, simply, "I am lying" or "This statement is false"] because of the inevitable self-reference in its statement --- such as in Cantor's "set of all sets" or "greatest cardinal number" paradox, Burali-Forti's "set of all ordinal numbers" or "greatest ordinal number" paradox, Russel's "set of all sets that do not belong to themselves" paradox, and Cantor's hierarchy-of-infinite-power-set theorem's "set of all generators whose images do not contain their generators for a presumed bijection between an infinite set and its power set". A contradictory self-referential or impredicative definition ("a definition of a collection of objects that uses the total collection itself") violates Russel's vicious circle principle ("whatever involves all of a collection must not be one of the collection").

BenCawaling@Yahoo.com

non-denumerability of the reals

> Cantor's theorem (P(M) > M) DOES prove non-denumerability of the reals

No it doesn't, at least on its own, because it doesn't establish the existence of the reals in the first place. You need the axiom of infinity first, which establishes the existence of a set N of all natural numbers. Then you need Axiom of Separation to show that the set {n in N: n notin fn}. Then you can show that for any function f whose argument is any natural number, and whose value is any set of natural numbers, there is some set of natural numebs not in the range of F. THEN you need power set axiom to establish the existence of a set of subsets of natural numbers. THEN you need to connect the idea of a real number in some way to the idea of a subset of natural numbers. so, quite a bit of work to do from Cantors theorem on its own.

dbu, 28 October 2003

I think most mathematicians assume the real numbers exist. Or at least assume some axiom system where they exist. Not everyone is a set theorist. Revolver

From the point of view of most ordinary mathematicians who are not set theorists, the reason Cantor's theorem falls short of proving the uncountability of the reals is simply that in addition to Cantor's theorem, one must also establish that the power set P(N) has the same cardinality as the reals, or at least that its cardinality is a lower bound on that of the reals. Of course, that is fairly readily done. Michael Hardy 18:55, 28 Oct 2003 (UTC)

Not sure what you are saying! Is this because ordinary mathematicians have faith in some unrestricted comprehension principle whereby the property "- is a natural number" automatically defines a set of objects, whatever? The whole point of set theory is to make all assumptions explicit, including the assumptions about comprehension which, if not spelled out carefully, lead ot nasty & famous paradoxes.

My point in raising it here is there is considerable confusion about what "Cantor's Theorem" actually is (see recent spate of postingson Phil-Logic e.g. You have defined it absolutely correctly: for any set M, P(M) > M. This on its own does not establish that anything like the set of natural numbers N actually exists.

Again, I think most people assume N exists. Maybe this is a point that only set theorists and others worry about. My point was, given the usual assumptions (if you press me, okay, ZFC + choice, or GBN + choice) the naturals and reals exist, and THEN once you have Cantor's thm, you have the nondenumerability of the reals. Since most people assume one of these axioms systems implicitly, that's what I meant, that Cantor's thm => R is uncountable. Revolver

It may be worth a bit of extra work in this article to spell out the assumptions & dispel confusions.

Dean B.

Uh, proving the natural numbers exist is another proof. The same goes for the reals. It has been proven that both exist, and if you wish to explore these proofs take some upper division math courses at your university. In fact I believe proving the reals exist is an entire undergrad course. But trust me, it has been done, and therefore we can assume that both exist when using and applying Cantor's Theorem. --Dissipate 20:19, 28 Jun 2004 (UTC)

Actually, you're wrong, Dissipate. The existence of the set of natural numbers depends on the axiom of infinity, as mentioned above, and there are formal systems which exclude this axiom, and hence are quite unable to prove the existence of N, let alone of R. I was just saying, this particular aspect is a minor point, in that most working mathematicians use ZFC or GBN + choice, etc. But you're quite wrong to say we can "assume that both exist" because of some upper division undergrad course somewhere. Revolver 02:14, 27 Sep 2004 (UTC)

'''Cantor's Theorem is untenable'''

The bone-of-contention "set of all the elements of a given infinite set which are not contained in their respective subset-images for a presupposed one-to-one correspondence between the elements of the given infinite set and the members of its power set" that Cantor defined in his "proof" is truthfully an indeterminate infinite set --- it is indeed an incomplete totality which is inconsistent (that is, logical contradictions would ensue) if regarded as a completed totality and; hence, it is actually not a completely constructible set just like Russel's "set of all sets that do not belong to themselves".

Let us simply consider as a counter-example the power set P(N) of the set N of natural numbers. The subset-of-N elements of P(N) comprise: (1) the empty or null set Ø; (2) the countably infinite n-element(s) subsets of N, for all n in N+; (3) the infinite proper subsets of N; and (4) the set N itself.

Let f be a one-to-one correspondence between N and P(N) and suppose T = {n in N : n is not in f(n)}. Because the empty set Ø has no member, it cannot "contain" its generator, say, n0 in N. Therefore, f(n0) = Ø implies n0 is in T. Because f is a one-to-one correspondence, then the generator of {n0} is not n0 inasmuch as we had already specified that the image of n0 is Ø. So, suppose the generator of {n0} is n1 in N --- that is, f(n1) = {n0}. Then, n1 is in T since n1 is not in {n0} and by the very definition of membership in T. Similarly, we could suppose n2 and n3 in N to be the respective generators of {n1} and {n0,n1} so that n2 and n3 are in T. Likewise, we could suppose n4, n5, n6, n7, n8, n9, n10, n11, n12, n13, n14, and n15 in N to be the respective generators of {n2}, {n3}, {n0,n2}, {n0,n3}, {n1,n2}, {n1,n3}, {n2,n3}, {n0,n1,n2}, {n0,n1,n3}, {n0,n2,n3}, {n1,n2,n3}, and {n0,n1,n2,n3} so that n4, n5, n6, n7, n8, n9, n10, n11, n12, n13, n14, and n15 are in T. Constructively, we could go on ad infinitum and assemble T = {n0,n1,n2,n3,...} --- therefore, T is a countably infinite proper subset of N (here, we were only interested in showing that T is an infinite set and we ignored the fact that the elements of T may not be arranged in ascending numerical order).

At this point, the constructivists and the intuitionists, following their Aristotelian view of "potential infinity", would argue that T is an incomplete totality or an indeterminate infinite proper subset of N because there is really no "last natural number"; and, hence, all the elements of the set T could not be known completely --- thus, it is ridiculous to even ask about "the generator of T". They remind us to clearly keep in mind that one-to-one correspondence does not require the completed act of pairing the elements of two infinite sets --- that is, it suffices that we can declare "and so on" as denoted by the 3-dot ellipsis ". . ." from some valid pattern or rule of matching respective elements --- hence, we can forthrightly dismiss Georg Cantor's claim that the presupposition of the existence of a one-to-one correspondence between N and P(N) is the culprit in the contradiction that ensues only when we perceive the correlation of elements to be a completed process.

On the other hand, with his already resolute belief of "actual infinity" and "completed totality of an infinite set" as well as an exhaustive "all at once view" of all the subsets-of-N elements of P(N) and the presumed one-to-one correspondence f between N and P(N), Georg Cantor could completely form T = {m0,m1,m2,m3,...} [here, the elements of T are arranged in ascending numerical order since we extracted them in the order of their appearance in the enumeration of the members of P(N) induced by the one-to-one correspondence f] which is also a subset-of-N member of P(N) and, hence, T must appear somewhere in the comprehensive countable listing enforced by f. Georg Cantor claimed that T's generator cannot be one of its elements --- that is, it cannot be mk for any natural number k --- because this would contradict the set-inclusion definition of an element of T. At the same time, because f is a one-to-one correspondence, T must have a generator which is not one of its elements --- from this contradiction (if T is a completely constructible set), Georg Cantor inferred that the presupposed one-to-one correspondence f cannot truly exist.

For our part, while we respectfully agree with the constructivists and intuitionists viewpoint on potential infinity, we want to demonstrate here the internal inconsistency in Cantor's theory of infinite sets, so we first grant arguendo Georg Cantor's tenets of "actual infinity" and "completed totality of an infinite set" and rebut Cantor's theorem under his own terms. Our quite simple counterargument focuses on the fact that T (if viewed as a completed totality) becomes an inconsistent totality equivalent to Cantor's "set of all sets", Burali-Forti's "set of all ordinal numbers", and Russel's "set of all sets that do not belong to themselves" which Georg Cantor himself considered to be not completely constructible.

It is enlightening to note here the equivalent logical contradiction involved in the inconsistent totality sets defined in Cantor's paradox, Burali-Forti's paradox, Russel's paradox, and Cantor's hierarchy-of-infinite-power-sets theorem --- that is, elements of these respective sets belong and do not belong to themselves at the same time. Interestingly, as noted by Oxford University Professor Adrian W. Moore in his book "The Infinite", Georg Cantor's attitude to his "greatest cardinal number" paradox, Burali-Forti's "greatest ordinal number" paradox, and Russel's "set of all sets that do not belong to themselves" paradox is admittedly one of affirmation that some totalities are immeasurably big, "absolutely" infinite to such a degree that they could not be assigned magnitudes in the way that, say, N "could". They are too big to be regarded as "genuine sets" --- they are nowadays called "proper classes".

Very clearly, T is a subset of N so it cannot be merely dismissed like the "totality of all cardinals" or the "totality of all ordinals" or the "set of all sets that do not belong to themselves" that Georg Cantor regarded as belonging to the class of inconsistent totalities which are immeasurably big. It is not T's size which makes T an inconsistent totality but its self-referential definition (just like the aforementioned first three "all-encompassing" sets) --- that is, T's set-membership proposition references T itself. Being a subset of N, the set T is a self-referenced element of the range P(N). We reiterate that it is the self-referential definition of T that effects the logical contradiction with regard to its completed totality and not the premise of existence of one-to-one correspondence between N and P(N) [we emphasize that if there is no one-to-one correspondence between N and P(N) then, for any non-one-to-one function f between N and P(N), either T is not a well-defined set or T's generator may be non-existent or the determination of T's generator is senseless or the determination of the inclusion|exclusion of T's generator in T is nonsensical]. It is very important to understand that there is no presupposition of existence of a one-to-one correspondence in the first three admitted inconsistent totalities --- however, every one of the four "all-encompassing" sets suffers from a self-referential definition that leads to a logical contradiction.

As with Georg Cantor's standpoint, we reject as well the mathematical existence of Cantor's "set of all sets", Burali-Forti's "set of all ordinal numbers", as well as Russel's "set of all sets that do not belong to themselves" for being inconsistent totalities --- that is, there are logical contradictions (not merely time-dependent constructibility concerns like "it would take an infinite time to assemble the entire set") for their existence as completed totalities of infinite sets. The inconsistent totalities of Georg Cantor's "set of all sets" and Bertrand Russel's "set of all sets that do not belong to themselves" follow from their self-referential definition at the set-level --- if these sets exists, then they are both included and not included in themselves. The inconsistent totality of Cesare Burali-Forti's "set of all ordinal numbers" arises from the self-referential definition of "ordinal number" as "the well-ordered set of all its preceding ordinal numbers" --- for examples, 5 = {0,1,2,3,4} or w+1 = {0,1,2,3,...,w} (here w is omega) --- where well-ordering of ordinals means "for each set of ordinals (finite or infinite), there is another ordinal which is the first to succeed them all". Clearly, the "set of all ordinal numbers" cannot exist because, by its well-ordering, there must be another ordinal number which is the first to succeed all of its elements --- which contradicts its posturing as already containing "all" the ordinal numbers.

Against Georg Cantor, however, we also steadfastly refuse (for being an inconsistent totality because of its contradictory self-referential definition) the mathematical existence of his completed bone-of-contention set T in the instant assailed theorem --- the set T is merely a paraphrase at the elements-level of the inconsistent totality sets defined at the set-level in Cantor's and Russel's paradoxes.

As parting remark, we state here in passing that P(N) can be enumerated by simply adding a "companion infinite proper subset of N" to each finite proper subset of N (discarding the repetitions of infinite proper subsets of N) in the generally accepted enumeration of all the finite subsets of N --- therefore, the logical contradiction involving T follows from the premise of "completed totality of an infinite set" and not from the premise of "existence of one-to-one correspondence between N and P(N)".

BenCawaling@Yahoo.com

Where does this proposed "companion infinite set" come from, i.e., which set is it? I can imagine, for example, taking the "companion" to the finite set { 1, 2, 3 } to be simply the complementary set, { 4, 5, 6, ... }, but that fails to enumerate P(N), since it omits infinite sets like the set { 2, 4, 6, 8, ... } of all even numbers, whose complement is not finite. Michael Hardy 15:08, 7 Sep 2004 (UTC)

'Enumerating the Power Set P(N) of the Set N of Natural Numbers'

At first glance, it appears quite impossible to enumerate all the elements of P(N) considering that infinity is approached from countably infinite directions --- that is, through the progression of all the singleton (1-element) subsets, through the progression of all the subsets with 2 elements, through the progression of all the subsets with 3 elements, and so on. The Cantorian requirement for a “valid enumeration” that would establish the countability of the elements of P(N) goes beyond this --- it is also required that the infinite proper subsets of N (such as the sets of all even or all odd or all prime natural numbers) be “actually” included in the enumeration scheme in the same manner that the enumeration scheme for the algebraic real numbers include both rational and irrational numbers.

It is educationally worthwhile to distinguish the enumeration of the algebraic real numbers from the enumeration of the elements of P(N). Each term in the enumeration of the algebraic real numbers (where the irrational numbers like the quadratic surds are listed along with the rational numbers) is a single complete element that exists independently by itself [such as 0, square root of 2, 1/3, pi, . . . --- these numbers exist regardless of their representations in place value positional numeral systems as terminating or not, with or without repeating digit(s)] while the terms in the listing of the elements of P(N) are sets — including the infinite proper subsets of N (such as the sets of even, odd or prime natural numbers) which do not exist independently of N (that is, their subset-elements are composed of members of N), which is also the indexing set used for the enumeration to verify the countability of P(N). [I am not discounting here the fact that relations exists between irrational numbers and infinite subsets of N, such as: pi/4 = 1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + 1/13 – 1/15 + . . . ]

We first emphasize the following very important point (this is related to the point made with respect to, say, the decimal expansions of fractional real numbers in my “discussion text” in Wikipedia’s Cantor’s Diagonal Argument topic): the set, say, {0,2,4,6,...} as written down or perceived does not specifically refer to a single infinite subset of N (say, the even natural numbers) unless there is mutual agreement (that is, a rule for membership of all the elements of the set is specified) on what the unwritten down terms really are. As a matter of fact, it is not possible to be able to absolutely distinguish the infinite subsets of N, say, {0,2,5,6,9,12,13,...}, {0,2,5,6,9,12,13,17,...}, and {0,2,5,6,9,12,13,17,22,...} (here, you have to imagine the infinite sets with arbitrarily large natural number of finite elements written down or specified and differing only in their “ending” terms) from each other without specifically defining what the 3-dot ellipsis “. . .” actually means for each of them.

From the “potential infinity” point of view of the constructivists or intuitionists (to which we subscribe), we could already dismiss the unreasonableness of Cantor’s theory of infinite sets based on the immediately preceding discussion. But we want to establish the internal inconsistency of Cantor’s paradise so we grant arguendo Cantor’s premises of “actual infinity”, “completed totality of infinite sets” and “completed infinity of infinite subsets” then ascertain the countability of P(N) based on these assumptions --- thus, refuting his hierarchy-of-infinite-power-sets theorem.

Let us first consider Cantor’s proof of the countability of the positive rational numbers whereby he envisioned an “all at once” viewable exhaustive infinite array such as:

 1	  2	  3	  4	  5	  6	  7	.  .  .

1/2 2/2 3/2 4/2 5/2 6/2 7/2 . . . 1/3 2/3 3/3 4/3 5/3 6/3 7/3 . . . 1/4 2/4 3/4 4/4 5/4 6/4 7/4 . . . 1/5 2/5 3/5 4/5 5/5 6/5 7/5 . . .

 .	  .	  .	  .	  .	  .	  .	 .
 .	  .	  .	  .	  .	  .	  .	    .
 .	  .	  .	  .	  .	  .	  .	       .

where all the positive rational numbers occurs simultaneously and defined his enumeration scheme as traversing the entire infinite array through the familiar zigzag path starting at the top-left corner and proceeding down-right through the diagonal elements. We stress here that this scheme is a generally accepted proof of the countability of the rational numbers despite the latter’s extensiveness (infinity by addition) and denseness (infinity by division) as well as in spite of the fact that almost all the rational numbers are situated in the “infinite realm” denoted by the 3-dot ellipsis “. . .”.

Next, we try to intuitively reveal the folly in the “uncountability” of P(N). It is a standard theorem of set theory that the countable union of countable sets is countable. The contraposition to this theorem is that an uncountable set of objects cannot be gathered from a countable collection of countable sets --- in other words, an uncountable set of objects can only be amassed from the elements of an uncountable set or from an uncountable collection of countable sets. The set N of natural numbers, as well as every one of its subsets, are countable sets by definition. The power set P(N) is the collection of all the subsets of N. The set N is the exhaustive or complete collection of all the objects belonging to the sets in P(N) --- that is, there is no set bigger than N that can be accumulated from all the elements of all the sets that are included in P(N).

All of the above is correct. Michael Hardy 21:05, 13 Sep 2004 (UTC)

Because no uncountable set can be gathered from the objects in the subset-of-N members of P(N), it is preposterous (that is, there is no logical necessity or it is merely a huge “leap of faith”) to deem P(N) as uncountable

The above is a gross non-sequitur. It is as if one said: "All members of N are finite" (that is certainly correct); "Therefore is is preposterous to say that N is infinite." Michael Hardy 21:05, 13 Sep 2004 (UTC)

==> As I noted in my first sentence with “intuitively”, I am presenting in this paragraph the constructivists’ or intuitionists’ “potential only” interpretation of mathematical infinity --- that is, to them (and to which I also subscribe) there are no actual infinite sets . . . Therefore, your logical fallacy issue of non sequitur is non-existent --- I only meant that the conclusion “to deem P(N) as uncountable” or, from your example, “Therefore it is preposterous to say that N is infinite." should not be deduced simply because they are not appropriate language-wise or they do not make sense [in your example, every natural number is an element which you refer to as “finite” (that is, a “finite number”) but N is a set which you refer to as “infinite” (that is, an “infinite set” with all the “finite numbers” as elements) so the jump from “finite number” to “infinite set” is “a matter of definition” (you need to define what an “infinite set” is as opposed to “infinite number”) or the latter’s existence is “a huge conceptual leap of faith”] . . . According to Ludwig Wittgenstein (I am not using “argument from authority” here, it is just that Wittgenstein is a well-known intuitionist and I sort of like the way he made his points), uses of “infinity” and such terms were quite straightforward. We have to learn to take them at face value. He saw something wrong in the traditional discussion of “the infinite” --- he believed that the correct use of terms such as “infinity” was to characterize the form of finite things and, relatedly, to generalize about the endless possibilities that finite things afford. To him, it was incorrect to apply such terms directly to what we encounter in experience and it was incorrect to use them to describe anything as being actually infinite --- for example, we could say “there are infinitely many numbers” but this simply mean “however many numbers we had counted, we could always count more” and not “there is no last number” because the phrase “last number” makes no sense. To understand a concept is to be clear about the use of words and phrases governing it. Felix Kaufmann said: “I deny that there were strictly any infinite sets, but instead, that we could talk about the natural numbers as a convenient façon de parler (“useful fiction”), for this made it easier to discuss finite sets.” It is like talking about the average parent --- there is no such person but it made it easier to discuss real parents. While it makes good sense to say “The average parent [unlike any ordinary parent] has 2.4 children” it does not make sense to say “The average parent is expecting another child” or “The average parent is 2 months pregnant”. For Wittgenstein, to describe something as actually infinite is not just a mistake --- it is a mishandling of the language --- and once this fact is properly recognized then the philosophical perplexity about the infinite would at last be dissipated. We could say “space and time are infinite” but this simply means “it is part of the form of a spatiotemporal object to have various possibilities of movement --- however far such an object had traveled, there would be space and time enough for it to travel still further”. We could also say “space is infinitely divisible” but this does not mean “space is made up of individual parts” only that “space gives to reality an infinite opportunity for division”. For Wittgenstein, it makes sense to say “This stick is infinitely divisible” but not “This stick has been infinitely divided”. Moreover, one should be clear as to precisely what sense the former statement made --- to construe it in the wrong way as meaning that “a situation could be brought about in which this stick could be divided into infinitely many pieces” is to start mishandling the language again and reopens the possibility of ill-begotten philosophical conundrums --- simply that “however much the stick had been divided, it could always be divided more”.

==> “Infinite sets” are Cantorian-defined concepts from his notion of one-to-one correspondence --- thus, “an infinite set is one which can be put in one-to-one correspondence with a proper subset of itself” (that is, it is possible to take away one element from an infinite set and leave a subset that is “equinumerous” to it) . . . [Ben Cawaling]

--- that is, while there is nothing rationally flawed in taking P(N) to be uncountable as “a matter of definition”,

Nobody treats it as a matter of definition. Rather, it is proved by an argument, which is given in this article. Michael Hardy 21:05, 13 Sep 2004 (UTC)

==> Again, “uncountability” is a Cantorian-defined concept . . . To the constructivists and the intuitionists, the subset-of-N elements of P(N) can be constructed at the same time as the elements of N are being enumerated --- hence, P(N) [or, rather, all the finite subsets of N as it would actually appear] is countable and there simply is no room for the notion of “uncountability” of P(N) . . . An argument “proving” some set is “uncountable” must begin with a defined notion of “uncountable” . . . I resolutely believe that I have refuted Cantor’s “proofs” of his infinity theorems in all the Wikipedia articles on these issues and have amply established that there is no “uncountable” set . . . I am proposing a redefinition (this is what I mean by “matters of definition” — concepts and terms depend on the proponents of theories) of “countable” to mean what is now “finite” and “uncountable” to mean what is presently “countably infinite”. In my proposed Countable Set Theory, “set construction” (wherein “elements” or “parts” have existential logical priority over “set” or “whole”) and “set perception” (wherein “set” or “whole” has existential logical priority over “elements” or “parts”), as well as “extensional” (by enumerating the individual terms) and “intensional” (by specifying a membership property or attribute or condition) definitions of a set, are equivalent and there is no cardinality beyond that of N [or, rather, N and all other “infinite sets” have _no_ (or, _non-finite_, depending on who’s defining it) cardinality]. Of course, you are arguing otherwise and I welcome your comments . . . [Ben Cawaling]

it is nonsensical to make this Cantorian viewpoint to be the standard interpretation in present-day mathematics.

(1) In a similar vein, founded on the “standard accepted proofs” of Georg Cantor’s infinity theorems, the concepts of “well-ordered sets”, “order isomorphism”, “order types of well-ordered sets”, and generalized “ordinal numbers” (a “countable ordinal” is defined as “an isomorphism class of well-ordered subsets of R”) that goes beyond the natural numbers were given meanings. Hence, on the belief that the set R of real numbers is “uncountable”, it is further claimed that “every well-ordered subset of R is countable” and that “there are uncountably many countable ordinals” (this is not a paradoxical statement just like the declaration “there are infinitely many finite numbers” --- however, the intended meaning in the latter is merely that “there is no greatest natural number”

No, that is not the intended meaning. The intended meaning is that no finite cardinality can be assigned to this set, but any finite cardinality can be assigned to some of its subsets.

==> As to the intended meaning of “there are infinitely many finite numbers”, it is very clear that the Aristotelians (“inductive” or “unending successors” or “counting” view) and the Cantorians (“cardinality” or “one-to-one correspondence of elements” view) will always have their respective contrasting interpretations — I’ll just leave it at that . . . Mathematicians and philosophers, however, take, say, Cantor’s “set of all sets” paradox and “greatest cardinal number” paradox as one and the same issue — whether one views Cantor’s paradox from set level, element-membership level, or count-of-elements (cardinality) level . . . [Ben Cawaling]

so the former must also be interpreted as merely saying that “there is no greatest ordinal number”). Because these are indeed “matters of definition”,

Nobody treats them as matters of definition. They are established by specific arguments.

==> Once again, “well-ordering”, “ordinal number”, “countable ordinal”, and other transfinite terms are Cantorian-invented-and-defined concepts — the Cantorian arguments that invoke them already presuppose their mathematical existences and definitions but in, say, Wittgenstein’s “grammar of infinity”, these terms are considered mishandling of the language . . . In my Countable Set Theory, and I suppose in other alternative “finitary or finitistic ” set theories, these concepts are not necessary (they simply do not exist) so they are not defined — different theories have different set of primitive terms and axioms; hence, they are “matters of definitions” . . . [Ben Cawaling]

one cannot argue against them --- however, we could repudiate the basis (that is, that “uncountable” sets exist) for their “definitions”.

(2) In general, the Löwenheim-Skolem theorem states that any first order theory that has a model has a countable model --- that is, a consistent system of predicate logic “with a few additions to capture arithmetic“, that has an interpretation in which each theorem comes out true for that interpretation, has an interpretation with a countable domain of objects while the Upward Löwenheim-Skolem theorem states that if a theory has an arbitrarily large finite model, then it has an infinite model. The ensuing Skolem Paradox [for example, a system of arithmetic about the real numbers (deemed to be “uncountable”) has a model wherein all the sets in the domain of objects are countable --- that is, systems about the real numbers can be interpreted as if they were about sets of objects which are not more numerous than the natural numbers] is “esoterically resolved” by pointing to the subtle distinction between what is metamathematically said of the object language and what is mathematically said in the object language.

(3) Jacques Herbrand in his Research on the Theory of Demonstration made the work of Leopold Löwenheim and Thoralf Skolem rigorous from the finitistic point of view. In essence, he introduced a proof system, showed that a first-order statement was derivable if and only if the attempt to build a countermodel failed at some finite stage, and demonstrated that there is an effective procedure to go from the knowledge that the countermodel failed at the kth stage, for some natural number k, to a derivation of the statement --- in other words, Herbrand has come up with a version of the Löwenheim-Skolem theorem that does not mention infinite models.

The above could well be true, and interesting, but you forgot to say that you're no longer assuming what you said you would assume arguendo. Michael Hardy 21:18, 13 Sep 2004 (UTC)

==> The Lowenheim-Skolem Theorem and Hadamard’s Theory of Demonstration are generally accepted mathematical logic principles. I was simply citing them at this point in my discussion to support my “intuitive” argument that “uncountability” and even “countable infinity” could be dispensed with in mathematics today — or, “finitism” should be made the standard in academic curricula worldwide. What remains is merely the sound demonstration (that must be generally accepted by peers) of the internal inconsistency of Cantor’s infinite set theory — which I am hopeful I have shown. My rigorous argument to establish the countability of P(N), assuming “arguendo” Cantor’s transfinite premises, begins in the next paragraph . . . [Ben Cawaling]

We now proceed with our rigorous argument to establish the denumerability of P(N). From the Cantorian perspective, there is an “infinite completion” end to the enumeration process --- in fact, every infinite subset of N is a “completed enumeration” of countably infinite elements of N.

Certainly true. An obvious point. Michael Hardy 21:18, 13 Sep 2004 (UTC)

Any two distinct infinite subsets of N "distinguish from each other" by the fact that there is some smallest natural number that is a member of one but not of the other (and then in most cases there are also others, bigger than the smallest one). There's no need for a "tail-end" member. Michael Hardy 21:18, 13 Sep 2004 (UTC)

==> You got me here! You are absolutely correct that there is no need for a “tail-end” member for infinite sets --- there cannot be one simply because “there is no greatest natural number”, “there is no greatest even natural number”, “there is no greatest odd natural number”, “there is no greatest square natural number”, “there is no greatest prime natural number”, etc. What I was thinking when I wrote it (I have already deleted the erroneous phrase) is the relation between an infinite subset of N and an infinite binary sequence (or permutation of {0,1} taken infinity-at-a-time) whereby a “1”-term in the latter means that its natural-number-position in the sequence is an element of the former; a “0”-term in the latter, otherwise. My point here is easier to follow if you relate it to my point made with regard to Cantor’s diagonal argument (please refer to my “Discussion” text “Cantor’s Diagonalization Argument is untenable” in Wikipedia on this topic) where it is necessary to properly line up _all_ the fractional real numbers digit-for-digit in an infinite square array in order to be able to absolutely concurrently distinguish them _all_ from each other “all at once” --- similarly, in order to absolutely distinguish all the infinite binary sequences, one has to postulate a “tail-end” digit at countable infinity position so that “all of them” will “properly fit” in an infinite square array (it does indeed strain the imagination or intuition).

==> In other words, for any finite number of distinct infinite subsets of N there is a least natural-number-element-count z (starting from the leftmost element as first member) where their members all first differ. I think you are forgetting that there are infinitely many infinite subsets of N that the Cantorians view as existing “all at once” — so this natural-number-element-count z is non-existent for infinitely many infinite subsets of N or that all the infinite subsets of N cannot be properly lined up term-for-term in order to absolutely distinguish all of them from each other “in one sweeping view in one breath”. Let us just consider the infinite sets {n1,n2,n3,...,nz,...} where z and all the ns are arbitrary natural numbers. We could specify infinitely many ways for the ending 3-dot ellipsis “...” to complete and “absolutely distinguish” each infinite set in this collection. Since z is arbitrary, it ranges through all the natural numbers. Therefore, it is _impossible_ to distinguish all the infinite sets in this collection. [Ben Cawaling]

It is clear that the enumeration first, say, of all the singleton subsets of N or all the infinite proper subsets of N would already exhaust our indexing set N so that we will not then be able to even begin to list the subsets of N with two or more finite number of elements. From the opposite view, this also tells us that almost all of the infinite proper subsets of N or almost all of the finite subsets of N with one or more elements are in the “infinite realm” --- that is, at the “infinite completion of the enumeration” as the Cantorians see them. Therefore, we have to device some enumeration scheme whereby we list the subset-of-N members of P(N) without taking as the first consideration the count of elements in each subset of N.

In order to satisfy the Cantorians, we can also include infinite proper subsets of N in the enumeration scheme for P(N) by simply also listing, for each suitable finite-subset-of-N (that is, avoiding duplication) listed, some finite number of companion-infinite-proper-subsets-of-N. A simple scheme for the latter is formed by just adding, to each suitable finite-subset-of-N listed in a countable listing of the finite elements of P(N), the infinite natural-number-standard-successors to the last element of the former.

Here I have to suspect that you meant "the ifinitely many natural number successors", rather than "the infinite natural number successors". Each natural number is finite. Michael Hardy 21:18, 13 Sep 2004 (UTC)

==> I thought my hyphenated “natural-number-standard-successors” would already be understandable. As you suspected it, I meant the union of the finite-subset-of-N listed with the infinite subset of N composed of all the consecutive natural numbers starting with the standard successor (that is, plus one) of the last element of the former.

In my notation below, each finite subset of N with a subscript of +infinity actually refers to two subsets of N --- the finite subset of N shown as well as its companion-infinite-proper-subset-of-N --- for example, {1,5}+infinity actually means the two subsets {1,5} and {1,5,6,7,8, . . .}. We could stipulate complicated schemes for the one or more companion-infinite-proper-subsets-of-N to each finite-subset-of-N listed; however, it is not necessary since any infinite proper subset of N, even say {4, 307, 1502, 20136, 9648173, . . .}, would be eventually included in the enumeration along with the constructive progression of the finite subsets of N --- all infinite proper subsets of N that were enumerated along with the finite subset of N would be merely duplicated (and these duplicates would just be deemed to be discarded) at the “infinite completion” of the enumeration as the Cantorians believed. In other words, one could simply remember that each infinite proper subset of N has a finite-subset-of-N precursor --- just remove the ending 3-dot ellipsis “. . .” from the infinite set, say, {n1,n2,n3,...,nz,...} for sufficiently large natural number z. We emphasize that, following Cantor’s tenet of “completed infinity”, all the finite-subset-of-N are exhaustively enumerated.

We can simply list by groups all the finite members of P(N) in order of increasing numerical value of the sum of the natural number elements in each subset; the subsets which have equal sums of their elements are listed in increasing number of elements in the subsets — those with the same number of elements are further arranged in increasing value of their first element; those with the same first element are further arranged in increasing value of their second element; and so on.

For examples (here, we emphasize with subscript +infinity each suitable finite-subset-of-N which has a companion-infinite-proper-subset-of-N as simply defined earlier),

The subset of N whose element add up to 0: {0}

The subsets of N whose element(s) add up to 1: {1}+infinity, {0,1}

The subsets of N whose element(s) add up to 2: {2}+infinity, {0,2}+infinity

The subsets of N whose element(s) add up to 3: {3}+infinity, {0,3}+infinity, {1,2}, {0,1,2}

The subsets of N whose element(s) add up to 4: {4}+infinity, {0,4}+infinity, {1,3}+infinity, {0,1,3}+infinity

The subsets of N whose element(s) add up to 5: {5}+infinity, {0,5}+infinity, {1,4}+infinity, {2,3}, {0,1,4}+infinity, {0,2,3}

The subsets of N whose element(s) add up to 6: {6}+infinity, {0,6}+infinity, {1,5}+infinity, {2,4}+infinity, {0,1,5}+infinity, {0,2,4}+infinity, {1,2,3}

etc.

Thus, a countable listing or enumeration of the finite and infinite subsets of N is readily given by: P(N) = { N, Ø, {0}, {1}, {1,2,3,...}, {0,1}, {2}, {2,3,4,...}, {0,2},

        {0,2,3,4,...}, {3}, {3,4,5,...}, {0,3}, {0,3,4,5,...}, {1,2},
        {0,1,2}, {4}, {4,5,6,...}, {0,4}, {0,4,5,6,...}, {1,3},
        {1,3,4,5,...}, {0,1,3}, {0,1,3,4,5,...}, {5}, {5,6,7,...},
        {0,5}, {0,5,6,7,...}, {1,4}, {1,4,5,6,...}, {2,3}, {0,1,4},
        {0,1,4,5,6,...}, {0,2,3}, {6}, {6,7,8,...}, {0,6},
        {0,6,7,8,...}, {1,5}, {1,5,6,7,...}, {2,4}, {2,4,5,6,...},
        {0,1,5}, {0,1,5,6,7,...}, {0,2,4}, {0,2,4,5,6,...},
        {1,2,3}, . . . }

Our second approach of enumerating the finite subsets of N follows the enumeration by cross-section array method (shown earlier) that Cantor himself used in listing the rational numbers but, instead of placing only one finite member of P(N) [that is, only one finite subset of N] in each array element, we put one or more of them [that is, some finite number of finite subsets of N] which obey a definite rule that ensures the inclusion of any finite subset of N in some array element and which minimizes its inclusion in multiple array elements. This method effectively combines the enumeration by groups of elements (say, our first approach above) and the enumeration by cross-section array methods — the basic idea is simply to piggyback all the countably infinite approaches to infinity (downward at each column, to the right at each row, and the count of elements in every group) with the sole zigzag diagonal down-right traversal of an infinite array where each array element contains a finite number of finite-subsets-of-N-elements of P(N).

The countability of P(N) is readily established by the enumeration first of N and Ø then by the finite and infinite proper subsets of N gathered from traversing (in the standard down-to-the-right zigzag diagonal path) the elements of the infinite cross-section array shown below (here, we emphasize with subscript +inf each suitable finite-subset-of-N which has a companion-infinite-proper-subset-of-N as simply defined earlier):

{0} {0,1} {0,1,2} {0,1,2,3} . . . {0,1,2,3,...,n-2,n-1,n} . . .

{1}+inf { {0,2}+inf, { {0,1,3}+inf, { {0,1,2,4}+inf, . . . { {0,1,2,3,...,n-2,n-1,n+1}+inf, . . . {1,2} } {0,2,3}, {0,1,3,4}, . {1,2,3} } {0,2,3,4}, . {1,2,3,4} } . {1,2,3,4,...,n-1,n,n+1} }

{2}+inf { {0,3}+inf, { {0,1,4}+inf, { {0,1,2,5}+inf, . . . { {0,1,2,3,...,n-2,n-1,n+2}+inf, . . . {1,3}+inf, {0,2,4}+inf, {0,1,3,5}+inf, {0,1,2,3,...,n-2,n,n+2}+inf, {2,3} } {0,3,4}, {0,1,4,5}, {0,1,2,3,...,n-2,n+1,n+2}, {1,2,4}+inf, . {0,2,3,4,...,n-1,n,n+2}+inf, {1,3,4}, . . {2,3,4} } . . {2,3,4,5} } . {2,3,4,...,n-1,n,n+2} }

{3}+inf { {0,4}+inf, { {0,1,5}+inf, { {0,1,2,6}+inf, . . . { {0,1,2,..., n-2,n-1,n+3}+inf, . . . {1,4}+ inf, {0,2,5}+inf, {0,1,3,6}+inf, {0,1,2,..., n-2,n,n+3}+inf, {2,4}+inf, {0,3,5}+inf, {0,1,4,6}+inf, {0,1,2,..., n-2,n+1,n+3}+inf, {3,4} } {0,4,5}, {0,1,5,6}, {0,1,2,..., n-2,n+2,n+3}, {1,3,5}+inf, {0,2,3,6}+inf, {0,1,3,...,n-1,n,n+3} }+inf, {1,3,5}+inf, {0,2,4,6}+inf, {0,1,3,...,n-1,n+1,n+3}+inf, {1,4,5}, {0,2,5,6}, {0,1,3,...,n-1,n+2,n+3}, {2,3,5}+inf, . {0,1,4,...,n,n+1,n+3} }+inf, {2,4,5}, . . {3,4,5} } . . {3,4,5,6} } . {3,4,5,6,...,n+2,n+3} }

 .	 .	.	.	.
 .	 .	.	.	.
 .	 .	.	.	.

{n}+inf { {0,n+1}+inf, { {0,1,n+2}+inf, { {0,1,2,n+3}+inf, . . . { {0,1,2,3,...,n-2,n-1,n+n}+inf, . . . {1,n+1}+inf, {0,2,n+2}+inf, {0,1,3,n+3}+inf, {0,1,2,3,...,n-2,n,n+n}+inf, {2,n+1}+inf, {0,3,n+2}+inf, {0,1,4,n+3}+inf, {0,1,2,3,...,n-2,n+1,n+n}+inf, . {0,4,n+2}+inf, {0,1,5,n+3}+inf, {0,1,2,3,…,n-2,n+2,n+n}+inf, . . {0,1,6,n+3}+inf, {0,1,2,3,...,n-2,n+3,n+n}+inf, . . . {0,1,2,3,...,n-2,n+4,n+n}+inf, {n,n+1} } . . . {n,n+1,n+2} } . . {n,n+1,n+2,n+3} } . {n,n+1,n+2,...,n+n} }

 .	.	.	.	.	.
 .	.	.	.	.	    .
 .	.	.	.	.	        .

Thus, a countable listing or enumeration of the finite and infinite subsets N is readily given by: P(N) = { N, Ø, {0}, {1}, {1,2,3,...}, {0,1}, {0,1,2}, {0,2},

        {0,2,3,4,...}, {1,2}, {2}, {2,3,4,...}, {3}, {3,4,5,...},
        {0,3}, {0,3,4,5,...}, {1,3}, {1,3,4,5,...}, {2,3}, {0,1,3},
        {0,1,3,4,5,...}, {0,2,3}, {1,2,3}, {0,1,2,3}, {0,1,2,3,4},
        {0,1,2,4}, {0,1,2,4,5,6,...}, {0,1,3,4}, {0,2,3,4}, {1,2,3,4},
        {0,1,4}, {0,1,4,5,6,...}, {0,2,4}, {0,2,4,5,6,...}, {0,3,4},
        {1,2,4}, {1,2,4,5,6,...}, {1,3,4}, {2,3,4}, . . . }

The finite subset or group of finite subsets of N contained in the array element located at row i and column j of our infinite array above can be generated by the compact expression: Sij (Cij, Bij, Eij) where i, j in N; Cij = < 0, 1, 2, 3, . . ., i+j >; Bij = { 0, 1, 2, 3, . . ., j-1, i+j }; [ here, Bi0 = { i } ] Eij = { i, i+1, i+2, i+3, . . ., i+j } whereby we take j-at-a-time increasing-order combinations (that is, j distinct elements) of the numbers in the Combination-subset-generator-base Cij beginning with the subset denoted by Bij and ending with the subset denoted by Eij. We perform some normalization procedure to the subsets of N in this collection of valid combinations by arranging the elements in each subset in increasing numerical order and discarding the subsets already included in array elements in the upper rows of the same column.

For examples, the finite subset or group of finite subsets of N contained in the array element Sij is generated as follows:

► i = 0, j = 0:	C00 = <0>;	B00 = {0};	E00 = {0};
	S00 = {{0}}
► i = 0, j = 1:	C01 = <0,1>;	B01 = {0,1};	E01 = {0,1};
	S01 = {{0,1}}
► i = 0, j = 2:	C02 = <0,1,2>;	B02 = {0,1,2};	E02 = {0,1,2};
	S02 = {{0,1,2}}
► i = 1, j = 0:	C10 = <0,1>;	B10 = {1};	E10 = {1};
	S10 = {{1}}
► i = 1, j = 1:	C11 = <0,1,2>;	B11 = {0,2};	E11 = {1,2};
	S11 = {{0,2},{1,2}}
► i = 1, j = 2:	C12 = <0,1,2,3>;	B12 = {0,1,3};	E12 = {1,2,3};
	S12 = {{0,1,3},{0,2,3},{1,2,3}}
► i = 2, j = 0:	C20 = <0,1,2>;	B20 = {2};	E20 = {2};
	S20 = {{2}}
► i = 2, j = 1:	C21 = <0,1,2,3>;	B21 = {0,3};	E21 = {2,3};
 	S21 = {{0,3},{1,2},{1,3},{2,3}}valid combinations
 	       =   {{ 0,3},{1,3},{2,3}}normalized
► i = 2, j = 2:	C22 = <0,1,2,3,4>;	B22 = {0,1,4};	E12 = {2,3,4};
 	S22 = {{0,1,4},{0,2,3},{0,2,4},{0,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}}valid combinations
 	          = {{0,1,4},{0,2,4},{0,3,4},{1,2,4},{1,3,4},{2,3,4}}normalized

Except for the empty set Ø and the set N itself, any finite element of P(N) (that is, each finite subset of N) can be expressed as a set: {a1,a2,a3,...,az} where z is in N+, a1, a2, . . ., az are in N; a1 < a2 < . . . < az. By the way we constructed our array elements, any {a1, a2, a3, . . ., az} is assured to be included in Sij where j = z and i = az (if it was not already included in the upper rows with i = a1 or a2 or a3 or . . . or az-1).

In retrospection, we reiterate here that the untenability of Cantor’s infinity theorems are simply best resolved by adhering to the Aristotelian doctrine of potential infinity.

BenCawaling@Yahoo.com

"In other words, one could simply remember that each infinite proper subset of N has a finite-subset-of-N precursor --- just remove the ending 3-dot ellipsis “. . .” from the infinite set, say, {n1,n2,n3,...,nz,...} for sufficiently large natural number z."

As Michael Hardy mentioned in the previous section, the set of even numbers is not the companion-infinite-proper-subset-of-N of any finite-subset-of-N, so the set of even numbers is not in your enumeration, so your enumeration does not include all subsets of N.

Also, who is the "we" you mention?

JumpDiscont (talk) 07:54, 18 April 2010 (UTC)

Is this assumption correct?

Why do we assume $f:A\to P(A)$ being one-to-one? This seems to be stronger than necessary.

IMVHO it is enough to assume f being any function $A\to 2^{A}.$ Then we show the set $B$ it is not an $f(b)$ output for any $b\in B$ (because such $b$ would belong to its image, so it must not be the $B$ element) and it is not $f(b')$ for any $b'\in B'=A\setminus B$ either (such $b'$ would have to belong to $B$ ).

That means $\forall x\in A\ (B\neq f(x))$ , so $f$ is not a surjection despite being injective or not.

As a result we get no function A→2^A is a surjection, so there's no such surjection — and, consequently, no bijection. Eventually, $\neg (|A|=|P(A)|).$

CiaPan 18:19, 3 February 2006 (UTC)

Good point: it is indeed stronger than what is needed. That doesn't make it "incorrect", but it does mean one can strengthen the result by deleting it. I have now done so. Michael Hardy 00:00, 5 February 2006 (UTC)

Thank you, Michael. It's not my invention – I got that point from the message by Wlodzimierz Holsztynski in Polish maths Usenet group (it's in Polish, semi-TeX notation; the last question reads 'So how could you dislike mathematics?')

Sorry for incorrect use of ′correct′ - I'm just en-1 user.
CiaPan 07:06, 6 February 2006 (UTC)

Self-contradiction in “proof by contradiction”

One of the “absorption laws” of propositional logic or statement calculus is: (P --> (Q AND R)) <--> ((P --> Q) AND (P --> R)). Thus, (P --> (Q AND ~Q)) <--> ((P --> Q) AND (P --> ~Q)).

The formal argument in the “proof” of general Cantor’s theorem can be summarized as follows ---

If there is a 1:1 correspondence between S and P(S), then the generator of T is in T. [1]

If there is a 1:1 correspondence between S and P(S), then the generator of T is not in T. [2]

Therefore, there is no 1:1 correspondence between S and P(S).

The conclusion follows from the “belief” that propositions [1] and [2] are contradictory. It might be argued that the conclusion follows from the contradiction “the generator of T is in T” AND “the generator of T is not in T”. However, the “absorption law” equivalence could not be discounted — that is, the latter contradiction claim also asserts the former “contradiction” claim. Moreover, it is the claims P --> Q and P --> ~Q that are separately demonstrated in this type of “proof by contradiction” and not the claim P --> (Q AND ~Q).

The following discussion by Alice Ambrose and Morris Lazerowitz in their book entitled “Fundamentals of Symbolic Logic” (New York: Holt, Rinehart and Winston; 1962) is enlightening in pointing out the logical defect in the preceding Cantor’s reasoning ---

Any two propositions of ordinary discourse are related in one of the seven ways described (pages 85 – 92) [equivalence, superimplication, subalteration, subcontrariety, contrariety, contradiction, and logical independence]. Failure to understand their relationships is responsible for many of the fallacies in reasoning. For example, contradictories and contraries, contraries and subcontraries, are frequently confused, and propositions are sometimes supposed to be equivalent when they are not.

As an illustration of a further logical relation commonly confused, take the two propositions ---

If it rains, the crops will be good. [1]

If it rains, the crops will not be good. [2]

It might be supposed that these two propositions could not both be true, and that, hence, a person who made both these statements would be uttering an inconsistency. One needs merely to note that both propositions are true under the condition that it does not rain, to see that they are consistent with each other, and that therefore the supposition of their inconsistency is a mistake. These propositions are subcontraries.

In symbolic logic, both Georg Cantor’s argument as well as Alice Ambrose and Morris Lazerowitz’s example are of the form: P --> Q and P --> ~Q. Moreover, ((P --> Q) AND (P --> ~Q)) --> ~P is a tautology --- it is a flawed (particularly when there is no relevant relation between P and Q) variant of “proof by contradiction”.

By the very definition of material implication, both P --> Q and P --> ~Q are true at the same time when P is false (regardless of the presence or absence of material relevance of the antecedent P to the consequent Q or ~Q) — so, invoking that these 2 propositional forms are inconsistent with each other is indeed preposterous. It might be argued (in fact, as guaranteed by the tautology scheme cited above) that the simultaneous truth of these two propositions _implies_ the falsity of the antecedent P. What I am counter-arguing is that they are _defined_ to be so — that is, it is a gross self-contradiction to call upon a definition to rationalize an argument. However, I reiterate that, as presented, the flaw in Cantor’s argument is in the false belief that [1] and [2] are contradictories (that is, when 2 propositions cannot both be true or both be false at the same time or that their conjunction is always false for all truth-value assignments to their atomic formulas or prime constituents).

Georg Cantor inferred his conclusion without regard for the material or factual truth of his two implication premises. In the simpler-to-analyze example by Ambrose and Lazerowitz on the “rain” and “good crops” relation, we can easily see that both the given implication-premises lack material truth:

There are countless of actual true-to-life circumstances whereby either “the crops will be good” or “the crops will not be good” is true without their truth being a direct consequence of the truth or falsity of “it rains”.

On the other hand, if “it rains” adequately only then “the crops will be good” is true while if “it rains” exceedingly hard so that flooding occurs then “the crops will not be good” is also true.

Ambrose and Lazerowitz expounded on the issue of escaping commitment to the conclusion of an inference which is also particularly relevant in pointing out the flaw in Cantor’s line of reasoning ---

It is to be noted that whenever an inference is made, not only is an implication asserted to hold between premises and conclusion, but both premises and the conclusion are asserted to be true [it is emphasized that modus ponens ((P --> Q) AND P) --> Q is a tautology]. Both these facts are relevant to a consideration of the means of escaping commitment to the truth of an inferred conclusion. There are, in general, two ways of doing this. One way is to deny that the implication holds. This amounts to pointing out that the argument is formally invalid. The second way is to take exception to the material truth of the asserted premises; that is, either to refuse to agree to the initial assumptions or to point out their actual falsity. The relevance of denying the truth of the premises depends upon a logical fact about the relation between the antecedent and consequent of any implication when the antecedent is false.

Consider the argument ---

If it rains, it pours.

It is raining.

Therefore, it is pouring.

This asserts, in part, that if the first two propositions are true then “It is pouring” must be true. Suppose now that either the implicative proposition “If it rains, it pours” is false or that “It is raining” is false. The conjunction of the two is in either case false. . . . the falsity of the antecedent (P --> Q) AND P is consistent with the falsity of Q as well as with its truth; hence, the truth of Q does not follow from the falsity of (P --> Q) AND P.

The function ~((P --> Q) AND P) --> Q is not tautologous --- the truth-value of Q is not uniquely determined by ~((P --> Q) AND P). In general, if one denies the material truth of the premises or refuses to assent to it, there is no logical necessity of assenting to the truth of the conclusion.

Applying Ambrose and Lazerowitz’s well-informed logical declarations to Georg Cantor’s alleged ”proof” of his hierarchy-of-infinite-power-sets theorem, it is easily seen that Georg Cantor’s argument is not a valid application of “proof by contradiction” deduction — we firmly deny the material truth of its implication premises or we refuse to assent to them on the ground that T [the set of all the elements of the infinite set S which are not contained in their respective images for the presumed one-to-one correspondence between S and its power set P(S)] is not really a completely constructible set (as defined, T is an indeterminate infinite set) or the contradiction with regard to the generator of T occurs only if we look at T as a completed totality of an infinite set.

The simultaneous truth of P --> Q and P --> ~Q when P is false are embodied in the definition of modern Fregean logic’s material implication (regardless of the presence or absence of material relevance of the antecedent P to the consequent Q or ~Q) --- so, it is a gross self-contradiction to call upon some definition (which cannot be contradicted) to rationalize a faulty alleged “proof by contradiction” argument. Furthermore, because both P --> Q and P --> ~Q are defined true when P is false, then they do not form a contradiction. The self-contradiction is in invoking that they form a contradiction in spite of the concerted efforts by present-day logicians justifying the modern meaning of material implication that they do not.

It might be argued that the defect is merely in the nomenclature “proof by contradiction” which could be immediately remedied by just dropping the “contradiction” reference to the argumentation. However, it is stressed that this is not simply the case --- rather, it is the abandonment by modern Fregean logic of the existential import of the universal quantifier that jettisoned such relations as subcontraries and left only contradiction relations in the traditional so-called Aristotle’s “square of opposition” (relating “All S is P”, “No S is P”, “Some S is P”, “Some S is not P”) --- the sides (contrariety, subcontrariety, superimplication, and subalternation) are discarded while the diagonal (contradiction) is retained.

In other words, in the classical Aristotlean logic, “All S is P” (also expressible as “No S is non-P”) and “No S is P” (also expressible as “All S is non-P”) implies the existence of S. With the Fregean logic interpretation dropping the existential import of a universal quantifier (cajoled by the seeming simplification offered by adhering to a Boolean algebra implementation), comes the definition of material implication with P --> Q and P --> ~Q being both true when P is false without any regard for any factual relevance relating the antecedent P and the consequent Q or ~Q. As a consequence, in modern Fregean logic, “it will be necessary to accept what at first sight is paradoxical” --- for example, “both ‘All leprechauns are bearded’ [which can also be stated as “No leprechauns are not bearded”] and ‘No leprechauns are bearded’ [which can also be expressed as “All leprechauns are not bearded”] will be counted true, given the circumstance that there are no leprechauns” [Ambrose and Lazerowitz].

Scientific theories rigorously observe the Aristotlean logic’s implied existential import of the universal quantifier so they are successfully applied in practice. In Fregean predicate logic, the formula (For all)vP --> (There exist)vP is a generally accepted theorem which makes explicit what was implicit in Aristotlean logic. However, the rationalization for defining material implication to be true whenever the antecedent is false had already been forgotten --- hence, the hidden self-contradiction (in the example cited about leprechauns, the apparent contradiction is easily seen when the statements with the same quantifier are compared).

It is noted that every model for a first-order theory is prescribed to have a non-empty domain. It is also stressed that any specification of a self-contradiction serves to define an empty set.

Related as “vacuous truths” to logic’s material implication “paradox” is the inherent “paradox” in set theory --- if the empty set is an element of any set’s power set (or a subset of any set), then the empty set is also an element of the power set of the given set’s complement set (or a subset of the given set’s complement set) --- thus, the set of all subsets of a given set and the set of all subsets of its complement set are not mutually exclusive despite the fact that their intersection set contains the empty set (this means a hierarchical level of interpretation for the supposedly unique empty set). In the present case, the self-contradiction is in discarding the existential import of the universal quantifier while giving existential attribute to the empty set — that is, the empty set has cardinal number 0 while the set that contains the empty set has cardinal number 1.

This engenders positive motivation for formulating some set theory based on the primitive concepts “set” and “subset” by considering power sets or sets of subsets instead of sets of individual elements (that is, {a} instead of just a) — the isomorphism with the incompletable set of all natural numbers whose every element has a successor is evident from the fact that every subset implies a superset. Thus, paradoxes involving the comparison of the sizes of two distinct sets with respect to “one being a subset of the other” and “one-to-one correspondence of their respective individual elements” would be mooted ab initio — that is, there will be no “uncountable set” unless the latter signifies “every subset (or, element) always has a superset (or, successor element)” or “not a completeable set”.

Every semantic paradox has its analog in set theory, and every set theory paradox has its semantic analog --- that is, every truth-value statement can be rephrased as a statement about sets, and vice versa. The liar-paradox assertion --- “This statement is false” --- can be translated into --- “This statement is a member of the set of all false statements”. The correlation with the completed infinite set self-contradiction is evident — that is, the countably infinite set of all false statements cannot be truly completed. Also, the more basic association with the general inexpressibility of the negation of a countably infinite whole (that is, “the set of all false statements” as the negative of “the set of all true statements”) in terms of its elements and their negatives (that is, the truth or falsity of every statement) is equally manifest. It is further stressed that the assertion “This statement is an element of the set of all true statements” is not a self-contradiction.

The preceding discussion is simply stated in symbolic logic. The truth of a countably infinite disjunction P1 OR P2 OR P3 OR … could be simply established by the truth of just one of its variables even though the latter are countably infinite; however, the truth of a negated countably infinite disjunction ~( P1 OR P2  OR P3 …) = ~P1 AND ~P2 AND ~P3 … could only be ascertained from the truth of all of its negated variables which might be impossible to establish for a domain with countably infinite number of elements.

This provides a very simple proof for Godel’s incompleteness theorem (the relevance of the encompassed natural number system is clear). Please read my discussion text in the Wikipedia article “Godel’s Incompleteness Theorems”. [BenCawaling@Yahoo.com --- 10 February 2006]

Self-contradiction in one-to-one correspondence (About the incomplete totality of the set of all prime natural numbers)

Essay and discussion moved to User:BenCawaling/Essay. Gandalf61 08:40, 14 April 2006 (UTC)

Cantor's theorem in metric spaces

AFAIK the result saying that in a complete metric space every descreasing sequence A_n such that $\lim _{n\to \infty }d(A_{n})=0$ (diameter converges to 0) has non-empty intersection is sometimes called Cantor's theorem. Do we have this theorem in wiki (maybe onther some other name)? --Kompik 08:46, 18 February 2007 (UTC)

Do you mean this one: http://mathworld.wolfram.com/CantorsIntersectionTheorem.html ?

I suppose it is not described in Wiki — see pages index at Special:Allpages/cantor. --CiaPan 16:25, 8 October 2007 (UTC)

Exactly. Also here [1] is a useful link. It could be added as a part of PlanetMath Exchange. I'll try to do so, when I have more time. --Kompik 22:05, 3 December 2007 (UTC)

Whoops - almost exactly. The theorem you mentioned is about compact sets. What I have mentioned was about complete metric space and closed sets (with a condition on diameter). --Kompik 22:08, 3 December 2007 (UTC)

Section on Controversy?

Instead of a "debate hall," could we not have a section discussing the controversies with this theorem? One that comes to mind is the assertion that an infinite set is any sort of a set at all. Landroo 20:15, 11 March 2007 (UTC)

Georg Cantor?

Oddly, the only person that this article links to is Ernst Zermelo. Isn't it usual to have something equivalent to "named for Georg Cantor" somewhere in the first few lines? —Preceding unsigned comment added by 130.243.139.62 (talk) 06:30, 13 November 2007 (UTC)

Link added in the theorem's name. --CiaPan 14:11, 13 November 2007 (UTC)

Find the flaw

Hi! What's the problem with this?

P(\mathbb {N} )=\{\varnothing ,\{0\},\{1\},\{0,1\},\{2\},\{0,2\},\{1,2\},\{0,1,2\},\{3\},\{0,3\},\{1,3\},\{0,1,3\},\{2,3\},\{0,2,3\},\{1,2,3\},\{0,1,2,3\}...\}

(We always add a new number to the previous steps) Isn't this a good enumeration? Mmarci (talk) 18:44, 6 January 2008 (UTC)

That's an enumeration of the set of all finite subsets of N. But P(N) is the set of all subsets of N (both finite and infinite). --Zundark (talk) 19:05, 6 January 2008 (UTC)

Zundark is of course right. But the other flaw is in the typesetting. It says

\{0,1,2,3\}...\,

where it ought to say

\{0,1,2,3\},\dots \,

i.e. "\dots" instead of "...". And I always use the comma in that context, although I don't know that the style manual says about that. Michael Hardy (talk) 20:00, 6 January 2008 (UTC)

Link to a disambiguation page???

There is a link (in "The proof" that leads to an disambiguation page: Diagonal argument - should not it link to one of the disambiguations (I am not sure to which one it should lead) 213.220.205.123 (talk) 20:14, 27 January 2008 (UTC)

I've fixed this by making this link to Cantor's diagonal argument – although there should be room for a a generic article on diagonal arguments. --Lambiam 03:51, 28 January 2008 (UTC)

Cantor Anti-Diagonal Argument — Clarifying Determinateness and Consistency in Knowledgeful Mathematical Discourse

Perhaps my unfinished manuscript "Cantor Anti-Diagonal Argument -- Clarifying Determinateness and Consistency in Knowledgeful Mathematical Discourse" would be useful now to those interested in understanding Cantor anti-diagonal argument. I was hoping to submit it to the Bulletin of Symbolic Logic this year. Unfortunately, since 1 January 2008, I have been suffering from recurring extremely blurred vision due to frequent “exploding optical nerves” brought on by my diabetes (I can’t afford laser eye surgery) and I had only about 20 productive days in the last 8 months. At this rate, it would take me a long while to finish my paper or may not be able to complete it if I go permanently blind soon. I just hope my endeavors to clarify mathematical infinity and modern logic would reach the next (if not the present) generations of mathematicians, philosophers, and logicians. [BenCawaling@Yahoo.com] BenCawaling (talk) 08:04, 4 September 2008 (UTC)

Then again, perhaps it wouldn't, since the site is no longer available. JumpDiscont (talk) 07:02, 25 April 2010 (UTC)

Ahem...

Isn't the whole story just predicate calculus ?

From :

$\lnot \exists \ b\quad [\forall x\quad (x{\mathcal {R}}\ b\iff \lnot x{\mathcal {R}}x)]$ , where ${\mathcal {R}}$ is any binary predicate, e.g. « barber paradox »,

we get, by replacing " $x{\mathcal {R}}y$ " with " $x\in f(y)$ " :

$\lnot \exists \ b\quad [\forall x\quad (x\in f(b)\iff x\notin f(x))]$

--Michel42 (talk) 19:35, 11 September 2008 (UTC)

Yes, that's the argument. — Carl (CBM · talk) 21:55, 11 September 2008 (UTC)

Cantor's fallacy

I note that “it is an emperical fact that something on the order of 90% or so of working mathematicians accept Cantorian set theory both in theory and in practice, to some extent”. And I have to say that such a low level of support, and even that only “to some extent”, for what is supposedly a proved theorem encourages me to point to what seems an obvious error in its alleged proof.

The proof of Cantor's theorem apparently says that, just for the sake of argument, we can assume, what none of us believes, that a one-to-one mapping exists, in some sense, from all possible subsets of the natural numbers into the natural numbers. So for the purposes of this “proof” we have a numbered list of all subsets of the natural numbers, including all subsets conceivable and inconceivable, definable and undefinable. Let us then, on the basis of that list, define a specific subset Q of the natural numbers. That subset Q must, in accordance with our opening assumption, occur at some position in our list. Let it be number N. The definition of Q then says that if N is in Q it is not, and if N is not in Q it is. And the proof says that because this is clearly nonsense we can be sure that our postulated mapping does not exist. But is it not obvious that it is Q, whose definition is patently self-contradictory, which cannot exist?

Can some kind reader please explain why only 10% of “working mathematicians” have doubts about the validity of Cantor's theorem.

W J Eckerslyke (talk) 10:58, 1 February 2009 (UTC)

I don't believe this has anything to do with the article at hand. In the interest of keeping talk pages focused on the goal of improving articles, talk pages are not an appropriate forum for this sort of discussion. I will point you at this paper, by Wilfred Hodges as an editor of the Journal of Symbolic Logic. It discusses a few mistakes people sometimes make about Cantor's theorem: [2]. — Carl (CBM · talk) 20:16, 1 February 2009 (UTC)

I had hoped that a clear demonstration of its invalidity might have been deemed to have something to do with the article at hand. I understand the need for an encyclopaedia to represent orthodoxy, but I believe a reasonable balance needs to be struck between orthodoxy and truth. I suggest that there should be a policy which says that if more that (say) 4% of working mathematicians have doubts about the validity of a theorem then at the very least the existence of those doubts should be mentioned in even the most orthodox article. W J Eckerslyke (talk) 12:55, 7 February 2009 (UTC)

I strongly doubt strongly that as much as 1% of mathematicians have any reservations about the correctness of Cantor's theorem. It is presented in essentially every introductory real analysis textbook, and has been completely formalized by the Mizar project. If there were any logical flaw in the proof it would be well known by now. So I agree that a clear refutation of Cantor's theorem would be relevant to the article at hand, but there isn't any such refutation.

The few mathematicians who might have issues with the proof don't think that the proof is literally wrong, they have issues with more general things like the use of infinite sets in mathematics. But I don't think the percentage of mathematicians with that viewpoint is 1% either. The 10% figure you are quoting is hard to fathom.

I do recommend the paper by Hodges, because he discusses several of the most common mistakes that he has seen in attempted refutations of Cantor's proof. — Carl (CBM · talk) 13:24, 8 February 2009 (UTC)

I agree with CBM. Cantor's theorem is true; its proof is valid; and virtually everyone agrees on these facts. JRSpriggs (talk) 21:05, 8 February 2009 (UTC)

But Cantor's theorem relies on the power set axiom ; perhaps the article should mention that we don't know (unlike choice or regularity) whether the power set axiom is compatible with other axioms of ZFC or not. --Michel421 (talk) 23:02, 21 March 2009 (UTC)

How does Cantor's theorem rely on the power set axiom? It can be stated as "For every bijection between a set and a collection of subsets of that set, there is at least one subset that is not in the range of the bijection." Stated that way, it makes no reference to powersets, and the proof does not use the powerset axiom.

Also, it's not clear what you mean by "don't know" that the powerset axiom is compatible with the axioms of ZFC. — Carl (CBM · talk) 00:45, 22 March 2009 (UTC)

I mean that there's no proof of relative consistency for the axiom, while there's one for the axiom of choice. --Michel421 (talk) 09:26, 22 March 2009 (UTC)

"For every bijection between a set and a collection of subsets of that set, there is at least one subset that is not in the range of the bijection." - Yeah but then any binary relation works as well (barber paradox), it's just predicate calculus. And without the power set axiom, that doesn't allow for the existence of non-denumerable cardinals --Michel421 (talk) 13:07, 22 March 2009 (UTC)

There's no consistency proof in ZFC, of course, but we know that we can't expect one anyway because of the incompleteness theorem.

You are also right that one cannot get non-denumerable cardinals without the power set axiom, but that doesn't mean that Cantor's theorem itself relies on the power set axiom. It's just that Cantor's theorem is usually stated that way because it's usually studied in a context where the power set axiom is available. The proof of Cantor's theorem works perfectly well in second-order arithmetic, even though there is no power set axiom in that context; Cantor's result shows that there is no sequence of sets of naturals that includes all sets of naturals. — Carl (CBM · talk) 13:29, 22 March 2009 (UTC)

I was talking about relative consistency, not the consistency of ZFC (which is not provable in ZFC). The incompleteness theorem didn't forbid relative consistency proofs for choice and regularity ; why should it forbid a relative consistency proof for the power set ? --Michel421 (talk) 18:08, 22 March 2009 (UTC)

I just meant that, because ZFC proves the consistency of ZFC - Powerset, ZFC cannot also prove "If (ZFC - Powerset) is consistent then ZFC is consistent". This is different than with AC because ZFC does prove "If ZF is consistent then ZFC is consistent", but ZFC does not prove that ZF is consistent.

It may be that there is some relative consistency proof for the powerset axiom that is not formalizable in ZFC, but the consistency of ZFC itself is also provable by methods that cannot be formalized in ZFC. I guess I don't see what you were getting at originally. — Carl (CBM · talk) 18:36, 22 March 2009 (UTC)

Computer Scientists Know Cantor Diagonal is Wrong

While most "main stream" mathematicians accept Cantor's Diagonal Proof, it's easily understood to be false by computer scientists who are "constructionists".

How many real numbers are there? Simple. As many as there are computer programs capable of generating the nth digit of a real number when asked. The total number of finite computer programs is countable, and can be listed. Every real number is generated by an algorithm on the list.

So, why doesn't Cantor's Diagonal Argument disprove my simple list? My list of all algorithms contains invalid algorithms that will "hang" and never finish calculating the nth digit when asked. The Halting Problem shows that we cannot ever remove all the algorithms that hang from the list. Therefore, Cantor's algorithm hangs! QED.

Ok... so that list only contains computable numbers, and there are some unusual "definable" but not computable numbers. In my view, the burden of proof for uncountable real numbers is on the mathematicians, as the Cantor Diagonal hangs on my list.WaywardGeek (talk) 21:37, 2 June 2009 (UTC)

Every finite algorithm run in a finite memory can reach only finite number of states, so it can generate only finite number of responses. That means it can generate only a finite number of independent digits. So you can not have an algorithm that generates a digit at arbitrary posistion of a real number, simply because you will be unable to give an arbitrary long input to define an arbitrary far position of the digit. Your countable set of algoritms can (at best case) generate a countable set of numbers of finite positional representation. --CiaPan (talk) 07:01, 3 June 2009 (UTC)

Argument nature

The refutation of Cantor's agument is quite simple. The error is similar to the logical puzzle about the barber who shaves all those who do not shave themselves. While at first blush plausible, such a barber is shown to be logically impossible. With Cantor, the diagonally constructed number also seems possible, but is actually a contradiction: what he defines is the last element of an infinite list of elements, which is of course logically impossible. ---stolf —Preceding unsigned comment added by Stolf (talk • contribs) 16:30, 11 September 2009 (UTC)

Cantor's argument uses reductio ad absurdum. That is, for the sake of argument, he assumes the opposite of what he wants to prove, and then deduces an impossibility from it.

So you should expect to see the argument end in a contradiction; it is supposed to do so. JRSpriggs (talk) 18:31, 11 September 2009 (UTC)

That's not necessary. Of course the argument can be expressed in reductio ad absurdum style as

'suppose the sets are equipollent; then there exists a bijective function between them; assume f is such bijection (...) and we see f is not a bijection'.

But you don't need to proove by contradiction if the statement can be proven directly: we show for ANY function f between given sets that f is not bijective, then we conclude such bijection does not exist, so the sets' cardinalities differ.

There is no place to emphasize the final contradiction, as we don't use a contradiction in the proof. --CiaPan (talk) 10:44, 14 September 2009 (UTC)

In other words, if a list were possible, it would show us what the last element looked like... but since there is no last element, there can be no list? i guess this would be the traditional interpretation of the argument.

i am trying to understand how such a patently absurd idea as "sizes" of infinite sets could have become orthodoxy, after having been rightly rejected when first proposed. it seems to me that cantor's argument is a paradox in that it entails that one of 2 impossible ideas must be true.....

(1) an infinite, hence unlimited, quantity can indeed be limited by something "bigger"....

(2) a clearly defined string of 1's and 0's (the diagonal construction) does not in fact represent any actual number at all....

whichever horn of the dilemma is true, it is certainly counterintuitive.... my thought that (2) is true follows the case of the barber...the idea is that just because something can be described, with words or even numerals, does not mean it exists....but how could the diagonal number not exist?....i don't know...perhaps to the extent that nothing notationally infinite can exist actually, only potentially.... ---stolf —Preceding unsigned comment added by Stolf (talk • contribs) 15:31, 14 September 2009 (UTC)

Sorry, I do not know how to explain it to you, as I can't even understand the first words of your question. What do you mean by if a list were possible? And what is a list? There is no such term neither in the theorem statement nor in its general proof.

Possibly you're refering to the case of natural numbers. Do you mean a hypothetical sequence of all sets of natural numbers? Or a 'list' of pairing off all those sets with natural numbers?

How can you define a 'last element' to an infinite list...? This is a contradiction, as 'last' implies 'finite'.

Where have you taken 'string of 1's and 0's' from? It does not appear here. If you want to discuss a diagonal argument article, please write there...

but if you want to talk/learn more/teach others about the Cantor's theorem and its philosophical, ontological, social and mathematical backgrounds and implications, then go to some maths discussion forum. Wikipedia's talk pages are not the good place for such talks:

Article talk pages should not be used by editors as a platform for their personal views, nor for casual conversation. Article talk pages are only to be used for discussing improvements to their associated pages.[3]

CiaPan (talk) 07:07, 17 September 2009 (UTC)

To Stolf: You seem to be laboring under many misconceptions about set theory. So it is hard to know where to start.

Mathematical logicians regard set theory as describing a completed totality (see Von Neumann universe), not merely a process for creating things.
"Infinite" merely means "not finite". It does not mean "unlimited" which is too vague to be a proper definition.
Every ω-sequence of zeros and ones can be evaluated as a real number in the interval [0,1]. What the diagonal construction gives you is a real number which is not in the original ω-sequence of reals in that interval. Thereby establishing that the mapping from the natural numbers to the interval [0,1] cannot be onto. JRSpriggs (talk) 01:36, 18 September 2009 (UTC)

Is the assumption behind Cantor's theorem valid?

I am new to editing Wikipedia and do not know all the conventions. Wikipedia encourages direct editing. The user Paul August suggested that I need to discuss and gain consensus for my edit on the talk page.

Here is the contention. Cantor’s theorem assumes that the power set exists for every set, regardless of whether the set is finite or infinite, based on the axiom of power set. Is this a valid assumption?

A recent book^[1] shows that this assumption cannot be made without a supplemental condition for finite sets and that there is no net increase in cardinality when this condition is taken into account. Moreover, this supplemental condition is not defined for infinite sets.

A (finite) set is defined as a collection of distinct elements. All elements of a (finite) set are different objects and there is a single instance of each element in the set – no object is repeated. For example, in the set S = {x, y, z} each of the three distinct objects “x”, “y” and “z” occurs just once in the set. Given the set S, we can form eight possible subsets of this set. However, we cannot claim all eight subsets can exist simultaneously because we have just one copy of each of the three objects “x”, “y” and “z” unless we use additional instances of the set S.

The book is self-published and that is why the entire argument is reproduced here. This contention can be reviewed based on the description on this page. If additional clarifications are needed I will gladly add those here.

Having to “wait indefinitely” sounds harsh and arbitrary. That said, if the situation was reversed and I was acting as an editor who controls what changes can or cannot be made, I might have imposed similar conditions because I understand we cannot have edits without adequate consensus. The churn would be enormous. However, I would feel a responsibility, I would even say a duty, to review each contribution in a fair, unbiased, and timely manner with perhaps one of these responses: (1) I don’t agree for the following reasons; (2) I agree; (3) I cannot find anything wrong with the argument but I am not ready to pronounce it correct yet (and then return at a later date and provide an answer).

The Power set of S is defined as P(S) = { {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} } and has eight subsets of S in it. These eight subsets cannot all exist as a “completed totality” because it requires fours instances of each of the objects “x”, “y” and “z” to exist simultaneously. For this to be feasible, we would need three additional copies of the original set S. To form the Power set of a set with n elements, we need 2^n-1 instances of that set. It should be no surprise that we land up with 2ⁿ subsets in the Power set. It is a direct consequence of the (implicit) assumption that the original set is counted 2^n-1 times. If one sums up the cardinalities of all subsets in the Power set of a set with n elements then this sum turns to be precisely n2^n-1, the exact product of the cardinality n of the original set and the 2^n-1 instances of the original set we needed to construct the Power set. We started with 2^n-1 sets each of size n and landed up with 2ⁿ subsets of this set but of sizes which range from 0 to n, hardly a profound result.

The user CiaPan commented that this logic is “absurd; just as if you said 3 can't be simultaneously equal 1+2 and 7-4 'cause that would require two instances of '3'” but this analogy is not correct. These are equations and there is no definition that limits the number of equations. However, set theory does define a set as a collection of distinct objects and most of set theory deals with the cardinality or count of objects in a set as well comparisons of the cardinalities of different sets. Zukojohri (talk) 12:46, 16 March 2016 (UTC)

References

^ Johri, Pravin K. & Johri, Alisha A. (2016). “Un-Real Analysis: Why Mathematics is Counterintuitive and Impact on Theoretical Physics”, Available from Amazon.com, ISBN: 978-1519776204

This way of reasoning leads to a conclusion the X axis and the Y axis of the Cartesian coordinate system on the Euclidean plane can not exist simultaneously! That's because a line is a subset of a plane, i.e. a set of points of a plane, and the two lines both contain the same point, namely the coords system's origin, (0,0) — and there's only one 'copy' of that point in the plane, so two lines can not have that point at the same time. ABSURD.
In a real-life analogy: there can't be a set of men and a set of New York citizens (both being subsets of 'humans') at the same time, 'cause every male Newyorker exists as a single individual, so he can't belong to two sets at the same time.
CiaPan (talk) 13:46, 16 March 2016 (UTC)

I appreciate your comments but I think you are missing the point. No one is making a general claim that there cannot be duplicates. For example, in a sequence an element of the sequence can be replicated an arbitrary number of times. However, we cannot call a sequence a set and cannot use set theory to study sequences. No one is even making the claim that there cannot be a power set (of a finite set) even though the objects inside the subsets in the power set have been replicated multiple times. The claim is one cannot start with a single copy of a set and construct the power set from this single copy. One has to start with multiple copies of the set because the power set contains duplicates of the objects in the original set. In particular, one needs 2^n-1 copies of a finite set of size n to construct its power set. Now, if one compares the cardinality of (one copy of) the original set and its power set, one can reach the conclusion that there is an increase in cardinality as Cantor did. But one should really compare the total cardinality of the starting state (multiple copies of a set), and the total cardinality of the ending state (the power set), and then there is no net increase in cardinality. The condition that one needs 2^n-1 copies of a finite set of size n to construct its power set cannot be extended to an infinite set as that expression is not defined in mathematics if n is infinite. Does the power set of an infinite set exist? It does not follow based on this reasoning. This argument does not preclude the use of some other form of reasoning to justify the existence of the power set of an infinite set. Zukojohri (talk) 12:46, 17 March 2016 (UTC)

Any more comments? What is the convention now? How long do I have to wait for additional comments before I can go and modify the main page? Zukojohri (talk) 12:26, 28 March 2016 (UTC)

I would suggest waiting indefinitely. Besides the probable WP:COI, this self-published book is not a reliable source (WP:SELFPUBLISH) and no one has agreed with you. Should you make edits consistent with what you have said above, they will be quickly reverted by many editors. Bill Cherowitzo (talk) 17:15, 28 March 2016 (UTC)

Yeah, sure... Similary:

One cannot start with a single copy of a set of humans and construct the set of women, the set of musicians and the set of Nigerians from this single copy. One has to start with multiple copies of the set of humans because the three sets contain duplicates of the people in the original set.

You seem to miss a basic property of a set: it is not a 'separate copy'; it's just a group of objects having some predefined property. For example a set of 'tall people' contains those who have the body length above some defined value, and 'footballers' are those playing football. You can be tall and be a footballer at the same time, just by meeting both defining criteria. That means you belong to both sets, although you are still a single entity. Odd numbers are integers which are not divisible by 2, prime numbers are integers not divisible by any natural number (except 1 and themselves). And number 13 is odd and is prime – it belongs to both sets, but still it is one number.

If we were to consider 'separate copies of objects', we would loose most of the set theory. How would you define a set intersection, which is a common part of sets, if sets have no elements in common, because each has its own 'copy' of objects? The two axes of coord. system would not intesect at the system's origin, because each would have 'its own copy' of the zero point, distinct from the same point in the other line. And not only coordinate systems' axes – no other lines or curves would intersect any more... More generally, no sets would intersect. Is it what you intend? --CiaPan (talk) 08:37, 30 March 2016 (UTC)

The book is self-published and that is why the entire argument is reproduced here. This contention can be reviewed based on the description on this page. If additional clarifications are needed I will gladly add those here.

Having to “wait indefinitely” sounds harsh and arbitrary. That said, if the situation was reversed and I was acting as an editor who controls what changes can or cannot be made, I might have imposed similar conditions because I understand we cannot have edits without adequate consensus. The churn would be enormous. However, I would feel a responsibility, I would even say a duty, to review each contribution in a fair, unbiased, and timely manner with perhaps one of these responses: (1) I don’t agree for the following reasons; (2) I agree; (3) I cannot find anything wrong with the argument but I am not ready to pronounce it correct yet (and then return at a later date and provide an answer).

Harsh, perhaps, but definitely not arbitrary. Wikipedia is not a free referring service and it has policies in place to ensure that it does not turn into one. While there are certainly individuals here who are capable of doing this work, our job is to report on what is accepted by the larger academic community. If you want Wikipedia to discuss your viewpoint, you need to have it vetted by that larger community first, and only then will we be able to add it to our articles. User CiaPan has gone beyond what is needed from an editor in responding to your comments and unfortunately this has encouraged you to continue. I, on the other hand, am following policy (Wikipedia:Verifiability) and won't even look at this material until it appears in a reliable secondary source (WP:Source). Bill Cherowitzo (talk) 17:33, 2 April 2016 (UTC)

I sincerely appreciate the comments from the user CiaPan. Even though I think the claim is described clearly, the fact that a reasonable reader has formed a different opinion than what I intended can mean one of two things: Either the claim is wrong or the claim is not described in a way everyone can follow exactly what is asserted.

I fully agree with this user - the basic property of a set is that it is a group of distinct objects satisfying predefined conditions and that the objects in the set exist. My claim is that the Power set imposes a very specific condition that the objects in the Power set need to satisfy, and this property has not been factored in Cantor’s theorem. So, there is no conflict between the claim and the definition of a set. This specific condition states that the Power set is the set of all subsets of a given set and it has to be factored in the question “can a Power set exist?”

To illustrate the claim I choose to use the simplest example: a set with just two objects in it. I could have used one of the examples cited by the user CiaPan but I think my example adequately covers the arguments this user is making. Take a pen and pencil from your desk and call this collection the set A = {pen, pencil}. Now, ask the questions:

Does the subset B = {pen} exist?

Does the subset C = {pencil} exist?

Does the subset D = A = {pen, pencil} exist?

The objects “pen” and “pencil” exist because the starting condition is that the set A exists. The answer to all three questions, taken one at a time, is yes because each subset is a group of objects with the predefined condition that the objects are in the set A. Even though no objects are repeated in the set A, and we only have a single pen and a single pencil in the set A, there is no conflict so far. All subsets can be created, one at a time, and the (single) objects pen and pencil can appear in multiple subsets (if we are independently asking the question whether each of those subsets exist).

I am not making the claim that the subsets B and D or the subsets C and D cannot have an object in common. I apologize if the original description created this impression. I am only making the claim specifically as it relates to a Power set.

The Power set S(A) = { {}, {pen}, {pencil}, {pen, pencil} } of the set A includes all three subsets of the set A defined above and the empty set. Isn’t there an additional condition imposed by a Power set? All these subsets must now exist concurrently or the Power set cannot exist as a completed totality? Try to take one pen and one pencil from your desk and form the Power set S(A) with just those two objects on your desk. It cannot be done unless a second pen and second pencil (that is, a second copy of the set A) is used!

Stated more generally, we need 2^n-1 copies of a finite set of size n to form its Power set. This implicit condition is not defined when we talk of the Power set of an infinite set and it raises the question whether the axiom of Power set is valid for an infinite set. In mathematics, we take the Power set to exist for all sets, finite or infinite, based on the axiom of Power set. An axiom is just a stipulation – that is an assumption which is taken to be always true. We need to refer to Hermann’s Weyl’s statement regarding infinite set theory:

… classical logic was abstracted from the mathematics of finite sets and their subsets …. Forgetful of this limited origin, one afterwards mistook that logic for something above and prior to all mathematics, and finally applied it, without justification, to the mathematics of infinite sets. This is the Fall and original sin of [Cantor's] set theory …

Just because we have looked at sets in a certain manner does not necessarily make it right and one must be open to re-examining some of the assumptions made in set theory.

I agree with the user CiaPan that the implications of this contention could be profound – “we could lose most of set theory” but not for the reasons cited by the user. Because there are serious implications we should carefully evaluate this contention and try our best to prove it wrong but ignoring it indefinitely is not fair.

Zukojohri (talk) 16:42, 2 April 2016 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Cantor's theorem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

overlaps with the diagonal argument article. Needs more discussion, right now it is proof oriented. CMummert · talk 19:06, 11 May 2007 (UTC)

Last edited at 19:06, 11 May 2007 (UTC). Substituted at 06:22, 7 May 2016 (UTC)

[1] Johri, Pravin K. & Johri, Alisha A. (2016). “Un-Real Analysis: Why Mathematics is Counterintuitive and Impact on Theoretical Physics”, Available from Amazon.com, ISBN: 978-1519776204

[1]