Talk:Axiom of choice/Archive 2/Ben

(This subarchive is split from the main archive Talk:Axiom of choice/Archive2 — contributors were User:Arthur Rubin, User:BenCawaling, and User:Lethe, who have all given permission for the refactoring.)

To add to the confusion — there are models in which the union of a well-ordered family of well-orderable sets is well-orderable, but the union of a countable number of countable sets is not necessarily countable. — Arthur Rubin | (talk) 18:11, 30 May 2006 (UTC)

Could you please point to me your reference for your cited “models”? The simplest proof I know that the union of a countable number of countable sets is countable is found in Leo Zippin’s “Uses of Infinity” (an MAA publication). Typically, the proof that the union of two countable sets is countable goes by taking alternating elements from each of the two countable sets — for example, given {a₁, a₂, a₃, …} and {b₁, b₂, b₃, …}, then {a₁, b₁, a₂, b₂, a₃, b₃, …} proves the countability of their union set. Do you believe this proof? Does this union set “enumeration” really present a 1-1 correspondence with the natural numbers — remember that the two given sets are both countably infinite? My counterpoint is related to “uncountability claim” by Cantor’s diagonal argument. Cantor’s original diagonal argument (see Bertrand Russell’s “Prnciples of Mathematics”, Section 346) was applied to infinite binary sequences — let us just use “0” and “1” and their permutations taken infinity-at-a-time. Here we have two countably infinite sets (because they only differ in a finite count of digits since they all have the same digit at the omegath position) — all the permutations that have “0” in the omegath position and all those that have “1” at the omegath position. It seems we have contradictory conclusions here. [[email protected]] BenCawaling 09:52, 12 June 2006 (UTC)

