21

When one writes down the axioms of ZFC, or any other axiomatic theory for that matter, and making statements like "let x, y ..." doesn't this assume an understanding (and thus existence) of natural numbers implicitly? (Q1)

How is the reader to interpret statements such as existence of separate symbols, nevermind sets, without an intuitive notion of numbers?

Bourbaki talks about this within the framework of metamathematics, but then declares that the reader can read words, differentiate between different words etc. and that to assume otherwise is idiotic.

Is there an introduction to these circle of ideas & debates somewhere you'd recommend? (Q2)

Deniz
  • 387
  • 3
  • 9
  • 5
    This kind of issue is raised by Poincare in "Science and Method", and (if I both remember and understand correctly) forms part of his criticism of impredicative definitions (such as the definition of the number two as the equivalence class of all two elements sets under the equivalence relation of bijection). – Emerton Nov 26 '10 at 06:05
  • Related question: http://mathoverflow.net/questions/40296/is-it-important-to-distinguish-between-meta-theory-and-theory – Martin Brandenburg Nov 26 '10 at 09:02

4 Answers4

25

It seems that Deniz is raising a slightly uncomfortable question of whether some circularity is built into mathematical foundations. A similar common-sense circularity is what might be called the "paradox of the dictionary": since all words are defined in terms of other words, either dictionaries are hopelessly circular, or some words need to be left undefined in order to break out of the impasse.

As it happens, I am preparing an article for eventual exportation to the nLab which at the outset deals with precisely this question. In the present draft, I have this passage:

Logical foundations avoids this paradox ultimately by being concrete. We may put it this way: logic at the primary level consists of instructions for dealing with formal linguistic items, but the concrete actions for executing those instructions (electrons moving through logic gates, a person unconsciously making an inference in response to a situation) are not themselves linguistic items, not of the language. They are nevertheless as precise as one could wish. $$ $$ We emphasize this point because in our descriptions below, we obviously must use language to describe logic, and some of this language will look just like the formal mathematics that logic is supposed to be prior to. Nevertheless, the apparent circularity should be considered spurious: it is assumed that the programmer who reads an instruction such as "concatenate a list of lists into a master list" does not need to have mathematical language to formalize this, but will be able to translate this directly into actions performed in the real world. However, at the same time, the mathematically literate reader may like having a mathematical meta-layer in which to understand the instructions. The presence of this meta-level should not be a source of confusion, leading one to think we are pulling a circular "fast one".

In other words, to break out of the circularity, it is enough to observe that computers can be programmed to recognize certain strings as well-formed terms or formulas (of a given axiomatic theory), and how to recognize inferences as valid. It's not as if there needs to be some background theory, or the prior existence of a completed or actual infinity of all expressions which might come up, sitting inside the computer. The computer is programmed to handle finite parts of the theory correctly, and the same applies to human users of a theory (although we say "taught", not "programmed").

