Predicates, Numbers, and Sets

Predicate Logic

We realise that propositional logic is not enough. If we know that “all men are mortal” and “Socrates is a man”, it ought to follow that “Socrates is mortal.” But propositional logic cannot reach this conclusion: it treats each sentence as an indivisible whole and cannot look inside to see the relationship between the object (Socrates), the property (being a man), and the consequence (being mortal).

To see the problem more concretely, consider the following mathematical argument:

Every prime number greater than $2$ is odd. The number $7$ is a prime number greater than $2$. Therefore, $7$ is odd.

This looks like a straightforward application of modus ponens (Lesson 1). Yet propositional logic cannot carry it out: there is no way to symbolise “Every prime number greater than $2$ is odd” as a conditional $p \to q$ whose premise $p$ is “The number $7$ is a prime number greater than $2$.” The first sentence speaks about all primes; the second speaks about a specific number. Propositional logic has no mechanism to connect the two.

What is missing is the ability to distinguish the object of our speech from the description we make about it. To overcome this, we introduce predicate logic, which allows us to reason about objects and their properties.

Variables and Predicates

Recall that a variable is a symbol standing in for an object that has not yet been specified, and a term is a symbol denoting an object (Lesson 1). Specific terms such as the natural number $5$ or the constant $\pi$ are called constants; variables are terms whose value has not been determined. A term on its own does not form a complete sentence and has no truth value.

We can attach a description to a variable: write $\text{man}(x)$ to say ”$x$ is a man”, or $x > 3$ to say ”$x$ is a number larger than $3$.” These expressions are not propositions (Definition 1), because their truth value depends on what $x$ actually is.

If $P$ is the monadic predicate for being prime and $7$ is a term, then $P(7)$ is the proposition ”$7$ is prime.” If $G$ is the dyadic predicate for “is greater than”, then $G(\pi, 3)$ is the proposition ”$\pi$ is greater than $3$.” These are the atomic propositions of first-order logic.

A predicate’s variables take values in a domain $U$, called the universe of discourse. In the previous example, $U$ is the integers. Once values from $U$ are substituted, the predicate becomes a proposition with truth value $\top$ or $\bot$. Hence the logical connectives from Lesson 1 apply directly.

More generally, we can build new predicates out of old ones using connectives. Expressions constructed from predicates and logical connectives that still contain free variables are called propositional functions.

Sets and Numbers

We have been throwing around numbers and their collections somewhat loosely. In Lesson 1, Example 1 asserted "$2 + 3 = 5$" and Example 1 item 3 stated “For any real number $x$, $x^2 \geq 0$”, while the truth tables themselves are indexed by rows we count with integers. Earlier we had hints to specific collections of numbers. It is time to properly introduce them.

Fundamental to mathematics is the notion of a set. We will study sets in great detail in later lessons, but from this point onwards you will find them in every chapter of this textbook, so we take some time to think about them now. We will not treat sets formally at this stage; for now, the following definition will suffice.

The sets of concern to us first and foremost are the number sets: sets whose elements are particular types of number. At this introductory level, many details will be temporarily swept under the rug; we will work at a level of precision which is appropriate for our current stage, but still allows us to develop a reasonable amount of intuition.

Later on, if time permits, we plan to cover the construction of the number systems from first principles. For now, we start with the simple build-up.

Numbers and Magnitude

The study of mathematics is built upon the study of increasing and decreasing quantities, or magnitudes, sometimes referred to as the science of quantity.

From the fruit that a person purchases at a store, to the measurement of vast interstellar distances, the concept of quantity is ubiquitous. However, we cannot quantify or determine a specific amount except by comparing it to a similar magnitude of the same kind. For instance, when enumerating fruit, we might regard the collection as a single total or distinguish them by category (apples, pears, bananas). To formalise this comparison, we require a standard.

Write the chosen unit as $u$ and the magnitude as $M$. The measured number is $n$ with $M = n u$. This is exactly the model we use on the number line: once $0$ and the unit length are fixed, each point gets the signed measure of its displacement from $0$ in that unit.

