The Logic of Real and Complex Numbers

I’ve always liked logic. I studied it a bunch in high school and college. Nowadays it’s a kind of hobby. I turn to it for relief sometimes when I become frustrated trying to figure out what I can do about global warming. Lately I’ve been digging a bit deeper into the logic behind the real and complex numbers. And I’m teaching a graduate course on real analysis this fall, so I actually have a slight excuse for doing this.

There’s something about logic that’s both fascinated and terrified me ever since I was a kid: it’s how we can’t fully pin down infinite structures, like the real or complex number systems, using a language with finitely many symbols and a theory with finitely many axioms.

It’s terrifying that we don’t fully know what we’re talking about when we’re talking about numbers! But it’s fascinating that we can understand a lot about the limitations.

There are many different things to say about this, depending on what features of these number systems we want to describe, and what kind of logic we want to use.

Maybe I should start with the natural numbers, since that story is more famous. This can also serve as a lightning review of some basic concepts which I’ll pretend you already vaguely know: first-order versus second-order logic, proofs versus models, and so on. If you don’t know these, you can either fake it or read some of the many links in this article!

Natural numbers

When Peano originally described the natural numbers he did so using axioms phrased in second-order logic. In first-order logic we can quantify over variables: for example, we can say

\forall x \; (P(x)) \; \Rightarrow \; P(y)) \;

which means that if the predicate P holds for all x it holds for any variable y. In second-order logic we can also quantify over predicates: for example, we can say

\forall P \; (P(x) \Leftrightarrow P(y)) \; \Leftrightarrow \; x = y

which says that x = y if and only if for every predicate P, P(x) is true precisely when P(y) is true. Leibniz used this principle, called the identity of indiscernibles, to define equality… and this is a nice example of the greater power of second-order logic. In first-order logic we typically include equality as part of the language and add axioms describing its properties, like

\forall x \; \forall y \; (x = y \Leftrightarrow y = x)

In second-order logic we can define equality and prove these properties starting from the properties we already have for \Leftrightarrow.

Anyway, in his axioms for the natural numbers, Peano used second-order logic to formulate the principle of mathematical induction in this sort of way:

\forall P \; \big[ P(0) \; \& \; \forall n \; ((P(n) \Rightarrow P(n+1)) \; \; \Rightarrow \; \; \forall n \; P(n))\big]

This says that if you’ve got any predicate that’s true for 0 and is true for n+1 whenever it’s true for n, then it’s true for all natural numbers.

In 1888, Dedekind showed that Peano’s original axioms for the natural numbers are categorical, meaning all its models are isomorphic.

The concept of ‘model’ involves set theory. In a model you pick a set S for your variables to range over, pick a subset of S for each predicate—namely the subset where that predicate is true —and so on, in such a way that all the axioms in that theory are satisfied. If two models are isomorphic, they’re the same for all practical purposes.

So, in simple rough terms, a categorical theory is one that gives a full description of the mathematical structure it’s talking about.

This makes Dedekind’s result sound like great news. It sounds like Peano’s original second-order axioms for arithmetic completely describe the natural numbers.

However, there’s an important wrinkle. There are many inherently undetermined things about set theory! So in fact, a categorical theory only gives a full description of the mathematical structure it’s talking about relative to a choice of what sets are like.

So, Dedekind’s result just shoves everything mysterious and undetermined about the natural numbers under the carpet: they become mysterious and undetermined things about set theory. This became clear much later, thanks to Gödel and others. And in the process, it became clear that second-order logic is a bit problematic compared to first-order logic.

You see, first-order logic has a set of deduction rules that are:

• sound: Every provable sentence holds in every model.

• semantically complete: Every sentence that holds in every model is provable.

• effective: There is an algorithm that can correctly decide whether any given sequence of symbols is a proof.

Second-order logic does not! It’s ‘too powerful’ to also have all three of these nice properties.

So, these days people often work with a first-order version of Peano’s axioms for arithmetic. Instead of writing down a single axiom for mathematical induction:

\forall P \; \big[ P(0) \; \& \; \forall n \; P(n) \Rightarrow P(n+1)) \; \; \Rightarrow \;\; \forall n \; (P(n))\big]

we write down an axiom schema—an infinite list of axioms—with one axiom like this:

\phi(0) \; \& \; \forall n \; (\phi(n) \Rightarrow \phi(n+1)) \; \; \Rightarrow \;\; \forall n \; (\phi(n))

for each formula \phi that we can actually write down using the language of arithmetic.

This first-order version of Peano arithmetic is not categorical: it has lots of nonisomorphic models. People often pretend there’s one ‘best’ model: they call it the ‘standard’ natural numbers, and call all the others ‘nonstandard’. But there’s something a bit fishy about this.

Indeed, Gödel’s first incompleteness theorem says there are many statements about natural numbers that can neither be proved nor disproved starting from Peano’s axioms. It follows that for any such statement we can find a model of the Peano axioms in which that statement holds, and also a model in which it does not.

Furthermore, this remains true even if we add any list of extra axioms to Peano arithmetic, as long as there’s some algorithm that can list all these axioms.

So, I’d prefer to say there are many different ‘versions’ of the natural numbers, just as there are many different groups.

We can study these different versions, and it’s a fascinating subject:

• Wikipedia, Nonstandard models of arithmetic.

However, I want to talk about the situation for other number systems!

The real numbers

The situation is better for the real numbers—at least if we are willing to think about them in a ‘purely algebraic’ way, leaving most analysis behind.

To do this, we can use the theory of a ‘real closed field’. This is a list of axioms, formulated in first-order logic, which describe how +, \times, 0, 1 and \le work for the real numbers. You can think of these axioms as consisting of three parts:

• the field axioms: the usual algebraic identities involving +, \times, 0 and 1 together with laws saying that everything has an additive inverse and everything except 0 has a multiplicative inverse.

• the formally real field axiom, saying that -1 is not a sum of squares. This implies that we can equip the field with a concept of \le that makes it into an ordered field—but not necessarily in a unique way.

• the real closed field axioms, which says that also for any number x, either x or -x has a square root, and every polynomial of odd degree has a root. Among other things this implies our field can be made into an ordered field in a unique way. To do this, we say x \le y if and only if y - x has a square root.

Tarski showed this theory is complete: any first-order sentence involving only the operations +, \times, 0, 1 and the relation \le can either be proved or disproved starting from the above axioms.

Nonetheless, the theory of real closed fields is not categorical: besides the real numbers, there are many other models! These models are all elementarily equivalent: any sentence involving just +, \times, 0, 1, \le and first-order logic that holds in one model holds in all the rest. But these models are not all isomorphic: we can’t get a bijection between them that preserves +, \times, 0, 1 and \le.