The proof that the union of a countable number of countables sets is countable requires some form of the axiom of choice. My statement here is that UW (the union of a well-orderable set of well-orderable sets is well-orderable) does not imply UCC (the union of a countable set of countable sets is countable) in ZF. (I'd give a reference, if I believed you would really be interested. ) — Arthur Rubin | (talk) 17:17, 12 June 2006 (UTC)

But I am seriously interested. I am collecting these "stuffs" so I could find the flaws in them --- or, perhaps, they may convince me of the existence of "uncountable" sets. Leo Zippin's proof is very simple --- indeed, his "little book" is for high school students --- it does not require the axiom of choice. He simply "enumerated" each element x(i,j) where the indices are the ith element of the jth collection and the sum i+j is [0,1,]2,3,4,... [[email protected]] BenCawaling 10:49, 13 June 2006 (UTC)

That's a proof that ω × ω is countable. It's distinctly different from UCC. Unless you can see the difference, or why UW is non-trivial, I don't see the point in giving examples. — Arthur Rubin | (talk) 17:51, 13 June 2006 (UTC)

It certainly helps if one reads cited references. I have no intention of embarrassing you here but I am compelled to inform you (more importantly the other Wikipedia users) of the following excerpt from pages 54 – 55 of Leo Zippin’s “Uses of Infinity” book (No. 7 in The Mathematical Association of America’s New Mathematics Library “series written by professional mathematicians in order to make some important mathematical ideas interesting and understandable to a large audience of high school students and laymen”).

“Theorem : Let S be a set of sets S₁, S₂, S₃, … . If S is finite or has the power Aleph-0, and if all sets S₁, S₂, S₃, … have the power Aleph-0, then the set of all objects belonging to these sets also has the power Aleph-0.

This assertion can also be written in the form of equations: 1 × Aleph-0 = Aleph-0, 2 × Aleph-0 = Aleph-0, 3 × Aleph-0 = Aleph-0, …, Aleph-0 × Aleph-0 = Aleph-0.

The proof is simple. By hypothesis, every set S₁, S₂, S₃, … can be arranged in a sequence. Let us denote by x(i,j) the ith object in S_j. For instance, x(2,3) denotes the 2nd object in the 3rd sequence S₃. Now, there is only a finite number of terms x(i,j) with i + j equal to some number a. Hence, we can arrange the terms with i + j = 2 into a sequence, follow it by the sequence containing all terms with i + j = 3, follow this by a sequence containing all terms with i + j = 4, etc. Then, we obtain a sequence consisting each object occurring in any S_j at least once. Strike out the repetitions and you have a sequence containing each of our objects exactly once.

When a set of objects is put into one-to-one correspondence with the integers in this way, it is said to be counted. A set which can be counted is called countable. The theorem stated above asserts that a finite or countable infinity of countable infinities is countable. A set which cannot be put into one-to-one correspondence with the integers in this way is called uncountable.”

I could very well be just a lowly mathematical layperson but my simple understanding of the above quoted text is crystal clear — Doesn’t “the set of all objects belonging to these sets” mean the “union set”? Don’t “finite” and “the power Aleph-0” mean “countable”? Doesn’t “Aleph-0” and “ω” mean the same thing? Also, “by hypothesis, … countable” means you are given sequences for each S_j and for their collection-set S — it doesn’t matter if there are infinitely many ways of enumerating the elements of a countably infinite set, you simply use the one given “by hypothesis”. I read your user page and you claim to have a Ph. D. in Mathematical Logic from California Institute of Technology. Judging from your comments that I have read in Wikipedia articles (indeed, I was recipient of several of them including the last one at bar — here, I don’t mind if I am wrong and corrected but you are arrogantly declaring that Leo Zippin, a professional mathematician (as a matter of fact, this is a standard textbook proof with no known author), and all the editors of the MAA New Mathematical Library book series, are wrong (your favorite adjective in Wikipedia talk pages), I frankly do not share your own authoritarian, extremely high opinion of your imagined mathematical prowess — in fact, I am truly doubtful you could provide me with your cited reference(s). You are just typical of the present majority crop of “mathematicians” when it comes to Cantor’s transfinite theory.

Zippin is not wrong, nor did Rubin ever claim that he was. Zippin's proof is correct. He doesn't mention the axiom of choice in his proof, nor should he. It is, afterall, a book for high schoolers. But his proof does rely on the axiom of choice implicitly. When he assumes that he can label the elements of the union x_i,j, he has already invoked choice. Every bit of his proof after that is showing that ω×ω is equipollent with ω. Now Ben, if you would like to understand the axiom of choice, I would suggest that you stop reading high school books. Furthermore, be aware that very many people ues the axiom of choice implicitly. That means that they don't tell you that they're using it. It can therefore be hard to know whether they are using it or not, unless you understand the axiom of choice very well. Even the people writing the proofs may not know when they are using it. So please don't post any more proofs which don't mention choice as evidence that something can be proved without choice. -lethe ^{talk +} 08:47, 15 June 2006 (UTC)

Well, I still do not rest my case. There is still the contradictory conclusion with Cantor’s diagonal argument — I’ll try to make my comments “decipherable” for your level of understanding. First, in his book “Principles of Mathematics”, Bertrand Russell cited Cantor’s diagonalization proof as follows —

“Let m and w, Cantor says, be two mutually exclusive characters, and consider a collection M of elements E, where each element E is a denumerable collection, x₁, x₂, . . ., x_n, . . ., and each x is either an m or a w. The collection M is to consist of all possible elements E of the above description. Then M is not denumerable, i.e., it is of a power higher than the first. For let us take any denumerable collection of E’s, which are defined as follows:

E₁ = ( a₁₁, a₁₂, ..., a_1n, ... )

E₂ = ( a₂₁, a₂₂, ..., a_2n, ... )

E₃ = ( a₃₁, a₃₂, ..., a_3n, ... )

. . .

E_p = ( a_p1, a_p2, ..., a_pn, ... )

. . .

where the a’s are each an m or a w in some determinate manner. (For example, the first p terms of E_p might be m’s, the rest all w’s. Or any other law might be suggested, which insures that the E’s of our series are all different.) Then, however our series of E’s be chosen, we can always find a term E₀, belonging to the collection M, but not to the denumerable series of E’s. For let E₀ be the series ( b₁, b₂, ..., b_n, ... ), where, for every n, b_n is different from a_nn — i.e., if a_nn is an m then b_n is a w, and vice versa. Then, every one of our denumerable series of E’s contains at least one term not identical with the corresponding term of E₀, and hence E₀ is not any one of the terms of our denumerable series of E’s. Hence, no such series can contain all the E’s, and hence the E’s are not denumerable, i.e., M has a power higher than the first.”

Now, I resolutely challenge you to prove yourself worthy of your mathematical self-importance — which of my following assertions is flawed and why? Please do be gentle with your counterarguments on my limited understanding.

1. Granting arguendo Cantor’s concepts of “completed infinite sequence” and “all-at-once view of the totality of an infinite set”, the determinate definition of each E ensures that the character at the ωth position is known and also the “completed totality” of the infinite set M.

2. The set B of all infinite binary sequences (that is, the permutations of {0,1} taken infinity-at-a-time) is an equivalent-superset to Georg Cantor’s collection M. The set B is the union set of B₀ and B₁ where B₀ is the set of all infinite binary sequences with the digit 0 at the ωth position and B₁ is the set of all infinite binary sequences with the digit 1 at the ωth position.

I prefer using the binary digits {0,1} over Cantor’s {w,m} because we could easily relate, by just prefixing each infinite binary sequence with a binary expansion point, B₀ (if it suits you, ignore the 0 digit at the ωth position) equal to the set of all fractional rational numbers plus 0 (that is, 0.000…) and B₁ equal to the set of all fractional irrational numbers plus 1 (that is, 0.111…). We could discard 0 from B₀ and 1 from B₁ and simply consider the open interval (0,1).

In common binary system, π – 3 = 0. 0010010000111... . The 1-1 correspondences — <0.0, 0.00, 0.001, 0.0010, 0.00100, 0.001001, …, π - 3> <--> <0, 0, 1, 0, 0, 1, …, 1> [here, “<” and “ >” were used as delimiters instead of “{” and “}” to emphasize that we are dealing with sequences which allow for duplicate terms and with fixed order for each term and not with sets] affirms Cantor’s “completed infinite sequence” to capture the fractional irrational numbers — justifying the digit 1 at the ωth position of their binary expansions.

3. Both B₀ and B₁ are countable sets — because all the elements in each respective set differ in their digits only in a finite count of positions since they all have the same digit at the ωth position (by Cantor’s definition of the first transfinite ordinal number ω, all numbers preceding it are finite natural numbers). For B₀, all its elements can be enumerated by starting with the infinite binary sequence with all 0s as its digits and listing all the other elements in the order that they differ digit-for-digit from left to right from it — that is, 00000…, 10000…, 01000…, 11000…, and so on. Similarly for B₁, all its elements can be enumerated by starting with the infinite binary sequence with all 1s as its digits and listing all the other elements in the order that they differ digit-for-digit from left to right from it — that is, 11111…, 01111…, 10111…, 00111…, and so on.

I also emphasize that the respective countability of both B₀ and B₁ are evident from the inapplicability of Cantor’s diagonal argument separately applied to each set. A complete row-listing of all the elements of B₀ would yield an anti-diagonal “fractional irrational number” whose ωth digit is 1. Likewise, a complete row-listing of all the elements of B₁ would yield an anti-diagonal “fractional rational number” whose ωth digit is 0.

4. The union set B of B₀ and B₁ is a countable set being the union of two countable sets — by applying the above theorem.

5. On the other hand, granting arguendo Cantor’s transfinite ordinal numbers, if we row-list all the elements of B (the “last” column for each element has an index ω) — the union set of the two countable sets B₀ and B₁ — then the “last” row has an index ω + 1 simply because, say, one element from B₀ must follow the ωth row element from B₁ since, otherwise (if the last row has index ω only), B₀ would have a finite cardinality (or, vice versa on B₀ and B₁). In plain words, we do not have an “infinite square”, as Cantor thought, in his diagonal argument. As a matter of fact, the (ω+1)th row element is the anti-diagonal element!

This is as “decipherable” as I could get. Let the readers decide. [[email protected]] BenCawaling 04:00, 15 June 2006 (UTC)

(quoting from your first argument.) The proof is simple. By hypothesis, every set S₁, S₂, S₃, … can be arranged in a sequence. Let us denote by x(i,j) the ith object in S_j.

STOP. The assertion that S₀ (real mathematicians start with 0), S₁, S₂ are countable means:

$(\forall i\in \omega )(\exists f)(f:\omega \leftrightarrow S_{i})$

Without the axiom of choice (which Leo Zippin may be implicitly assuming), it does not mean:

$(\exists f)(\forall i\in \omega )(f(i):\omega \leftrightarrow S_{i})$

(By $f:A\leftrightarrow B$, I mean f is a surjection from A to B. My mother usually used $f:A\approx B$, but I don't want to confuse you.)

As for your anti-Cantor argument, there is no ω^th element of the sequence to be "completed" There is no ω^th coordinate of E_i, nor is there an E_ω. I don't know how to make it plainer. — Arthur Rubin | (talk) 06:36, 15 June 2006 (UTC)