$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 2.8: Nonlogical Axioms

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

When we are trying to prove theorems in mathematics, there are almost always additional axioms, beyond the set of logical axioms $$\Lambda$$, that we use. If we are trying to prove a theorem about vector spaces, the axioms of vector spaces come in might handy. If we are proving theorems in a real analysis course, we need to have axioms about the structure of the real numbers. These additional axioms are sometimes explicitly stated and sometimes they are almost always there. In this section we give a couple of examples of sets of nonlogical axioms that we might use in writing deductions.

Example 2.8.1. For many of us, the first explicit set of nonlogical axioms that we wee is in a course on linear algebra. To work those axioms out explicitly, let us fix the language $$\mathcal{L}$$ as consisting of one binary function symbol, $$\oplus$$, and infinitely many unary function symbols, $$c \cdot$$, one for each real number $$c$$. (Yes that symbol is "c-dot".) These function symbols will be used to represent the functions of scalar multiplication. We will also have one constant symbol, 0, to represent the zero vector of the vector space. Here, then, is one way to list the nonlogical axioms of a vector space:

1. $$\left( \forall x \right) \left( \forall y \right) x \oplus y = y \oplus x$$ (vector addition is commutative).
2. $$\left( \forall x \right) \left( \forall y \right) \left( \forall z \right) x \oplus \left( y \oplus z \right) = \left( x \oplus y \right) \oplus z$$ (vector addition is associative).
3. $$\left( \forall x \right) x \oplus 0 = x$$.
4. $$\left( \forall x \right) \left( \exists y \right) x \oplus y = 0$$.
5. $$\left( \forall x \right) 1 \cdot x = x$$.
6. $$\left( \forall x \right) \left( c_1 c_2 \right) \cdot x = c_1 \cdot \left( c_2 \cdot x \right)$$.
7. $$\left( \forall x \right) \left( \forall y \right) c \cdot \left( x \oplus y \right) = c \cdot x \oplus c \cdot y$$.
8. $$\left( \forall x \right) \left( c_1 + c_2 \right) \cdot x = c_1 \cdot x \oplus c_2 \cdot x$$.

Notice a couple of things here: There are infinitely man axioms listed, as the last three axioms are really axiom schemas, consisting of one axiom for each choice of $$c$$, $$c_1$$, and $$c_2$$. An axiom schema is a template, saying that a formula is in the axiom set if it is of a certain form. Also notice that I've cheated in using the addition sign to stand for addition and juxtaposition to stand for multiplication of real numbers since the language $$\mathcal{L}$$ does not allow that sort of thing. See Exercise 1.

Example 2.8.2. We will write out the axioms for a dense linear order without endpoints. Our language consists of a single binary relation symbol, $$<$$. Our nonlogical axioms are:

1. $$\left( \forall x \right) \left( \forall y \right) \left( x < y \lor x = y \lor y < x \right)$$.
2. $$\left( \forall x \right) \left( \forall y \right) \left[ x = y \rightarrow \neg x < y \right]$$.
3. $$\left( \forall x \right) \left( \forall y \right) \left( \forall z \right) \left[ \left( x < y \land y < z \right) \rightarrow x < z \right]$$.
4. $$\left( \forall x \right) \left( \forall y \right) \left[ x < y \rightarrow \left( \left( \exists z \right) \left( x < z \land z < y \right) \right) \right]$$.
5. $$\left( \forall x \right) \left( \exists y \right) \left( \exists z \right) \left( y < x \land x < z \right)$$.

The first three axioms guarantee that the relation denoted by $$<$$ is a linear order, the fourth axiom states that the relation is dense, and the final axiom ensures that there is no smallest element and no greatest element.

Notice that in both of our examples, the axiom set involved is decidable: Given a formula $$\phi$$ that is alleged to be either an axiom for vector spaces or an axiom for dense linear orders without endpoints, we could decide whether or not the formula was, in fact, such an axiom. And furthermore, we could write a computer program that could decide the issue for us.