The Number Line

In order to define the number sets, we will need three things: an infinite line, a fixed point on this line, and a fixed unit of length.

So here we go. Here is an infinite line:

The arrows indicate that it is supposed to extend in both directions without end. The points on the line will represent numbers (specifically, real numbers, a misleading term that will be defined later).

Now let us fix a point on this line, and label it $0$:

This point represents the number zero; it is the point against which all other numbers will be measured. Numbers to the left of $0$ on the line are said to be negative, and those to the right are positive; $0$ itself is neither positive nor negative.

Finally, let us fix a unit of length:

This unit of length turns position into measure: each point is assigned a signed number telling how many unit lengths it lies from $0$.

We will use the number line to construct the principal number sets of interest to us: the set $\mathbb{N}$ of natural numbers, the set $\mathbb{Z}$ of integers, the set $\mathbb{Q}$ of rational numbers, and the set $\mathbb{R}$ of real numbers. Each of these sets has a different character and is used for different purposes, as we will see throughout this course.

Natural Numbers ($\mathbb{N}$)

The natural numbers are the numbers used for counting. They are the answers to questions of the form “how many”: I have three uncles, three guinea pigs, and zero cats.

The natural numbers are represented by the points on the number line which can be obtained by starting at $0$ and moving right by the unit length any number of times:

In more familiar terms, they are the non-negative whole numbers. The notation $n \in \mathbb{N}$ means that $n$ is a natural number.

Integers ($\mathbb{Z}$)

Addition combines magnitudes; its inverse takes them away. This inverse operation is called subtraction, denoted by the symbol $-$. Formally, subtraction is the inverse of addition, meaning the operation $-b$ undoes the effect of $+b$, and vice versa. This relationship is expressed by:

We can also view subtraction as finding a “missing addend.”

Our definition of subtraction has so far assumed that $a$ is larger than $b$. What about $3 - 5$? Using Definition 22, we seek a number $c$ such that $c + 5 = 3$. No such number exists among the natural numbers.

Algebra is the general theory of these operations; we establish laws and follow them. When results like $3 - 5$ cannot be interpreted with our current numbers, they force us to invent new concepts that are consistent with our laws.

Mechanically, calculating $3 - 5$ means starting at $3$ and applying the predecessor action $-1$ five times:

A step to the left from $0$ takes us off the natural number line. To resolve this, we must extend our system. A step of $-1$ from $0$ lands on a point we call negative one, or $-1$. A further step lands on $-2$.

With this, we can complete our calculation: $3 - 5 = (3 - 3) - 2 = 0 - 2 = -2$.

By extending our number line to include these new negative numbers, along with zero and the natural numbers, we form a more complete system.

The integers can be used for measuring the difference between two natural numbers. For example, suppose you have five apples and five bananas. Another person, also holding apples and bananas, wishes to trade. After the exchange, you have seven apples and only one banana. Thus you have two more apples and four fewer bananas.

Since an increment in quantity can be represented by moving to the right on the number line by the unit length, a decrement in quantity can therefore be represented by moving to the left by the unit length. Doing so gives rise to the integers:

The notation $n \in \mathbb{Z}$ means that $n$ is an integer.

Rational Numbers ($\mathbb{Q}$)

Just as subtraction forced us beyond the natural numbers, division now forces us beyond the integers. But before we can discuss division, we need its prerequisite.

Another standard notation for division is the fraction bar, where $a \div b$ is written as $\frac{a}{b}$. This notation is familiar from arithmetic, where $\frac{a}{b}$ represents $a$ of the $b$-th parts of a unit. We can see that these two ideas are the same: if we take $b$ copies of the quantity $\frac{a}{b}$, we have $b \cdot \frac{a}{b}$, which by the arithmetical definition is $a$. Since this matches our algebraic definition (Definition 26), the notations are equivalent and can be used interchangeably.

