Feedback on Doron Zeilberger's Opinion 68
Feedback by Dana Scott
From dana.scott at cs dot cmu dot edu Sun Dec 18 10:47:52 2005
Greetings Doron:
Concerning you recent Opinion 68, I have to say emphatically that
you are overreacting again! Clearly the new results of Fox are
very dramatic; however, a quick internet search turned up slides
of a recent talk by Daniel J. Kleitman and Jacob Fox where it
is pointed out that Paul Erdős and Shizuo Kakutani already proved
in 1943 that the NEGATION of the Continuum Hypothesis is equivalent
to the equation x1 + x2 - x3 - x4 = 0 being countably-regular (i.e.,
with respect to countable partitions of the reals). This is a
result of the same type as those of Fox (if not as refined and not
as dramatic -- as far as the linear equation is concerned), so
if you are to be shocked, shocked by such things, you should have
been in a state of shock for the last 60 years!
Remember the old results of Hausdorff-Banach-Tarski, which in
particular claim that a solid sphere can be "broken" into finitely
many subsets and "reassembled" as two spheres of the same size
as the original ball. This method can only be done with a well
ordering of the real numbers, and a well ordering as a subset of
the plane is always a Lebesgue non-measurable set. In fact,
Sierpinski showed many years ago that a non-principal ultrafilter
in the Boolean algebra of all sets of integers also implies the
existence of a non-measurable set.
The lesson here is that arbitrary sets of reals can be monstrously
horrible. So? We have known this for a very long time. And don't
forget that people once hated the idea that there could be a
continuous function nowhere differentiable. But they learned
to live with these things and pay more attention to the non-
pathological functions, sets, and spaces.
The area where you -- as a combinatorial personality -- should
really be worried concerns the recent work of Harvey Friedman.
He finds propositions of FINITE combinatorics which are "true"
but can only be proved with the aid of very large cardinals.
He is speaking of cardinal numbers so large they make the
aleph_n cardinals look like baby toys. You can say these
"theorems" are not "interesting", but I personally think you
would be wrong. Ask Harvey for a quick lesson about his results.
And best wishes for the New Year!
Dana S. Scott
From dana.scott at cs dot cmu dot edu Mon Dec 19 15:31:36 2005
Hey Doron!
Thanks for the reply. We all could use some peaceful sleep
these days, but I really wish you would take a peek at Harvey's
brief paper on his new incompleteness results. (It is a six-page
abstract without proofs but with much attention given to putting
the statement into context.) He says:
> 'Beautiful' is a word used by mathematicians with a semi
> rigorous meaning. We give an 'arguably beautiful' explicitly
> Pi01-sentence independent of ZFC. See Proposition A from section 1.
The PDF-file can be downloaded from:
http://www.math.ohio-state.edu/%7Efriedman/pdf/Pi01120905.pdf
He makes a clear distinctions between things that are provable
and analogous statements which are independent. And I don't feel
that excluding potential infinity is the right move to happiness here.
As regards Fox, his statements are very, very nice (and he ties up
many loose ends), but I don't agree that he is "more concrete"
than the old Erdős-Kakutani result. (BTW, here is the reference:
"On non-denumerable graphs", Bull. AMS, vol. 49 (1943),
PP. 457-489. )
But we don't have to argue about this point considering all that
Fox has done.
I did some more searching and found a copy of his excellent
paper (at a non-MIT site!) as follows:
http://www.math.ucsd.edu/~sbutler/seminar/FoxRado1.pdf
I notice he credits you (and others) "for helpful advice and
comments concerning this subject matter" -- though he does not admit
to doing the Devil's work!
As regards measurability, I find it especially interesting that Fox
and a collaborator have shown in ZF set theory that the equation
x1 + 2 x2 + 4 x3 = x4
is NOT 4-regular if you assume the Axiom of Choice, but IT IS
if you assume Dependent Choice and Every Set of Reals Lebesgue
Measurable. (The latter assumptions were proved consistent with
ZF -- assuming an inaccessible cardinal -- by Solovay back in
1970.) There is no question that measurable sets are better than
non-measurable ones! (And Fox indicates other reasons to think
so.)
Indeed, the well known proof from Choice for finding a non-measurable
set by picking one representative out of each coset of the quotient
(R/Z)/(Q/Z)
(where R/Z is the additive group of reals mod 1, and Q/Z is the subgroup
of rationals mod 1), shows that choosing arbitrarily from a suite of
uncountably many sets is highly non-constructive.
So maybe the right advice here is simply: AVOID BAD SETS!
All the best,
-- Dana Scott
P.S. And, yes, you can post my comments. I would like to hear other
comments for other people as well.
Feedback by Alexander Zenkin
From alexzen at com2com dot ru Wed Dec 21 10:45:37 2005
Sent: Tuesday, December 20, 2005 10:00 PM
To: Doron Zeilberger (zeilberg at math dot rutgers dot edu)
Subject: As to 'Opinion 68'
Dear Doron,
Here are some 'people' who are your like-mindeds as to Actual Infinity
THE LIST-1 of scientists who rejected Actual Infinity.
- Aristotle, Euclid, Leibniz, Berkeley, Locke, Descartes, Kant, Spinoza
( d'Espinosa ), Lagrange, Gauss, Lobachevsky, Cauchy, Kronecker,
Hermite, Felix Klein, Poincare, Bair, Borel, Lebesgue, Brouwer, Quine,
Percy W.Bridgman (Nobel-1946), Wittgenstein, Weyl, Luzin, Errett Bishop,
Solomon Feferman, Jaroslav Peregrin, Valentin Fedorovich Turchin,
P.Vopenka and a lot of other outstanding CREATORS of the CLASSICAL
(i.e., working really) LOGIC and the CLASSICAL (i.e., working really)
MATHEMATICS AS A WHOLE !!! (see http://alexzen.by.ru/ ) And, of course,
Alexander Zenkin.
It should be accentuated here that beginning from Kronecker, i.e., from
about 70s of XIX century, the protest against a use of the actual
infinity in mathematics as a self-contradictory notion took the form of
the distinctly negative attitude to the set theory by Georg Cantor that
is based on the algorithmic usage of the actual infinity conception.
Some fatal nonsenses of 'naive' Cantor's as well as 'non-naive'
axiomatic set theory are considered in the recent papers.
> A.A.Zenkin, Logic of Actual Infinity and G.Cantor's Diagonal
> Proof of the Uncountability of the Continuum. - The Review of Modern
> Logic, Vol. 9, Number 3&4, 27-82 (2004).
>
> A.A.Zenkin, Scientific Intuition of Genii Against Mytho-'Logic'
> of Cantor's Transfinite 'Paradise'. - Philosophia Scientia, 9 (2), 145
> - 163 (2005).
http://alexzen.by.ru/papers/2005/Zenkin-PhilSc-9-2-2005.pdf
If one rejects actual infinity, then there is not "a continuous function
nowhere differentiable".
The actual infinity is a necessary condition of Cantor's diagonal proof
of the power-set theorem.
If one rejects actual infinity, then the theorem becomes unprovable and
therefore there are not any cardinals greater than aleph_0.
Best wishes for the New Year!
From alexzen at com2com dot ru Jan. 8, 2006
Dear Doron,
In your Opinion 68 you wrote:
"My mind was made up about a month ago, during a wonderful talk (in the
INTEGERS 2005 conference in honor of Ron Graham's 70th birthday) by MIT
(undergrad!) Jacob Fox (whom I am sure you would have a chance to hear
about in years to come), that meta-proved that the answer to an
extremely concrete question about coloring the points in the plane, has
two completely different answers (I think it was 3 and 4) depending on
the axiom system for Set Theory one uses. What is the right answer?, 3
or 4? Neither, of course! The question was meaningless to begin with,
since it talked about the infinite plane, and infinite is just as
fictional (in fact, much more so) than white unicorns. . ."
Here is another example of the like stupidity matured in
Cantor's 'paradise': a so-called cardinality of the continuum depends on
an indexing of its elements within the framework of Cantor's 'diagonal'
proof of his fundamental theorem on the uncountability of the continuum.
DESIGNATIONS: X=[0,1], N={1,2,3,.}, |Z| is a cardinality of a
set Z for any Z.
CDM = Cantor's Diagonal Method,
AST = Axiomatic Set Theory.
RAA = Reductio ad ansurdum.
Consider the traditional proof of Cantor's theorem.
CANTOR'S THEOREM (1890). "The set X is uncountable", i.e.,
|X|>|N|.
PROOF (by RAA-method). Assume that "the set X is countable",
i.e., |X|=|N|. Then there exists a 1-1-correspondence between elements
of X and N. Let
x1 , x2 , x3 , . . . (1)
be an enumeration (a list) of ALL real numbers from X. The
CDM-application to the list (1) generates a new real, say, y, which, by
its construction, differs from every real in the list (1). Consequently,
the list (1) contains NOT ALL reals from X. Contradiction. Q.E.D.
Now we shall prove a statement which clarifies one unknown
logical peculiarity of the Cantor diagonal argument.
THEOREM 3. The cardinality of the set X depends upon an indexing
of its elements in the list (1).
PROOF. Consider again traditional Cantor's proof.
CANTOR'S THEOREM. "The set X is uncountable", i.e., |X|>|N|.
PROOF. Assume that "X is countable", i.e., |X|=|N|. Then there
is a list
x1 , x2 , x3 , . . . (1)
of ALL real numbers from X.
However, from the standpoint of modern AST, the condition "X is
countable" means that X is equivalent to any countable set, e.g., to the
set Nev = {2,4,6,.} of all even natural numbers. It means that, by
virtue of the transitivity of the equivalency relation between countable
sets X, N and Nev, all elements of the initial Cantor's list (1) can be
re-indexed with the elements of the set, Nev :
x2, x4, x6, ... . (1.1)
Since the list (1.1) saves the number and the order of reals in
the initial list (1), the CDM-application to the list (1.1) generates
the same new Cantor's real y which doesn't belong to the list (1.1) like
the CDM-application to the initial list (1).
But now we have a possibility to index any (even infinite)
number of new Cantor's reals, generated by CDM-application to the
initial list (1) (or to the list (1.1) what is the same) and not
belonging to the list (1), with elements of the free set Nod = {1,3,5,
...}. It means that a number of elements in N is not less than a number
of reals in X, i.e., |N| >= |X|. The last means that the RAA-assumption
"X is countable" (|X|=|N|) becomes irrefutable, and consequently the
statement "The set X is uncountable" (|X|>|N|) becomes unprovable.
Thus, if the reals in the list (1) of Cantor's proof are indexed
with ALL natural numbers 1,2,3, . . ., then, according to the
traditional Cantor's proof, |X| > |N|. But if the same reals are indexed
with NOT ALL natural numbers (e.g., with 2,4,6,. . .), then |N| >= |X|.
It means that within the framework of Cantor's proof the cardinality of
the set X (continuum) essentially depends upon an indexing of its
elements in the list (1). Q.E.D.
It's obvious that the dependence of the cardinality of the
infinite set X upon an indexing of its elements is an absurdity from the
point of view of Cantor's ('naive') set theory as well as from the point
of view of modern ('non-naive') axiomatic set theory.
REMARK 1. From the Theorem 3 it follows, in particular, that the
infinite sets, X and N, may be equivalent, i.e., |X| = |N|, but there is
not a rule (algorithm) to establish a 1-1-correspondence between
elements of these sets.
Here is a direct proof of such a non-trivial possibility.
THEOREM 4. If X is equivalent to N, then there is not a rule
(algorithm) to produce a 1-1-correspondence between elements of X and N.
PROOF. Assume that X is equivalent to N, but there is a rule
(algorithm) producing a 1-1-correspondence between elements of X and N,
i.e., there is a list (1) containing ALL reals from X. Applying Cantor's
diagonal method (algorithm) to the list (1), we shall construct a NEW
real, say y, which doesn't belong to (1). Contradiction. Q.E.D.
Applying the law of contraposition to the Theorem 4, we get the
following quite strange statement.
COROLLARY 1. If there is a 1-1-correspondence between elements
of the sets, X and N, then these sets are non-equivalent.
It's obvious that the Corollary 1 is an ordinary stupidity of
Cantor's 'paradise' since that contradicts flatly to the definition
itself of the paradigmatic notion of the non-equivalency of infinite
sets of Cantor's set theory and modern AST.
MY MAIN CONCLUSION.
- Cantor's 'paradise' as well as all modern axiomatic set theory is
based on the (self-contradictory) concept of actual infinity. Cantor
emphasized plainly and constantly that all transfinite objects of his
set theory are based on the actual infinity. Modern AST-people try to
persuade us to believe that the AST does not use actual infinity. It is
an intentional and blatant lie, since if infinite sets, X and N, are
potential, then the uncountability of the continuum becomes unprovable,
but without the notorious uncountablity of continuum the modern AST as
a whole transforms into a long twaddle about nothing and really is "a
pathological incident in history of mathematics from which future
generations will be horrified" (Luitzen Egbertus Jan Brouwer).
Best regards,
Alexander Zenkin
Back to
Opinion 68 of Doron Zeilberger
Doron Zeilberger's Homepage