I recently defended my dissertation and I have had a number of non-mathematician friends and family asking me to try to explain what it is I study. In a nutshell, I study models of Peano Arithmetic and their elementary extensions. This post is meant to give an introduction to Peano Arithmetic and in a later post I will go into more details about the problems I have been working on.

Peano Axioms

My research is primarily in the first-order theory of Peano Arithmetic (PA). “First-order” refers to first-order logic, which I like to think of as providing a framework for formalizing mathematics. In first-order logic, we can express statements like “multiplication distributes over addition” as ““. That is, we allow ourselves to use symbols for addition and multiplication, and can build up statements using logical connectives (“and”, “or” and “not”) and quantifiers  (““, meaning “for all”, or ““, meaning “there exists”).

Peano Arithmetic is a list of axioms written in this first-order language. These axioms include the above statement that multiplication distributes over addition, as well as other elementary statements about arithmetic including that addition and multiplication are commutative and associative. The other main axioms are the induction schema: an infinite list of axioms stating, essentially, for any property that can be expressed in first-order logic, if holds and, holds, then holds. In other words, for any property expressible by a formula of first-order logic , if the number 0 has that property, and, whenever n has that property, n + 1 also has that property, then every number will have that property.

The idea behind this axiom is that many facts about numbers can be proved using “proof by induction“. It was originally hoped that all number theoretic facts could be proved in this way, but Peano Arithmetic is famously incomplete.

A model of Peano Arithmetic is a set M, with operations and (that is, M has to be closed under addition and multiplication, so if we add or multiply two elements of M, we get another element of M), satisfying these axioms. That means that addition and multiplication will need to be commutative and associative, and multiplication should distribute over addition. Every model of PA will have the natural numbers as an initial segment, but there are also non-standard models, which contain numbers greater than any standard natural number. In fact, first order logic is not strong enough to categorically axiomatize the standard model ; that is, there is no set of first-order axioms for which the only model satisfying those axioms is the standard model.

A careful reader may wonder how it is possible for a non-standard model of arithmetic to satisfy the induction schema. The argument goes: 0 is a natural number, and if n is a natural number then n + 1 is also, so by induction, every element of a model of arithmetic should be a natural number! Of course, this presupposes the idea that the property “x is a natural number” can be expressed in first-order logic, and in fact this is not possible (the proof that this is impossible is actually just the proof that there exist non-standard models).

Arithmetic and Set Theory

A nice result about PA is that it interprets finite set theory. In a model M of PA, if n and m are elements of M, we can define the relation to mean that the n-th bit of the binary representation of m is 1. This is expressible in in the first order language of arithmetic; that is, there is a formula expressing that the x-th bit of the binary representation of y is 1. So in any model M of PA, the set coded by an element m of M is (the set of all those indices at which the binary representation of m has a 1). For example, the number 13, represented in binary as 1101, will code the set { 0, 2, 3 } (count the places with a 1 in them from right to left, starting at 0). It’s not hard to see that every finite set can be coded by some number.

Forgetting about arithmetic for a second, we can now think of our model of PA as just containing sets, which are all related to each other by this relation. It turns out that for any model of PA, if we think of it as a model of set theory using this relation, it will satisfy all the axioms of set theory with one notable exception: the axiom of infinity. That is, this model really will look like a model of set theory, except that it will not have any infinite sets.

Set theory enjoys a special place in the foundations of mathematics: often everything (all mathematical objects, functions, spaces, etc.) is defined in terms of sets, and in particular numbers are just particular kinds of sets. That is, number theory can be formalized in terms of set theory. Here we have the opposite idea: we define sets in terms of numbers, and formalize set theory in terms of number theory (Peano Arithmetic). Anything that can be proven from finite set theory can be formalized and proven within PA.

We might hope that any question about finite mathematical objects which has an answer can be answered within PA, but it turns out this isn’t true: some arguments about finite objects really do require infinity. The video below, from the excellent YouTube channel PBS Infinite Series, does a great job explaining a problem where this phenomenon occurs: