Logical Underpinnings of Mathematics

Our understanding of mathematics is based in applied logic, just as our understanding of reality is based in applied mathematics. Thus, logic and mathematics are tools for furthering our understanding. Mathematics and logic are closely entwined; their intersection is the field of mathematical logic, the machinery by which we establish mathematical facts (logical truth). We will continue with a naive notion of truth for a while.

Deductive Logic

Deductive logic serves to establish a new mathematical assertion (true statement), deduced from prior established assertions about mathematical objects from the domain of discourse. The formal mathematics consists of chains of truth-preserving assertions, logically linking each assertion to more primitive, proven assertions, and ultimately to the primitive notions and axioms to which we assign intuited truth.

History of Formal Logic

The logic of a proof (the links in the deductive reasoning chain) is based conceptually on the simple deductive syllogism of Aristotle (we owe a bit to the classical Greek scholars).

Before there was a formal representation of logic, assertions were made in natural language. Most mathematical proofs still formulate natural language assertions, perhaps extended to address mathematical concepts. Following after Aristotle was the great Stoic logician/philosopher Chrysippus, who formalized logic into something that resembles modern propositional logic. But his writings were largely lost. Most of what we know comes from third parties with knowledge of his teachings. So Aristotle’s more well-documented teachings guided logic for the next 1500 years.

The statement types are:

modus ponens inference rule (syllogism)
major and minor premises entail conclusion
generalization inference rule
proposition with variable x: p(x) entails, for all x, p(x)

In modern propositional logic, a hypothetical syllogism is written:


where A and B are statements, each representing a logical value True or False.

The semantics associated with this syntax reads:

  • major premise: AB: A implies B (if A then B)
  • minor premise A: assert A (A is True)
  • conclusion B : therefore B (then B is True)

The logic of a proof is thus a chain of such arguments (the set of intermediate premises and conclusions), together with a model, the underlying set of truth conditions of the premises.

Most human-generated proofs in mathematics are stated in natural language, restricted to a certain style and regimen that makes the flow of logic as transparent as possible. But supporting the natural language exposition are equivalent statements that belong to the propositional logic. While it would be artificial and obscuring to construct mathematical proofs in the syntax of propositional logic, conceptually, all proof is a sequence of just such arguments.

A syllogism is always a valid argument, regardless whether the premises are true or not. If the premises are true, then the syllogism is a sound argument and the conclusion is also true. But a valid argument will reach an invalid conclusion when the premises are not true statements. A proof is a set of sound arguments that establish a true statement derived from other true statements. In a chain of syllogisms, the conclusion is the only result to pass on to a subsequent argument, where it will factor into the subsequent’s premises.

Art of the Proof

The ability to chain arguments together in a useful logical ordering comes with mastery of the art the proof. In advanced mathematics, these chains can lead far away from the immediate concepts before returning with support, often highly abstract, for a pertinent conclusion.

Such wandering away from questions raised by a theme, and then returning with support, reminds us of the pattern of the sonata form of classical music, with its theme assertion, followed by further development of thematic material, and then recapitulation. The human mind is receptive to this pattern for resolving complex ideas.

The primary motivation behind many of the memes of our mathematics is the need for more proof tools. Development of ever larger hammers seems to be required to break through to proofs that remain unreachable with slighter tools. Such heavier-duty tools are called ‘big machinery’. The necessity for big machinery, to prove a seemingly simple conjecture, is a mathematician’s idea of a good joke.

Thus Fermat’s last conjecture was stated in a couple of lines in 1637, but it required 400 pages of late 20th century mathematics to deduce a proof. Funny ha-ha, particularly since Fermat remarked he had a simple proof in mind, but it was a little too large to be written in the margin of his manuscript. Fermat apparently also had inclinations toward humor.

Sequences of syllogisms of various flavors (modus ponens, modus tollens, modus tollendo ponens, etc.), have provided the arguments of all demonstrative mathematical proofs from Aristotle until the late 19th century, when the first and second order logic theory was devised to formalize deductive logic. The first order logical inference rules formalize modus ponens and generalization.