Example 2.8.3. It is time to introduce a collection of nonlogical axioms that will be vitally important to us for the rest of the book. We work in the language of number theory,

$\mathcal { L } _ { N T } = \{ 0 , S , + , \cdot, E , < \}.$

The set of axioms we will call $$N$$ is a minimal set of assumptions to describe a bare-bones version of the usual operations on the set of natural numbers. Just how weak these axioms are will be discussed in the next chapter. These axioms will, however, be important to us in Chapters 4, 5, and 6 precisely because they are so weak.

The Axioms of $$N$$

\begin{align} &1. \left( \forall x \right) \neg Sx = 0. \\ &2. \left( \forall x \right) \left( \forall y \right) \left[ Sx = Sy \rightarrow x = y \right]. \\ &3. \left( \forall x \right) x + 0 = x. \\ &4. \left( \forall x \right) \left( \forall y \right) x + Sy = S \left( x + y \right). \\ &5. \left( \forall x \right) x \cdot 0 = 0. \\ &6. \left( \forall x \right) \left( \forall y \right) x \cdot Sy = \left( x \cdot y \right) + x. \\ &7. \left( \forall x \right) xE0 = S0. \\ &8. \left( \forall x \right) \left( \forall y \right) xE \left( Sy \right) = \left( xEy \right) \cdot x. \\ &9. \left( \forall x \right) \neg x < 0. \\ &10. \left( \forall x \right) \left( \forall y \right) \left[ x < Sy \leftrightarrow \left( x < y \lor x = y \right) \right].\\ &11. \left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right]. \end{align}

