1  Language and logic

1.1 Mathematics is a language

Mathematics is the language of scientific model building. For example, the expression \[\begin{equation} F = ma \end{equation}\] corresponds, in the sense of Newton’s second axiom, to a theory of the motion of objects under the action of forces (Newton (1687)). Likewise, the expression \[\begin{equation} \max_{q(z)} \int q(z) \ln \left(\frac{p(y,z)}{q(z)}\right)\,dz \end{equation}\] corresponds, in the sense of variational inference, to contemporary theory about how the brain works (Friston (2005)). Mathematical symbolism serves in particular to communicate scientific insights precisely and aims to describe complex matters exactly and efficiently. As in reflective engagement with any form of language, the question “What is this supposed to mean?” therefore always remains the guiding question when working with mathematical content and symbolism.

As a language system, mathematics has a number of special features. First, its contents are often abstract. This is because mathematics strives for the broadest possible general comprehensibility and applicability. Mathematical approaches to the phenomena of the world are interested in making insights as easy as possible to transfer to other contexts. To make this possible, mathematics tries to work as precisely and understandably as possible, that is, in terms of precise concepts. It proceeds in a strictly hierarchical way, so that concepts introduced later often presuppose a good understanding of the underlying concepts introduced earlier.

The precision of mathematical language implies a high density of information. It is therefore rather sober and leaves out what is superfluous, so that, in the best case, everything in a mathematical text is relevant for communicating an idea. As recipients of mathematical texts, we perceive their information density through the high cognitive energy required when reading such a text. This high energy expenditure calls in particular for calm and slowness when reading with the aim of genuine understanding. The following quotation may serve as a guiding principle for working with mathematical texts: “A mathematical text cannot be read like a novel. One has to work through it” (Unger (2000)). After reading a short mathematical text, one should always ask critically whether one has really understood what has been read or whether further sources should be consulted to clarify the matter. It is also helpful, in the spirit of Richard Feynman’s famous quotation “What I cannot create, I do not understand”, to make one’s own notes and to reconstruct mathematical language systems oneself.

If one wants to gain access to the world of scientific model building, then it is helpful, when dealing with its mathematical expressions and symbolism, to use the same strategies as when learning a foreign language. In addition to immersing oneself in the corresponding language space, that is, constant exposure to mathematical modes of expression, this certainly includes first memorizing concepts and translating texts into everyday language. A deep and secure understanding of mathematical model building then arises in particular through the application of mathematical ways of thinking in written and spoken form.

1.2 Basic building blocks

In the following, we introduce three basic building blocks of mathematical communication that will accompany us throughout: the concepts of a definition, a theorem, and a proof.

Definition

A definition is a cornerstone of a mathematical system that is neither justified nor deductively derived within that system. Definitions can only be evaluated according to their usefulness within a mathematical system. A definition is best memorized first and questioned only once one has understood its use in application or is not convinced by it. Some relaxation and calm are generally helpful when dealing with definitions that appear complex at first sight. To indicate that we define a symbol as something, we use the notation “\(:=\)”. For example, the expression “\(a := 2\)” defines the symbol \(a\) as the number two. In this text, definitions always end with the symbol \(\bullet\).

Theorem

A theorem is a mathematical statement that can be recognized as correct (true) by means of a proof. That is, a theorem is always derived from definitions and/or other theorems. In this sense, theorems are the empirical results of mathematics. In applied, data-analytic mathematics, theorems are often helpful for calculations. It is therefore worth memorizing them, because they usually form the basis for data analysis and data interpretation. Equations often appear in theorems. These equations arise from the assumptions of the theorem. To mark equations, we use the equals sign “\(=\)”. For example, in a given context, the expression “\(a = 2\)” says that, because of certain assumptions, the variable \(a\) has the value two. In this text, theorems always end with the symbol \(\circ\).

Proof

A proof is a chain of argumentation that draws on known definitions and theorems to establish the correctness (truth) of a theorem. Short proofs often contribute to understanding a theorem. Long proofs tend to do so less. Proofs are therefore, in particular, answers to the question why a mathematical statement holds (“Why is this so?”). Proofs are not memorized. When proofs are short, it is sensible to work through them, because they usually repeat content that is assumed to be known. When they are long, it is more sensible to skip them at first so as not to get lost in details and lose the main path through the mathematical structure. In this text, proofs always end with the symbol \(\Box\).