Todd Trimble
  • 52,336
  • Am very glad that you are working on writing this up. – Urs Schreiber Nov 26 '10 at 14:50
  • Is it complete now? – Deniz Apr 01 '14 at 07:13
  • 2
    @Deniz: I do not agree with Todd's proposed escape from circularity. His proposal implicitly assumes that there is a purely deterministic procedures to check a proof encoded as a string and stored in some physical medium. That is in fact assuming more than the consistency of PA. How do you know that the computer actually does what is claimed? You don't, unless you assume that the computer is in a world governed by some underlying system that already contains a manifestation of the natural numbers. – user21820 Dec 29 '15 at 06:56
  • 1
    @Deniz: Worse still, if the universe has finitely many particles, then no such physical procedure for checking proofs over first-order logic can even exist! The conventional response is that we are talking about an ideal computer, such as a Turing machine, but that is self-defeating because any idealization can only be done in yet another logic system, and precisely because it is once again estranged from the real world, the same reliance on the abstract notion of natural numbers and their properties is an obviously unjustifiable one. – user21820 Dec 29 '15 at 07:02
  • @Deniz: An alternative would be to claim that our mathematical notion of $\mathbb{N}$ is merely an approximation to some manifestation in the real world, but we then have to admit that our formal systems are not necessarily embeddable in the real world, which means that either we accept that many theorems are simply meaningless or wrong in the real world, or we resign mathematics to being a symbol-pushing game. Note that if you claim that the natural numbers actually embed into the universe, then as in my first comment we are assuming even more than Con(PA), essentially. – user21820 Dec 29 '15 at 07:09
  • 1
    Regarding meaning in the real world, that is not the requirement of theorems: what is the meaning of Fermat's last theorem? – Fan Zheng Oct 15 '16 at 01:35
  • @FanZheng: That's an easy question to answer! It means that there are no four decimal integer strings $x,y,z,n$ such that the Python-3 program n>2 and x**n+y**n==z**n returns true. – user21820 Feb 25 '17 at 07:00
  • 1
    @user21820, I don't know enough about Python 3 to know whether the most trivial objection to that meaning is valid: does Python support bigints natively? Even if this trivial objection isn't satisfied, I'm not sure that I want the meaning of Fermat's theorem to be tied to a particular piece of software, necessarily (not anything to do with Python, just with software) with its own bugs. If it comes down to that, what if I compile Python with a version of Ken Thompson's compiler designed specifically to make Python programs report true when they detect attempts to probe FLT? – LSpice Oct 06 '17 at 17:22
  • @LSpice: Yes Python 3 supports big integers natively. Anyway if you know computability theory you will know that that's clearly not the point; we all assume the existence and basic properties of finite binary strings precisely because we have some real-world notion of them. If we did not in the first place have finite binary strings in any physical media, we would not even have come up with axioms stating their properties (nor the axioms of PA−, which are interpretable in TC). See also this for more related points. – user21820 Oct 07 '17 at 04:36
  • @LSpice: I also wish to address your last point, which is that it is simply irrelevant. Any compiler that does not implement Python 3, exactly as it was designed, is by definition not a compiler of Python 3. It should have been clear that I made a claim about real Python-3 compilers, not fakes. Just saying that compilers can have bugs in them is actually an evasion of the real issue, just as I can equally say that your browser's implementation of HTTPS could have bugs in it. But see, HTTPS would work if there are no bugs, and that fact verifies the mathematics behind it. – user21820 Oct 07 '17 at 10:14
  • @LSpice: Incidentally, the fact that you can read MathOverflow pages is something that you'll not be able to explain without agreeing that Fermat's little theorem (which is provable in PA) has real-world meaning in much the same manner as I claimed for Fermat's last theorem, at least for numbers up to $2^{2048}$. Don't forget that HTTPS was designed based on Fermat's little theorem, after it was proven by mathematicians, and would not have been discovered otherwise. So there is indeed some abstract nature of programs that PA captures at small scales. – user21820 Oct 07 '17 at 10:23
  • 1
    @user21820, I am not claiming that theorems have no real-world consequences, only that I am not prepared to judge the theorems' meanings by those real-world consequences—especially if they are tied to highly fallible things like a specific piece of software. (I would be equally sceptical if the mathematical meaning of a theorem were to be judged completely by one person's proof of it.) I don't even know what it means to say that a piece of software would work if it had no bugs, and that that verifies the mathematics; that seems too circular an argument to be falsifiable. – LSpice Oct 07 '17 at 17:01
  • @LSpice: I think I understood your point. My point above was that you are going to have a tough time explaining how billions of people and probably trillions of HTTPS connections per year are made and none of them seem to fail inexplicably. If you understand HTTPS, you would know that successful connections require Fermat's little theorem to work for a particular instance unique to each webpage, and failure would mean that you can't decrypt, not to say read the webpage. This is empirical verification far better than almost all scientific theories, so you shouldn't bring up "falsifiable". – user21820 Oct 07 '17 at 17:07
  • I was wondering whether this is the article mentioned in the post (which was a draft at the time): Todd Trimble: Notes on predicate logic. (Maybe it would be worth including a link into the answer? Although I know that some MO users are not too keen on bumping old questions.) – Martin Sleziak Aug 07 '22 at 08:44
  • @MartinSleziak Yes, that was the one. Maybe some day I'll get back to it (although I think the nLab has disabled some of the personal pages). – Todd Trimble Aug 08 '22 at 13:26
