jnc-tutorial

Intey

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

14 pages

English

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Informations

Publié par	Intey
Nombre de lectures	18
Langue	English

Extrait

What is mathematical logic? A survey
1John N. Crossley
School of Computer Science and Software Engineering,
Monash University, Clayton, Victoria, Australia 3800
John.Crossley@infotech.monash.edu.au
1 Introduction
Whatismathematicallogic?Mathematicallogicistheapplicationofmathemat-
ical techniques to logic.
Whatislogic?IbelieveIamfollowingtheancientGreekphilosopherAristotle
when I say that logic is the (correct) rearranging of facts to ﬁnd the information
that we want.
Logic has two aspects: formal and informal. In a sense logic belongs to ev-
eryone although we often accuse others of being illogical. Informal logic exists
whenever we have a language. In particular Indian Logic has been known for a
very long time.
Formal(oftencalled,‘mathematical’)logichasitsoriginsinancientGreecein
theWestwithAristotle.Mathematicallogichastwosides:syntaxandsemantics.
Syntax is how we say things; semantics is what we mean.
By looking at the way that we behave and the way the world behaves, Aris-
totle was able to elicit some basic laws. His style of categorizing logic led to the
notion of the syllogism.
The most famous example of a syllogism is
All men are mortal
Socrates is a man
[Therefore] Socrates is mortal
Nowadays we mathematicians would write this as
∀x(Man(x)→ Mortal (x))
Man(S) (1)
Mortal (S)
One very general form of the above rule is
A (A→B)
(2)
B
otherwise know as modus ponens or detachment: the A is ‘detached’ from the
formula (A→B) leaving B. This is just one example of a logical rule.This rule, and other rules of logic such as
(A∧B)A B
or
(A∧B) A
where ∧ is read ‘and’, have obvious interpretations. These rules come from ob-
serving how we use concepts.
This analytic approach was that taken by George Boole, an Irish mathemati-
cian in the nineteenth century. It is from his work that we have Boolean algebra
or Boolean logic or, as it is often known today, propositional calculus.
Later in the nineteenth century Gottlob Frege developed a small suite of
logical laws that are with us today and suﬃce for all of mathematics. These are
the rules of the predicate calculus. The rules relate only to the syntax. Although
they are abstracted from the way we talk and think, the meaning, the semantics,
is something quite separate.
The most familiar example of semantics is given by truth-tables such as the
one for conjunction (or ‘and’,∧):
∧ T F
T T F
F F F
Here we are given the truth-values of the formulaeA andB and we work out the
truth of the conjunction (A∧B) by taking the value for A at the side and the
value for B at the top and ﬁnding the value where column and row intersect.
In general, determining the truth of a syntactic expression (formula) A requires
looking carefully at its constituents.
At this point we should pause because we are now dealing with two com-
pletely diﬀerent things, two diﬀerent aspects of languages.
Ontheonehandwehavetherulesforworkingwithstringsofsymbols–rules
suchas modus ponensabove;ontheotherhandwearelookingatmeanings.This
latter is the study of semantics. The former is syntax – the study of the way that
language is put together from symbols. In English this latter includes the way
we put words together to make a sentence.
Consider something we, in essence, wrote earlier (in (1)), or rather a slight
variant of it.
∀x(M(x)→D(x)) (3)
IfM(x) is interpreted as ‘x is a man’ andD(x) as ‘x will die’, then this formula
is obviously true under this interpretation. However, if we interpret M(x) as ‘x
is an animal’ and D(x) as ‘x has at most two legs’, then it is obviously false
under this diﬀerent interpretation.
Note that the formula itself is neither true nor false, it is a formula – a piece
of syntax.
22 Syntax and Semantics
The ﬁrst concern of mathematical logic is the relation between syntax and se-
mantics.
First let us consider syntax a little more closely.
Any logic starts from certain basic symbols. In ordinary mathematical logic,
and I will say what ‘ordinary’ means later in Section 4, we have symbols (letters)
for variables:x,y,z,... andletters for predicates or properties, such asM andD
above. We also have letters for relations and functions. For example,L(x) might
arise in a context: ‘there is a line between the points x and y’, or in a context
‘x is married to y’. We use small letters for functions, f ,f .... Such arise in1 2
arithmetic where we may usef for +, or have a functioni, say, in group theory1
that is intended to denote the inverse of an element. Applying these function
letters (perhaps repeatedly) gives rise to (individual) terms.
Together all of these give us atomic formulae – basic formulae such asL(x,y)
or M(f (x,f (y ))) or D(y).3 1 2
Atomic formulae can the be joined together by logical connectives to form
more complicated formulae, sometimes called ‘well-formed formulae’, such as
(M(x)∧D(y)) or (M(x)→D(x)) or ∀x(M(x)→D(x)).
These have been joined using connectives: propositional connectives ∧ (read as
‘and’), ∨ (read as ‘or’), → (read as ‘implies’), ¬ (read as ‘not’); and the quan-
1tiﬁers: ∀ (read as ‘for all’) and ∃ (read as ‘there exists’). The precise rules for
constructing formulae can be found in any logic textbook, such as [21].
Wethenhaverulesforgeneratingmoreformulae.Wehavealreadymetmodus
ponens in (2). This rule is also know as implication elimination, (→-E): the →
above the line is eliminated below it.
2In Fig. 1 we give the rules which were discovered in the late nineteenth cen-
turybyFrege(thoughLeibnizknewmanyofthemlongbeforeintheseventeenth
century). The formulation here is known as Natural Deduction since the rules
(with two exceptions) look very close to our actual practice in reasoning. In this
formulation we do not have axioms but we may have hypotheses, i.e. formulae
that we assume. Here an expression such asΔ,A‘B is read ‘from the formulae
in Δ and the formula A we can prove the formula B’.
The rules should be easy to read with at most two exceptions. These are
(∨-E) and (∃-E). The former corresponds to proof by cases. We can paraphrase
it as follows: ‘If, from A we can prove C and from B we can prove C, then we
can prove C from (A∨B)’. Likewise (∃-E) can be paraphrased as: ‘If we can
prove C from some particular x such that P (with x replacing y), and we can
also prove that there is some y such that P, then we can prove C’.
1 Somepeopleavoidusingnegation,¬.Theyemployaconstant⊥forthefalseformula.
Then they use the formula (A→⊥) instead of ¬A.
2 The phrase ‘x is free/not free in [some formula]’ is a technical condition that avoids
misunderstandings.
3(Axiom-I) (Ass-I)
‘A A‘A
0Δ‘A Δ ‘ (A→B)Δ,A‘B
(→-I) (→-E)
0Δ‘ (A→B) Δ,Δ ‘B
Δ‘∀x.AΔ‘A (∀-I) (∀-E)
Δ‘∀x.A Δ‘A[c/x]
x is free in A, not free in Δ
Δ‘P[a/y] Δ ‘∃y.P Δ ,P[x/y]‘C1 2
(∃-I) (∃-E)
Δ‘∃y.P Δ ,Δ ‘C1 2
where x is not free in C
0Δ‘A Δ ‘B (∧-I)
0Δ,Δ ‘ (A∧B)
Δ‘ (A ∧A ) Δ‘ (A ∧A )1 2 1 2
(∧-E ) (∧-E )1 2
Δ‘A Δ‘A1 2
Δ‘A Δ‘A1 2
(∨-I ) (∨-I )1 2
Δ‘ (A ∨A ) Δ‘ (A ∨A )1 2 1 2
Δ‘ (A∨B) Δ ,A‘C Δ ,B‘C1 2
(∨-E)
Δ ,Δ ,Δ‘C1 2
Δ‘⊥ (⊥-E)
Δ‘A
Fig.1. The basic rules of predicate calculus.
It is obvious that these rules are ‘good’ rules if we just interpret them in an
intuitive way. That is to say, when so interpreted they lead from true assertions
to other true assertions.
We build proofs by repeatedly applying the rules. Since some of the rules
have two premises (top lines) we actually get a tree. The tree is a proof of the
formula at the root of the tree.
3 The Completeness Theorem and Model Theory
It should be quite surprising that when we analyze the sort of language we use
in mathematics, and elsewhere too, that the few basic rules, given above and
originally due to Frege, suﬃce to yield all those syntactic expression that are
always true – and no others. This is the most dramatic result that mathematical
logic produced in the ﬁrst half of the twentieth century:
4Theorem 1 (The Completeness Theorem). There is a ﬁnite (small) set of
logical rules which will yield all, and only, those formulae which are true under
any interpretation.
What is an interpretation? We have given a hint when discussing (3) above.
First we have to establish what domain we are talking about, e.g. people, or
natural numbers. Then we have to interpret the predicates in the language and
these will usually be interpreted as relations, one such example in the case of
numbers is the relation ≤. Here is a diﬀerent example. If we have a language
involving P(x,y) and we consider interpreting this predicate P as ‘x divides y
and we only allow x,y, etc. to be interpreted as natural numbers, then we can
see that
(P(x,y)∧P(y,z))→P(x,z)
is always true.
On the other hand
(P(x,y)∨P(y,x)) (4)
is sometime true and sometimes false, while
∀x¬P(x,x) (5)
is false since every number divides itself.
However if we interpret P(x,y) as ‘y is strictly greater than x’, then (4) is
sometimes true and sometimes false and (5) is true.
If we go to a completely diﬀerent interpretation and let the variables range
over human beings and now interpret P(x,y) as ‘x is married to y’ then we get
diﬀerent results.
Theactualformaldeﬁnitionof‘trueinaninterpretation’isquitecomplicated
(see e.g. [2