In addition to definitions, theorems, and proofs, mathematical texts contain other typical building blocks, such as axioms, lemmas, corollaries, and conjectures. We will not use these terms and therefore give only a brief overview of them.

  • Axioms are unproved fundamental assumptions in the sense that they serve as starting points for building mathematical systems. The transition between definitions and axioms is often fluid. Because we will not work at a particularly deep mathematical level, we prefer the term definition in almost all cases.
  • A lemma is an “auxiliary theorem”, that is, a mathematical statement that is proved but is not as important as a theorem. Because, on the one hand, we focus on important content and, on the other hand, we do not want to discriminate among mathematical statements, we avoid this term and instead use the term theorem throughout.
  • A corollary is a mathematical statement that follows from a theorem by a simple proof. Because the “simplicity” of mathematical proofs is a relative property, we avoid this term and instead also use the term theorem throughout.
  • Conjectures are mathematical statements for which it is unknown whether they are provable or refutable. Because we work in the area of applied mathematics, we will not encounter conjectures.

1.3 Propositional logic

Having now become acquainted with some basic building blocks of mathematical language systems, we turn to propositional logic, a simple system that allows relationships between mathematical statements to be established and formalized. Propositional logic plays a central role, for example, in the definition of set operations, in optimization conditions for functions, and in many proofs. In data-analytic applications, propositional logic is the basis of Boolean logic in programming. In mathematical psychology, propositional logic is the basis of the representational theory of measurement.

We begin with the definition of the concept of a mathematical statement.

Definition 1.1 (Statement) A statement is a sentence to which the property true or false can be assigned unambiguously.

The adjective true can also be understood as correct. We abbreviate true by “t” and false by “f”. In the field of real numbers, for example, the statement \(1 + 1 = 2\) is true and the statement \(1 + 1 = 3\) is false. Note that the binarity of the truth value of statements is a basic assumption of propositional logic and therefore to be understood formally and scientifically, not empirically. Truth values do not refer to definitions. Definitions fix meanings.

A first way of working with statements is to negate them. This leads to the following definition.

Definition 1.2 (Negation) Let \(A\) be a statement. Then the negation of \(A\) is the statement that is false when \(A\) is true and true when \(A\) is false. The negation of \(A\) is denoted by \(\neg A\), read as “not \(A\)”.

Example 1.1 (Negation of statements) The negation of the statement “The sun is shining” is the statement “The sun is not shining”. The negation of the statement \(1 + 1 = 2\) is the statement \(1 + 1 \ne 2\), and the negation of the statement \(x > 1\) is the statement \(x \le 1\).

The definition of the negation of a statement \(A\) is represented in tabular form as follows:

Table 1.1: Truth table of negation
\(A\) \(\neg A\)
t f
f t

Tables of this form are called truth tables. They are a popular tool in propositional logic, and we will use them often in the following.

If one wants to connect two statements logically, the concepts of conjunction and disjunction are available.

Definition 1.3 (Conjunction) Let \(A\) and \(B\) be statements. Then the conjunction of \(A\) and \(B\) is the statement that is true if and only if both \(A\) and \(B\) are true. The conjunction of \(A\) and \(B\) is denoted by \(A \land B\), read as “\(A\) and \(B\)”.

The definition of conjunction implies the following truth table:

Table 1.2: Truth table of conjunction
\(A\) \(B\) \(A \land B\)
t t t
t f f
f t f
f f f

Example 1.2 (Conjunction of statements) Let \(A\) be the statement \(2 \ge 1\) and \(B\) the statement \(2 > 1\). Since both \(A\) and \(B\) are true, the statement \((2 \ge 1) \land (2 > 1)\) is also true.

As another example, let \(A\) be the statement \(1 \ge 1\) and \(B\) the statement \(1 > 1\). Here, only \(A\) is true and \(B\) is false. Thus the statement \((1 \ge 1) \land (1 > 1)\) is false.

Definition 1.4 (Disjunction) Let \(A\) and \(B\) be statements. Then the disjunction of \(A\) and \(B\) is the statement that is true if and only if at least one of the two statements \(A\) and \(B\) is true. The disjunction of \(A\) and \(B\) is denoted by \(A \lor B\), read as “\(A\) or \(B\)”.

The definition of disjunction implies the following truth table:

Table 1.3: Truth table of disjunction
\(A\) \(B\) \(A \lor B\)
t t t
t f t
f t t
f f f

