We will define our formal systems and write our proofs in the language of mathematics. In this section, we give an overview of the major building blocks of this language. These will be defined more rigorously as they come up in actual formal systems.
One of the first things we learn as children is how to name things. In mathematics, the names we give to our ideas and structures are strings or symbols we will call identifiers. Whenever we define a formal system, we can specify which strings and symbols are the identifiers in that system. Identifiers in mathematics come in two flavors, constants and variables.
A constant can be thought of as an identifier that names a fixed, specific mathematical entity. Common examples of constants you have encountered in previous math courses like calculus are things like $7$, $\pi$, $\ln$, $\cos$, $+$, and $=$. They name a particular number or function or relation.
A variable, on the other hand, can be thought of as a name for an unspecified individual mathematical entity, usually of a certain type. The most common identifiers used for this purpose in mathematics are a single lower case letter, upper case letter, or Greek letter, such as $x$, $P$, or $\alpha$.
In this course, identifiers can be any case sensitive finite sequence of alphanumeric characters and mathematical symbols, excluding punctuation like commas, periods, spaces, and brackets, and a few reserved words that we will encounter later.
Identifiers can also be combined in various ways to form larger mathematical expressions. A single identifier is called an atomic expression. A mathematical expression comprised of more than one identifier is called a compound expression. The same identifier might appear more than once in a compound expression. Like variables, expressions will frequently represent a mathematical object of a certain type.
For example, you may have seen expressions such as $y=x+1$. This compound expression contains two variables, $x$ and $y$, and three constants, $=$, $+$, and $1$.
In addition to indentifiers, mathematical expressions often use punctuation and formatting to form expressions that are easier to read, or to distinguish or identify two expressions. Common punctuations used in mathematical expressions include parentheses, elipses, periods, and commas. Common formatting used includes superscripts, subscripts, and arranging expressions into columns or grids in various ways. For example, we use expressions like $$\binom{n}{n}x^n+\binom{n}{n-1}x^{n-1}+\cdots+\binom{n}{0}$$ $$a_0,a_1,\ldots,a_n$$ $$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$
Mathematical expressions can also contain English words in addition to symbols. For example, you may have seen piecewise functions defined by an expression like $$T(n)=\begin{cases} \frac{n}{2} & \text{if $n$ is even} \\ \frac{3n+1}{2} & \text{otherwise} \end{cases}$$ Indeed, many mathematical expressions will consist entirely of English words. For example,“The hypotenuse is the longest side of a right triangle.” is one such expression.
As we embark on our journey to build mathematics from the ground up, we will say exactly which mathematical expressions constitute the statements in the formal systems we define, which will be a subset of the more general language of mathematics we are describing here.
Generally speaking, statements can be thought of as mathematical expressions or sentences which can be said to be true or false – expressions which if you said them in a courtroom during a trial, a lawyer could accuse you of lying or telling the truth. For example, expressions like $2<3$, $1+1=3$, and “Every set is a subset of itself.” are usually statements in mathematics because they are either true or false, whereas expressions like $x^2+1$, $\frac{1}{2}$, and $\triangle ABC$ usually are not. Notice, however, that we do not need to know whether a statement is true or false to know that it is a statement. For example, $x<2$ is true if $x$ represents the number $1$ but false if it represents the number $2$. Either way, we can say that the expression $x<2$ is either true or false, and therefore can be considered a statement.
Despite the wide variety of notation used in mathematics, all compound expressions can be constructed by applying one expression to zero or more other expressions. For example, we can apply the atomic symbol $\gcd$ to the atomic symbols $x$ and $y$ to obtain the compound expression $\gcd(x,y)$. This process of creating a new compound expression from existing atomic or compound expressions is called application (or function application). The expression being applied is called the operator and the expressions it is being applied to are called the arguments.
There are several common ways to denote compound expressions.
There are many other ways we can format compound expressions for specific operators, but these three are the most common.
Compound Expression Notation
| Expression | Prefix | Infix | List |
|---|---|---|---|
| $f(x)$ | $f(x)$ | – | $(f\xs x)$ |
| $f(x,y)$ | $f(x,y)$ | $x\mathbin{f}y$ | $(f\xs x\xs y)$ |
| $f(x(y))$ | $f(x(y))$ | – | $(f\xs( x\xs y)))$ |
| $f(x,y,z)$ | $f(x,y,z)$ | $x\mathbin{f}y\mathbin{f}z$ | $(f \xs x \xs y \xs z)$ |
| $(f+g)(x-h)$ | $(\xop{+}(f,g))(\xop{-}(x,h))$ | – | $((\xop{+}\xs f\xs \xs g)\xs \xs (\xop{-}\xs x\xs \xs h))$ |
| $x_1$ | $x(1)$ | – | $(x\xs 1)$ |
| $1+1$ | $\xop{+}(1,1)$ | $1+1$ | $(\xop{+}\xs 1\xs \xs 1)$ |
| $1+2+3$ | $\xop{+}(1,2,3)$ | $1+2+3$ | $(\xop{+}\xs 1\xs 2\xs 3)$ |
| $(1+2)+3$ | $\xop{+}(\xop{+}(1,2),3)$ | $(1+2)+3$ | $(\xop{+}\xs (\xop{+}\xs 1\xs 2)\xs 3)$ |
| $x^2$ | $\text{^}(x,2)$ | $x\text{^}2$ | $(\text{^}\xs x\xs \xs 2)$ |
| $\gcd(4,6)$ | $\gcd(4,6)$ | $4\mathbin{\gcd}6$ | $(\xop{gcd}\xs 4\xs 6)$ |
| $3\cdot x=1$ | $\xop{=}(\cdot(3,x),1)$ | $(3\cdot x) = 1 $ | $(\xop{=}\xs( \cdot\xs 3\xs x)\xs 1)$ |
| Gina loves mocha | loves(Gina , mocha) | Gina loves mocha | (loves Gina mocha) |
From now on, when we use the term expression we will mean either an identifier or a compound expression formed by applying an expression to one or more expressions via function application, as illustrated in the table. Notice that the exponentiation operator $\text{^}$ is usually omitted and formatted with the second argument as a superscript in traditional math notation. Similarly, is also commonplace in mathematics to omit explicit multiplication symbols in algebraic expressions like $3x^3+2x-1$, but in this course we will always write it explicitly, like $3\cdot x^3+2\cdot x-1$.
Prefix and list notation include parentheses, so their meaning is unambiguous, but compound expressions that combine different infix operators sometimes require parentheses to disambiguate them. For example, if $\star$ and $\diamond$ are infix operators and we write $a \star b \diamond c$ does that mean $(a \star b) \diamond c$ or $a \star (b \diamond c)$. In list notation, the former is $(\diamond\xs (\star\xs a\xs b)\xs c)$ whereas the latter is $(\star \xs a\xs (\diamond\xs b\xs c))$. In such a situation, we can use parentheses to disambiguate which one we mean.
We can eliminate extra parentheses and reduce clutter by assigning precedence to the operators. In the example $a \star b \diamond c$ if we say that $\star$ has higher precedence than $\diamond$ we are asserting that this expression should be interpreted as $(a \star b) \diamond c$. If we say that $\diamond$ has higher precedence than $\star$ then it would be interpreted as $a \star (b \diamond c)$. If the operators have the same precedence, then the expression is ambiguous and therefore syntactically invalid.
Some operators have universally accepted precedence, for example in elementary arithmetic, multiplication $\cdot$ has higher precedence than addition $+$, so that $3\cdot x+1$ is interpreted as $(3\cdot x)+1$, not $3\cdot(x+1)$. Other choices of precedence are not as universally accepted and may vary from textbook to textbook. In this course we will use the following precedence for the operators.
| Precedence (high to low) |
|---|
| parentheses $(\xs)$, tuples $\langle\xs \rangle$, equivalence classes $[\xs ]$, sets $\{\xs \}$, symbols, numbers |
| exponentials $\left(x^2\right)$ |
| function application $\left(f_0(x,y)(z)\right)$ |
| postfix ($n!$, $f’$) |
| abstract infix operators ($\star$, $\oplus$, $\otimes$, $\odot$) |
| negation ($-x$), reciprocal ($1/2$) |
| product ($2\cdot x$) |
| summation $\left(\sum_{k=0}^n f(k)\right)$ |
| indexed union and intersection $\left(\bigcup_{i \in \mathbb{N}} A_{i}\right)$ |
| sum ($x+y-1$) |
| choose $\binom{m+n}{m}$ |
| composition $\left(g\circ f\right)$ |
| intersection ($A\cap B$) |
| union ($A\cup B$) |
| cartesian product ($A\times B$) |
| relative complement ($A\setminus B$) |
| relations ($f:A\to B$, $\underset{m}{\equiv}$, $\subseteq$, $\in$, $\notin$, $\mid$, $\leq$, $\lt$, $=$, $\neq$, $\sim$, ‘is’, ‘loves’) |
| not ($\neg$) |
| and ($\wedge$) |
| or ($\vee$) |
| implies ($\Rightarrow$) |
| iff ($\Leftrightarrow$) |
| binding ($x.P(x)$) |
| quantified ($\forall x.P(x)$) |
| declarations (‘Declare’, ‘Let’, ‘for some’) |
Note that subtraction is treated as addition of the negative and division as multiplication of the reciprocal, so that $x-2$ means the same thing as $x+(-2)$ (i.e., $(\xop{+}\xs x\xs (\xop{-}\xs 2))$ in list notation), and $x/2$ means the same thing as $(\xop{\cdot}\xs x\xs (\xop{/}\xs 2))$ in list notation. Consecutive, unparenthesized function applications are applied left to right, so that e.g., $f(x)(y)(z)$ is interpreted as $(((f\xs x)\xs y)\xs z)$ in list notation.
The statements in the formal systems used in mathematics generally consists of some syntactically well-defined collection of expressions and sentences. While some statements and theorems might consist of a single expression like $n+0=n$, much of everyday mathematics is expressed with statements and theorems that are comprised of multiple expressions arranged in nested structures according to a grammar involving keywords and punctuation.
Indeed, we frequently organize the sentences in a book by collecting them together into nested hierarchical structures called chapters, sections, subsections, and so on. Similarly, statements in mathematics are also frequently organized by placing them into nested hierarchical structures called environments. Like other books, a math textbook can have environments such as chapters, sections, subsections, but will also frequently contain other more specialized mathematical environments, such as theorems, proofs, subproofs, definitions, declarations, examples, and many others.
Example . Consider the following theorem that might be found in any calculus textbook.
Theorem (Fundamental Theorem of Calculus) If $f$ is continuous on $[a,b]$ and $F:[a,b]\to\RR$ is defined by $$F(x)=\int_a^x f(t)\,dt$$ then $F$ is differentiable on $(a,b)$, and $F’(x)=f(x)$.
Notice that this theorem statement is an English sentence, comprised of multiple expressions arranged inside the enclosing box according to a certain grammar. The grey box containing the theorem is an example of an environment.
Environments serve two main purposes. First, as the name suggests, an environment defines a scope that delineates where certain assumptions or definitions are assumed to be under consideration. In the previous example, the assumption that $f$ is continuous is restricted to the inside of the theorem environment that contains it. Similarly, if the author of a book says in Chapter 1, “In this chapter we will assume that $n$ is a positive integer.”, the reader would not normally assume that the same assumption about $n$ holds in Chapter 2. So the Chapter itself is acting as an environment in that situation.
Second, environments can also be statements in or about the formal system itself. The Fundamental Theorem of Calculus stated above is a theorem of calculus, and thus a statement in that sense.
We will have four kinds of environments - Theorems, Proofs, Rules, and Premises (capitalized when we want to refer to an environment of that type). A Proof environment that is inside of another environment is called a Subproof environment. Rather than lableing them, we will distinguish the four environment types visually by their background color (Rule – blue, Premise – cream, Theorem – grey, Proof – white) as shown.
Rule
Premise
Theorem
Proof/Subproof
All environments can contain Premise and Subproof environments and expressions (nested to any depth). We will see how the four environment types differ later on. For now we are just adding them to our language.
In the toy proof systems we encountered in Chapter 2, the rules were
not statements in the system. For example, Rule 1 in the
circle-dot system is not a circle-dot string, and
Spin Left is not a sequence of colors in the Scrambler
system. The conditional theorem stated and proved in
Example 2.4 is not a
theorem in the formal system, but rather a fact about that
formal system. Namely, the system has the property that if
math were a theorem then cool would be a
theorem, too. Its proof shows why that claim is objectively valid.
Indeed the proof shows something more general - that the Theorem holds
in any formal system that satisfies Rule 1 and has
math as a theorem.
From this perspective we can view rules as assumptions about the formal system we are interested in, and Theorems as facts about any formal system satisfying those assumptions. In order to expand our language to support such Theorems, we need to add the concept of an assumption.
Definition . Any expression or environment can be declared to be an assumption. An expression or environment that is not declared to be an assumption is said to be a claim.
Expressions prefixed with one of the words
Assume, Suppose, If,
Given, From, or Define (case
insensitive) are assumptions. All other expressions are claims.
Environments Rule and Premise are assumptions. The Proof/Subproof and Premise environments are claims.
Naturally the terms Assume, Suppose,
If, Given, From, or
Define (case insensitive) are only used to indicate that
an expression is an assumption. They cannot be used as identifiers
themselves either alone or as part of a compound expression.
We will extend our Language of Mathematics a few more times as we introduce a a few additional concepts, but we can already do a lot with what we have defined so far, as we will see in the next chapter.
We will write all of our formal proofs in a single Proof environment which we will refer to as a document. This will have many different kinds of content.
Since we want our proofs to both be objectively verifiable and expository, we will have two kinds of content in our document - meaningful and expository. Meaningful content will contribute to the objective validity of the document. The expository content is purely for commentary and communication that can help the reader of our document understand the meaningful aspects. Meaningful expressions will be written in a gold font, whereas expository comments will be written in ordinary black font. All environments are meaningful.
Example . Here is an example document (a proof environment) containing some meaningful expressions and expository ones.
This black text is just commmentary but expressions in gold text such as Gina loves mocha or $1+1=2$ are meaningful.
From now on, whenever we refer to assumptions, claims, statements, expressions or environments, we are only referring to meaningful content, not anything said in exposition.
Claims in a document can be marked with a green check ( ) to indicate that they they must be valid in any formal system that satisfies what has already been said up to that point. Claims which cannot be determined to be valid are said to be indeterminate, and marked with a yellow question mark ( ). Thus the expression Gina loves mocha is marked as valid, while Gina loves mocha is marked as indeterminate.
Complete the following table.
| Prefix | Infix | List |
|---|---|---|
| $\cos(x)$ | ||
| $(+\xs( \text{^}\xs x\xs 2)\xs x\xs 1)$ | ||
| $f$ is continuous | ||
| $x<0$ | ||
| $f(g(x,y),0)$ | ||
| $(=\xs( \text{-}\xs( \text{^}\xs x\xs 2)\xs 1)\xs( \cdot\xs( \text{-}\xs x\xs 1)\xs( +\xs x\xs 1)))$ | ||
| (is math fun) | ||
| $(f(x))(y)$ | ||
| $x = y = 0$ |
Write down three famous mathematical equations or inequalities you know, and write each one in (a) standard math formatting, (b) prefix notation, (c) infix notation, and (d) applicative list notation.
Fully parenthesize each of the following expressions according to the precedence of operations, and express each one in list notation.
