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

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

which says that if and only if for every predicate is true precisely when 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

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

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:

This says that if you’ve got any predicate that’s true for and is true for whenever it’s true for 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 for your variables to range over, pick a subset of 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:

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

for each formula 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 and work for the real numbers. You can think of these axioms as consisting of three parts:

• the **field** axioms: the usual algebraic identities involving and together with laws saying that everything has an additive inverse and everything except has a multiplicative inverse.

• the **formally real field** axiom, saying that is not the square of anything. This implies that we can equip the field with a concept of 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 either or 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 if and only if has a square root.

Tarski showed this theory is **complete**: any first-order sentence involving only the operations and the relation 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 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 and

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 is **arithmetical** if there is a formula in the language of first-order Peano arithmetic, with two free variables, such that

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 along with just enough other numbers to get a real closed field again. Or, we could throw in both and This probably gives a bigger real closed field—but nobody knows, because for all we know, could equal 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 that is bigger than and so on—and then do what it takes to get another real closed field. This involves throwing in elements like

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

where is any integer, perhaps negative, is any

positive integer, and the coefficients are real.

What’s It’s just a formal variable. But the real Puiseux series are real closed field, and acts like 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 bigger than 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 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 and together with laws saying that everything has an additive inverse and everything except has a multiplicative inverse.

• the **ordered field** axiom, saying there is a total ordering such that and implies and implies

• 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 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 is some cardinal. A first-order theory describing structure on a single set is called **κ-categorical** if it has a unique model of cardinality And 1965, a logician named Michael Morley showed that if a list of axioms is -categorical for *some* uncountable it’s -categorical for *every* uncountable 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 and We don’t include anything about 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

• 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 and 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 we can choose another real closed field not isomorphic to with the same cardinality. We can build the complex numbers using pairs of real numbers. We can use the same trick to build a field using pairs of guys in But it’s easy to check that this funny field is algebraically closed and of characteristic zero. Since it has the same cardinality as it must be isomorphic to

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.

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?

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

Thanks!

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

Whoops! Duly moved.

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, …?

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.

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?

arch1 wrote:

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.

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

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 means without a theory of natural numbers!

In other words, you can’t make your idea of

precise without using precisely the ideas about natural numbers that you’re trying to explain, or prove. As I said:repeated applicationsYou 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.

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:-))

arch1 wrote:

Right.

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:

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 exceptnatural numbers. It’s better to look at the modern form of the Peano axioms.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)

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

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

nonstandardmodel 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’.

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?

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

exceptmathematical 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

doeswork, I can point out the flaw.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 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 , and , and , and , 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 , since it clearly isn’t , 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 , 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. , 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 ” will fail because “” requires the theory of natural numbers.

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 that’s the successor of a rogue element that’s the successor of a rogue element … 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.

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

I see, that seems very reasonable now. Thanks!

Actually, what I meant by “you can’t prove 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.

Max Lee wrote:

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

• John Baez, Surprises in logic.

I liked this post :).

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 is in some sense “more fundamental” than —which might tie into why complex numbers appear at the heart of physics.

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é.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”?

Thanks! I fixed that.

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

I’m a bit surprised that it’s an open question whether or not is irrational! Given how simple some of the proofs are for the irrationality of and 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.

Greg wrote:

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

Actually, now that I look, I see people saying that nobody knows if 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 I would have heard.

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

Given that the irrationality of and are individually quite easy to prove, you might think

theirdifference would be easy to prove irrational too.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 that are linearly independent over the rational numbers , the fieldhas transcendence degree at least $n$ over .

Here is the field of rational numbers, and the

transcendence degreeof a field over a field is the cardinality of the largest set of elements of that obey no polynomial equations with coefficients in .So, if Schanuel’s conjecture is true,

has transcendence degree 2, so and 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 fieldis field with an operation obeying these rules: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

anotheroperation on the complex numbers, some sort of ‘pseudoexponentiation’, which obeysbut 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.

Lots of interesting things to ponder! But at least the puzzle wasn’t too hard. Suppose and were

bothrational. Then the quadratic:has rational coefficients. But:

which contradicts the known fact that is transcendental.

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).

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

The contradiction is that if and are both rational, then and 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 and can’t both be rational.

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

Show that there are irrational numbers such that is rational.

Okay, consider . It could be rational, in which case we’re done. So suppose it’s irrational. Then note that

so we’re done.

In fact, Kuzmin showed in 1930 that for any natural numbers with and not a perfect square, is transcendental. Hence is transcendental and thus so is its square root . This shows the difference between what you can get from cheap tricks and what you can get from real work.

Here’s an easy and non-cheap solution to that last puzzle: is irrational, and is also irrational (for if where are integers, then and therefore , contradicting the fundamental theorem of arithmetic). Thus and are irrational, but we have .

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.

Good point! Over the

n-Category Café, Mike Shulman said it a bit differently, and quite nicely:By the way, this is precise:

but this is a bit vague:

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.

Bit late to the party, but…

You write

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’tequivalent 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’!

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….

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 is

basic semi-algebraicif it is the set of solutions to a finite system consisting of polynomial inequalities and equalities . (Here can be replaced by any real closed field.) Then, a subset of issemi-algebraicif it is a finite union of basic semi-algebraic sets. It’s not hard to see that semi-algebraic sets in are closed under finite unions, finite intersections, and their complements in . Or in other words, semi-algebraic sets model Boolean combinations of (i.e., where we apply Boolean operations to) basic predicates , .The Tarski–Seidenberg theorem says that the image of a semi-algebraic set under the projection map (sending ) is also semi-algebraic. For example, the image of the sphere under the projection to the -plane is the set of solutions to .

This result may seem innocent at first, but it has a very powerful consequence:

anyfirst-order formula in the language of real closed fields, which is built up from Boolean operations and quantifiers 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 is modeled by the set of solutions , which is the image of the set of solutions under the projection map . So if starts off being a Boolean combination of basic predicates, then by the Tarski–Seidenberg theorem, the existential quantification is equivalent to some Boolean combination of basic predicates, involving no quantification. Similarly, by writing as , 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 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 ( means is on the line segment between and ) and congruence ( means the line segment is congruent to ). 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.

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 , but you need to generalize the notion of semi-algebraic set. Instead of just introducing the predicate meaning “ is a square”, you need to introduce infinitely many, saying “ 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 This is apparently a tough question.

Third, the Ax–Grothendieck theorem says that any 1-1 polynomial function is also onto, but all the proofs Marty knows use characteristic methods. A nice way to think about this uses model theory. First you prove it with a finite field replacing , 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.

Really? Someone

made himteach 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 hehad toteach Euclidean geometry, we may have some obnoxious department chair to thank for a large body of interesting results in logic.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).

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’ of points, lines and maybe circles there would be elementary procedures for generating a collection of new ones: ruler-and-compass constructions, essentially. Then, starting with any collection one could iteratively define

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 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.

You have a slight mistake here:

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.)

Toby wrote:

I like a mathematician with confidence.

Yes, you’re right Toby.

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.)

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…”

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

We wouldn’t be interested in logic if we didn’t like niggling. Cf. my meta-niggling about your niggling.

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 real

snumbers” in the final paragraph of the “The real numbers” section and a typo of “we’re” in the following paragraph.Thanks, I’ll fix those typos.

Yes, part of the fun is how logic lets us see where logic leaves off.

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?

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.

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?

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.

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,

Azimuth8 September 2014.