20

This issue came up both in the logic course that I taught last semester and in the set theory course that I am teaching this semester.

What I told the students is that in order to do mathematical logic, we need a basic understanding of words over a finite alphabet. We cannot build a theory from less than that.
But if we understand finite strings, we basically have the natural numbers.
Some parts of mathematical logic assume some basic set theory, such as the completeness theorem of first order languages over uncountable alphabets (or just alphabets that are not recursively enumerable). But this can be avoided if you stick to sufficiently simple alphabets (or even finite alphabets).

Similarly, you cannot do axiomatic set theory without a basic understanding of logic, which in turn requires a basic understanding of strings.

On the other hand, once you have built a sufficient theory of logic and set theory, you can use that in order to analyse mathematics. This is somewhat similar to the way that we learn mathematics: You learn to add natural numbers first, and then (usually something like 12 or more years after that) you learn about Peano Axioms that put everything on a solid foundation. I believe that this sort of circle cannot be avoided.

Stefan Geschke
  • 16,346
  • 2
  • 53
  • 80
  • In some sense, we formalise the things we want to study (sets, numbers, whatever), and that formalisation necessarily is built on the (observed) properties of the things we want to study. I.e. we observe that natural numbers have certain properties, and invent a formalisation (e.g. Peano arithmetic) that fits. So in this sense, the circularity is by design. – Ketil Tveiten Nov 26 '10 at 09:02
  • 2
    @Ketil: I agree that the circularity is by design, but I also don't see a way it could be avoided. You have to built on something in order to built a foundation of mathematics.

    There is one striking example where we seem to built something from nothing, and that is the von Neumann hierarchy of sets. Starting from the empty set, we construct all sets by just iterating the power sets operation. But in order to carry out this approach, we need to be able to define things using formulas. And hence we need formulas. And hence we need strings. And then we are back to the natural numbers.

     – Stefan Geschke Nov 26 '10 at 09:45
  • @Stefan -- exactly! We suspend our disbelief for a bit, and try to 'simulate' set theory, and then construct numbers and so on in this make-believe universe. We already assumed numbers but that was "in the real world".

    Two ways to think about this: If we forego any notion of "meaning", then we are not constructing numbers, just manipulating strings to get other strings. This dissolves the question.

    But if we do imbue our axioms with the intended "meaning", it is unclear to me why assuming ZFC and building something that corresponds to our intuitive notion of numbers is the natural foundation

     – Deniz Nov 26 '10 at 09:58
  • @Deniz: Well, it is one foundation, and it is one that turned out to be extremely successful and one that was developed after quite a bit of struggle with other attempts.

    I agree that ZFC might actually be stronger than what is realistically needed to carry out most of mathematics. But I believe that the most striking argument for some theory like ZFC is that practically all mathematician work within the system without necessarily being familiar with it on a formal level. This indicates that ZFC is natural after all.
    (To be continued.)

     – Stefan Geschke Nov 26 '10 at 10:10
  • Some critics of my point of view say that this is just a social phenomenon: Basically every mathematician is educated to works within this framework. While there is certainly some point to this, I cannot fully agree. – Stefan Geschke Nov 26 '10 at 10:12
  • 1
    @Stefan: I would say that practically all mathematicians work with sets and functions (with the category of sets and functions, if you like). The further reduction of functions to sets (thus founding mathematics on a single membership predicate, leading to ZFC if taken seriously) is an optional move which has pluses and minuses, but it leads to issues most mathematicians have little practical interest in. – Todd Trimble Nov 26 '10 at 10:59
  • @Stefan: I didn't mean to say we should somehow try to avoid this circularity, I meant to say that we shouldn't worry about it.

    That natural numbers show up in the prerequisites to formalisation of mathematics probably reflects the fact that the natural numbers are a very basic structure, rather than that we need knowledge about them to construct the formalisation to get it right (even if we do, kinda).

     – Ketil Tveiten Nov 26 '10 at 12:53
  • @Deniz: It doesn't matter whether something in (say) ZFC that behaves like the natural numbers is the 'natural' foundation, indeed it doesn't really make sense to ask if it is. To put it this way: what are the natural numbers, really? One could say they are 'the set of finite ordinals' (i.e. quoting the ZFC definition), but how is that different from [however they are defined in NBG]? From the perspective of how they behave, not at all. Is either one the Right True Answer? Yes and no. No, because neither is any more right than any other model; Yes, because they do what they're supposed to ... – Ketil Tveiten Nov 26 '10 at 13:02
  • ... which is model how the natural numbers behave. So, it doesn't matter what foundations we use (and none of them are really 'more natural' than the others), so long as they let us do what we want. ZFC is just a neat way of formalising how sets (should) behave, where things work the way they are supposed to (w.r.t. 'ordinary' mathematics) and that's all we need. We might as well have been working in NBG, (so far as I know) the 'ordinary' mathematics wouldn't know the difference. – Ketil Tveiten Nov 26 '10 at 13:05
  • @Ketil: I wouldn't say that NGB is all that different from ZFC.
    They are pretty much formalizations of the same concepts.
    This is why it doesn't make a difference for usual mathematics which system we are working in.     – Stefan Geschke Nov 26 '10 at 19:43
  • Yes, I agree with both points -- I understand that whatever gives us a working formalism where we can prove things & resolve uncertainties is good enough. It sounds like we take our everyday world for granted, and then agree on a formal language & rules like ZFC, define functions as "ordered pairs" etc. simply to resolve uncertainties & inherent ambiguities in our intuitive notions. I agree Stefan's last sentence about "this sort of circularity". Can we comprehend anything except in light of new combinations of what we already comprehend? This gets very 'philosophical' very fast. – Deniz Dec 02 '10 at 15:50
