Basic Logic, Lecture 9

Luca Incurvati

[email protected]

Luca Incurvati ([email protected]) Basic Logic 9 1 / 32

 Outline

1 Introducing second-order logic

2 The language of second-order logic

3 The semantics of second-order logic

4 A deductive system for second-order logic

Luca Incurvati ([email protected]) Basic Logic 9 2 / 32

 Introducing second-order logic

From first- to second-order logic

Consider the following argument:

George Boolos is a a great logician
George Boolos is a great philosopher
So, something is both a great logician and a great philosopher
We can translate this informally valid argument into a formally valid
argument of first-order logic as follows:
Fa
Ga
So, ∃x(Fx ∧ Gx)

Luca Incurvati ([email protected]) Basic Logic 9 3 / 32

 Introducing second-order logic

From first- to second-order logic

Now consider the argument:

George Boolos is a a great logician
Julia Robinson is a great logician
So, there is something that both George Boolos and Julia Robinson are
We cannot translate this informally valid argument into a formally
valid argument of first-order logic.
The problem is that in first-order logic we can only quantify into
name position (‘nominal position’).

Luca Incurvati ([email protected]) Basic Logic 9 4 / 32

 Introducing second-order logic

From first- to second-order logic

We can solve this problem by allowing quantification into predicate

position.
We replace the predicate constants with variables and allow
quantifiers to bind these variables.
Quantification into predicate position is known as second-order
quantification.
Thus, we can translate the second argument into the formally valid
argument of second-order logic as follows:
Fa
Gb
So, ∃X (Xa ∧ Xb)

Luca Incurvati ([email protected]) Basic Logic 9 5 / 32

 The language of second-order logic

1 Introducing second-order logic

2 The language of second-order logic

3 The semantics of second-order logic

4 A deductive system for second-order logic

Luca Incurvati ([email protected]) Basic Logic 9 6 / 32

 The language of second-order logic

Vocabulary

1 Individual variables: x, y , z, . . . (denumerably infinitely many)

2 Predicate variables: X 1 , Y 1 , Z 1 , . . . X 2 , Y 2 , Z 2 , . . . (denumerably
infinitely many for each degree; superscripts indicate the degree of the
predicate variable)
3 Non-logical constants:
individual constants: a, b, c, . . . (denumerably infinitely many).
predicates: denumerably infinitely many for each degree; we’ll use F
and G as examples of monadic predicates and R as an example of a
dyadic one.
4 Logical constants:
sentential connectives: ¬, ∨, ∧, →
quantifiers: ∀, ∃
5 Auxiliary symbols: (, )

Luca Incurvati ([email protected]) Basic Logic 9 7 / 32

 The language of second-order logic

Grammar

As in the first-order case, we need to characterize the set of sentences

of second-order logic.
As before, we first need to define the notion of a formula, and then
that a of a sentence in terms of it.
The notion of a formula is in turn defined in terms of the notion of an
atomic formula (defined in terms of the notion of a term).

Luca Incurvati ([email protected]) Basic Logic 9 8 / 32

 The language of second-order logic

Grammar

As in the first-order case, we need to characterize the set of sentences

of second-order logic.
As before, we first need to define the notion of a formula, and then
that a of a sentence in terms of it.
The notion of a formula is in turn defined in terms of the notion of an
atomic formula (defined in terms of the notion of a term).
But in the second-order case, we allow predicate variables (as well as
predicate constants) to appear in atomic formulas and after ‘∃’ and
‘∀’.

Luca Incurvati ([email protected]) Basic Logic 9 8 / 32

 The language of second-order logic

The chain of definitions

Definition (Term of LSOL )

The terms of LSOL are the individual variables and individual constants.

Definition (Atomic Formula of LSOL )

An expression of LSOL is an atomic formula iff it consists of a predicate
constant or predicate variable of degree n followed by n terms.

Luca Incurvati ([email protected]) Basic Logic 9 9 / 32

 The language of second-order logic

The chain of definitions

Definition (Term of LSOL )

The terms of LSOL are the individual variables and individual constants.

Definition (Atomic Formula of LSOL )

An expression of LSOL is an atomic formula iff it consists of a predicate
constant or predicate variable of degree n followed by n terms.

The notion of a formula is defined by recursion.

Luca Incurvati ([email protected]) Basic Logic 9 9 / 32

 The language of second-order logic

The chain of definitions

Definition (Formula of LSOL )

(i) Every atomic formula of LSOL is a formula of LSOL ;

(ii) If ϕ is a formula of LSOL , then so is ¬ϕ.
(iii) If ϕ and ψ are formulas of LSOL , then so are (ϕ ∨ ψ), (ϕ ∧ ψ),
(ϕ → ψ).
(iv) If ϕ is a formula of LSOL , α is a variable (either individual or
predicate), ϕ contains at least one occurrence of α and ϕ contains
neither ∀α nor ∃α, then ∀αϕ and ∃αϕ are formulas of LSOL ;
(v) Nothing else is a formula of LSOL .

Luca Incurvati ([email protected]) Basic Logic 9 10 / 32

 The language of second-order logic

The chain of definitions

Definition (Bound and free occurrences of variables of LSOL )

An occurrence of a variable α (either individual or predicate) in a formula
ϕ of LSOL is bound iff it is within an occurrence in ϕ of the form ∀αψ or
of the form ∃αψ. Otherwise it is free.

Luca Incurvati ([email protected]) Basic Logic 9 11 / 32

 The language of second-order logic

The chain of definitions

Definition (Bound and free occurrences of variables of LSOL )

An occurrence of a variable α (either individual or predicate) in a formula
ϕ of LSOL is bound iff it is within an occurrence in ϕ of the form ∀αψ or
of the form ∃αψ. Otherwise it is free.

Finally, we can define the notion of a sentence:

Definition (Sentence of LSOL )

A sentence of LSOL is a formula of LSOL in which no variables occur free.

Luca Incurvati ([email protected]) Basic Logic 9 11 / 32

 The semantics of second-order logic

1 Introducing second-order logic

2 The language of second-order logic

3 The semantics of second-order logic

4 A deductive system for second-order logic

Luca Incurvati ([email protected]) Basic Logic 9 12 / 32

 The semantics of second-order logic

Introducing the semantics of second-order logic

As before, to give a semantics for second-order logic, we need to

define the notion of an interpretation and the notion of truth in an
interpretation.
In fact, we will look at two ways of doing this: full or standard
semantics and Henkin or non-standard semantics.
In both cases, we proceed in a very similar fashion to the first-order
case and use the β-variant method to define the notion of truth in an
interpretation.
As we shall see, the difference between full semantics and Henkin
semantics lies in the notion of interpretation adopted.

Luca Incurvati ([email protected]) Basic Logic 9 13 / 32

 The semantics of second-order logic

Full semantics: the notion of an interpretation defined

In the case of full semantics, the interpretations are just the

interpretations of first-order logic:

Definition (Full interpretation of SOL)

A full interpretation I of SOL is an ordered pair hD, Vi, where D is a
non-empty set of objects and V a function which assigns a member of D
to each individual constant and a set of n-tuples of objects from D to each
n-place predicate constant. We call D the domain of the interpretation
and V its valuation function.

Luca Incurvati ([email protected]) Basic Logic 9 14 / 32

 The semantics of second-order logic

Truth in an interpretation and second-order quantifiers

The definition of truth in an interpretation is a natural extension of

the definition for first-order logic, and is the same for both full
semantics and Henkin semantics.
The clauses for atomic sentences and the sentential connectives carry
over from the first-order case.
The clauses for sentences of the form ∀αψ and ∃αψ are also the
same, except that α can now be either an individual variable or a
predicate variable.

Luca Incurvati ([email protected]) Basic Logic 9 15 / 32

 The semantics of second-order logic