\(A \lor B\) is therefore also true when both \(A\) and \(B\) are true. The “or” considered here is thus more precisely an “and/or”. For this reason, disjunction is also called a “non-exclusive or”. As an example, let \(A\) be the statement \(2 \ge 1\) and let \(B\) be the statement \(2 > 1\). \(A\) is true and \(B\) is true. Thus the statement \((2 \ge 1) \lor (2 > 1)\) is true. Now again let \(A\) be the statement \(1 \ge 1\) and let \(B\) be the statement \(1 > 1\). Then \(A\) is true and \(B\) is false. Thus the statement \((1 \ge 1) \lor (1 > 1)\) is true.

One way of placing statements in a mechanical logical relationship is implication. It is defined as follows.

Definition 1.5 (Implication) Let \(A\) and \(B\) be propositions. The implication, denoted by \(A \Rightarrow B\), is the proposition that is false if and only if \(A\) is true and \(B\) is false. Here, \(A\) is called the premise and \(B\) the conclusion of the implication. We read \(A \Rightarrow B\) as “\(B\) follows from \(A\)”, “\(A\) implies \(B\)”, or “if \(A\), then \(B\)”.

The definition of implication can be represented by the following truth table:

Table 1.4: Truth table of implication
\(A\) \(B\) \(A \Rightarrow B\)
t t t
t f f
f t t
f f t

Example 1.3 (Damage to and closure of a bridge) To illustrate Table 1.4, we consider an everyday example involving a particular bridge at a particular time. Let \(A\) be the proposition “The bridge is damaged”, \(B\) the proposition “The bridge is closed”, and \(A \Rightarrow B\) the implication “If the bridge is damaged, then the bridge is closed”. We discuss the four cases in Table 1.4.

  1. \(A\) true, \(B\) true, \(A \Rightarrow B\) true. If \(A\) is true, the bridge is damaged, and if \(B\) is also true, the bridge is also closed. In this case, the implication “If the bridge is damaged, then the bridge is closed” is therefore obviously true.

  2. \(A\) true, \(B\) false, \(A \Rightarrow B\) false. If \(A\) is true, the bridge is damaged, and if \(B\) is false, the bridge is not closed. In this case, the implication “If the bridge is damaged, then the bridge is closed” is therefore obviously false.

  3. \(A\) false, \(B\) true, \(A \Rightarrow B\) true. If \(A\) is false, the bridge is not damaged, and if \(B\) is true, the bridge is closed. Since the premise \(A\) is false, the implication \(A \Rightarrow B\) is true by definition.

  4. \(A\) false, \(B\) false, \(A \Rightarrow B\) true. If \(A\) is false, the bridge is not damaged, and if \(B\) is false, the bridge is not closed. Since the premise \(A\) is false, the implication \(A \Rightarrow B\) is also true by definition in this case.

Example 1.4 (\(x = 2 \Rightarrow x^2 = 4\)) We discuss Table 1.4 using the implication \[\begin{equation} x = 2 \Rightarrow x^2 = 4 \end{equation}\] To do so, we consider the statements \[\begin{equation} A : x = 2 \mbox{ and } B : x^2 = 4. \end{equation}\] Depending on the definition of \(x\), both \(A\) and \(B\) can be true or false. For example, if \(x := 1\), both \(A : x = 2\) and \(B : x^2 = 4\) are false. Let us consider the rows of Table 1.4 in turn.

  1. \(A\) true, \(B\) true, \(A \Rightarrow B\) true. In this case, we must have \(x := 2\), since then \(2 = 2\) and \(2^2 = 4\) are true. This is the case that the implication describes directly: if \(x = 2\), then indeed \(x^2 = 4\).

  2. \(A\) true, \(B\) false, \(A \Rightarrow B\) false. Here, \(x = 2\) and \(x^2 \neq 4\) would have to hold simultaneously. However, this case cannot occur, since \(x = 2\) implies \(x^2 = 2 \cdot 2 = 4\). This excludes the only case in which the implication would be false.

  3. \(A\) false, \(B\) true, \(A \Rightarrow B\) true. This case can occur, since for \(x := -2\), \(A\) is false but \(B\) is true. By the definition in Table 1.4, however, this does not affect the truth of the implication.

  4. \(A\) false, \(B\) false, \(A \Rightarrow B\) true. This case can also occur, but it does not contradict the implication. For example, for \(x := 3\), statement \(A\) is false, so the premise of the implication is not satisfied.