Although we have just claimed that $$N$$ is a weak set of axioms, let us show that $$N$$ is strong enough to prove some of the basic facts about the relations and functions on the natural numbers. For the following discussion, if $$a$$ is a natural number, let $$\overline{a}$$ be the $$\mathcal{L}_{NT}$$-term $$SSS \cdots S0$$ (a $$S$$'s). So $$\overline{a}$$ is the canonical term of the language that is intended to refer to the natural number $$a$$.

Lemma 2.8.4. For natural numbers $$a$$ and $$b$$:

1. If $$a = b$$, then $$N \vdash \overline{a} = \overline{b}$$.
2. If $$a \neq b$$, then $$N \vdash \overline{a} \neq \overline{b}$$.
3. If $$a < b$$, then $$N \vdash \overline{a} < \overline{b}$$.
4. If $$a \nless b$$, then $$N \vdash \overline{a} \nless \overline{b}$$.
5. $$N \vdash \overline{a} + \overline{b} = \overline{a + b}$$
6. $$N \vdash \overline{a} \cdot \overline{b} = \overline{a \cdot b}$$
7. $$N \vdash \overline{a} E \overline{b} = \overline{a^b}$$

Proof. Let us begin with (1), and let us work rather carefully. Notice that the theorem is saying that if the number $$a$$ is equal to the number $$b$$, then there is a deduction from the axioms in $$N$$ of the formula

$SS \cdots S0 \: \left( aS \text{'s} \right) = SS \cdots S0 \: \left( bS \text{'s} \right).$

We work by induction on $$a$$ (and $$b$$, since $$a = b$$). So, first assume that $$a = b = 0$$. Here is the needed deduction in $$N$$:

$\begin{array}{lr} \vdots & \text{Deduction of} \: \left( \forall x \right) x = x \: \text{(see Lemma 2.7.2)} \\ \left( \forall x \right) x = x & \\ \left( \forall x \right) x = x \rightarrow 0 = 0 & \text{(Q1)} \\ 0 = 0 & \text{(PC)} \end{array}$

Now, what if $$a = b$$ and $$a$$ and $$b$$ are greater than 0? Then certainly $$a - 1$$ and $$b - 1$$ are equal, and by the inductive hypothesis there is a deduction of $$SS \cdots S0 \: \left( \left( a - 1 \right) S \text{'s} \right) = SS \cdots S0 \: \left( \left( b - 1 \right) S \text{'s} \right)$$. If we follow that deduction with a use of axiom (E2): $$x = y \rightarrow Sx = Sy$$, and then (PC) gives us $$SS \cdots S0 \: \left( a S \text{'s} \right) = SS \cdots S0 \: \left( b S \text{'s} \right)$$, as needed. Write out the details of the end of this deduction. It is a little trickier than we have made it sound when you actually have to use (Q1) to do the substitution. This finishes the inductive step of the proof, so (1) is established. (Alternatively, you can establish (1) using the axiom (E1) and several applications of (E2), but we thought you should see the inductive proof for practice.)

Looking at (2), suppose that $$a \neq b$$. If one of $$a$$ or $$b$$ is 0, then $$\neg \overline{a} = \overline{b}$$ follows quickly from Axiom N1 and the fact that $$N$$ proves that $$=$$ is an equivalence relation. If neither $$a$$ nor $$b$$ is 0, we proceed by induction on the smaller of $$a$$, $$b$$. Since $$a - 1 \neq b - 1$$, by the inductive hypothesis, $$N \vdash \neg \overline{a - 1} = \overline{b - 1}$$. Then by Axiom N2, $$N \vdash \neg S \overline{(a - 1)} = S \overline{(b -1)}$$. In other words, $$N \vdash \neg \overline{a} = \overline{b}$$, as $$S \overline{(a - 1)}$$ is typographically equivalent to $$\overline{a}$$ and $$S \overline{(b - 1)}$$ is typographically equivalent to $$\overline{b}$$.

For (3), we use induction on $$b$$. As $$a < b$$, we know that $$b \neq 0$$ and we know that $$a < b - 1$$ or $$a = b - 1$$. So either

$N \vdash \overline{a} < \overline{b - 1} \: \text{(by the inductive hypothesis)}$

or

$N \vdash \overline{a} = \overline{b - 1} \: \text{(by (1))}.$

So

$N \vdash \left( \overline{a} < \overline{b - 1} \lor \overline{a} = \overline{b - 1} \right).$

But then by Axiom N10, $$N \vdash \overline{a} < S \overline{(b - 1)}$$, which is exactly the same as $$N \vdash \overline{a} < \overline{b}$$.

We will now discuss (5), leaving (4), (6), and (7) to the exercises. We prove (5) by induction on $$b$$. If $$b = 0$$, then $$\overline{a + b} : \equiv \overline{a + 0} : \equiv \overline{a}$$. So Axiom N3 tells us that $$N \vdash \overline{a} + \overline{b} = \overline{a}$$.

For the inductive step, if $$b = c + 1$$, then $$\overline{a} + \overline{b} : \equiv \overline{a} + S \left( \overline{c} \right)$$. So Axiom N4 tells us that

$N \vdash \overline{a} + \overline{b} = S \left( \overline{a} + \overline{c} \right).$

Since $$N \vdash \overline{a} + \overline{c} = \overline{a + c}$$ by the inductive hypothesis, the equality axioms tell us that $$N \vdash S \left( \overline{a} + \overline{c} \right) = S \overline{(a + c)}$$. But $$S \overline{(a + c)}$$ is $$\overline{a + c + 1}$$, which is $$\overline{a + b}$$. Since we know (by Theorem 2.7.1) that $$N \vdash$$ "equality is transitive", $$N \vdash \overline{a} + \overline{b} = \overline{a + b}$$.

## Exercises

1. This problem is in the setting of Example 2.8.1. Exactly one of the following two statements is in the collection of nonlogical axioms of that example. Figure out which one it is, and why.
(a) $$\left( \forall x \right) \left( 17 + 42 \right) \cdot x = 17 \cdot x \oplus 42 \cdot x$$.
(b) $$\left( \forall x \right) 59 \cdot x = 17 \cdot x \oplus 42 \cdot x$$.
Now fix up the presentation of the axioms for a vector space. You may need to redefine the language, or you may be able to take what is presented in Example 2.8.1 and fix it up.
2. For each of the following structures, decide whether or not it satisfies all of the axioms of Example 2.8.2. If the structure is not a dense linear order without endpoints, point out which of the axioms the structure fails to satisfy.
(a) The structure $$\left( \mathbb{N}, < \right)$$, the natural numbers with the usual less than relation.
(b) The structure $$\left( \mathbb{Z}, < \right)$$, the integers with the usual less than relation.
(c) The structure $$\left( \mathbb{Q}, < \right)$$, the set of rational numbers with the usual less than relation.
(d) The structure $$\left( \mathbb{R}, < \right)$$, the real numbers with the usual less than relation.
(e) The structure $$\left( \mathbb{C}, < \right)$$, the complex numbers with the relation $$<$$ defined by:
$a + b i < c + d i \text { if } \text { and only } \text { if } \left( a ^ { 2 } + b ^ { 2 } \right) < \left( c ^ { 2 } + d ^ { 2 } \right).$
3. Write out the axioms for group theory. If you do not know the axioms of group theory, go to the library and check out any book with the phrase "abstract algebra", "modern algebra", or "group theory" in the title. Then check the index under "group". Specify your language carefully and then writing out the axioms should be easy.
4. In this exercise you are asked to write up some of the axioms of Zermelo-Fraenkel set theory, also known as ZF. The language of set theory consists of a single binary relation symbol, $$\in$$, that is intended to represent the relation "is an element of". So the formula $$x \in y$$ will usually be interpreted as meaning that the set $$x$$ is an element of the set $$y$$. Here are English versions of some of the axioms of ZF. Write them up formally as sentences in the language of set theory.
The Axiom of Extensionality: Two sets are equal if and only if they have the same elements.
The Null Set Axiom: There is a set with no elements.
The Pair Set Axiom: If $$a$$ and $$b$$ are sets, then there is a set whose only elements are $$a$$ and $$b$$.
The Axiom of Union: If $$a$$ is a set, then there is a set consisting of exactly the elements of the elements of $$a$$. [Query: Can you figure out why this is called the axiom of union? Write up an example, where $$a$$ is a set of three sets and each of those three sets has two elements. What does the set whose existence is guaranteed by this axiom look like?]
The Power Set Axiom: If $$a$$ is a set, then there is a set consisting of all of the subsets of $$a$$. [Suggestion: For this axiom it might be nice to define $$\subseteq$$ by saying that $$x \subseteq y$$ is shorthand for (some nice formula with $$x$$ and $$y$$ free in the language of set theory).]
5. Complete the proof of Lemma 2.8.4.
6. Lemma 2.8.4(2) states that there is a deduction in $$N$$ of the sentence $$\neg \left( = S0SS0 \right)$$. Find a deduction in $$N$$ of this sentence.
7. This problem is just to give you a hint of how little we can prove using the axiom system $$N$$. Suppose that we wanted to prove that $$N \nvdash \neg x < x$$. It makes sense (and is a consequence of the Soundness Theorem, Theorem 2.5.3) that one way to go about this would be to construct an $$\mathcal{L}_{NT}$$-structure $$\mathfrak{A}$$ in which all of the axioms of $$N$$ are true but $$\left( \forall x \right) \neg x < x$$ is not true. Do so. We would suggest that you take as your universe the set
$A = \{ 0,1,2,3 , \ldots \} \cup \{ a \},$
where $$a$$ is the letter $$a$$ and not a natural number. You need to define the functions $$S^\mathfrak{A}$$, $$+^\mathfrak{A}$$, etc., and the relation $$<^\mathfrak{A}$$. Don't do anything too strange for the natural numbers, but make sure that $$a <^\mathfrak{A} a$$. Check that the axioms of $$N$$ are true in the structure $$\mathfrak{A}$$, and you're finished!
8. Using more or less the same technique as in Exercise 7, show that $$N$$ does not prove that addition is commutative.