The β-variant method again

We introduced the β-variant method to explicate the idea that a

sentence such as ‘∀xFx’ is true in an interpretation I iff ‘Fx’ is true
for every value of ‘x’.

Luca Incurvati ([email protected]) Basic Logic 9 16 / 32

 The semantics of second-order logic

The β-variant method again

We introduced the β-variant method to explicate the idea that a

sentence such as ‘∀xFx’ is true in an interpretation I iff ‘Fx’ is true
for every value of ‘x’.
Strategy: we replace the variable with an individual constant to make
an ‘instance’ of ‘∀xFx’.
We then go through all interpretations I ? which differ from I only in
the object they assign to the individual constant.
We take the quantified statement to be true in I just in case the
instance is true in all interpretations I ? .

Luca Incurvati ([email protected]) Basic Logic 9 16 / 32

 The semantics of second-order logic

The β-variant method again

We want a sentence such as ‘∀XXa’ to be true in an interpretation I

iff ‘Xa’ is true for every value of ‘X ’.
Again, we use the β-variant method to explicate this idea, and extend
the strategy of the previous slide to the case of predicate variables.
N.B.: The values of predicate variables differ depending on their
degree: predicate variables of degree 1 are assigned subsets of the
domain; predicate variables of degree 2 are assigned sets of ordered
pairs of objects from the domain; etc.

Luca Incurvati ([email protected]) Basic Logic 9 17 / 32

 The semantics of second-order logic

The β-variant method again

Strategy: We replace the predicate variable with a predicate constant

to make an ‘instance’ of ‘∀XXa’.
We then go through all interpretations I ? which differ from I only in
the extension (in this case: subset of the domain) they assign to the
predicate constant.
The truth or falsity of the instance in these interpretations determines
the truth or falsity of the quantified statement: the statement is true
in I just in case the instance is true in all interpretations I ? .
This makes it clear that we need to redefine the notion of a β-variant
interpretation.

Luca Incurvati ([email protected]) Basic Logic 9 18 / 32

 The semantics of second-order logic

β-variants for second-order logic defined

Definition (β-variant for SOL)
Let β be an individual constant or a predicate constant. Then
interpretation I ? is a β-variant of interpretation I iff I ? and I differ, if
at all, only in their assignment to β (that is, the assignment by their
valuation functions to β).

As before, note that an interpretation is a β-variant of itself.

Luca Incurvati ([email protected]) Basic Logic 9 19 / 32

 The semantics of second-order logic

β-variants for second-order logic defined

Definition (β-variant for SOL)
Let β be an individual constant or a predicate constant. Then
interpretation I ? is a β-variant of interpretation I iff I ? and I differ, if
at all, only in their assignment to β (that is, the assignment by their
valuation functions to β).

As before, note that an interpretation is a β-variant of itself.

ψ[β/α]
For any formula ψ, variable α (of either sort) and constant of the same
type as α, ψ[β/α] is the result of replacing all free occurrences of α in ψ by
β.

As before, we fix on the first constant of the appropriate type not

appearing in ψ.
Luca Incurvati ([email protected]) Basic Logic 9 19 / 32
 The semantics of second-order logic

Truth in an interpretation defined

We can now define the notion of truth in an interpretation:

Definition (Truth in an interpretation of SOL)

(i) Let θn be an n-place predicate and γ1 , γ2 , . . . be individual constants.