An implication holds for all values under consideration if and only if none of these values makes \(A\) true and \(B\) false. A single counterexample refutes this general claim. In the following example, we again exclude the case in which \(A\) is true and \(B\) is false.

Example 1.5 (An even square and an even integer) We want to show that if the square of an integer \(m\) is even, then \(m\) is also even. Formally, for a fixed integer \(m\), we have the propositions \[\begin{equation} A : m^2 \text{ is even},\, B : m \text{ is even} \end{equation}\] and want to show that \(A \Rightarrow B\) is true for every integer \(m\). We can write this as follows.

  • For every integer \(m\), if \(m^2\) is even, then \(m\) is also even.
  • For every integer \(m\), “\(m^2\) is even \(\Rightarrow\) \(m\) is even”.

According to the truth table for implication, \(A \Rightarrow B\) is false only when \(A\) is true and \(B\) is false. We only need to ensure that the case “\(m^2\) is even” and “the integer \(m\) is odd” cannot occur. To do so, we show that if the integer \(m\) is odd, then \(m^2\) is also odd.

Let the integer \(m\) be odd. Then there is an integer \(k\) such that \(m = 2k + 1\). The square of such an \(m\) satisfies \[\begin{equation} m^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. \end{equation}\] Thus, \(m^2\) is again of the form \(2n + 1\), with the integer \(n := 2k^2 + 2k\). The case “\(A\) true and \(B\) false” therefore cannot occur. Consequently, the implication \[\begin{equation} m^2 \text{ is even} \Rightarrow m \text{ is even} \end{equation}\] is true for every integer \(m\).

A further intuitive understanding of the definition of implication in the truth table above arises from reading it as an attempt to capture and formalize the idea of a consequence in propositional logic. To do so, read the truth states in Table 1.4 in the order truth state of \(A\), truth state of \(A \Rightarrow B\), and finally truth state of \(B\). Read in this way, the table shows that if \(A\) is true and \(A \Rightarrow B\) is true, then \(B\) is true. Thus, if one constructs a true implication based on a true statement, for example by transforming equations, it follows that \(B\) is also true. If \(A\) is true and \(A \Rightarrow B\) is false, then \(B\) is false. This too can be used to refute statements. Finally, if \(A\) is false and \(A \Rightarrow B\) is true, \(B\) can be either true or false. Only from a true premise does a true implication always yield a true conclusion. When the premise is false, the implication is true regardless of the truth value of the conclusion. The truth of \(A \Rightarrow B\) and the falsity of \(A\) therefore do not determine whether \(B\) is true or false.

Implication gives rise to the concepts of sufficient and necessary conditions. If \(A \Rightarrow B\) is true, we say that “\(A\) is sufficient for \(B\)” and that “\(B\) is necessary for \(A\)”. This terminology can be explained as follows. If \(A \Rightarrow B\) is true, then whenever \(A\) is true, \(B\) is also true. The truth of \(A\) suffices for the truth of \(B\). Thus, \(A\) is sufficient for \(B\). Furthermore, if \(A \Rightarrow B\) is true and \(B\) is false, then \(A\) is also false. The truth of \(B\) is therefore necessary for the truth of \(A\).

A very frequently occurring relation between two statements is their equivalence.

Definition 1.6 (Equivalence) Let \(A\) and \(B\) be statements. The equivalence of \(A\) and \(B\) is the statement that is true if and only if \(A\) and \(B\) are both true or if \(A\) and \(B\) are both false. The equivalence of \(A\) and \(B\) is denoted by \(A \Leftrightarrow B\) and read as “\(A\) if and only if \(B\)” or “\(A\) is equivalent to \(B\)”.

The definition of equivalence implies the following truth table:

Table 1.5: Truth table of equivalence
\(A\) \(B\) \(A \Leftrightarrow B\)
t t t
t f f
f t f
f f t

The definition of the concept of logical equivalence allows, among other things, the equivalence of two statements to be established by means of implications.

Definition 1.7 (Logical equivalence) Two statements are called logically equivalent if their truth tables are the same.

As examples of logical equivalences that are frequently used in proof arguments, we show the statements of the following theorem.