Indeed, only finite-sized mathematical structures can be ‘nailed down’ up to isomorphism by theories in first-order logic. You see, the Löwenheim–Skolem theorem says that if a first-order theory in a countable language has an infinite model, it has at least one model of each infinite cardinality. So, if we’re trying to use this kind of theory to describe an infinitely big mathematical structure, the most we can hope for is that after we specify its cardinality, the axioms completely determine it.

However, the real closed field axioms aren’t even this good. For starters, they have infinitely many nonisomorphic countable models. Here are a few:

• the algebraic real numbers: these are the real numbers that obey polynomial equations with integer coefficients.

• the computable real numbers: these are the real numbers that can be computed to arbitrary precision by a computer program.

• the arithmetical real numbers: these are the numbers definable in the language of arithmetic. More precisely, a real number x is arithmetical if there is a formula \phi in the language of first-order Peano arithmetic, with two free variables, such that

\displaystyle{ \forall m \; \forall n \; (\frac{m}{n} \le x \; \; \Leftrightarrow \; \; \phi(n,m)) }

Every computable real number is arithmetical, but not vice versa: just because you can define a real number in the above way does not mean you can actually compute it to arbitrary precision!

And indeed, there are other even bigger countable real closed fields, consisting of real numbers that are definable using more powerful methods, like second-order Peano arithmetic.

We can also get countable real closed fields using tricks like this: take the algebraic real numbers and throw in the number \pi along with just enough other numbers to get a real closed field again. Or, we could throw in both \pi and e. This probably gives a bigger real closed field—but nobody knows, because for all we know, \pi could equal e plus some rational number! Everyone believes this is false, but nobody has proved it.

There are also lots of nonisomorphic uncountable real closed fields, including ones that include the usual real numbers.

For example, we can take the real numbers and throw in an element \infty that is bigger than 1, 2, 3, \dots, and so on—and then do what it takes to get another real closed field. This involves throwing in elements like

-\infty, \; \infty + 1, \; 1/\infty, \; \infty^2, \; \sqrt{\infty}, \; \sqrt{\infty^2 + 17} , \dots

and so on. So, we get lots of infinities and infinitesimals.

It gets a bit confusing here, trying to figure out what equals what. But there’s another real closed field containing an infinite element that seems easier to manage. It’s called the field of real Puiseux series. These are series of the form

\sum_{i = k}^\infty a_i z^{i/n}

where k is any integer, perhaps negative, n is any
positive integer, and the coefficients a_i are real.

What’s z? It’s just a formal variable. But the real Puiseux series are real closed field, and z acts like 1/\infty: it’s positive, but smaller than any positive real number.

With considerably more work, we can make up a real closed field that:

• contains the real numbers,

• contains an element \infty bigger than 1,2,3, \dots, and

• obeys the transfer principle, which says that a first-order statement phrased in the usual language of set theory holds for the real numbers if and only if it holds for this other number system.

Any real closed field with these properties is called a system of hyperreal numbers. In the 1960s, the logician Abraham Robinson used them to make Leibniz’s old idea of infinitesimals in calculus fully rigorous. The resulting theory is called nonstandard analysis.

So, I hope you see there’s an exciting—or perhaps appalling—diversity of real closed fields. But don’t forget: they’re all elementarily equivalent. If a sentence involving just +, \times, 0, 1, \le and first-order logic holds in any one of these real closed fields, it holds in all of them!

You might wonder what second-order logic has to say about this.

Here the situation looks very different. In second-order logic we can do analysis, because we can quantify over predicates, which allows us to talk about subsets of real numbers. And in second-order logic we can write down a theory of real numbers that’s categorical! It’s called the theory of a Dedekind-complete ordered field. Again, we can group the axioms in three bunches:

• the field axioms: the usual algebraic identities involving +, \times, 0 and 1 together with laws saying that everything has an additive inverse and everything except 0 has a multiplicative inverse.

• the ordered field axiom, saying there is a total ordering \le such that x \le y and x' \le y' implies x + x' \le y + y' and x,y \ge 0 implies x y \ge 0.

• the Dedekind completeness axiom, which says that every nonempty subset with an upper bound has a least upper bound. But instead of talking about subsets, we talk about the predicates that hold on those subsets, so we say “for all predicates P such that…”

Because they’re categorical, people often use these axioms to define the real numbers. But because they’re second-order, the problem of many nonisomorphic models has really just been swept under the rug. If we use second-order logic, we won’t have a concept of ‘proof’ that’s sound, semantically complete and effective. And if we use first-order axioms for set theory to explicitly talk about subsets instead of predicates, then our set theory will have many models! Each model will have a version of the real numbers in it that’s unique up to isomorphism… but the versions in different models will be really different.

In fact, there’s a precise sense in which the ‘standard real numbers’ in one model of set theory can be the ‘hyperreals’ in another. This was first shown by Abraham Robinson.

The complex numbers

I mentioned that when we’re studying an infinite mathematical structure using first-order logic, the best we can hope for is to have one model of each size (up to isomorphism). The real numbers are far from being this nice… but the complex numbers come much closer!

More precisely, say \kappa is some cardinal. A first-order theory describing structure on a single set is called κ-categorical if it has a unique model of cardinality \kappa. And 1965, a logician named Michael Morley showed that if a list of axioms is \kappa-categorical for some uncountable \kappa, it’s \kappa-categorical for every uncountable \kappa. I haven’t worked my way through the proof, which seems to be full of interesting ideas. But such theories are called uncountably categorical.

A great example is the ‘purely algebraic’ theory of the complex numbers. By this I mean we only write down axioms involving +, \times, 0 and 1. We don’t include anything about \le this time, nor anything about complex conjugation. You see, if we start talking about complex conjugation we can pick out the real numbers inside the complex numbers, and then we’re more or less back to the story we had for real numbers.

This theory is called the theory of an algebraically closed field of characteristic zero. Yet again, the axioms come in three bunches:

• the field axioms.

• the characteristic zero axioms: these are an infinite list of axioms saying that

1 \ne 0, \quad 1+1 \ne 0, \quad 1+1+1 \ne 0, \dots

• the algebraically closed axioms: these say that every non-constant polynomial has a root.

Pretty much any mathematician worth their salt knows that the complex numbers are a model of these axioms, whose cardinality is that of the continuum. There are lots of different countable models: the algebraic complex numbers, the computable complex numbers, and so on. But because the above theory is uncountably categorical, there is exactly one algebraically closed field of characteristic zero of each uncountable cardinality… up to isomorphism.

This implies some interesting things.

For example, we can take the complex numbers, throw in an extra element, and let it freely generate a bigger algebraically closed field. It’s ‘bigger’ in the sense that it contains the complex numbers as a proper subset, indeed a subfield. But since it has the same cardinality as the complex numbers, it’s isomorphic to the complex numbers!

