Study Notes Series, Issue №1
Formal Truth and Logic
Introduction to Mathematics for non-Mathematicians
I am a student myself and not (yet) a professional mathematician. This article and the following ones go along as I am learning myself. I follow the script of my lectures and attempt to rephrase in my own words as much as possible. For more information and resources, please see the concluding notes at the end of the article.
I kindly invite you to point out errors in my reasoning and to join me on my journey to epiphany.
Mathematics is a precise language, attempting to build a set of universal and known truths that hold, given only an elementary predefined set of axioms. Not only since the days of Hilbert, Russell and Gödel, the idea has persisted that from the right choice of initial axioms, all truths to be known would result as a consequence of the application of pure logical reasoning. Albeit a rather philosophical question whether an objective truth exists— It is no coincidence, that many figures in foundational mathematics were also philosophers — logical deduction lies at the heart of how Mathematics operates as a scientific discipline.
And on a side note: Formal logic is also directly tied to the emergence of Computer Science as a scientific discipline with the publication of Alan M. Turing’s paper “On Computable Numbers, with an Application to the Entscheidungsproblem”. Formal logic can be condensed — abstracted — to Boolean logic, where the intricacies of the argument to be evaluated as either true or false are put back and the pure information content is boiled down to a combination of binary states, i.e. to either-or. But I am getting ahead of myself.
True and False Statements
Logical arguments are constructed from statements, which can be attributed exactly one of two properties: true or false. Typical examples include statements about how two or more entities relate to each other, such as:
- I am the son of my mother. (true in most cases)
- 2 + 1 = 3 (intuitively true, I guess)
- If 12 ≥ 9, then 6 ≥ 7 and 2 × 2 = 4 (false, but probably not for entirely obvious reasons) (cf. [1], p. 17 and p. 56)
Of course, these are contrived examples. We will come back to the latter expression when talking about logical operators. It itself consists of individual statements, that are combined through logical operators to form an entirely new statement. Let us also defer at this point the question on how to establish the truth of an elementary statement, which itself cannot be further divided into other statements. To do that, we first need to define what we fundamentally assume to be true without requiring further evidence. Let us instead examine the structure of logical expressions.
I have used the terms expression and statement interchangeably, but to avoid any ambiguity in the usage of the terms, let us quickly determine, when it is justified to do that: First of all, all statements are expressions, but an expression is not necessarily a statement. Expressions have an inherent value. This value can be determined through evaluating the expression, e.g.:
- The expression 2 + 3 evaluates to 5
- The expression (1.2 + 4) ÷ 4 evaluates to 1.3
- The expression -10 evaluates to -10
- The expression 2² = 3 evaluates to false
Only the last expression is also a statement. As mentioned further above, a statement can be attributed the property of being either true or false. More formally expressed: The output space of a statement is a set of only two possible elements — true or false. Every expression, which qualifies as a statement evaluates to one of these two values.
What we have not done so far, is determine the domain— or body — of values, which either defines legal input values to our expression, the legal set of outputs, or even the legal set of operations defined over the elements of this body of values. It may seem the obvious thing to do from a mathematical perspective, and trivial at best from a layman’s point of view. Often it feels as cumbersome as the preemptive declarations required by the Pascal programming language. But similar to Pascal, it is…
a) … a helpful tool for yourself to detect fallacies at the implementation stage of your argument, …
b) … a concise way of communicating which rules govern the domain you are talking about (e.g. arithmetic operators behave crucially different, when talking about multi-dimensional bodies, as in vector space) and…
c) … not optional for driving a legitimate argument.
In Computer Science in particular, the situation of having various Types from different value domains with their respective set of elements from which they can be drawn and the operators that can operate on these elements, is a very real situation. In linguistic terms: The body defines the syntax and the semantics of valid expressions. Although languages like Python may try to convince you otherwise, there is e.g. no universally agreed definition for arithmetic operators like “+” and “-” on alphabetic characters and character arrays. As the saying goes: Type Safety is not usually a problem… until it is.
We have been talking about statements, hence today our output space are truth values.
Combinations with Connectives and Quantifiers
Usually an argumentation or proof requires a qualification, under which conditions it holds, how individual statements relate to one another, or how a statement generalizes over a group of sufficiently likewise cases. A statement can be qualified or tied to a condition through a combination of logical connectives. Quantifiers limit or express the general validity of a statement.
Logical Connectives
Logical connectives are operators that always transform their expression to a truth value. Classical examples for connectives from our everyday language are AND, OR and NOT. Their meaning slightly differs from our intuitive understanding of the word. That is due to their narrower definition, removing all ambiguity in interpreting a mathematical logical sentence.
Lets go through the definition of these logical connectives. This list is not exhaustive, but any other logical operation can be expressed through a combination of the following elementary connectives. Truth tables, as you will see, are a convenient way to gain insight into how logical connectives operate on their operands.
Unary Operators
The only unary logical connective in this list is the negation. Let A be a statement, which can be attributed the property of being either true or false:
Definition: The negation ¬A of A is the statement, which is false, if A is true, and which is true, if A is false ([1], p. 18).
That is the negation, or logical NOT, inverts the truth value of the statement. That means, a true statement negated evaluates to false, and a false statement negated evaluates to true. Expressed in a truth table, it looks like this:
Other unary connectives not further explained here, are the constant expressions logical true and logical false, and the logical identity.
Binary Operators
The binary logical connectives, i.e. operators which require two arguments, are the conjunction, the disjunction, the implication, and the equivalence.
The conjunction is one of the most fundamental connectives. The natural language’s cousin of the logical conjunction is the grammatical and, which serves to form a compound sentences. Hence, the conjunction is also known as logical AND. Be A and B respectively either true or false statements:
Definition: The conjunction A ∧ B of A and B is the statement, which is true exactly if both A and B are true ([1], p. 18).
The conjunction evaluates to true if and only if all of its operands are true. Otherwise, it results in a value of false.
Similar to how the conjunction represents a logical AND expression, the disjunction represents logical OR. Let A and B be statements:
Definition: The disjunction A ∨ B of A and B is the statement, which is true exactly if at least one of the statements A or B is true ([1], p. 19).
Conversely to the conjunction, the disjunction evaluates to false, if and only if all of its operands are false. In any other case it produces a value of true. Hence, the logical OR is more permissive than the logical AND in that it only requires one of its arguments to be true, for the entire statement to become true.
The implication is possibly the one connective in this list, which is the easiest misleading. Maybe that is due a conception that an implication describes a causal relationship. Let A and B here be statements again:
Definition: The implication A → B of A and B is the statement, which is false exactly if A is true and B is false ([1], p. 19).
That means, an implication will always produce a value of true, unless its first operand is true and its second operand is false. It may seem like an arbitrarily specific condition. But put in different words: You can never imply something wrong from a correct statement.
It is important to understand, that an implication is a directional statement and that an implication does not automatically determine that the reverse statement B → A were also true or false, respectively. What colloquially is often described as an implication, actually is determined via equivalence. Be A and B both statements again:
Definition: The equivalence A ↔ B of A and B is the statement, which is true exactly if A and B are both true, or if A and B are both false ([1], p. 20).
An equivalence still does not establish a causal relationship between its operands.
So, given again the example from the beginning: If 12 ≥ 9, then 6 ≥ 7 and 2 × 2 = 4. We can replace the individual statements with variables, to make it easier:
“If A, then B and C”, where A is 12 ≥ 9, B is 6 ≥ 7, and C is 2 × 2 = 4. Written in proper formal notation:
(1) A → (B ∧ C)
This statement is composed of an implication and a conjunction. The implication is true, as long as (B ∧ C) is not false, while A is true. If A were false, then statement (1) would always be true. (B ∧ C) is true, exactly when both B and C are true. We evaluate the statements A, B, and C as follows:
A: 12 ≥ 9 is true
B: 6 ≥ 7 is false
C: 2 × 2 = 4 is true
Inserting these back into statement (1):
(2) true → (false ∧ true)
The parentheses (false ∧ true) evaluate to false:
(3) true → false
As this is the only scenario, for which a logical implication returns false, our entire statement is false. We did not look once at the whether “if A, then B” is a sensible statement from a causal point of view. Consider, if we had changed the above statement to: If 12 ≥ 9, then 7 ≥ 7 and 2 × 2 = 4. According to the rules that we have established further above, this statement is in fact true, even though none of the individual statements are conditionally related to each other.
Remember when I said, the statement were “false, but probably not for entirely obvious reasons”?
Logical Quantifiers
From a logical perspective, there are only three quantities that are essential to describe the realm of validity of a statement: None, at least one and all. The prior two are in fact two instances of the same property. None is synonymous with not one. Why is it not that none and all are opposites to each other instead? If you negate all to not all, it still leaves room for a quantity of perhaps some to which a given statement may apply. Negating at least one to not at least one negates the existence of the property in question definitively, no matter to how few elements at least one has referred to in the first place. That means effectively, there are two fundamental quantities and their corresponding negations.
Existential Quantifier
The existence of something is mathematically expressed through the symbol ∃. How is this relevant for logical statements? Well, sometimes we would like to express, that there exists definitely at least one instance of something with a specific property. Or other times we would like to limit a statement by saying “If there is at least one thing with property X…”.
Definition: Existential quantifier ∃: The symbol ∃ is verbally expressed through “There exists” ([1], p. 23).
Mentally you can always insert the words “at least one” to make the meaning of this phrase unambiguous for even non-Mathematicians. As mentioned, quantifiers are usually used in the context of “There exists a x with property X”:
(4) ∃x: X
For example as in this phrase:
(5) ∃n ∈ ℕ: n = 1
It reads: “There exists at least one natural number n, which is equal to 1.”
Universal Quantifier
Distinct from the mere existence of an element with a property, is the ubiquity of a property in a group of certain elements.
Definition: Universal quantifier ∀: The symbol ∀ is verbally expressed through “For all” ([1], p. 23).
The universal quantifier complements the above case of the existential quantifier, as:
(6) ∀x: X
Which reads: “For all x with property X”. Applied to the example with natural numbers:
(7) ∀n ∈ ℕ: n > 0
It means: “For all natural numbers n, the relation n > 0 holds true”. An example for a true statement using both existential and universal quantifiers would be:
(8) ∃n ∈ ℕ: (∀m ∈ ℕ: n ≤ m) (cf. [1], p. 24)
Verbally expressed it reads: “There is a natural number n, for which the relation n ≤ m holds for any natural number m.” The statement would not be true, if at least m were allowed to also be a negative number.
Negating Quantifiers
We touched the subject when introducing the concept of logical quantifiers. The opposite of “All x have property X” is not “No x have property X”. The foolproof way to get to the logically correct negation of a logical statement is to invert the quantifier from existential to universal quantifier or vice-versa and then to negate the adherent statement.
A statement, such as ∃x: X would negate to ∀x: ¬X.
Negating the statement ∀x: X yields ∃x: ¬X.
In other words: The negation of “There is a x with X” is “¬X holds for all x”. The negation of the statement “X holds for all x” is “There is at least one x for which ¬X holds”. Lets apply our knowledge to negate statement (8):
The statement is composed of three individual statements A, B, and C. Unnesting the statements will make the procedure clearer:
(9) A: ∃n ∈ ℕ: B
(10) B: ∀m ∈ ℕ: C
(11) C: n ≤ m
Negating A means to invert the existential quantifier to a universal quantifier and then negating statement B. Therefore:
(12) ¬A: ∀n ∈ ℕ: ¬B
Hence, we naturally also have to negate B by flipping the universal quantifier and negating C:
(13) ¬B: ∃m ∈ ℕ: ¬C
What is the negation of the statement n ≤ m? We have not covered that topic at this point, because it is actually not a question that formal logic would be meant to answer, but rather set theory. The complement of a set specified by a property is the set of all elements, to which this property does not apply.
(14) ¬C: n > m
Putting it all together, we come to the negation of the entire statement:
(15) ∀n ∈ ℕ: (∃m ∈ ℕ: n > m)
The statement “There is a natural number n, for which the relation n ≤ m holds for any natural number m” negates to “For all natural numbers n, there is a natural number m for which the relation n > m holds”. Incidentally — and unsurprisingly — this statement is not true, as it produces a contradiction for the very possible scenario in which n = 1.
Conclusion
Congratulations for making it this far! Feel free to have yourself a cookie — you earned it. Together we just laid out our basic tool set to understand how to approach mathematical reasoning, and we have everything now that we need, to move on to mathematical induction, discussing proofs and hard evidence.
In the next article, we will question unquestionable truths. We will discuss proof techniques. And ultimately, we will prevail. Stay tuned!
References
[1] L. Unger: Mathematische Grundlagen: Grundlagen. Kurseinheit 1, Volume 1, FernUniversität, Hagen, 2019.
