Talk:Cantor's theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] 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.

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

[edit] ===

hjgkukyufjktugu 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

[edit] 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

[edit] =

> 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

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)

[edit] [[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)


[edit] '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

[edit] 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 \ne f(x)), so f is not a surjection despite being injective or not.

As a result we get no function A→2A 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?') image:smile.png
Sorry for incorrect use of ′correct′ - I'm just en-1 user.
CiaPan 07:06, 6 February 2006 (UTC)

[edit] 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]

[edit] 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)

Retrieved from "http://en.wikipedia.org../../../c/a/n/Talk%7ECantor%27s_theorem_0367.html"