Theorem 1.1 (Logical equivalences) Let \(A\) and \(B\) be two statements. Then the following statements are logically equivalent:

  1. \(A \Leftrightarrow B\) and \((A \Rightarrow B) \land (B \Rightarrow A)\) (2) \(A \Rightarrow B\) and \((\neg B) \Rightarrow (\neg A)\)

Proof. By the definition of logical equivalence, we have to show that the truth tables of the statements under consideration are the same. We show first (1), then (2).

(1) We recall the truth table of \(A \Leftrightarrow B\):

\(A\) \(B\) \(A \Leftrightarrow B\)
t t t
t f f
f t f
f f t

We further consider the truth table of \((A \Rightarrow B) \land (B \Rightarrow A)\):

\(A\) \(B\) \(A \Rightarrow B\) \(B \Rightarrow A\) \((A \Rightarrow B) \land (B \Rightarrow A)\)
t t t t t
t f f t f
f t t f f
f f t t t

Comparing the truth table of \(A \Leftrightarrow B\) with the first two and the last column of the truth table of \((A \Rightarrow B) \land (B \Rightarrow A)\) shows their equality.

(2) We recall the truth table of \(A \Rightarrow B\):

\(A\) \(B\) \(A \Rightarrow B\)
t t t
t f f
f t t
f f t

We further consider the truth table of \((\neg B) \Rightarrow (\neg A)\):

\(A\) \(B\) \(\neg B\) \(\neg A\) \((\neg B) \Rightarrow (\neg A)\)
t t f f t
t f t f f
f t f t t
f f t t t

Comparing the truth table of \(A \Rightarrow B\) with the first two and the last column of the truth table of \((\neg B) \Rightarrow (\neg A)\) shows their equality.

The first statement of Theorem 1.1 says that the statement “\(A\) and \(B\) are equivalent” is logically equivalent to the statement “from \(A\) follows \(B\) and from \(B\) follows \(A\)”. This is the basis for many so-called direct proofs using equivalence transformations. The second statement of Theorem 1.1 says that the statement “from \(A\) follows \(B\)” is logically equivalent to the statement “from not \(B\) follows not \(A\)”. This is the basis for the technique of indirect proof. We consider these proof techniques more closely in the following section. First, we summarize the meanings of the symbols introduced in this section once more in the table below.

Table 1.6: Symbol overview. \(A\) and \(B\) are statements, that is, \(A\) and \(B\) are either true or false.
Symbol Meaning Note
\(\neg A\) Not \(A\) True when \(A\) is false, and vice versa
\(A \land B\) \(A\) and \(B\) True only when both \(A\) and \(B\) are true
\(A \lor B\) \(A\) and/or \(B\) True when at least one of the statements is true
\(A \Rightarrow B\) From \(A\) follows \(B\) \(B\) is necessary for \(A\), \(A\) is sufficient for \(B\)
\(A \Leftrightarrow B\) \(A\) is equivalent to \(B\) Both \(A \Rightarrow B\) and \(B \Rightarrow A\) hold

1.4 Equivalence transformations

Mathematical problems often represent information about an unknown variable implicitly by means of an equation or inequality. To determine the possible values of the variable, that is, the solution set of the equation or inequality, explicitly, one uses equivalence transformations. Here, we consider only the equivalence transformations of equations and inequalities in real variables familiar from school mathematics. Equivalence transformations of equations and inequalities preserve the truth value for every value of the variable in the domain under consideration. This often involves applying the same suitable operation to both sides. For a transformation of an equation or inequality statement \(A\) into an equation or inequality statement \(B\) to be an equivalence transformation, both \(A \Rightarrow B\) and \(B \Rightarrow A\) must hold for every value of the variable in the domain under consideration. The transformation must therefore be valid in both directions.

For equations, admissible equivalence transformations include in particular

  • adding a number to both sides of the equation,
  • subtracting a number from both sides of the equation,
  • multiplying both sides of the equation by a nonzero number,
  • dividing both sides of the equation by a nonzero number, and
  • applying an invertible function to both sides of the equation, provided both sides lie in its domain.