The motivation for the next number system is that the result of dividing one integer by another is not necessarily another integer. However, the result is sometimes an integer; for example, six apples can be divided between three people, and each person receives an integral number of apples.

This makes division interesting: how can we measure the failure of one integer’s divisibility by another? How can we deduce when one integer is divisible by another? What is the structure of the set of integers when viewed through the lens of division? This set of questions is so important it spans a large portion of the second half of this course, in something called number theory.

But for now, we simply need a system of numbers that can express the result of any division (except by zero). Bored of eating apples and bananas, suppose you buy a pizza which is divided into eight slices. A friend and you decide to share it. You eat three slices and your friend eats five. Unfortunately, we cannot represent the proportion of the pizza each of you has eaten using natural numbers or integers. However, we are not far off: we can count the number of equal parts the pizza was split into, and of those parts, we can count how many we had. On the number line, this is represented by splitting the unit line segment from $0$ to $1$ into eight equal pieces, and proceeding from there. This kind of procedure gives rise to the rational numbers.

The notation $q \in \mathbb{Q}$ means that $q$ is a rational number.

Real Numbers ($\mathbb{R}$)

Quantity and change can be measured in the abstract using real numbers.

The real numbers are central to real analysis, a branch of mathematics introduced later in this course. They turn the rationals into a continuum by “filling in the gaps”: they have the property of completeness, meaning that if a quantity can be approximated with arbitrary precision by real numbers, then that quantity is itself a real number. We will state a fully formal definition later.

We can define the basic arithmetic operations (addition, subtraction, multiplication and division) on the real numbers, and a notion of ordering, in terms of the infinite number line.

Ordering. A real number $a$ is less than a real number $b$, written $a < b$, if $a$ lies to the left of $b$ on the number line. The usual conventions for the symbols $\leq$ apply: $a \leq b$ means that either $a < b$ or $a = b$.

Addition. Suppose we want to add a real number $a$ to a real number $b$. We translate $a$ by $b$ units to the right; if $b < 0$ then this amounts to translating $a$ by an equivalent number of units to the left. Concretely, take two copies of the number line, one above the other, with the same choice of unit length. Move the $0$ of the lower number line beneath the point $a$ of the upper number line. Then $a + b$ is the point on the upper number line lying above the point $b$ of the lower number line.

Multiplication. Suppose we want to multiply a real number $a$ by a real number $b$. We scale the number line, and perhaps reflect it. Concretely, take two copies of the number line, one above the other. Align the $0$ points on both number lines, and stretch the lower number line evenly until the point $1$ on the lower number line is below the point $a$ on the upper number line (if $a < 0$, the number line must be reflected for this to work). Then $a \cdot b$ is the point on the upper number line lying above $b$ on the lower number line.

The real numbers satisfy a collection of axioms that characterise them completely. We state these now for reference; their consequences will be explored throughout the course.

Terms such as “field”, “totally ordered field”, “least upper bound”, and “complete” are signposts for structure that we will define rigorously later. In this chapter, treat (A1)-(A11) as the operational rules for calculation and proof.

(A1) Addition commutes: $a + b = b + a$ for all $a, b \in \mathbb{R}$.

(A2) Addition is associative: $(a + b) + c = a + (b + c)$ for all $a, b, c \in \mathbb{R}$.

(A3) Zero is the additive identity: $a + 0 = 0 + a = a$ for all $a \in \mathbb{R}$.

(A4) Additive inverses: for each $a \in \mathbb{R}$ there exists $-a \in \mathbb{R}$ such that $a + (-a) = 0$.

(A5) Multiplication commutes: $ab = ba$ for all $a, b \in \mathbb{R}$.

(A6) Multiplication is associative: $(ab)c = a(bc)$ for all $a, b, c \in \mathbb{R}$.

(A7) One is the multiplicative identity: $a \cdot 1 = a$ for all $a \in \mathbb{R}$.

