Introduction to Logic
Before getting into the study of analysis, we need to understand some basic concepts in logic. Indeed, logic is the foundation of all mathematical reasoning, and it will be used extensively through this blog series.
Logical Connectives
In logic, a statement is an assertion which is either true T or false F, but not both. For example, the statement \(1 > 0\) is T and \(1 = 2\) is F. Now suppose we have generic statements \(P\), \(Q\) and \(R\), then we can construct compound statements using logical connectives. For example, we have the following:
- Conjunction, denoted by \(P \land Q\), which is true if and only if both \(P\) and \(Q\) are true, and false otherwise;
- Disjunction, denoted by \(P \lor Q\), which is true if and only if \(P\) or \(Q\) or both are true;
- Implication, denoted by \(P \Rightarrow Q\), which is true unless \(P\) is true and \(Q\) is false; and
- Negation, denoted by \(\neg P\), which is true if and only if \(P\) is false.
These logical connectives can be defined using truth tables as follows:
| \(P\) | \(Q\) | \(P \land Q\) | \(P \lor Q\) | \(P \Rightarrow Q\) | \(\neg P\) |
|---|---|---|---|---|---|
| T | T | T | T | T | F |
| T | F | F | T | F | F |
| F | T | F | T | T | T |
| F | F | F | F | T | T |
For more reading on this, see here. We note that the implication \(P \Rightarrow Q\) can be interpreted as "if \(P\) then \(Q\)", and is equivalent to \(\neg P \lor Q\). The distributive and de Morgan's laws are important properties of logical connectives, and are given as follows:
We can see how these work using truth tables as above.
Contrapositive
The contrapositive of an implication \(P \Rightarrow Q\) is defined as \(\neg Q \Rightarrow \neg P\). Both of these are logically equivalent, meaning we can prove either one is true - indeed, sometimes the contrapositive is easier to prove. Indeed, the truth table below shows the logical equivalence.
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | \(\neg Q\) | \(\neg P\) | \(\neg Q \Rightarrow \neg P\) |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Universal and Existential Quantifiers
While we are here, we also define the universal \(\forall\) and existential \(\exists\) quantifiers:
- \(\forall\) means "for all" or "for every";
- \(\exists\) means "there exists" or "there is at least one"; and
- \(:\) means "such that", sometimes also denoted simply as \(s.t.\)
Then if \(P(x)\) is some statement involving the variable \(x\), we can form the universal statement \(\forall x, P(x)\), which is true if and only if \(P(x)\) is true for every possible value of \(x\). The logical negation of this statement \(\neg (\forall x\, P(x))\) is equivalent to the existential statement \(\exists x: \neg P(x)\), which is true if and only if there exists at least one value of \(x\) such that \(P(x)\) is false.
For example, \(\forall x \in \mathbb{R}, x^2 \geq 0\) is true (see here for more information on \(\mathbb{R}\)). Indeed, any real number squared is non-negative, e.g. \((-3)^2 = 9 \geq 0\) and \(2^2 = 4 \geq 0\). For the converse statement, consider \(P(x)\) to be \(x^3 > 0\) and \(x\) to be any real number. Then clearly if we look at any negative \(x\), say \(x = -1\), we have \(P(x) = (-1)^3 = 1 < 0\), so there does exist an \(x\) for which \(\neg P(x)\) is true.
Axioms
An axiom is simply a statement that is taken to be true without proof, and serves as a starting point for further reasoning and arguments. Indeed, many mathematical systems are built upon a set of axioms. For example, the field and order axioms of \(\mathbb{R}\) are defined below.
Field Axioms
These define the arithmetic properties of addition and multiplication within the set \(\mathbb{R}\). This includes properties like commutativity, associativity, distributivity, identity elements (\(0\) and \(1\)), and additive/multiplicative inverses.
| Axiom ID | Axiom | Description |
|---|---|---|
| A1 | \(\forall a, b, c \in \mathbb{R}, a + (b + c) = (a + b) + c\) | \(+\) is associative |
| A2 | \(\forall a, b \in \mathbb{R}, a + b = b + a\) | \(+\) is commutative |
| A3 | \(\exists 0 \in \mathbb{R} : \forall a \in \mathbb{R}, a + 0 = a = 0 + a\) | additive identity |
| A4 | \(\forall a \in \mathbb{R}\, \exists (-a) \in \mathbb{R} : a + (-a) = 0 = (-a) + a\) | additive inverse |
| A5 | \(\forall a, b, c \in \mathbb{R}, a(bc) = (ab)c\) | \(\times\) is associative |
| A6 | \(\forall a, b \in \mathbb{R}, ab = ba\) | \(\times\) is commutative |
| A7 | \(\exists 1 \in \mathbb{R}\backslash \{0\} : \forall a \in \mathbb{R}, a1 = a = 1a\) | multiplicative identity |
| A8 | \(\forall a \in \mathbb{R}\backslash \{0\} \exists a^{-1} \in \mathbb{R} : aa^{-1} = 1 = a^{-1}a\) | multiplicative inverse |
| A9 | \(\forall a, b , c \in \mathbb{R}, a(b+c) = ab + ac\) | distributivity |
The notation \(A \backslash B\) is used to denote the set of elements in \(A\) that are not in \(B\). So \(\mathbb{R} \backslash \{0\}\) is the set of all real numbers except \(0\).
Order Axioms
These build on the field axioms by introducing a notion of order (i.e., inequality) to the set \(\mathbb{R}\). For example, trichotomy is that every number \(x\) is either negative, positive or \(0\)
| Axiom ID | Axiom | Description |
|---|---|---|
| A10 | \(\forall a \in \mathbb{R}\) either \(a < 0\), \(a = 0\) or \(a > 0\) | trichotomy of cardinals |
| A11 | \(\forall a, b, c \in \mathbb{R}\) if \(a < b\) then \(a + c < b + c\) | |
| A12 | \(\forall a, b, c \in \mathbb{R}\) if \(a < b\) and \(c > 0\) then \(ac < bc\) |
For more information on axioms, see here.
Examples
Using these axioms we can derive many useful properties of real numbers.
Example 1. The additive identity \(0\) in \(\mathbb{R}\) is unique.
Solution. To prove this, we suppose there are two additive identities, say \(0_A\) and \(0_B\). Then by A3 we have that for any \(a\) in \(\mathbb{R}\) that \(a + 0_A = a\) and \(a + 0_B = a\). Now letting \(a = 0_B\) in the first equation gives \(0_B + 0_A = 0_A\), and \(a = 0_A\) in the second gives \(0_A + 0_B = 0_A\). Then using A2 we see that \(0_A = 0_B + 0_A = 0_A + 0_B = 0_B\), hence \(0_A = 0_B\). So if there were to exist two additive identities, we have just shown that they must be equal, hence uniqueness.
Example 2. For any \(a,b \in \mathbb{R}\), if \(ab = 0\) then either \(a = 0\) or \(b = 0\).
Solution. Suppose that \(ab = 0\) but that \(a \neq 0\) (without loss of generality WLOG, since we could just relabel the variables). Then by A8 there exists a multiplicative inverse \(a^{-1}\) such that \(a^{-1}a = 1\) and so
Example 3. For any \(a \in \mathbb{R}\), we have \(-(-a) = a\).
Solution. That is, the additive inverse of the additive inverse of \(a\) is just \(a\) itself. So for any \(a \in \mathbb{R}\), axiom A4 gives us an element \(-a \in \mathbb{R}\) with \(a + (-a) = 0 = (-a) + a\). But since \((-a) \in \mathbb{R}\), axiom A4 also gives us an element \(-(-a) \in \mathbb{R}\) such that
Then adding \(-(-a)\) to both sides of the equation \(a + (-a) = 0\), using A1/A3 we see that
and both sides are equal. A similar proof would show that \((a^{-1})^{-1} = a\) for any \(a\).
Example 4. For any \(a, b, c \in \mathbb{R}\), if \(a + c = b + c\) then \(a = b\).
Solution. There is an additive inverse \(-c\) such that \(c + (-c) = 0\) and so adding \(-c\) to both sides of the equation and using associativity we see that
and so \(a = b\). A similar proof would prove that if \(a \neq 0\) and \(ab = ac\), then \(b = c\).