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$.
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. 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 | Applicative |
|---|---|---|---|
| $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)$ |
| $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.
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 this statement 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. We will encounter four specific flavors of environments in the next chapter, when we discuss deduction.
Complete the following table.
| Prefix | Infix | Applicative |
|---|---|---|
| $\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.