If ϕ is an atomic sentence θn γ1 , γ2 , . . . , γn , then ϕ is true in I iff
hV(γ1 , V(γ2 ), . . . , V(γn )i ∈ V(θn ).
(ii) If ϕ is ¬ψ, then ϕ is true in I iff ψ is not true in I.
(iii) If ϕ is ψ ∧ χ, then ϕ is true in I iff ψ is true in I and χ is true in I.

Luca Incurvati ([email protected]) Basic Logic 9 20 / 32

 The semantics of second-order logic

Truth in an interpretation defined

(iv) If ϕ is ψ ∨ χ, then ϕ is true in I iff ψ is true in I or χ is true in I.

(v) If ϕ is ψ → χ, then ϕ is true in I iff ψ is not true in I or χ is true in
I.
(vi) If ϕ is ∀αψ, then ϕ is true in I iff ψ[β/α] is true in every β-variant of
I.
(vii) If ϕ is ∃αψ, then ϕ is true in I iff ψ[β/α] is true in some β-variant of
I.

Luca Incurvati ([email protected]) Basic Logic 9 21 / 32

 The semantics of second-order logic

On the interpretations of full semantics

The interpretations of full semantics are the same as those of

first-order logic because once we specify the domain of the individual
variables, this determines the domain of the predicate variables (for
each degree):

1 For predicates of degree 1, the domain consists of all subsets of the

domain of the individual variables.
2 For predicates of degree 2, the domain consists of all sets of ordered
pairs of objects from the domain of the individual variables.
3 Etc.

Luca Incurvati ([email protected]) Basic Logic 9 22 / 32

 The semantics of second-order logic

On the interpretations of Henkin semantics

In the case of Henkin semantics, on the other hand, we specify the

domain of the predicate variables of each degree separately.
As a result, the domain of the predicate variables is as follows:

1 For predicates of degree 1, the domain consists of some subsets of

the domain of the individual variables.
2 For predicates of degree 2, the domain consists of some sets of
ordered pairs of objects from the domain of the individual variables.
3 Etc.

Luca Incurvati ([email protected]) Basic Logic 9 23 / 32

 The semantics of second-order logic

Henkin semantics: the notion of an interpretation defined

More precisely, in Henkin semantics the notion of an interpretation is

defined thus:

Definition (Henkin interpretation of SOL)

A Henkin interpretation I of SOL is a structure hD, S, Vi, where
D is a non-empty set of objects;
S is a sequence of sets such that S1 is a non-empty subset of the
powerset of D, S2 is a non-empty subset of the set of all sets of
ordered pairs of objects from D, and so on;
V is a function which assigns a member of D to each individual
constant and a member of Sn to each n-place predicate constant.
We call D the domain of the interpretation, S its sequence of
second-order domains and V its valuation function.

Luca Incurvati ([email protected]) Basic Logic 9 24 / 32

 The semantics of second-order logic

On the range of the second-order variables

On both full and Henkin semantics, the items in the range of the
second-order variables are sets or sets of n-tuples.
When one motivates second-order logic, however, one usually talks as
if the things we are quantifying over are properties, relations, etc.

Luca Incurvati ([email protected]) Basic Logic 9 25 / 32

 The semantics of second-order logic

On the range of the second-order variables

On both full and Henkin semantics, the items in the range of the
second-order variables are sets or sets of n-tuples.
When one motivates second-order logic, however, one usually talks as
if the things we are quantifying over are properties, relations, etc.
But one can maintain that the values of the second-order variables
are properties or relations whilst using full or Henkin semantics: the
idea is that we use sets as surrogates for properties or relations.
One reason for doing this is that there is no symbol for identity
between second-order entities in the language, for we have built
things so that we are only allowed to put predicate constants or
variables in predicate position.
Thus, even if different properties or relations can be extensionally
equivalent, there is no way to express their distinctness in the
language of second-order logic.
Luca Incurvati ([email protected]) Basic Logic 9 25 / 32
 A deductive system for second-order logic

1 Introducing second-order logic

2 The language of second-order logic

3 The semantics of second-order logic

4 A deductive system for second-order logic

Luca Incurvati ([email protected]) Basic Logic 9 26 / 32

 A deductive system for second-order logic

Obtaining a deductive system for second-order logic

A deductive system for second-order logic is obtained by extending a

deductive system for first-order logic with appropriate axioms/rules
involving predicate variables.
We need to pick such a deductive system; say we we use the natural
deduction system for first-order logic we have been using.
The first thing to do is add rules for the second-order quantifiers: it is
straightforward to adapt the rules for the first-order quantifiers to the
second-order case.

Luca Incurvati ([email protected]) Basic Logic 9 27 / 32

 A deductive system for second-order logic

The rules for the second-order quantifiers

ϕ n n
∀2 I ∀α ϕ(α )
n
∀α ϕ n ∀2 E
ϕ(θ )

[ϕ]

ϕ(θn ) ..
2 .
∃αn ϕ ∃ I ∃αn ϕ ψ
∃2 E
ψ

Here αn is a n-degree second-order variable and θn is an n-place

predicate constant; in the case of ∀2 I and ∃2 E , we impose the usual
restrictions.

Luca Incurvati ([email protected]) Basic Logic 9 28 / 32

 A deductive system for second-order logic

The Comprehension Scheme

Next, we usually have the Axiom Scheme of Comprehension:

∃X n ∀x1 , . . . , xn (X n x1 , . . . , xn ↔ ϕ(x1 , . . . , xn )),

where X n may not occur free in ϕ.

For n = 1, this says that every open formula of the form ϕ(x)
determines a set whose members are all and only the objects which
are ϕ.
For n = 2, this says that every open formula of the form ϕ(x, y )
determines a set whose members are all and only the ordered pairs of
objects which stand in the relation ϕ.
And so on.

Luca Incurvati ([email protected]) Basic Logic 9 29 / 32

 A deductive system for second-order logic

The Axiom of Choice

Finally, it is also customary to include (a version of) the Axiom of

Choice:
∀X n+1 (∀x1 , . . . , ∀xn ∃yX n+1 x1 , . . . , xn y →
∃f n ∀x1 , . . . , ∀xn X n+1 x1 , . . . , xn f (x1 , . . . , xn ))
where X n may not occur free in ϕ.
For n = 1, this says, of any dyadic relation R, that if for any object x
there is an object y which is R-related to it, then there is a function
which ‘chooses’ one object which is R-related to x, for each x (a
choice function).

Luca Incurvati ([email protected]) Basic Logic 9 30 / 32

 A deductive system for second-order logic

Comprehension, Choice and the choice of semantics

The deductive system just outlined is not sound for Henkin semantics:
there are Henkin interpretations in which instances of the
Comprehension Scheme and the Axiom of Choice are false.
For this reason, it is customary to restrict attention to faithful Henkin
interpretations – Henkin interpretations in which each instance of the
Comprehension Scheme and the Axiom of Choice are true.

Luca Incurvati ([email protected]) Basic Logic 9 31 / 32

 A deductive system for second-order logic

Comprehension, Choice and the choice of semantics

The deductive system just outlined is not sound for Henkin semantics:
there are Henkin interpretations in which instances of the
Comprehension Scheme and the Axiom of Choice are false.
For this reason, it is customary to restrict attention to faithful Henkin
interpretations – Henkin interpretations in which each instance of the
Comprehension Scheme and the Axiom of Choice are true.
On the other hand, the deductive system outlined is sound for full
semantics.
The reason is simply that the Comprehension Scheme and the Axiom
of Choice assert the existence of certain subsets of (or sets of n-tuples
from) the (first-order) domain.
And in full semantics the range of the predicate variables will contain
all subsets (or sets of n-tuples from) that domain.

Luca Incurvati ([email protected]) Basic Logic 9 31 / 32

 A deductive system for second-order logic

References

On language, semantics and deductive systems:

D.van Dalen, Logic and Structure, Ch. 4.
S.Shapiro, Foundations without Foundationalism, Ch. 3.
S.Shapiro, ‘Higher-order logic’, in S.Shapiro (ed.), The Oxford
Handbook of Philosophy of Mathematics and Logic.
S.Shapiro, ‘Classical logic II: higher-order logic’, in L.Goble (ed.), The
Blackwell Guide to Philosophical Logic

Luca Incurvati ([email protected]) Basic Logic 9 32 / 32