Example 1.6 (Equivalence transformations of an exponential equation) Anticipating Section 4.3, we consider the statement \[\begin{equation} 2 \exp(x) - 2 = 0. \end{equation}\] Then \[\begin{equation} \begin{aligned} 2 \exp(x) - 2 & = 0 \\ \Leftrightarrow 2 \exp(x) - 2 + 2 & = 0 + 2 \\ \Leftrightarrow 2 \exp(x) & = 2 \\ \Leftrightarrow \frac{1}{2} \cdot 2 \exp(x) & = \frac{1}{2} \cdot 2 \\ \Leftrightarrow \exp(x) & = 1 \\ \Leftrightarrow \ln(\exp(x)) & = \ln(1) \\ \Leftrightarrow x & = 0. \end{aligned} \end{equation}\] In summary, therefore, \[\begin{equation} 2 \exp(x) - 2 = 0 \Leftrightarrow x = 0. \end{equation}\]

For inequalities, admissible equivalence transformations include in particular

  • adding a number to both sides of the inequality,
  • subtracting a number from both sides of the inequality,
  • multiplying both sides of the inequality by a nonzero number, with multiplication by a negative number reversing the inequality sign,
  • dividing both sides of the inequality by a nonzero number, with division by a negative number reversing the inequality sign, and
  • applying a strictly increasing or strictly decreasing function to both sides of the inequality, provided both sides lie in its domain. For strictly decreasing functions, the inequality sign is reversed.

Example 1.7 (Equivalence transformations of an inequality) We consider the statement \[\begin{equation} -5 x - 2 \ge 8. \end{equation}\] Then \[\begin{equation} \begin{aligned} \begin{split} -5x - 2 & \ge 8 \\ \Leftrightarrow -5x - 2 + 2 & \ge 8 + 2 \\ \Leftrightarrow -5x & \ge 10 \\ \Leftrightarrow -\frac{1}{5} \cdot 5x & \ge \frac{1}{5} \cdot 10 \\ \Leftrightarrow -x & \ge 2 \\ \Leftrightarrow x & \le -2. \\ \end{split} \end{aligned} \end{equation}\] In summary, therefore, \[\begin{equation} -5x - 2 \ge 8 \Leftrightarrow x \le -2. \end{equation}\]

We now relate the concept of an equivalence transformation to the concept of equivalence introduced above. An equivalence transformation transforms an equation or inequality in such a way that the original and transformed statements have the same truth value for every value of the variable in the domain under consideration. They therefore have the same solution set. Consider, for example, the transformation \[\begin{equation} x + 3 = 7 \Leftrightarrow x = 4, \end{equation}\] obtained by subtracting \(3\) from both sides of the first equation. The first statement \(A : x + 3 = 7\) and the second statement \(B : x = 4\) have the same truth value for every value of \(x\). For example, both statements are true for \(x = 4\), whereas both are false for \(x \neq 4\). Thus, with reference to Table 1.5, only the two cases in which the equivalence is true occur. In particular, this corresponds to the fact that both equations have the same solution set, namely \[\begin{equation} \{x | x + 3 = 7 \} = \{x | x = 4 \} = \{4\}. \end{equation}\] However, not all transformations of equations or inequalities are equivalence transformations. For the statements \[\begin{equation} A: x = 2 \mbox{ and } B: x^2 = 4 \end{equation}\] \(A \Rightarrow B\) holds for every \(x \in \mathbb{R}\). The reverse direction \(B \Rightarrow A\), however, does not hold for all \(x \in \mathbb{R}\), since for \(x = -2\), \(B\) is true and \(A\) is false. According to the truth table of equivalence (Table 1.5), the two statements are therefore not equivalent for all \(x \in \mathbb{R}\). Correspondingly, the two equations have different solution sets, since the solution set of \(A\) is \[\begin{equation} \{x | x = 2\} = \{2\} \end{equation}\] and the solution set of \(B\) is \[\begin{equation} \{x | x^2 = 4\} = \{-2,2\}. \end{equation}\]

1.5 Proof techniques

In this section, we outline three fundamental techniques for proving an implication \(A \Rightarrow B\): direct proof, proof by contraposition, and proof by contradiction. Proofs by contraposition and proofs by contradiction are also called indirect proofs.

Direct proofs usually use small steps, in our applications mostly transformations of equations, to show \(A \Rightarrow B\). Formally, it suffices to establish the direction \[\begin{equation} A \Rightarrow A_1 \Rightarrow A_2 \Rightarrow \cdots \Rightarrow B \end{equation}\] If the entire chain in such a proof consists of equivalences, \[\begin{equation} A \Leftrightarrow A_1 \Leftrightarrow A_2 \Leftrightarrow \cdots \Leftrightarrow B, \end{equation}\] then the proof even establishes \[\begin{equation} A \Leftrightarrow B \end{equation}\] and thus more than was actually required.