Just as syllogisms are chained within a proof, proofs are themselves chained to create ever more complex layers of argument. Each proof is a transformation of established prior truth statements, together with some new premises, into a new truth statement. The memeplex that is mathematics is mechanically merely a chain of such transformations of the base axiomatic truths, interpreted within the model through which each logical link conserves truth.

Thus logic is our blueprint, not in the sense of specifying what we build, but rather specifying the methods telling us how to build it, the rules that must pertain. Once the ‘how’ is determined, the ‘what’ is inevitable (logical, as Spock would tell us). This inevitable ‘what’ is lifeless, however, mere logical symbols on a page, a meaningless exercise. The meaning is informed by our intuition, producing mathematical visualizations that bring the memes to life.

Constructive and Non-Constructive Logic

There are proofs, call them direct, that illustrate why some truths lead to other truths. For instance, a proposition regarding the existence of an object could be proved by showing how to construct one, or by providing an example of one. Another common constructive proof uses mathematical induction to show that a property is associated with all elements in a set. For example, it could prove that the sum of the first n cubes is equal the sum of the first n integers squared.These are the most satisfactory type of proof. (A few mathematicians, constructivists, insist that mathematics only admit this type proof; this likely makes their job harder.)

Construction of classical mathematics, however, has always depended heavily on indirect proofs, where we end up not much closer to understanding why a statement is true than before we proved it so. For example, new statements can be established by showing that their falsity would produce a logical contradiction.

Here is a link to a short and sweet indirect proof:

Such ‘back door’ cleverness has appeal. Yet one might hope indirect proofs are just convenient truth place holders in our memeplex, awaiting eventual replacement via direct proofs that shed light on the reason why something needs to be true (other than why it can’t not be true). However, a perfect world with only direct proofs is not to be. It has been shown that, in our chosen logic, there can be no direct proof of some facts in the classical mathematics universe. For instance, Courant points out that there can be no direct proof of the non-denumerability of the reals.

Sometimes the constructive distinction is not clear, as in the following two examples.

i) Prove √2 irrational

Here we are presented with an essentially constructive proof (words are not really necessary). We can visualize and intuit why the premise cannot be false. Yet by adding the words to describe the argument, we end up with a proof based on contradiction.

ii) Prove every set of n integers has a subset whose sum is divisible by n

Here, the premise is provided a constructive interpretation by creating an abstract subset, say of n pigeons, and defining division by n in terms of building n pigeon houses. The argument then shows that if division by n were not true, there would be too many values (pigeons) for available containers (pigeon houses), thus invoking the pigeonhole principle that requires two pigeons to share the same house.

Indirect arguments by contradiction have a further dark side. They are based on a proposition of the type p ∨ ¬p (read p or not p). This argument requires a statement of this form to be a tautology (always true), but this in turn requires the law of the excluded middle. But if the domain of discourse includes certain infinite sets, it may not be valid to assume that p ∨ ¬p is always true. There are other logic theories, not based on Boolean algebra, that can account for the middle state where p ∨ ¬p is undecidable.

The intuitionist school of mathematics works in this other math universe. Meanwhile, the overall classical construction can continue.

Primitive Notions and First/Second Order Logic (Predicate Calculus)

Just as with real world structures, our formal mathematics demands that our edifice have a foundation. This foundation will provide a context, a minimal domain of discourse, from which the remainder will evolve deductively.

Our intuition provides the outline of this foundation, by our primitive notions, concepts which admit no further definition other than our intuition can provide. The primitive notions of mathematics include numbers, points, lines, and sets. They remain undefined, known to us through our intuition and through elaborated behaviors. There are also defined notions in our foundation, specifying synthetic entities that will be of utility in future reasoning. These can be considered a derived layer, overlaying our primitives.