7

Note that there are different ways of thinking about set theory and more generally about Logic. They can be thought as a foundation for mathematics or they can be thought as a part of mathematics. If you are thinking of them as a foundation, at the end you have to accept some intuitive concepts, the point of foundation is not that it does not assume anything and builds on nothing, the point is that it is based on accepted theories. Almost all of mathematicians accept the very weak theories about natural numbers and they are sufficient for building the needed metamathematics for set theory. (Primitive Recursive Arithmetic would suffice but even weaker theories are sufficient).

I would suggest the introduction of K. Kunen's "Set Theory" book (the part he discusses the formalist viewpoint) and S.C. Kleene's "Metamathematics".

Kaveh
  • 5,362
2

If i may add (although this post is kind of old)

This circularity "problem" (if one wishes to see it as such), appears in (what is refered as) classical mathematics.

Now one should bear in mind that even these classical mathematics (continuing along the lines of aristotle, euclid, archimedes, leibniz, cantor, hilbert, russel, goedel, etc..), have been cutoff and formalised (or sterilised if you like) to a greater extened that originaly meant.

In any case this is not the main argument.

But i would like to draw attention to the intuitionistic flavor of mathematics (and especially of the LEJ Brouwer path) (see for example LEJ Brouwer, Cambridge Lectures on Intuitionism, most of first lecture plus the appendix on marxists.org).

There Brouwer, aware of the problem, explicitly takes on the issue of mathematics over language or syntax.

Excerpt:

FIRST ACT OF INTUITIONISM

Completely separating mathematics from mathematical language and hence from the phenomena of language described by theoretical logic, recognising that intuitionistic mathematics is an essentially languageless activity of the mind having its origin in the perception of a move of time. This perception of a move of time may be described as the falling apart of a life moment into two distinct things, one of which gives way to the other, but is retained by memory. If the twoity thus born is divested of all quality, it passes into the empty form of the common substratum of all twoities. And it is this common substratum, this empty form, which is the basic intuition of mathematics.

Nikos M.
  • 149