(A8) Multiplicative inverses for nonzero elements: for each $a \neq 0 \in \mathbb{R}$ there exists $\frac{1}{a} \in \mathbb{R}$ such that $a \cdot \frac{1}{a} = 1$.

(A9) Distributive properties: $a(b + c) = ab + ac$ and $(a + b)c = ac + bc$ for all $a, b, c \in \mathbb{R}$.

(A10) Totally ordered field: for $a, b \in \mathbb{R}$:

• (i) Antisymmetry: if $a \leq b$ and $b \leq a$ then $a = b$.
• (ii) Transitivity: if $a \leq b$ and $b \leq c$ then $a \leq c$.
• (iii) Totality: $a \leq b$ or $b \leq a$.

(A11) Least upper bound property: every nonempty subset of $\mathbb{R}$ that has an upper bound has a least upper bound. This makes the real numbers complete.

Apparent obvious facts about numbers require the axioms stated above, and the proofs are worth seeing once: they practise reasoning from first principles and build a toolkit for the chapters ahead.

Uniqueness of zero. Axiom (A3) says that $0$ is an additive identity. The following argument shows it is the only one. Suppose $a + x = a$ for some number $a$. Then

All four properties (A1)–(A4) were needed to justify what amounts to “subtracting $a$ from both sides.” A similar argument shows that additive inverses are unique: if $a + x = 0$ then $x = -a$.

Multiplication by zero. Why is $a \cdot 0 = 0$? The number $0$ appears only in (A3) and (A4), which concern addition. Without (A9), the axioms say nothing about multiplying by $0$. Since $0 + 0 = 0$ by (A3), distributivity gives

Adding $-(a \cdot 0)$ to both sides yields $a \cdot 0 = 0$.

The sign rules. Why is the product of two negative numbers positive? This is not a convention; (A1)–(A9) force it. First, $(-a) \cdot b = -(a \cdot b)$:

so $(-a) \cdot b$ is the additive inverse of $a \cdot b$. With this in hand:

Adding $ab$ to both sides: $(-a)(-b) = ab$. The product of two negative numbers is positive not because we decided it should be, but because (A1)–(A9) leave no alternative.

The zero-product property. If $ab = 0$ and $a \neq 0$, then $b = 0$:

by (A6), (A8), and (A7) in turn. Equivalently: if $ab = 0$ then $a = 0$ or $b = 0$. This is the workhorse behind solving polynomial equations by factoring. If $(x - 1)(x - 2) = 0$, then $x - 1 = 0$ or $x - 2 = 0$, so $x = 1$ or $x = 2$. The factorisation $x^2 - 3x + 2 = (x - 1)(x - 2)$ is itself a triple application of (A9):

Ordering and squares. The phrase “totally ordered field” in (A10) bundles in two requirements linking the ordering to arithmetic: if $a \leqslant b$ then $a + c \leqslant b + c$ for all $c$; and if $a, b \geqslant 0$ then $ab \geqslant 0$. Together with the sign rules these yield: if $a < 0$ and $b < 0$ then $ab > 0$, since $(-a)(-b) = ab$ and $-a, -b > 0$.

In particular, $a^2 > 0$ whenever $a \neq 0$, whether $a$ is positive or negative. Since $1 = 1^2$ and $1 \neq 0$ (if $1 = 0$ then $a = a \cdot 1 = a \cdot 0 = 0$ for every $a$, collapsing the number system to a single element), we obtain $1 > 0$.

Irrational Numbers

Before we can talk about irrational numbers, we should say what they are.

Unlike $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$, there is no standard single letter denoting the irrational numbers. However, once we develop the language of sets more fully, we will be able to write the collection of irrational numbers as $\mathbb{R} \setminus \mathbb{Q}$ (read: “the reals set minus the rationals”).

That such numbers exist at all is not obvious. Consider an isosceles right-angled triangle with both shorter sides of length $1$:

By the Pythagorean theorem, the hypotenuse has length $\sqrt{1^2 + 1^2} = \sqrt{2}$. This is a perfectly concrete geometric magnitude: it is the distance between two corners of a unit square. Yet $\sqrt{2}$ is not rational. There is no fraction $\frac{a}{b}$ with $a, b \in \mathbb{Z}$ and $b \neq 0$ that equals $\sqrt{2}$ exactly.

Proving that a real number is irrational is not particularly easy, in general. The classical proof that $\sqrt{2} \notin \mathbb{Q}$ proceeds by contradiction and is one of the most celebrated arguments in all of mathematics. We will carry out this proof later. For now, the interested reader may consult the proof that $\sqrt{2}$ is irrational. Similar arguments establish the irrationality of $\sqrt{3}$, $\sqrt{5}$, and in fact $\sqrt{n}$ for any natural number $n$ that is not a perfect square.

Other important irrational numbers arise throughout mathematics: $\pi$ (the ratio of a circle’s circumference to its diameter) and $e$ (the base of the natural logarithm) are both irrational, though their proofs require substantially more machinery.

We can use the irrationality of $\sqrt{2}$ to observe something about how rational and irrational numbers interact under multiplication.

Complex Numbers ($\mathbb{C}$)

We have seen that multiplication by real numbers corresponds with scaling and reflection of the number line: scaling alone when the multiplicand is positive, and scaling with reflection when it is negative. We could alternatively interpret this reflection as a rotation by half a turn, since the effect on the number line is the same.

You might then wonder what happens if we rotate by arbitrary angles, rather than only half turns. What we end up with is a plane of numbers, not merely a line. Moreover, the rules that we expect arithmetic operations to satisfy still hold: addition corresponds with translation, and multiplication corresponds with scaling and rotation. This resulting number system is that of the complex numbers.

There is a particularly important complex number, $i$, which is the point in the complex plane exactly one unit above $0$:

Multiplication by $i$ has the effect of rotating the plane by a quarter turn anticlockwise. In particular, we have

The complex numbers have the astonishing property that square roots of all complex numbers exist, including all the real numbers.

Every complex number can be written in the form $a + bi$, where $a, b \in \mathbb{R}$. This number corresponds with the point on the complex plane obtained by moving $a$ units to the right and $b$ units up, reversing directions as usual if $a$ or $b$ is negative. Arithmetic on the complex numbers works just as with the real numbers; in particular, using the fact that $i^2 = -1$, we obtain

We will discuss complex numbers further in the portion of this course on polynomials.

Polynomials

Each of the number sets introduced above comes equipped with nicely behaving notions of addition and multiplication. Polynomials are built from these two operations.

Instead of writing out the coefficients of a polynomial each time, we may write $p(x)$ or $q(x)$. The "$(x)$" indicates that $x$ is the indeterminate of the polynomial. If $\alpha$ is a number and $p(x)$ is a polynomial in indeterminate $x$, we write $p(\alpha)$ for the result of substituting $\alpha$ for $x$ in the expression $p(x)$.

Note that, if $S$ is any of the sets $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ or $\mathbb{C}$, and $p(x)$ is a polynomial over $S$, then $p(\alpha) \in S$ for all $\alpha \in S$.

The quadratic formula tells us that the roots of the polynomial $x^2 + ax + b$, where $a, b \in \mathbb{C}$, are precisely the complex numbers

Note our avoidance of the symbol "$\pm$", which is commonly found in discussions of quadratic polynomials. The symbol "$\pm$" is dangerous because it may suppress the word “and” or the word “or”, depending on context. This kind of ambiguity is not something we will want to deal with when discussing the logical structure of a proposition (Lesson 1).

A recurring technique in mathematics is completing the square: rewriting a quadratic expression so that the indeterminate appears inside a single squared term. The key identity is

which one can verify by expanding the right-hand side. This is useful because the squared term $(x + a/2)^2$ is always non-negative, while the remaining constant $b - a^2/4$ does not depend on $x$.

The following exercise uses completing the square to classify the real roots of a quadratic polynomial entirely in terms of its coefficients.