We must be able to describe our foundational notions precisely, so that we can communicate and argue their form, necessity, sufficiency, validity. The predicate calculus provides the syntax and domain semantics for this communication and analysis. The calculus expresses variables ranging over notional domains, predicates defining true statements regarding variables ranging over domain elements, and quantifiers ‘for all’ and ‘for any’ that act on variables or predicates.

The first order logic admits quantification over variables only; the second order logic permits quantification over predicates as well. A second order statement can be expressed in the first order logic, but it expands into a first order schema expressing a predicate for each variable element of the variable’s domain. Since fundamental mathematical notions address an infinitude of elements, points, lines, etc., this results in a schema with an infinitude of predicates.

The arithmetic notion of mathematical induction is the only instance where the need for second order logic arises in our basic calculus. By expressing that statement with first order logic and its countable infinitude of predicates, our foundation can be expressed entirely in first order logic, with the one infinitary extension in support of which we provide the induction axiom.

This first order theory has become the formal logic system of our classical mathematics, which has implications:

I. When a first-order theory has any infinite model, then it has infinite models of every cardinality. In particular, no first-order theory with an infinite model can be categorical. First order logic cannot even express countability. Further, there is no first-order theory whose only model has the set of natural numbers as its domain, or whose only model has the set of real numbers as its domain. Many extensions of first-order logic, including infinitary and higher-order logic, are more expressive in the sense that they do permit categorical axiomatization of the natural numbers or real numbers.

II. First-order logic is undecidable, meaning a sound, complete and terminating decision algorithm for provability is impossible. This has led to the study of interesting decidable fragments such as C2, first-order logic with two variables and the counting quantifiers: “there exists at least n” and “there exists at most n”.

III. First order logic cannot be used in graph theory to validate existence of a path between two nodes, because graph theory is not first class.


Axioms are statements which provide for existence and behavior of our notions. Axioms are assumptions that are not deducible from any prior propositions. Axiomatic foundations require great skill in composition to ensure they can support an indefinite future construction.

To support future deduction, the chosen system of axioms must be construed as true statements. Whether they are true depends on our interpretation of the primitive notions, our undefined entities. When an interpretation of the primitive notions is found that renders all the axiomatic statements true, one has defined a model for the system. A model supports deductive reasoning chains.

By the middle of the twentieth century, the major axiom systems of our classical mathematics were established and widely accepted. They are still in use today: the Zermelo-Fraenkel Axiomatic Set Theory with Choice (ZFC), the Dedekind-Peano Postulates of arithmetic (PA: Peano Arithmetic, derivable from a set-theoretic definition of the natural numbers in ZFC), and Euclid’s five postulates for geometry (as modernized by Hilbert and expressed in terms of ZFC).

These were not the only axiom sets available, but these have served us well for many decades. These arithmetic and geometry axiom sets are expressed in terms of the ZFC language. This exemplifies our hierarchical axiomatic basis: a collection of primitive notions for sets and their members (ZFC), in terms of which we can further assert universally useful notions pertaining to arithmetic and geometry.

Sets: Zermelo-Frankel Axioms With Choice (ZFC)

Sets, being the foundation of all else, should be the most well-considered and finely-drawn structures of our mathematics. Unfortunately, they are not. Necessary and sufficient conditions to meet our classical mathematical needs have not been the first objective of set axiom development. Rather, consistency and avoidance of antimony have been the driving design criteria. Thus our set axioms tend to be stronger than necessary, adding infrastructure that is not needed in classical mathematics outside of the set theory itself. ZFC is the result.

#1 Axiom of Extensionality: If X and Y have the same elements, then X=Y.
#2 Axiom of the Unordered Pair: For any a and b there exists a set {a,b} that contains exactly a and b. (also called Axiom of Pairing)
#3 Axiom of Subsets: If phi is a property (with parameter p), then for any X and p there exists a set Y={u in X:phi(u,p)} that contains all those u in X that have the property phi. (also called Axiom of Separation or Axiom of Comprehension)
#4 Axiom of the Sum Set: For any X there exists a set Y= union X, the union of all elements of X. (also called Axiom of Union)
#5 Axiom of the Power Set: For any X there exists a set Y=P(X), the set of all subsets of X.
#6 Axiom of Infinity: There exists an infinite set.
#7 Axiom of Replacement: If F is a function, then for any X there exists a set Y=F[X]={F(x):x in X}.
#8 Axiom of Foundation: Every nonempty set has an minimal element. (also called Axiom of Regularity)
#9 Axiom of Choice: Every family of nonempty sets has a choice function.