And then, because this ‘bigger’ field is isomorphic to the complex numbers, we can turn this argument around. We can take the complex numbers, remove a lot of carefully chosen elements, and get a subfield that’s isomorphic to the complex numbers.

Or, if we like, we can take the complex numbers, adjoin a really huge set of extra elements, and let them freely generate an algebraically closed field of characteristic zero. The cardinality of this field can be as big as we want. It will be determined up to isomorphism by its cardinality.

One piece of good news is that thanks to a result of Tarski, the theory of an algebraically closed field of characteristic zero is complete, and thus, all its models are elementarily equivalent. In other words, all the same first-order sentences written in the language of +, \times, 0 and 1 hold in every model.

But here’s a piece of strange news.

As I already mentioned, the theory of a real closed field is not uncountably categorical. This implies something really weird. Besides the ‘usual’ real numbers \mathbb{R} we can choose another real closed field \mathbb{R}', not isomorphic to \mathbb{R}, with the same cardinality. We can build the complex numbers \mathbb{C} using pairs of real numbers. We can use the same trick to build a field \mathbb{C}' using pairs of guys in \mathbb{R}'. But it’s easy to check that this funny field \mathbb{C}' is algebraically closed and of characteristic zero. Since it has the same cardinality as \mathbb{C}, it must be isomorphic to \mathbb{C}.

In short, different ‘versions’ of the real numbers can give rise to the same version of the complex numbers!

References

So, I hope you see that the logical foundations of the real and complex number systems are quite slippery… yet with work, we can understand a lot about this slipperiness.

Besides the references I’ve given, I just want to mention two more. First, here’s a free introductory calculus textbook based on nonstandard analysis:

• H. Jerome Keisler, Elementary Calculus: an Infinitesimal Approach, available as a website or in PDF.

And here’s an expository paper that digs deeper into uncountably categorical theories:

• Nick Ramsey, Morley’s categoricity theorem.

This entry was posted on Monday, September 8th, 2014 at 1:00 am and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