Example 1.8 (Direct proof of \(x = 2 \Rightarrow x^2 = 4\)) As an example, consider the statements for a real number \(x\) \[\begin{equation} A: x = 2 \qquad\text{and}\qquad B: x^2 = 4. \end{equation}\] For a direct proof of \(A \Rightarrow B\), assume \(x = 2\). Then \[\begin{equation} x^2 = 2^2 = 4. \end{equation}\] This proves the implication \[\begin{equation} x = 2 \Rightarrow x^2 = 4 \end{equation}\]

The calculation can also be written as the chain \[\begin{equation} x = 2 \Leftrightarrow 2x = 4 \Rightarrow x^2 = 4 \end{equation}\] Here, only the first step is an equivalence, whereas the second is merely an implication: the value \(x = -2\) satisfies \(x^2 = 4\) but not \(2x = 4\). Overall, this chain therefore establishes only \[\begin{equation} x = 2 \Rightarrow x^2 = 4. \end{equation}\] The reverse direction does not hold, so the two statements are not equivalent.

Proofs by contraposition use the logical equivalence of \(A \Rightarrow B\) and \((\neg B) \Rightarrow (\neg A)\). One assumes \(\neg B\) and derives \(\neg A\). The contrapositive is thus proved directly. This excludes the case in which \(A\) is true and \(B\) is false, since false \(B\) would also imply false \(A\).

Example 1.9 (Proof by contraposition of \(x = 2 \Rightarrow x^2 = 4\)) For the statements \[\begin{equation} A: x = 2 \qquad\text{and}\qquad B: x^2 = 4 \end{equation}\] the negations are \[\begin{equation} \neg A: x \neq 2 \qquad\text{and}\qquad \neg B: x^2 \neq 4. \end{equation}\] We therefore want to prove the contrapositive \[\begin{equation} x^2 \neq 4 \Rightarrow x \neq 2 \end{equation}\] To do so, assume \(x^2 \neq 4\). Subtracting \(4\) gives \[\begin{equation} x^2 - 4 \neq 0. \end{equation}\] The difference of squares identity also gives \[\begin{equation} x^2 - 4 = x^2 - 2^2 = (x-2)(x+2). \end{equation}\] We therefore obtain \[\begin{equation} (x-2)(x+2) \neq 0. \end{equation}\] Since the product is nonzero, we must in particular have \(x-2 \neq 0\). If this factor were zero, the product would also be zero. It follows that \(x \neq 2\). This proves the contrapositive and hence the original implication \[\begin{equation} x = 2 \Rightarrow x^2 = 4 \end{equation}\]

Proofs by contradiction use the fact that, according to Table 1.4, the implication \(A \Rightarrow B\) is false in only one case, namely when \(A\) is true and \(B\) is false. This case is described by the statement \(A \land (\neg B)\). In a proof by contradiction, one therefore assumes \(A \land (\neg B)\) and shows that this assumption leads to a contradiction, for example a statement of the form \(C \land (\neg C)\). This excludes the only case in which the implication would be false. Consequently, the implication is true.

Example 1.10 (Proof by contradiction of \(x = 2 \Rightarrow x^2 = 4\)) Considering the implication \(A \Rightarrow B\) from this perspective for \[\begin{equation} A: x = 2 \qquad\text{and}\qquad B: x^2 = 4, \end{equation}\] the statement \(A \land (\neg B)\) corresponds to \[\begin{equation} x = 2 \qquad\text{and}\qquad x^2 \neq 4. \end{equation}\] At the same time, if \(x\) takes the value \(2\), then \(x^2\) takes the value \(4\). Under the assumption \(A \land (\neg B)\), we therefore have \[\begin{equation} x^2 = 4 \qquad\text{and}\qquad x^2 \neq 4. \end{equation}\] This is a contradiction. Hence we have proved \[\begin{equation} x = 2 \Rightarrow x^2 = 4 \end{equation}\]

Finally, we demonstrate the three proof techniques using the same theorem.

Theorem 1.2 (Squares of positive numbers) Let \(a\) and \(b\) be two positive real numbers. Then \[\begin{equation} a^2 < b^2 \Rightarrow a < b. \end{equation}\]

Proof. Let \[\begin{equation} A: a^2 < b^2 \qquad\text{and}\qquad B: a < b. \end{equation}\] We give three alternative proofs of the implication \(A \Rightarrow B\).