Sets are not defined or even mentioned in the formal set-theoretic axiom set, ZFC. The axioms of ZFC provide rules based on a relation ‘is a member of’, another rule for selecting a member, existence statements for the null and infinite sets, and rules for the standard set operations.

There are equivalent-strength alternatives, but ZFC is not arbitrary in its construction; unless one can approach the problem from a substantially different mind set, with more left to implementation layer logic, and less in the theory itself, ZFC seems the best available theory to carry mathematics on its back.

Work continues to find reductions in scale for ZFC, to support a more compact model. For instance, the only two infinities that our mathematics need address, outside of set theory itself, are countable infinity and the infinity of the continuum. Further, only a countable number of elements from the continuum will ever be enumerated as separable elements of our mathematics, such as the algebraic numbers, and transfinite numbers resulting from geometric ratios, such as pi. So perhaps just one countably infinite set need be part of our set theory.

Other than to improve optics (aesthetics), why change ZFC if it works? Efforts to explore such an alternative will keep certain issues in front of us. The ZFC theory comes with baggage, machinery unnecessary beyond this specific theory of sets. Yet if we fail to keep this in our mind, these logical necessities may creep out of the theory’s machinery and into higher level logical arguments, with a life of their own. We must always recognize these arguments are not a wider requirement of our mathematics. Mathematics is not the same as whatever is formalized in ZFC. For a more mathematically mature exposition of alternatives, refer to Holmes, M. Randall, “Alternative Axiomatic Set Theories”, The Stanford Encyclopedia of Philosophy (Winter 2017 Edition), Edward N. Zalta (ed.).

Arithmetic: Peano Postulates

A system of five axioms for the set of natural numbers {\mathbb{N}} and a function {S} (successor) on it, introduced by G. Peano (1889):

#1 {0 \in \mathbb{N}}
#2 {x \in \mathbb{N} \to Sx \in \mathbb{N}}
#3 {x \in \mathbb{N} \to Sx \neq 0}
#4 {x \in \mathbb{N} \wedge y \in \mathbb{N} \wedge Sx =Sy \to x = y}
#5 {0 \in M \wedge \forall x (x\in M \to Sx\in M) \to \mathbb{N} \subseteq M} for any property {M} (axiom of induction).

First-order logic syntax is defined recursively as a set of statements comprised of combinations of constants, variables, connectors and qualifiers. Semantics are assigned via choice of domain of discourse (over which the variables range), and the syntactic rules of the first order theory (logical meanings of the statement tokens). These formalisms facilitate study of logic theory as well as automated proof systems. We also encounter such formalisms when they are used to make rigorous the axioms on which our mathematics is built.

Numbers are not defined in the PA axioms. The PA axioms assert the existence of entities that behave according to our intuition about the natural numbers, via rules involving a ‘successor’ relation.

Geometry: Euclid’s Five Postulates

Certain sets and members are recognized by our intuition as lines and points in space. Other axioms define spatial notions: between, coincident, and equal/congruent. Our intuition informs us that geometric concepts are being established via set theory.

#1 A straight line segment can be drawn joining any two points.
#2 Any straight line segment can be extended indefinitely in a straight line.
#3 Given any straight line segment, a circle can be drawn having the segment as radius and one endpoint as center.
#4 All right angles are congruent.
#5If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two right angles, then the two lines inevitably must intersect each other on that side if extended far enough. This postulate is equivalent to what is known as the parallel postulate.

