Comment by btilly | Hacker News Reader

Comment by btilly | Hacker News Reader

Parent Full thread

Your ignorance hides wisdom and an unexamined assumption in classical mathematics.

The problem is what does existence mean?

Classical math includes "procedures" with processes based on absolute truth. They avoid paradox only because you cannot reason about the reasoning process itself. The result of this is simpler arguments, but we must accept the existence of things that we can never, even in principle, write down.

Now let's change existence to mean that mathematical things only exist when we can write them down. (Classical mathematics calls this the constructible universe.) So procedures must be computer programs. Real numbers are represented computer programs that produce a sequence of rational numbers converging at a known rate. An enumeration of real numbers is a program that produces a list of programs that themselves represent real numbers. And so on.

Now try Cantor's argument. We start with an enumeration of the real numbers. A program that creates a list of programs. We then construct a new real number as per Cantor. So far so good. And, as Cantor said, the new real number cannot be on the enumeration. Cantor now concludes that there are more real numbers.

BUT his conclusion is now false! I can easily write down a program that lists every possible program. Ones that crash. Ones that run forever and never stop. And, yes, ones that represent real numbers. It is a countable list. And our new real is on the list!

The problem isn't that there are too many real numbers. It is that you can't decide whether or not a given program represents a real number without solving the halting problem. So every enumeration has a choice - it either includes things that aren't real numbers, or it misses some real numbers. But all the things that can be real numbers are on a countable list!

The only sense in which there can be "more" real numbers in classical mathematics is that we accept the "existence" of numbers whose claim to exist is extremely tentative. And we do so with decision "procedures" that depend on decisions made based on unverifiable absolute truths.

If you want a sense of how different mathematics looks if you don't do that, look up Constructivism.

> They avoid paradox only because you cannot reason about the reasoning process itself.

All of ZFC can be formulated with an effectively computable set of first-order axioms and every valid theorem has a proof which is nothing more than a finite string of symbols which can be checked in finite time.

It's really odd to claim that "you cannot reason about the reasoning process of classical mathematics".

The procedure used within Cantor's diagonalization proof depends on a sequence of choices, each of which is based on whether something is absolutely true, even though that truth cannot necessarily be established by any finite set of reasoning from a finite set of axioms.

Actually doing this requires making decisions based on absolute truth. The procedure could never be done in practice because there is no reasoning process available in first order logic that can always determine absolute truth. In fact even being able to determine the absolute truth of whether our current axioms are consistent would imply a contradiction. (Thanks, Gödel.)

Whether it makes any sense to talk about such constructions at all was the heart of the Formalist vs Constructivist debate about "the law of the excluded middle".

The formal first order proofs from ZFC that you mention depend on the axioms of ZFC. Which in turn are assumed. What is actually proven is, "If these are true, then that is the conclusion." But the axioms must be assumed. What is proven is that the axioms lead to the conclusion. And not that the axioms are true or the conclusion matches our naive notions of truth or existence.

As to that, a Constructivist can't even get through the first axiom of ZFC before finding problems to question. The axiom of extensionality says that two sets are equal if and only if they have the same elements. In classical mathematics, elements either are or are not in the set. And two sets either do or don't have the same elements. And we can build procedures based on that truth. But such statements based on absolute truth might not be able to be established through any reasoning process. Procedures requiring decisions made on such absolute truths cannot actually be performed. In what way can we establish existence by constructions involving impossible procedures based on information that no reasoning process can ever verify.

I will make this problem concrete.

Let's let A be the empty set. And B be the set of non-trivial zeros of the Riemann zeta function. According to classical mathematics, either ZFC may prove that A = B, it may prove that A is not B, or the question may be undecidable. If the question is undecidable, then through https://en.wikipedia.org/wiki/Second-order_arithmetic you can prove that A = B. (The principle of the proof is the same as how Gödel proved that if ZF is consistent, then so is ZFC.) Classical mathematicians happily accept that claim, even though it rests on a statement that might be true without any possibility of proof. And, furthermore, classical mathematicians will happily accept proofs based on constructions that require an infinite number of decisions that are similarly impossible to make through any form of first-order logic.