Direct proof

Since \(a,b > 0\), we have \(b+a > 0\). We therefore obtain \[\begin{equation} \begin{aligned} a^2 < b^2 &\Leftrightarrow 0 < b^2-a^2 \\ &\Leftrightarrow 0 < (b+a)(b-a) \\ &\Leftrightarrow 0 < b-a \\ &\Leftrightarrow a < b. \end{aligned} \end{equation}\] In the third step, we divide by the positive number \(b+a\). This proves \(A \Rightarrow B\). Since the entire chain consists of equivalences, we have in fact shown \(A \Leftrightarrow B\).

Proof by contraposition

The negations of the statements are \[\begin{equation} \neg A: a^2 \ge b^2 \qquad\text{and}\qquad \neg B: a \ge b. \end{equation}\] Assume \(\neg B\), that is, \(a \ge b\). Since \(a,b > 0\), multiplication by \(a\) and \(b\), respectively, gives \[\begin{equation} a^2 \ge ab \qquad\text{and}\qquad ab \ge b^2. \end{equation}\] Hence \[\begin{equation} a^2 \ge ab \ge b^2, \end{equation}\] which is \(\neg A\). This proves the contrapositive \((\neg B) \Rightarrow (\neg A)\) and hence the original implication \(A \Rightarrow B\).

Proof by contradiction

Assume \(A \land (\neg B)\), that is, \[\begin{equation} a^2 < b^2 \qquad\text{and}\qquad a \ge b, \end{equation}\] Since \(a,b > 0\), multiplying \(a \ge b\) by \(a\) and \(b\), respectively, gives \[\begin{equation} a^2 \ge ab \ge b^2. \end{equation}\] Thus \(a^2 \ge b^2\). This contradicts the statement \(a^2 < b^2\), which was also assumed. The assumption \(A \land (\neg B)\) is therefore excluded, and the implication \(A \Rightarrow B\) is proved.

Study questions

  1. Explain the distinctive features of mathematical language.
  2. What are essential activities for learning a language?
  3. Explain the concept of a definition.
  4. Explain the concept of a theorem.
  5. Explain the concept of a proof.
  6. State the definition of a mathematical proposition.
  7. State the definition of the negation of a mathematical proposition.
  8. State the definition of the conjunction of two mathematical propositions.
  9. State the definition of the disjunction of two mathematical propositions.
  10. State the definition of implication.
  11. State the definition of equivalence.
  12. State the definition of logical equivalence.
  13. Explain the concept of a direct proof.
  14. Explain the concept of an indirect proof.
  15. Explain the concept of proof by contradiction.

Study question answers

  1. Mathematical language is precise, abstract, and hierarchically structured. It has a high information density and aims at statements that are as general as possible. See 1.
  2. Essential activities include immersion in the language, memorizing concepts, translating into everyday language, and written and spoken use. See
  3. A definition specifies the meaning of a concept or symbol. See
  4. A theorem is a mathematical proposition whose truth is established by a proof based on definitions, assumptions, and known results. See
  5. A proof is a logical chain of argumentation that derives the truth of a proposition from its assumptions and known results. See
  6. See Definition 1.1.
  7. See Definition 1.2.
  8. See Definition 1.3.
  9. See Definition 1.4.
  10. See Definition 1.5.
  11. See Definition 1.6.
  12. See Definition 1.7.
  13. A direct proof derives the conclusion \(B\) from the premise \(A\) through valid inferences. In particular, equivalence transformations may be used. See
  14. An indirect proof derives the negation of the premise \(\neg A\) from the negation of the conclusion \(\neg B\) through valid inferences. It uses the logical equivalence of \(A \Rightarrow B\) and \((\neg B) \Rightarrow (\neg A)\). See 3.
  15. A proof by contradiction assumes the premise \(A\) and the negation of the conclusion \(\neg B\) and derives a false statement. This excludes the only case in which \(A \Rightarrow B\) is false. See 3.
Friston, K. J. (2005). A theory of cortical responses. Philosophical Transactions of the Royal Society B: Biological Sciences, 360(1456), 815–836. https://doi.org/10.1098/rstb.2005.1622
Newton, I. (1687). Philosophiae Naturalis Principia Mathematica. Royal Society.
Unger, L. (2000). Grundkurs Mathematik.