‘Euclid himself used only the first four postulates (“absolute geometry”) for the first 28 propositions of the Elements, but was forced to invoke the parallel postulate on the 29th. In 1823, Janos Bolyai and Nicolai Lobachevsky independently realized that entirely self-consistent “non-Euclidean geometries” could be created in which the parallel postulate did not hold. (Gauss had also discovered but suppressed the existence of non-Euclidean geometries.)'[see Wolfram MathWorld]

Necessary Properties of Axioms

Mathematical foundation pioneers did not get their axioms perfected on the first try. The axioms have been made more sophisticated over time, usually by refining them to have certain ‘nice’ properties that maximize consistency and completeness while avoiding antinomy.

To this end, mathematicians imbue the axioms with certain essential properties, as they relate to one another.

    Axioms are independent because one cannot be deduced from the others. Axioms are consistent because a contradiction cannot be derived from them.
    Axioms are complete because the validity of all derivable statements can be established from only these assumptions.

Mathematical Pragmatism

As a practical note, Halmos, in the Introduction to his text on Naive Set Theory, advises students to understand the axiomatic underpinnings of their trade. But he goes further: “read it, absorb it, and forget it”. Fortunately, Halmos restricted his domain of discussion to formal set theory, so mathematicians were not being urged to forget mathematical induction! Mathematicians also find direct use of the foundational machinery useful in formal proofs of basic intuitive operations we take for granted, such as 1 + 1 = 2.

The rest of mathematics is not much affected by any remaining uncertainties or weaknesses at the axiomatic level. Classical mathematics is completely supported under this system when certain types of infinite sets are excluded from the domain of discourse. Doing so does not reduce the effectiveness or validity of the total of developed mathematics to date.

Looking To The Future

Continuing new challenges and refinements create an ongoing mathematical specialty, work on axiomatic and logical foundations. ZFC is a case in point. It exists at the core of classical mathematics, yet the formal completeness and consistency of ZFC is still open to debate. Its inadequacy is highlighted in the relationships of distinct transfinite sets, and most visibly with the Cantor Continuum Hypothesis (CH), an open mathematical question that now is known to be independent of the ZFC axioms (we cannot logically argue its validity at this time).

Mathematicians have put forth approaches for extending/revising ZFC, broadening its domain and enhancing its consistency. A typical goal has been to augment ZFC at least to a point where CH is decidable. Although CH seems to be accepted in spite of its current inaccessible basis, Conway states: “The prevailing opinion today is that CH should be considered false”.

Formal necessity may cause mathematicians to go beyond the current state of the art in logic and axioms, in order to eliminate some apparent limitations at the boundaries of our mainstream mathematics. Such tinkering will need to be extremely well thought. One hopes such revised choices will not affect our mainstream body of work, which should be derivable from the revised axioms, and which in worst case would continue to be isolated in a ‘classical’ bubble whose esoteric limitations are well-understood.

Mathematical Truth

Via our chosen Aristotelian deductive logic system, we consider our proven theorems to be true (factual). There could be two understandings of mathematical truth: mathematical truth is a product of human mind; mathematical truth is a product of our external reality.

In my naive conception, I stand between these philosophical stances. Mathematics is a pure construction of mind, but its derivation via our chosen applied logic should always produce equivalent theories of mathematics. In this sense, mathematical truth exists beyond the logical mind, in a proto-logic space that is characterized by our intuition of our reality.

That reality behaves rationally becomes more and more established as time goes by, since our developing mathematics still accurately describes and predicts reality’s spatio-temporal workings, the interactions of matter and energy. This is the proto-logical space that mathematical truth occupies, the behavioral or phase space that governs the why and how of its workings. We exist in this physical space, and our naive conceptions of it are the basis for mathematical truth.

So, would one better say mathematical truth is discovered, invented, or created? I choose created (constructed) in the ordinary sense of mathematical progress via applied logic; discovery may more accurately convey the sense of naive truths in mathematics, those that suggest the bases for our axioms; invention may propel the advances in metamathematics and metalogic, where choice of foundational logical precepts is determined.


Comments Welcome

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s