Constructivism collapses all of that. In that philosophy, we can't talk about the truth of any statement unless a proof as been found for or against it. Procedures may not depend on the impossible task of deciding the undecidable. Nor can we sneak such assumptions in through things like the axiom of extensionality. Which makes the classical proof just pointless symbol manipulation that implies nothing about what does or doesn't exist.

Here is the Constructivist view. If we assume things that make no sense, we conclude things that also make no sense. Rather than trying to understand the nonsensical conclusion, we should avoid the nonsensical assumption. There aren't an uncountable number of real numbers who can never be defined, even in principle, in any finite way. Mathematical things that can't be defined, simply don't exist.

This view only seems strange to us because it is impossible to study higher mathematics without being indoctrinated into the classical mathematical approach. It is only after learning to think outside of that box that you start to realize how arbitrary the implicit assumptions are.

> The formal first order proofs from ZFC that you mention depend on the axioms of ZFC. Which in turn are assumed. What is actually proven is, "If these are true, then that is the conclusion." But the axioms must be assumed. What is proven is that the axioms lead to the conclusion. And not that the axioms are true or the conclusion matches our naive notions of truth or existence.

That is true of every kind of mathematics. Ex nihilo nihil. There is no argument that can be made without any sort of axiom (you can derive tautologies, but only if you agree on at least the inference rules you're going to use - if you don't even agree on that you're out of luck).

You don't like the axioms of ZFC, or LEM, or whatever - fine. But you can't argue that whatever you want to use instead doesn't suffer from exactly the same problems. Maybe you find your axioms "more intuitive". Okay, and you're free to do mathematics in whichever way you prefer. But I guarantee that someone else will come along and tell you that your own axioms don't look all that intuitive to them. In fact, it seems like you assume that the integers exist. But an ultrafinitist would look at you in disbelief because they don't think that infinite sets exist at all (after all, where are the infinite sets in nature?). So which axioms are the "true" ones?

Personally, I'm not interested in metaphysical questions about what is "mathematically true". It's satisfying enough that a) we can constructively prove that classical proofs are valid chains of inferences from their axioms to their conclusions, b) nobody has found a contradiction in ZFC for over 100 years, c) the results we get from applying mathematics to the real world are astonishingly useful in all sorts of domains. Many mathematicians consider that a win and then move on without pondering about metaphysical things that we can never have an answer to.

> This view only seems strange to us because it is impossible to study higher mathematics without being indoctrinated into the classical mathematical approach.

Calling other people "indoctrinated" doesn't make your argument stronger. For the record, there's enough constructivist advocates hanging around programming-related communities, so it's not like these voices aren't heard here.

edit: And in any case, you did massively shift the goalposts here, because first you claimed that "we can't reason about the reasoning used in classical mathematics" (wrong, we can do all sorts of reasoning about classical reasoning without even having to resort to infinities and other weird things), now you're claiming that classical mathematics isn't "true" (or not provably so) - but that's an entirely different discussion.

No goalpost shifting.

Procedures in classical mathematics require a series of decisions made based on absolute truths accessible by no process of reasoning. Mathematics that includes entities created through such procedures avoid contradiction exactly because the truths are true, whether or not any reasoning exists that could show it.

Computability limits itself to procedures involving decision processes that can themselves be reasoned about. Attempts to create computable analogs of classical decision procedures reveal a whole world of logical subtleties thanks to the unavoidable possibility of self-reference.

The difference is this. In classical mathematics, diagonalization results in uncountable infinities. In computable mathematics, diagonalization results in undecidability. The reason why classical mathematics avoids undecidability is because decisions are made by appeals to absolute truth. Which represents a lack of process that therefore cannot be diagonalized.

Your argument is basically "my truths are true because they are true". That to me isn't mathematics anymore, it's metaphysics.

Thank you and all the very thoughtful and helpful replies!

Definitely going to check out Construvism, which is a new term to me, and was mentioned by several replies.

Reply on news.ycombinator.com