artiface/artiface/ IntroductionToLogic

Introduction to Logic I would summarise modern Mathematical Logic as what happens when mathematics learns to talk about itself. As such, it takes formal logic and turns it into an object of mathematical study, considering theorems and proofs as mathematical objects, much as one has objects such as graphs and sets in more conventional mathematics. But much of the theoretical interest in mathematical logic, especially what is called Arithmetic, lies in the fact that mathematical statements are sufficiently formal that they can be turned into formal logical statements which are, as such, just sequences of symbols from some alphabet. I shall discuss briefly how one builds things from alphabets in the following subsection on First Order Logic.

Propositional calculus I should first point out that by ‘calculus’ here we do not mean what most people (who have studied enough maths) think of by the word ‘calculus’, which is more properly called the ‘differential calculus’, involving rates of change and summation of continuous functions.

The propositional calculus concerns statements and the logical connectives And(∧), Or(∨) and Not(¬). Simple statements have no logical connectives in them and cannot be broken down any further. Compound statements are made up of other statements, simple or compound, by joining them with logical connectives. New statements can be formed from old via rules of inference. Some common rules of inference are the following.

Modus Ponens Example:

Premise 1: If it’s raining then it’s cloudy. Premise 2: It’s raining. Conclusion: It’s cloudy.

Form:

Premise 1: P → Q Premise 2: P Conclusion: Q

In symbols:

P→Q,P ⊢ Q

De Morgan’s Laws ¬(A∧B) ↔ (¬A)∨(¬B)

¬(A∨B) ↔ (¬A)∧(¬B)

Quantifiers One thing we cannot express in the propositional calculus is statements like ‘all cats are animals’. Here the issue is the word ‘all’. By saying “all X’s are Y’s”, we are quantifying over collections, such as numbers or animals. There are two main quantifiers used in mathematical logic, ‘for all‘ (for which we use the symbol ∀), and ‘there exists‘ (for which we use the symbol ∃). We can use this to express the feature of counting numbers that no matter how high we count, we can always count higher:

For all counting numbers x, there exists a counting number x + 1

∀x∈ℕ ∃y∈ℕ y=x+1

First Order Logic First Order Logic is perhaps the simplest form of logic with quantifiers. In First Order Logic, all quantifiers quantify over the same collection. (So if one quantifier is talking about natural numbers, as we had above when we wrote ∀x∈ℕ, then all quantifiers must talk about natural numbers.) As such our sentence above becomes simply

∀x∃y y=x+1

It is interesting to note that most modern mathematics is expressible and provable using first order logic, the symbols for our basic arithmetical operations, +, -, ×, /, where quantifiers range over the natural numbers. (This formalised arithmetic is known as Peano Arithmetic.)

Symbols We now discuss how formulae and sentences in First Order Logic are constructed. We begin with symbols, the indivisible units of what we can write down. In the case of arithmetic these are +, -, ×, /, <, ∀, ∃, ¬ and a collection of as many variables as we wish, denoted x1, x2, …, xi, …. All formal sentences and formulae are made up of these symbols, and only these symbols. We call a collection of symbols an alphabet. Traditionally Σ is used to denote an alphabet.

Strings Much as happens in modern programming languages, symbols are combined into sequences known as strings. For example, with the alphabet of symbols used in arithmetic, we could form the string x4<<y+-3+4. Not all strings make sense. For that we introduce the notion of a language. Given an alphabet Σ, the collection of all strings we can build from that alphabet is denoted by Σ*.

Languages Formally, given an alphabet Σ, a language ℒ over Σ is simply a collection of strings in Σ*. Elements of ℒ are referred to as sentences. Usually there are a collection of rules defining what sentences occur in a given language. For example, we could say that if a string φ is in ℒ, and another string ψ is also a string in ℒ, then the string “( φ ) + ( ψ )” is also in ℒ. This notion of formal languages is also fundamental to modern programming languages, and indeed there are purpose built tools for translating descriptions of languages into code that can parse them.

Theories To reason about something, we need to have some given sentences as a starting point. Indeed it has been stated that mathematics is the study of statements of the form ‘P implies Q’.

Logical Operations Sentences may be combined using the logical operators ∧ (And, or conjunction), ∨ (Or, or disjunction), and ¬ (Not, or negation). So we may say:

[x > 1] ∧ [x < 5]

meaning ‘x is greater than 1, and x is less than 5’.

We use square brackets where necessary (since round brackets are part of the alphabet of symbols we are dealing with). We also have logical operators for implication, ⇐, ⇒, and ⇔, allowing us to say things like

[x > 2] ⇒ [x > 1]

And we can combine these with quantifiers to say things like

∀x[ [x > 3] ⇒ [(2 × x) > 3] ]

Axioms To reason about things, we need some given starting points: sentences that we assume to be true from the outset. For example, for Peano Arithmetic we may have

0∈ℕ (0 is a number) ∀x[ x∈ℕ ⇒ x+1∈ℕ ] (every number has a successor) ∀x ¬[ x∈ℕ ∧ [ x+1 = 0 ] ] (0 is not the success of any number) …and so on Rules of Inference Given a set of sentences, there are rules of inference that allow us to deduce additional sentences. For example the rule of modus ponens tells us that if P is a true sentence, and P ⇒ Q is a true sentence, then Q is also a true sentence. Some rules of inference are uncontroversial, such as “if A is true, and B is true, then A∧B is true”. On the other hand, the law of the excluded middle, is broadly, but not universally accepted. This law is the foundation of a mathematical technique known as proof by contradiction, whereupon one begins by assuming the contrary of what one wishes to prove, and show that it leads to a contradiction. The reason some mathematicians reject this law, who go under the umbrella heading of constructivists, is that one can prove the existence of mathematical objects in a way which is non-constructive. To illustrate with an example, there is a smallest prime number greater than the number of hairs on my head. Such a number exists, but is impractical to work out. In some cases there are proofs that numbers exist, but which all the computational power available to humanity is not enough to compute.

Set Theory A major part of the foundations of modern mathematics is Set Theory. In its formal sense, set theory is the study of the relation ∈, and what we can do with it. In First Order Set Theory, our quantifiers range over sets, just as in arithmetic our quantifiers range over numbers. Among the usual axioms for Set Theory is the axiom of extensionality, written

∀x ∀y [ ∀z [ z ∈ x ⇔ x ∈ y ] ⇒ x = y ]

which states that two sets are equal if, and only if, they contain the same elements.

Given sets A and B, we can form their intersection, A∩B, union, A∪B, difference, A-B, and symmetric difference (AΔB = (A-B)∪(B-A). These correspond to the logical connectives And, Or, Not and Xor as follows:

x∈A∩B if and only if x∈A And x∈B x∈A∪B if and only if x∈A Or x∈B x∈A-B if and only if x∈A And Not x∈B x∈AΔB if and only if x∈A Xor x∈B Conclusion There is much more that can be said about mathematical logic, such as the discovery of theorems about what can and cannot be proved from a given set of axioms.