54 Responses to The Logic of Real and Complex Numbers

  1. Allen Knutson says:
    8 September, 2014 at 12:09 pm

    While hardly the same thing, the “strange news” is reminiscent of the following. There are uncountably many fake R^4s, homeomorphic but not diffeomorphic to the standard R^4. Take one and cross it with R. Now it’s diffeomorphic to R^5, since there’s only one! To what closed smooth submanifold of R^5 does Fake x 0 go under this diffeomorphism?

    Reply
  2. jpmarquis (@jpmarquis) says:
    8 September, 2014 at 1:37 pm

    Readers interested in this topic might also want to have a look at Philip Ehrlich’s work on surreal numbers, which he calls the absolute arithmetic continuum. Here is a reference: http://www.ohio.edu/people/ehrlich/Unification.pdf

    Reply
  3. jessemckeown says:
    8 September, 2014 at 2:39 pm

    I think you want to move a couple of quantifiers in the “arithmetic reals” definition.

    Reply
  4. arch1 says:
    8 September, 2014 at 6:41 pm

    John, it looks like you’re saying that in Peano’s second-order logic, mathematical induction (MI) is an axiom rather than a theorem. If so, why did Peano not incorporate enough logical power in his system to *prove* MI?

    Is it because any attempt to do so must in effect assume MI (in which case my hand should have obnoxiously shot up when our high school teacher argued for its truth)? Or is it because any attempt to do so results in contradiction? Or, …?

    Reply
    • John Baez says:
      9 September, 2014 at 1:37 am

      In most approaches to the natural numbers, mathematical induction is an axiom rather than a theorem!

      You can think of mathematical induction as a way of saying that every natural number is either 0, or 1, or 1+1, or 1+1+1, or… something like this, with some natural number of 1’s.

      This is the key fact about natural numbers, but it’s hard to state this fact in a non-circular way—you’ll notice I just said it in a circular way. Mathematical induction is a way of saying it in a non-circular way!

      We can prove mathematical induction as a theorem—but as far as I know, only if we start from some axiom that’s really mathematical induction in disguise.

      For example, we can assume that the natural numbers come with a concept of ≤ obeying some plausible axioms, and then add an axiom saying that “every nonempty set of natural numbers has a least element”. This is called the well-ordering principle.

      Given the other axioms we can use the well-ordering principle to prove mathematical induction… but we can also use mathematical induction to prove the well-ordering principle, so after some thought you’ll realize they are the same idea in two disguises:

      • Wikipedia, Mathematical induction: equivalence with the well-ordering principle.

      Finally, I should warn you that even the principle of mathematical induction is not powerful enough to completely break the circularity of saying “every natural number is either 0, or 1, or 1+1, or 1+1+1, or… something like this, with some natural number of 1’s”. The point is that nonstandard versions of the natural numbers obey the principle of mathematical induction but have numbers bigger than all the ‘standard’ natural numbers.

      Reply
      • arch1 says:
        9 September, 2014 at 4:30 pm

        Thanks John. If I understand the first part of your reply you’re saying that my math teacher must have effectively assumed MI when arguing for its truth.

        I do recall my teacher implicitly assuming that every natural number can be reached by repeatedly adding 1. But looking at the wikipedia article on the Peano Axioms, invoking the successor function S() on a natural number appears to be the only way to generate a natural number other than the one (call it 0) that is given us for free.

        If that’s right, how could my teacher’s assumption be false – how could there possibly be a natural number that isn’t either the one we’re given for free, or the result of (possibly repeated applications of) the only permitted means of generating a new one?

        Reply
        • John Baez says:
          10 September, 2014 at 2:34 am

          arch1 wrote:

          If I understand the first part of your reply you’re saying that my math teacher must have effectively assumed MI when arguing for its truth.

          As a teacher, when you try to teach students a rather complicated axiom like mathematical induction, you typically use their previous experience—in this case, their experience with the natural numbers—to coax them into seeing the axiom as ‘reasonable’ and ‘believable’. This is completely different than proving a theorem: it’s a matter of persuasion rather than proof. A really good teacher will (at least for sufficiently advanced students) explain the difference.

          If that’s right, how could my teacher’s assumption be false—how could there possibly be a natural number that isn’t either the one we’re given for free, or the result of (possibly repeated applications of) the only permitted means of generating a new one?

          Everyone agrees that the only natural numbers are zero and its successors:

          0, S(0), S(S(0)), \dots

          and this is why mathematical induction is true. The problem is that it’s impossible turn this into a rigorous proof. Why not? Because it’s impossible to say precisely what \dots means without a theory of natural numbers!

          In other words, you can’t make your idea of repeated applications precise without using precisely the ideas about natural numbers that you’re trying to explain, or prove. As I said:

          every natural number is either 0, or 1, or 1+1, or 1+1+1, or…something like this, with some natural number of 1’s. This is the key fact about natural numbers, but it’s hard to state this fact in a non-circular way—you’ll notice I just said it in a circular way. Mathematical induction is a way of saying it in a non-circular way!

          You might try to get around it this way: say that every natural number that’s not zero is the successor of some natural number. In fact this is an axiom of Peano arithmetic. However, this axiom is not enough to imply mathematical induction. You might enjoy figuring out why.

        • arch1 says:
          10 September, 2014 at 7:44 pm

          Thanks John. I guess the stumbling block in attempting to use the axiom you mention (“every natural number that’s not zero is the successor of some natural number”) to prove mathematical induction is at bottom the same thing that tripped us up before, because the ‘predecessor chain’ from an arbitrary natural number back to 0, being of arbitrary length, can’t be accomodated in any given proof without resorting to some equivalent of “…”.

          BTW I don’t see your axiom among the Peano axioms in Wikipedia. Maybe it’s part of an alternative formulation. (Then again, I find the axioms I *do* see there sufficiently puzzling – e.g. #7’s restatement suggests that “=” is intended to denote identity, but wouldn’t that render #5 redundant? – that it’s just as likely I’m mentally wedged again:-))

        • John Baez says:
          11 September, 2014 at 5:42 am

          arch1 wrote:

          I guess the stumbling block in attempting to use the axiom you mention (“every natural number that’s not zero is the successor of some natural number”) to prove mathematical induction is at bottom the same thing that tripped us up before…

          Right.

          BTW I don’t see your axiom among the Peano axioms in Wikipedia. Maybe it’s part of an alternative formulation.

          Whoops! I was being silly; this follows from the other axioms using mathematical induction, in a very simple and amusing way. Let

          P(n) = “either n = 0 or n = S(m) for some m”

          where S means “successor”. Then

          ∀n P(n)

          says that every number except zero is a successor. Let’s prove it by induction.

          It’s really easy to check that P(0) is true, since 0 = 0, and it’s really easy to check that

          P(n) ⇒ P(S(n))

          since P(S(n)) is always true: S(n) is the successor of n. So, by mathematical induction we get

          ∀n P(n)

          It’s in Robinson arithmetic, a system that leaves out mathematical induction, that we need an axiom saying every number except zero is a successor.

          The Wikipedia article on Peano arithmetic says this about axioms 2-5 in Peano’s original treatment. These axioms are about equality:

          Since they are logically valid in first-order logic with equality, they are not considered to be part of “the Peano axioms” in modern treatments.

          Indeed, axioms 2-4 are considered part of first-order logic, while axiom 5 is completely irrelevant to the modern form of the Peano axioms, which talk about nothing except natural numbers. It’s better to look at the modern form of the Peano axioms.

        • arch1 says:
          12 September, 2014 at 5:12 pm

          Thanks John, this helped a lot (as did the captioned photo in the Wikipedia “Peano Axioms” article, which makes it clear that an axiom system need not provide the means to *generate* the objects which it *discusses*, as I had implicitly assumed)

      • Toby Bartels says:
        10 September, 2014 at 3:13 am

        I should warn you that even the principle of mathematical induction is not powerful enough to completely break the circularity

        Well, in first-order logic it’s not enough. In second-order logic, it is!

        Reply
        • John Baez says:
          10 September, 2014 at 3:33 am

          I considered saying that, because there’s some truth to it: presumably you’re referring to the fact that the second-order Peano axioms are categorical.

          But the concept of ‘categorical theory’ is a model-theoretic concept, so it brings in set theory. When we take models of a theory in second-order logic, the models we get depend on the set theory we use… and the ‘standard model’ of the natural numbers in a nonstandard set theory can be essentially the same as a nonstandard model of the natural numbers in some ‘standard’ set theory.

          So while I’m not an expert on this stuff, I have the feeling that going to second-order logic merely ‘sweeps the problem under the rug’.

      • Max Lee says:
        30 July, 2016 at 2:29 pm

        John, could you state explicitly why “every natural number that’s not zero is the successor of some natural number” is insufficient to imply mathematical induction?

        Reply
        • John Baez says:
          31 July, 2016 at 3:33 am

          To prove that mathematical inducation doesn’t follow from the axiom you mentioned… presumably together with the other axioms of Peano arithmetic?… I’d have to give you a model of all the axioms of Peano arithmetic except mathematical induction, in which mathematical induction doesn’t hold.

          This would be a great thing to do, but since I don’t know your mathematical background I’d run the risk of doing a lot of work, writing a long explanation, and discovering it made no sense to you.

          So it might be better for both of us if I turn the tables on you. Try to derive the principle of mathematical induction from “every natural number that’s not zero is the successor of some natural number”. I don’t know why you think it’s possible, but if you try, you’ll see it doesn’t work. Or: if you explain why you think it does work, I can point out the flaw.

      • Max Lee says:
        31 July, 2016 at 8:39 am

        I’m replying to this comment because I couldn’t find the reply button on your comment further down the chain.

        Anyway, what prompted me to ask whether you could deduce mathematical induction from one of Robinson’s Axioms is the fact that the other Peano axioms capture the property that 0, S(0), S(S(0))... are natural numbers, but we need another axiom to prevent “rogue elements” from being members of the set; in other words, we want an axiom that says “the only natural numbers are 0, and S(0), and S(S(0)), and S(S(S(0))), and so on, and so forth.

        Clearly the induction axiom works, otherwise it wouldn’t be one of Peano Axioms in the first place! But what struck me as reasonable at first was your suggestion that the naive impulse would be to use this axiom, which I’ll call the Naive Induction Axiom:

        “Every natural number that isn’t zero is the successor of some natural number.”

        This could potentially rule out rogue elements like \frac{1}{2}, since it clearly isn’t 0, and it also isn’t the successor of any natural number, so it’s not a natural number. We can play the same game with other elements, by seeing whether it’s 0, or the successor of some natural number. If it isn’t either of those, it’s not a natural number.

        Perhaps there’s an implicit circularity in the above argument, which I’m missing? If that’s the case I’d like my mind to be straightened out about this simple misunderstanding.

        I’ve learned that the Robinson Axioms form a weaker arithmetic than the Peano Axioms, since there are statements which you cannot prove, e.g. \forall x(0+x=x), so clearly the Naive Induction Axiom is not enough for us to do the usual arithmetic, but I want to see intuitively that this would fail in the first place due to circularity, so to speak (like the intuitive notion that the axiom “the only natural numbers are 0, S(0), S(S(0)),...” will fail because “...” requires the theory of natural numbers.

        Reply
        • John Baez says:
          31 July, 2016 at 8:50 am

          Okay, let’s talk about ruling out “rogue elements”. That’s a decent way to get the intuition.

          The axiom “every natural number that isn’t zero is the successor of some natural number” doesn’t rule out the possibility of a rogue element x_1 that’s the successor of a rogue element x_2 that’s the successor of a rogue element x_3… and so on forever!

          This is called an “infinite descending chain”, for reasons that I hope are obvious. The principle of mathematical induction is equivalent, in reasonably powerful forms of logic, to the nonexistence of infinite descending chains. But note that the “…” in my previous paragraph requires some serious clarification before it makes rigorous sense! This is why we need a “reasonably powerful form of logic” to say what an infinite chain is, and to prove that the principle of mathematical induction is equivalent to the nonexistence of infinite descending chains.

          I’ve learned that the Robinson Axioms form a weaker arithmetic than the Peano Axioms, since there are statements which you cannot prove, e.g. \forall x(0+x=x)

          Actually 0+x=x is one of the axioms of Robinson arithmetic. It’s also an axiom in Peano arithmetic.

        • Max Lee says:
          31 July, 2016 at 9:12 am

          I see, that seems very reasonable now. Thanks!

          Actually, what I meant by “you can’t prove \forall x(0+x=x) assuming the axioms of Robinson’s Arithmetic” is explained here: https://summerofgodel.blogspot.my/2013/06/q-robinson-arithmetic.html. I stumbled upon it while searching for an explanation of the limitations of Robinson’s Arithmetic, which you alluded to in your comments. Thanks to your post, I’ve realised that logic is a mindbogglingly huge field with lots of interesting stuff! I had the impression that mathematical logic is a dull and cold subject from reading introduction to proofs and undergraduate Discrete Math books.

        • John Baez says:
          1 August, 2016 at 1:09 am

          Max Lee wrote:

          Thanks to your post, I’ve realised that logic is a mindbogglingly huge field with lots of interesting stuff!

          Thanks very much! Yes, and logic really confronts us with the limitations of our powers. You might like this:

          • John Baez, Surprises in logic.

  5. amarashiki says:
    8 September, 2014 at 6:54 pm

    I liked this post :).

    Reply
  6. Nathan Reed says:
    8 September, 2014 at 9:10 pm

    Fascinating post! That last bit, about different models of real numbers giving rise to the same complex numbers, reminds me a bit of Turing universality—how different models of computation that appear very different all give rise to the same set of computable functions. I can see why people might think that \mathbb{C} is in some sense “more fundamental” than \mathbb{R}—which might tie into why complex numbers appear at the heart of physics.

    Reply
    • John Baez says:
      9 September, 2014 at 1:45 am

      Indeed, my latest burst of interest in logic came from some papers arguing that the “logical perfection” of the complex numbers might explain their appearance in physics:

      • Boris Zilber, Perfect infinities and finite approximation.

      • Boris Zilber, On model theory, noncommutative geometry and physics.

      I explained the basic ideas over at the n-Category Café, and in the comments some people gave good criticisms:

      • John Baez, Uncountably categorical theories.

      I think these criticisms would need to be dealt with to make further progress. Briefly, while the ‘purely algebraic’ approach to the complex numbers gives an uncountably categorical theory, this approach doesn’t include complex conjugation or the topology on the complex numbers, both of which are crucial in quantum physics as we know it.

      The post here is kind of a slowed-down, expanded version of the easy part of my post on the n-Café.

      Reply
  7. Carlos Scheidegger says:
    8 September, 2014 at 10:19 pm

    I don’t have anything constructive to add to this fantastic post except to point out a very minor typo:

    “And in second-order logic can write down a theory of real numbers that’s categorical!”: add a “we” between “logic” and “can”?

    Reply
  8. Greg Egan says:
    9 September, 2014 at 3:25 am

    In the definition of arithmetical real numbers, I think the a should be an x or vice versa.

    I’m a bit surprised that it’s an open question whether or not \pi-e is irrational! Given how simple some of the proofs are for the irrationality of \pi and e individually, I wonder if it would actually be very difficult to prove, or whether people have just decided that it’s not a very interesting question.

    Reply
  9. John Baez says:
    9 September, 2014 at 4:06 am

    Greg wrote:

    In the definition of arithmetical real numbers, I think the a should be an x or vice versa.

    Yes, I’ll fix that. I’m in the mood for x.

    I’m a bit surprised that it’s an open question whether or not \pi-e is irrational!

    Actually, now that I look, I see people saying that nobody knows if \pi + e is irrational. This seems to be an independent question (though I’ve only thought about it for one minute, so I could be missing an easy trick). But I think if people knew the answer for \pi - e, I would have heard.

    Here’s a fun puzzle: show that at least one of \pi - e and e \pi must be irrational. There’s a one-line proof, not using anything very fancy.

    Given how simple some of the proofs are for the irrationality of \pi and e individually, I wonder if it would actually be very difficult to prove…

    Given that the irrationality of e and e + 1 are individually quite easy to prove, you might think their difference would be easy to prove irrational too.

    …or whether people have just decided that it’s not a very interesting question.

    I think mathematicians would consider this hugely interesting. But I don’t know how hard people have tried to prove this particular fact. People have though much harder about Schanuel’s conjecture, which would settle this and a vast number of similar questions:

    Schanuel’s conjecture. Given any complex numbers z_1,...,z_n that are linearly independent over the rational numbers \mathbb{Q}, the field

    \mathbb{Q}(z_1,...,z_n, \exp(z_1),...,\exp(z_n))

    has transcendence degree at least $n$ over \mathbb{Q}.

    Here \mathbb{Q} is the field of rational numbers, and the transcendence degree of a field L over a field K is the cardinality of the largest set of elements of L that obey no polynomial equations with coefficients in K.

    So, if Schanuel’s conjecture is true,

    \mathbb{Q}(1, i \pi, e^1,e^{i\pi}) = \mathbb{Q}(e, \pi)

    has transcendence degree 2, so e and \pi don’t obey any nontrivial polynomial equations with rational coefficients.

    And as Richard Elwes once pointed out to me, the logician Boris Zilber has proved a truly astounding fact about Schanuel’s conjecture, using ideas about uncountably categorical theories.

    An exponential field is field with an operation \exp obeying these rules:

    \exp(a + b) = \exp(a) \exp(b) , \quad \exp(0) = 1

    Zilber showed that up to isomorphism, there is a unique exponential field that obeys Schanuel’s conjecture and has the ordinary complex numbers as its underlying field!

    So either the complex numbers with its usual notion of exponentiation obeys Schanuel’s conjecture, or there is another operation on the complex numbers, some sort of ‘pseudoexponentiation’, which obeys

    \exp(a + b) = \exp(a) \exp(b) , \quad \exp(0) = 1

    but is not related to the usual exponentiation!

    Right now this is a very interesting ‘rhetorical argument’ for Schanuel’s conjecture: either it’s true or something very weird would have to be true. Maybe someday it will be part of a full proof.

    Reply
  10. Greg Egan says:
    9 September, 2014 at 4:44 am

    Lots of interesting things to ponder! But at least the puzzle wasn’t too hard. Suppose \pi-e and e \pi were both rational. Then the quadratic:

    q(x) = x^2 - (\pi-e) x - e \pi

    has rational coefficients. But:

    q(\pi) = \pi^2 - (\pi-e)\pi - e \pi =0

    which contradicts the known fact that \pi is transcendental.

    Reply
    • arch1 says:
      9 September, 2014 at 7:41 pm

      Greg, unless I’m missing something your final equation doesn’t contradict pi being transcendental – it can’t possibly, because it’s a true statement (in fact, it’s true when pi and e are replaced w/ any real numbers).

      Reply
      • arch1 says:
        9 September, 2014 at 7:49 pm

        I see, the contradiction is not in the final equation alone, but rather in that entire line and the one above.

        Reply
      • John Baez says:
        9 September, 2014 at 11:53 pm

        The contradiction is that if \pi - e and e\pi are both rational, then \pi and e are roots of a polynomial with rational coefficients—which is impossible, since they’re transcendental numbers.

        We can use the same type of argument to show that \pi + e and e \pi can’t both be rational.

        While we’re talking about easy, fun proofs, here’s a classic:

        Show that there are irrational numbers a,b such that a^b is rational.

        Okay, consider \sqrt{2}^{\sqrt{2}}. It could be rational, in which case we’re done. So suppose it’s irrational. Then note that

        \displaystyle{ \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} } = 2

        so we’re done.

        In fact, Kuzmin showed in 1930 that for any natural numbers m,n with m \ne 0,1 and n not a perfect square, m^{\sqrt{n}} is transcendental. Hence 2^{\sqrt{2}} is transcendental and thus so is its square root \sqrt{2}^{\sqrt{2}}. This shows the difference between what you can get from cheap tricks and what you can get from real work.

        Reply
        • Todd Trimble says:
          10 September, 2014 at 1:29 pm

          Here’s an easy and non-cheap solution to that last puzzle: \sqrt{2} is irrational, and 2\frac{\log 3}{\log 2} is also irrational (for if \frac{\log 3}{\log 2} = \frac{p}{q} where p, q are integers, then 2^{p/q} = 3 and therefore 2^p = 3^q, contradicting the fundamental theorem of arithmetic). Thus a = \sqrt{2} and b = 2\frac{\log 3}{\log 2} are irrational, but we have a^b = 3.

  11. Toby Bartels says:
    9 September, 2014 at 12:28 pm

    I feel like you left out the final statement. Turn around the statement that you actually ended with (before the references); you can start with an uncountable algebraically closed field of characteristic zero (which could be the standard field of complex numbers) and find within it many non-isomorphic but elementarily equivalent subfields of ‘real’ numbers (one of which could be the standard field of real numbers). Or to put it another way, you can find many non-isomorphic but elementarily equivalent complex-conjugation operations (technically: ring involutions) on the field.

    Reply
    • John Baez says:
      9 September, 2014 at 1:11 pm

      Good point! Over the n-Category Café, Mike Shulman said it a bit differently, and quite nicely:

      Put differently, the complex numbers contain more than one non-isomorphic real-closed field that together with i generate all of it.

      By the way, this is precise:

      you can find many non-isomorphic but elementarily equivalent complex-conjugation operations (technically: ring involutions) on the field.

      but this is a bit vague:

      you can start with an uncountable algebraically closed field of characteristic zero (which could be the standard field of complex numbers) and find within it many non-isomorphic but elementarily equivalent subfields of ‘real’ numbers

      until you say what ‘real’ means here. You probably mean more than ‘real closed fields’, since the standard reals probably contain within them some uncountable proper real closed subfields (though to be frank I didn’t give any examples and I can’t instantly think of any). You probably meant what you hinted at next: uncountable real closed fields that are fixed by some involution of the complex numbers. Or else what Mike said.

      Reply
  12. David Roberts says:
    11 September, 2014 at 2:19 am

    Bit late to the party, but…

    You write

    So in fact, a categorical theory only gives a full description of the mathematical structure it’s talking about relative to a choice of what sets are like.

    This is reflected in category theoretic approaches to sets in that the natural number object in a topos is unique up to isomorphism (and uniquely so, if we ask this to preserve the structure). But postulating the existence of a topos with nno that is also well-pointed and satisfies Choice (i.e. ETCS) we can build other toposes satisfying those conditions, which aren’t equivalent to the first, they have their own nno and arithmetic statements that may be false in one may be true in another.

    From the point of view of a material set theorist who thinks in terms of some vaguely Platonic universe of sets, then perhaps one feels there should be a ‘real’ set of natural numbers. But category theoretically, the thinking is more synthetic. I at least have no problems thinking about different toposes having completely different natural number objects – it would be surprising if they were ‘the same’!

    Reply
    • John Baez says:
      14 September, 2014 at 4:55 am

      Indeed, the interesting thing is not that different toposes have different natural numbers objects. The interesting thing is that in some cases it apparently makes sense to compare natural numbers objects across toposes, and get results like “the standard natural numbers in this nonstandard universe of sets is the same as some nonstandard natural numbers in the standard universe of sets”.

      Obviously you need some extra structure around to compare an object in one topos with an object in another topos—like, a map between topoi. With this around it’s not surprising that you can do it. But I haven’t seen people study nonstandard arithmetic (or analysis) using topos theory, so the details are pretty fuzzy to me.

      My not having seen it is probably due to the fact that I’ve never looked—I’m not claiming it hasn’t been done! I might prefer to learn all of model theory from a topos-theoretic perspective, thinking of a model as some sort of functor between topoi (for example a logical or geometric morphism). But I haven’t seen an introduction that takes this perspective and states a bunch of standard results this way: for example compactness, the Löwenheim–Skolem theorems, Morley’s categoricity theorem….

      Reply
  13. Todd Trimble says:
    13 September, 2014 at 2:49 pm

    This is a nice post; I’d like to add a few comments.

    First, a nitpick: in the description of the theory of algebraically closed fields, since you call characteristic zero an axiom “scheme”, you might as well do the same for the algebraic closure axiom: it’s also a schema/scheme or shorthand for an infinite number of axioms, one for each polynomial that says the polynomial has a root.

    Second: maybe a little more could be said about the completeness of the theory of real closed fields. Yes, the theory proves every sentence in the first-order language or its negation, and it’s even decidable: one can write down an algorithm or computer program which, when fed a sentence, is guaranteed to eventually halt and spit out a proof of the sentence or of its negation. But how does one go about showing this?

    A key result is the Tarski–Seidenberg theorem, first announced by Tarski in 1931 with a proof appearing in 1948 (and another in 1954, by Seidenberg). To state this, I’ll recall that a subset of \mathbb{R}^n is basic semi-algebraic if it is the set of solutions to a finite system consisting of polynomial inequalities p(x_1, x_2, \ldots, x_n) > 0 and equalities q(x_1, x_2, \ldots, x_n) = 0. (Here \mathbb{R} can be replaced by any real closed field.) Then, a subset of \mathbb{R}^n is semi-algebraic if it is a finite union of basic semi-algebraic sets. It’s not hard to see that semi-algebraic sets in \mathbb{R}^n are closed under finite unions, finite intersections, and their complements in \mathbb{R}^n. Or in other words, semi-algebraic sets model Boolean combinations of (i.e., where we apply Boolean operations \wedge, \vee, \neg to) basic predicates p(X) > 0, q(X) = 0.

    The Tarski–Seidenberg theorem says that the image of a semi-algebraic set S \subseteq \mathbb{R}^{n+1} under the projection map \mathbb{R}^{n+1} \to \mathbb{R}^n (sending (x_1, \ldots, x_n, x_{n+1}) \mapsto (x_1, \ldots, x_n)) is also semi-algebraic. For example, the image of the sphere x^2 + y^2 + z^2 = 1 under the projection to the x y-plane is the set of solutions to x^2 + y^2 \leq 1.

    This result may seem innocent at first, but it has a very powerful consequence: any first-order formula \phi(x_1, x_2, \ldots, x_n) in the language (\mathbb{R}, +, \cdot, 0, 1, >) of real closed fields, which is built up from Boolean operations and quantifiers \exists, \forall is logically equivalent to one which doesn’t involve any quantifiers at all! This proceeds by induction on the number of quantifiers. First, a formula \exists t \phi(X, t) is modeled by the set of solutions \{X = (x_1, \ldots, x_n): \exists t: \phi(x_1, \ldots, x_n, t), which is the image of the set of solutions \{(x_1, \ldots, x_n, t): \phi(x_1, \ldots, x_n, t) under the projection map (x_1, \ldots, x_n, t) \mapsto (x_1, \ldots, x_n). So if \phi starts off being a Boolean combination of basic predicates, then by the Tarski–Seidenberg theorem, the existential quantification \exists t \phi(X, t) is equivalent to some Boolean combination \psi of basic predicates, involving no quantification. Similarly, by writing \forall t \phi(X, t) as \neg \exists t \neg \phi(X, t), we can apply the Tarski–Seidenberg theorem again to show this is equivalent to a Boolean combination of basic predicates. Thus, if we have a logical formula involving some sequence of quantifiers \exists, \forall applied to a Boolean combination of basic predicates, we can start with the innermost quantifier and work one’s way out, systematically eliminating the quantifiers one by one. In the end, this procedure will reduce any sentence in the language to either “true” or “false”. A nice accessible set of notes is here.

    This is the basic technique for showing the theory is decidable and complete, among other nice properties. I think Tarski got started on this when he had to teach Euclidean geometry, and he set out to isolate a first-order theory of geometry and then analyze it (taking Hilbert’s axiomatic approach to Euclidean geometry a step further). The result is called Tarski geometry; it involves just “points” and two primitive relations, betweenness (B(x, y, z) means y is on the line segment between x and z) and congruence (C(x, y, z, w) means the line segment x y is congruent to z w). It’s quite ingenious. Tarski showed that the theory is decidable (and so basically all of Euclidean geometry that can be expressed in first-order terms is decidable); roughly speaking the theory is subsumed under the more general theory of real closed fields which came up naturally, as it were, in these studies. But the whole area of mathematics has exploded into the theory of o-minimal structures that was invented by model theorists. The book by van den Dries (see the references in the Wikipedia article) is a very good introduction to this.

    Reply
    • John Baez says:
      14 September, 2014 at 3:15 am

      Thanks for the explanations! Someday I’d like to learn all this stuff properly, though I can’t imagine using it in my work these days.

      A couple of days ago the mathematician Marty Weissman told me he read this blog article and had some comments.

      First, an analogue of the Tarski–Seidenberg theorem holds for the p-adic field \mathbb{Q}_p, but you need to generalize the notion of semi-algebraic set. Instead of just introducing the predicate x \ge 0, meaning “x is a square”, you need to introduce infinitely many, saying “x is an nth power”. This was done first by Ax and Kochen but then in a nicer way by Angus McIntyre.

      Second, nobody knows if an analogous theorem holds for the field of Laurent series \mathbb{F}_p((t)). This is apparently a tough question.

      Third, the Ax–Grothendieck theorem says that any 1-1 polynomial function f: \mathbb{C}^n \to \mathbb{C}^n is also onto, but all the proofs Marty knows use characteristic p methods. A nice way to think about this uses model theory. First you prove it with a finite field replacing \mathbb{C}, where it’s obvious. Then you let the characteristic go to infinity and use compactness (in the logic sense)!

      I’ll fix the bit about the axiom scheme for algebraic closure.

      I think Tarski got started on this when he had to teach Euclidean geometry…

      Really? Someone made him teach Euclidean geometry? I always imagined he just got annoyed at Hilbert’s axiomatization and wanted to do better. His axioms are really much better. If he came up with this stuff because he had to teach Euclidean geometry, we may have some obnoxious department chair to thank for a large body of interesting results in logic.

      Reply
      • Todd Trimble says:
        14 September, 2014 at 2:13 pm

        You’re right to question me — the “had to” was rash on my part. (At least I hedged with “I think” :-) — I was probably misremembering something I thought I read. Gee, could I qualify that last sentence any further?) Anyway, I found no evidence in Feferman’s biography that suggests that he started research on this because he was assigned to teach a course.)

        I don’t think it’s entirely out of the ordinary to go further than one’s predecessors as the result of “having to” (or maybe just “asking to”) teach a course on a subject, and being asked to teach a course wouldn’t be that unexpected in the case of a fairly junior faculty member, which I suppose Tarski might have been when he was 23. But Feferman surmises that he (Tarski) was in love with geometry since he was a child, and that doing it up right was a major research concern since the time of his first published papers, so I guess we should go along with that. The emphasis is on the fact that contrary to Hilbert, Tarski effectively took set theory out of the game (focusing on elementary or first-order axioms, and leaving out second-order axioms of continuity and the like).

        Reply
      • John Baez says:
        15 September, 2014 at 3:11 am

        Yes, I got interested in axiomatic geometry a while back for a couple of reasons:

        1) It would be nice to find incomplete axioms for plane geometry where you can add one extra axiom and get either spherical, Euclidean or hyperbolic geometry. So far all I’ve found is Bolyai’s absolute geometry. This is also called ‘neutral geometry’, but it’s not really ‘neutral’ in my opinion because it says parallel lines exist. So, it specializes to Euclidean or hyperbolic geometry, but not spherical geometry (which the specialists call ‘elliptic geometry’).

        2) I thought it would be nice to have a system where starting with any ‘collection’ C of points, lines and maybe circles there would be elementary procedures for generating a collection C' of new ones: ruler-and-compass constructions, essentially. Then, starting with any collection C_0, one could iteratively define

        C_{i+1} = C_i \cup C_i'

        and get a filtered collection. But sometimes different sequences of procedures give the same new point, line or circle due to a theorem in Euclidean geometry. So, the rate of growth of C_i will be slower than one would naively expect at first. And this should be somewhat analogous to the theory of Hilbert series. There should be something to learn about theorems in Euclidean geometry, ‘syzygies’ between theorems, and so on.

        Anyway, besides Hilbert’s rather wretchedly complicated axioms for Euclidean geometry, and Tarski’s delightful first-order axioms, there’s also Birkhoff’s axioms, which are terse but use the real numbers.

        Reply
    • Toby Bartels says:
      15 September, 2014 at 3:43 am

      You have a slight mistake here:

      the algebraic closure axiom: it’s also a schema/scheme or shorthand for an infinite number of axioms, one for each polynomial that says the polynomial has a root

      Not one for each polynomial; at best it would be one for each polynomial with definable coefficients, and that’s not enough. It’s one for each natural number (the degree), with a quantification to get the coefficients. Specifically, axiom n says

      ∀c1, ∀c2, … ∀cn, ∃r1, ∃r2, …, ∃rn, ∀x, x^n + c1 x^{n-1} + c2 x^{n-2} + … + cn = (x – r1) (x – r2) … (x – rn).

      (There are other ways to phrase it, but this way is the best.)

      Reply
  14. Christopher Menzel says:
    13 September, 2014 at 8:09 pm

    Terrific article.

    You say first-order logic has deduction rules that are effective, i.e., “there is an algorithm that can correctly decide whether any given sequence of symbols is a valid proof.” I have three rather trivial comments about this:

    First, I’d suggest saying that first-order logic has an effective deductive *system*. A rule (for a system in a given language L) is usually defined (when the notion is defined at all) to be a set of pairs ⟨Γ,φ⟩ where Γ is a set of sentences of L and φ is a sentence of L, and a rule, so defined, is effective if there is an algorithm that can correctly decide whether or not a given pair ⟨Γ,φ⟩ is an instance of the rule. So understood, from the effectiveness of the rules of a deductive system the effectiveness of the system itself doesn’t follow, since the system might include an undecidable set of axioms.

    Second, I’d suggest “sentences” (or “formulas”) rather than “symbols” in the definition of effectiveness, as that comports better with the usual definition of a proof.

    Third, instead of “valid proof” I’d suggest just “proof in the system”. A sequence of sentences that fails to satisfy the definition of a proof in the system isn’t an invalid or illegitimate proof, it’s just not a proof, period. (And the use of so fundamental a semantic term as “valid” in a proof-theoretic context could give rise to confusion.)

    Reply
    • John Baez says:
      14 September, 2014 at 4:36 am

      Thanks for your comments!

      Since this article is a popularization aimed at people who may not know much logic and may not want to learn much more, I wanted to be as nontechnical as possible. Luckily, people who want to learn more can read your comments.

      The formulation I lifted from Wikipedia—“there is an algorithm that can correctly decide whether any given sequence of symbols is a valid proof”—seems almost optimal when it comes to getting the idea across with a minimum of technical terminology. But I agree that the word “valid” is unnecessary, and even confusing for people who have learned just a little about the technical meaning of “validity”: just enough to get confused, not enough to get unconfused again. So I’ll scratch out “valid”, both here and on Wikipedia.

      I’ll also change “You see, first-order logic has deduction rules that are…” to “You see, first-order logic has a set of deduction rules that are…”

      Reply
  15. Christopher Menzel says:
    14 September, 2014 at 4:51 pm

    Fair enough! My comments (as you rightly surmise) are all just technical niggling — and hence hugely important to someone of my neurotic temperament! :-)

    Reply
  16. Jason Erbele says:
    15 September, 2014 at 5:12 am

    This was a fun article to read after finishing up teaching a lower division summer course on discrete mathematics (essentially a survey of set theory, combinatorics, probability, first-order logic, and proof techniques). It is interesting to know what the limitations of logic are, and to metaphorically peek over the edge of those boundaries, as if from the top of a cliff.

    There were two things that my nitpick radar noticed: “standard reals numbers” in the final paragraph of the “The real numbers” section and a typo of “we’re” in the following paragraph.

    Reply
  17. Thomas Benjamin says:
    17 May, 2016 at 12:23 pm

    I am interested in the following statement you make:

    “…And if we use first-order axioms of set theory to explicitly talk about subsets instead of predicates, then our set theory will have many models! Each model will have a version of the real numbers in it that’s unique up to isomorphism…but the versions in different models will be really different.”

    The specific difference I am interested is the truth or falsity of the Continuum Hypothesis. Your statement seems to imply that Dedekind-Completeness (when one uses first-order axioms of set theory to explicitly talk about subsets instead of predicates) is ‘internal’ relative to the model–that is, a mathematician ‘living’ in a model of set theory where, say, the Continuum hypothesis is true will still be able to state that the reals form a complete ordered field and so will not be able to find ‘gaps’ in her ‘real line’. Is this analysis correct?

    Reply
    • John Baez says:
      17 May, 2016 at 3:25 pm

      Yes, your analysis is correct: in any model of ZF there is a complete ordered field that is unique up to isomorphism. The validity or not of the Continuum Hypothesis plays no role here.

      Reply
      • Thomas Benjamin says:
        19 May, 2016 at 11:30 am

        Since for Dedekind–complete ordered fields defined in ZF, the problem of many nonisomorphic models has been transferred to ZF, if one just wished to consider the axioms for the Dedekind-complete ordered fiedls by themselves; is there a way to ‘schematize’ Dedekind’s completeness axiom (i.e. replace the completeness axiom with a first-order schema)? Would Tarski’s Axiom of Continuity do the trick?

        Reply
      • John Baez says:
        19 May, 2016 at 5:41 pm

        I believe we discussed that possibility somewhere in the discussion either here or at this parallel post:

        • John Baez, Uncountably categorical theories, The n-Category Café, 31 August 2014.

        … but it’s been a while, so I could be wrong. The idea would be to work, not with all bounded sets, but those defined by formulae in the language.

        Reply
  18. Nonstandard Integers as Complex Numbers | Azimuth says:
    3 March, 2018 at 7:29 pm

    For more on the logic of complex numbers, written at about the same level as this, try this post of mine:

    • The logic of real and complex numbers, Azimuth 8 September 2014.

    Reply

Leave a reply to John Baez Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.