Basic Logic, Lecture 4

Luca Incurvati

[email protected]

Luca Incurvati ([email protected]) Basic Logic 4 1 / 42

 Outline

1 Language of FOL

2 Semantics of FOL

3 Deductive system of FOL

4 Variations on first-order logic

Luca Incurvati ([email protected]) Basic Logic 4 2 / 42

 Language of FOL

Vocabulary

The vocabulary of LFOL consists of:

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

2 Non-logical constants:
individual constants: a, b, c, . . . (denumerably infinitely many).
predicates: denumerably infinitely many for each degree; we’ll use F as
an example of a monadic predicate and R as an example of a dyadic
one.
3 Logical constants:
sentential connectives: ¬, ∨, ∧, →
quantifiers: ∀, ∃
4 Auxiliary symbols: (, )

Luca Incurvati ([email protected]) Basic Logic 4 3 / 42

 Language of FOL

Grammar

In first-order logic, atomic sentences have structure but cannot be

decomposed into smaller sentences.
In particular, a quantified sentence such as ‘∀xFx’ is constructed by
appending ‘∀x’ to ‘Fx’, which is not a sentence: it’s a formula.

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

 Language of FOL

Grammar

In first-order logic, atomic sentences have structure but cannot be

decomposed into smaller sentences.
In particular, a quantified sentence such as ‘∀xFx’ is constructed by
appending ‘∀x’ to ‘Fx’, which is not a sentence: it’s a formula.
Hence, to characterize the set of sentences of first-order logic, 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 other auxiliary
notions.

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

 Language of FOL

The chain of definitions

Definition 2.1 (Term of LFOL )

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

Definition 2.2 (Atomic Formula of LFOL )

An expression of LFOL is an atomic formula iff it consists of a predicate
of degree n followed by n terms.

Luca Incurvati ([email protected]) Basic Logic 4 5 / 42

 Language of FOL

The chain of definitions

Definition 2.1 (Term of LFOL )

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

Definition 2.2 (Atomic Formula of LFOL )

An expression of LFOL is an atomic formula iff it consists of a predicate
of degree n followed by n terms.

The notion of a formula is defined by recursion.

Luca Incurvati ([email protected]) Basic Logic 4 5 / 42

 Language of FOL

The chain of definitions

Definition 2.3 (Formula of LFOL )

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

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

Luca Incurvati ([email protected]) Basic Logic 4 6 / 42

 Language of FOL

The chain of definitions

Definition 2.4 (Bound and free occurrences of variables of LFOL )

An occurrence of a variable α in a formula ϕ of LFOL 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 4 7 / 42

 Language of FOL

The chain of definitions

Definition 2.4 (Bound and free occurrences of variables of LFOL )

An occurrence of a variable α in a formula ϕ of LFOL 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 2.5 (Sentence of LFOL )

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

Luca Incurvati ([email protected]) Basic Logic 4 7 / 42

 Semantics of FOL

1 Language of FOL

2 Semantics of FOL

3 Deductive system of FOL

4 Variations on first-order logic

Luca Incurvati ([email protected]) Basic Logic 4 8 / 42

 Semantics of FOL

The notion of an interpretation: the general idea

Recall that the fundamental notion of logical consequence is defined

in terms of the notion of truth in an interpretation.
We want to know when a certain interpretation makes a sentence
true.

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

 Semantics of FOL

The notion of an interpretation: the general idea

Recall that the fundamental notion of logical consequence is defined

in terms of the notion of truth in an interpretation.
We want to know when a certain interpretation makes a sentence
true.
In the propositional case, the answer is easy: an interpretation assigns
truth-values to atomic sentences, and this assignment determines the
truth-value of complex sentences.
In the first-order case, however, interpretations take into account the
structure that atomic sentences may have.

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

 Semantics of FOL

The notion of an interpretation: the general idea

An interpretation for first-order logic assigns objects to individual

constants and sets of objects or ordered n-tuples of objects to
predicates.
For instance, if our language has an individual constant ‘a’ and a
predicate ‘F ’, a given interpretation will assign some object to ‘a’ and
some set of objects to ‘F ’.

Luca Incurvati ([email protected]) Basic Logic 4 10 / 42

 Semantics of FOL

The notion of an interpretation: the general idea

An interpretation for first-order logic assigns objects to individual

constants and sets of objects or ordered n-tuples of objects to
predicates.
For instance, if our language has an individual constant ‘a’ and a
predicate ‘F ’, a given interpretation will assign some object to ‘a’ and
some set of objects to ‘F ’.
This determines the truth of value of ‘Fa’: ‘Fa’ is true in this
interpretation iff the objects it assigns to ‘a’ is a member of the set it
assigns to ‘F ’.
If the predicate has degree n > 1, the interpretation assigns to it a set
of ordered n-tuples. (N.B.: in fact, this will be the case, strictly
speaking, for all predicates.)

Luca Incurvati ([email protected]) Basic Logic 4 10 / 42

 Semantics of FOL

The notion of an interpretation defined

Definition 3.1 (Interpretation of FOL)

An interpretation I of FOL 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 constant and a set of n-tuples to each n-place predicate. We call
D the domain of the interpretation and V its valuation function.

As anticipated, officially we are assigning sets of 1-tuples of elements

of the domain to 1-place predicates. This is just for convenience.

Luca Incurvati ([email protected]) Basic Logic 4 11 / 42

 Semantics of FOL

The problem of quantifiers

In the case of propositional logic, the definition of truth in an

interpretation can be given by simply making the truth-values of
complex sentences depend on the truth-values of their constituent,
less complex sentences.
Thus, we have clauses such as: If ϕ is ψ ∧ χ, then ϕ is true in I iff ψ
is true in I and χ is true in I.

Luca Incurvati ([email protected]) Basic Logic 4 12 / 42

 Semantics of FOL

The problem of quantifiers

In the case of propositional logic, the definition of truth in an

interpretation can be given by simply making the truth-values of
complex sentences depend on the truth-values of their constituent,
less complex sentences.
Thus, we have clauses such as: If ϕ is ψ ∧ χ, then ϕ is true in I iff ψ
is true in I and χ is true in I.
If we ignore quantifiers and variables, we could do something similar
in the first-order case.
All we would have to do is add a clause telling us how the truth-value
of atomic sentences is determined by the assignment of objects to
individual constants and sets of n-tuples to n-place predicates.

Luca Incurvati ([email protected]) Basic Logic 4 12 / 42

 Semantics of FOL

The problem of quantifiers

But if we want to define the notion of truth in an interpretation for

sentences involving quantifiers and variables, things are more
complicated.
The point, again, is that a sentence such as ‘∀xFx’ does not have
constituents which are themselves sentences, and only sentences have
truth-values.

Luca Incurvati ([email protected]) Basic Logic 4 13 / 42

 Semantics of FOL

The problem of quantifiers

But if we want to define the notion of truth in an interpretation for

sentences involving quantifiers and variables, things are more
complicated.
The point, again, is that a sentence such as ‘∀xFx’ does not have
constituents which are themselves sentences, and only sentences have
truth-values.
Still, we want, e.g., the truth-value of ‘∀xFx’ to depend on the
assignment of objects and sets of n-tuples effected by the
interpretation and the meaning of the universal quantifier.
For instance, it is part of the meaning of the universal quantifier that
if ‘∀xFx’ is true in an interpretation I, then ‘¬Fa’ is not true in I.

Luca Incurvati ([email protected]) Basic Logic 4 13 / 42

 Semantics of FOL

Two methods

Two standard methods: Tarski’s method and the β-variant method.

Tarski’s method consists in defining an analogue for truth for formulas
with free variables – the notion of satisfaction – and then defining
truth in terms of it.

Luca Incurvati ([email protected]) Basic Logic 4 14 / 42

 Semantics of FOL

Two methods

Two standard methods: Tarski’s method and the β-variant method.

Tarski’s method consists in defining an analogue for truth for formulas
with free variables – the notion of satisfaction – and then defining
truth in terms of it.
The β-variant method does not assign semantic properties to
formulas with free variables.
Rather, it determines the truth value of quantified sentences in terms
of possible reinterpretations of an individual constant instantiating the
relevant variable.

Luca Incurvati ([email protected]) Basic Logic 4 14 / 42

 Semantics of FOL

The β-variant method

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

iff ‘Fx’ is true for every value of ‘x’: the β-variant method explicates
the idea as follows.

Luca Incurvati ([email protected]) Basic Logic 4 15 / 42

 Semantics of FOL

The β-variant method

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

iff ‘Fx’ is true for every value of ‘x’: the β-variant method explicates
the idea as follows.
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.
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 ? .

Luca Incurvati ([email protected]) Basic Logic 4 15 / 42

 Semantics of FOL

β-variants defined
Definition 3.2 (β-variant)
Let β be an individual 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 β).

Note that an interpretation is a β-variant of itself.

Luca Incurvati ([email protected]) Basic Logic 4 16 / 42

 Semantics of FOL

β-variants defined
Definition 3.2 (β-variant)
Let β be an individual 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 β).

Note that an interpretation is a β-variant of itself.

ψ[β/α]
For any formula ψ, individual variable α and individual constant β, ψ[β/α]
is the result of replacing all free occurrences of α in ψ with β.

We fix on the first individual constant not appearing in ψ. (‘First’ for

definiteness, ‘not appearing in ψ’ because we want β-variants to
preserve the assignment of objects to any individual constant
appearing in ψ.)
Luca Incurvati ([email protected]) Basic Logic 4 16 / 42
 Semantics of FOL

Truth in an interpretation defined

Definition 3.3 (Truth in an interpretation of FOL)

1 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 ).
2 If ϕ is ¬ψ, then ϕ is true in I iff ψ is not true in I.
3 If ϕ is ψ ∧ χ, then ϕ is true in I iff ψ is true in I and χ is true in I.
4 If ϕ is ψ ∨ χ, then ϕ is true in I iff ψ is true in I or χ is true in I.
5 If ϕ is ψ → χ, then ϕ is true in I iff ψ is not true in I or χ is true in
I.
6 If ϕ is ∀αψ, then ϕ is true in I iff ψ[β/α] is true in every β-variant of
I.
7 If ϕ is ∃αψ, then ϕ is true in I iff ψ[β/α] is true in some β-variant of
I.
Luca Incurvati ([email protected]) Basic Logic 4 17 / 42
 Deductive system of FOL

Universal elimination

To obtain a deductive system for first-order logic, we expand the

natural deduction system of PL with four rules, an introduction and
an elimination rule for each of the two quantifiers.

Rule of universal elimination

∀αϕ(α)
∀E
ϕ(γ)

where α is a variable and γ is a constant.

Luca Incurvati ([email protected]) Basic Logic 4 18 / 42

 Deductive system of FOL

Existential introduction

Rule of existential introduction

ϕ(γ)
∃I
∃αϕ(α)

where γ is a constant and α is a variable that does not occur in ϕ(γ).

Luca Incurvati ([email protected]) Basic Logic 4 19 / 42

 Deductive system of FOL

Existential introduction

So we allow:
Raad
∃I
∃xRxad
∃I
∃y ∃xRxyd
But we disallow:
Raad
∃I
∃xRxad
∃I
∃x∃xRxxd

Luca Incurvati ([email protected]) Basic Logic 4 20 / 42

 Deductive system of FOL

Universal introduction

We would like to introduce ∀xFx if we have somehow established, for

every object in the domain, that is F .
We could try to establish this by proving each of Fa1 , Fa2 , . . ., but
since there are infinitely many constants in our language, this attempt
would never come to an end.
Instead, we could try to prove Fb where b is an arbitrary name.
We try to capture this idea by requiring that the name does not occur
in any assumption which is undischarged at the moment where we
apply the rule of inference.

Luca Incurvati ([email protected]) Basic Logic 4 21 / 42

 Deductive system of FOL

Universal introduction

Rule of universal introduction

ϕ(γ)
∀I
∀αϕ(α)

where γ is a constant that does not occur in any undischarged assumption

and α is a variable that does not occur in ϕ(γ).

Luca Incurvati ([email protected]) Basic Logic 4 22 / 42

 Deductive system of FOL

Universal introduction

Clearly, the following argument is bad: Everyone loves Wittgenstein;

therefore everyone loves themselves.
We might symbolise this argument as: ∀xLxa ∴ ∀xLxx. Suppose we
tried to vindicate this with the following deduction:
∀xLxa
∀E
Laa
∀I
∀xLxx
This is disallowed because a occurred already in an undischarged
assumption.

Luca Incurvati ([email protected]) Basic Logic 4 23 / 42

 Deductive system of FOL

Universal introduction

Although the name may not occur in any undischarged assumption, it

may occur in a discharged assumption. For example:
[Fa]1 [Fa]1
∧I
Fa ∧ Fa
∧E
Fa → I1
Fa → Fa
∀I
∀x(Fx → Fx)
So we have that ∀x(Fx → Fx), as it should be.

Luca Incurvati ([email protected]) Basic Logic 4 24 / 42

 Deductive system of FOL

Existential elimination

Rule of existential elimination

[ϕ(γ)]
..
.
ψ ∃αϕ(α)
∃E
ψ

where α is a variable and γ does not occur in any undischarged

assumption of the subderivation of ψ, or in ψ, or in ∃αϕ(α).

Luca Incurvati ([email protected]) Basic Logic 4 25 / 42

 Deductive system of FOL

Existential elimination

Clearly, the following argument is bad: Jane is American; there is

someone who is not American; therefore Jane is both American and
not American.
We might symbolise this argument as: Fa, ∃x¬Fx ∴ Fa ∧ ¬Fa.
Suppose we tried to vindicate this with the following deduction:
[¬Fa]1 Fa
∧I
Fa ∧ ¬Fa ∃x¬Fx ∃E
1
Fa ∧ ¬Fa
This is disallowed because the constant a we used to form a
substitution instance of ∃x¬Fx occurs in ψ.

Luca Incurvati ([email protected]) Basic Logic 4 26 / 42

 Deductive system of FOL

Existential elimination

Now consider:
[¬Fa]1 Fa
∧I
Fa ∧ ¬Fa
∃I
∃x(Fx ∧ ¬Fx) ∃x¬Fx
∃E1
∃x(Fx ∧ ¬Fx)
This is still disallowed because the constant a we used to form a
substitution instance of ∃x¬Fx occurs in an undischarged assumption
(a premise, in this case), namely Fa.
Moral: If you want to squeeze information out of an existential
quantifier, choose a new name for your substitution instance.

Luca Incurvati ([email protected]) Basic Logic 4 27 / 42

 Deductive system of FOL

An example

As an example, we give a proof of the syllogistic form Fesapo (one of

those which depended upon existential import): Something is G ; no
F is G ; all G are H; therefore some H is not F . (That is, we prove
∃xGx, ∀x(Fx → ¬Gx), ∀x(Gx → Hx) ` ∃x(Hx ∧ ¬Fx).)

Luca Incurvati ([email protected]) Basic Logic 4 28 / 42

 Deductive system of FOL

An example

As an example, we give a proof of the syllogistic form Fesapo (one of

those which depended upon existential import): Something is G ; no
F is G ; all G are H; therefore some H is not F . (That is, we prove
∃xGx, ∀x(Fx → ¬Gx), ∀x(Gx → Hx) ` ∃x(Hx ∧ ¬Fx).)

∀x(Fx → ¬Gx)
∀E
Fa → ¬Ga [Fa]1
∀x(Gx → Hx) →E
¬Ga [Ga]2
∀E 2 ¬E
Ga → Ha [Ga] ⊥
→E ¬I1
Ha ¬Fa
∧I
Ha ∧ ¬Fa
∃I
∃x(Hx ∧ ¬Fx) ∃xGx
∃E2
∃x(Hx ∧ ¬Fx)

Luca Incurvati ([email protected]) Basic Logic 4 28 / 42

 Variations on first-order logic

1 Language of FOL

2 Semantics of FOL

3 Deductive system of FOL

4 Variations on first-order logic

Luca Incurvati ([email protected]) Basic Logic 4 29 / 42

 Variations on first-order logic

Preliminary remarks

Variations are possible on each of three components of a logic:

Luca Incurvati ([email protected]) Basic Logic 4 30 / 42

 Variations on first-order logic

Preliminary remarks

Variations are possible on each of three components of a logic:

1 Language: notational variations, different sets of logical constants,

different sets of non-logical constants, etc.
2 Deductive system: axiomatic, natural deduction, sequent calculus,
tableaux; in all cases we can have different axioms or rules, which
may give rise to different extensions of the deducibility relation.
3 Semantics: interpretations may have different elements (e.g.
different domains); truth in an interpretation may be defined in
different ways (as we hinted at); all of this may give rise to different
extensions of the logical consequence relation.

Luca Incurvati ([email protected]) Basic Logic 4 30 / 42

 Variations on first-order logic

Identity

The argument
Hesperus shines in the evening
Hesperus is Phosphorus
Hence, Phosphorus shines in the evening
is informally valid, but cannot be rendered as a valid argument in
first-order logic.

Luca Incurvati ([email protected]) Basic Logic 4 31 / 42

 Variations on first-order logic

Identity

The argument
Hesperus shines in the evening
Hesperus is Phosphorus
Hence, Phosphorus shines in the evening
is informally valid, but cannot be rendered as a valid argument in
first-order logic.
This is because identity can only be treated as a predicate
(non-logical constant); solution: treat ‘=’ as a logical constant.
By making appropriate changes to language, deductive system and
semantics, we obtain first-order logic with identity (FOL= ).

Luca Incurvati ([email protected]) Basic Logic 4 31 / 42

 Variations on first-order logic

Identity as a logical constant

What does it mean to treat ‘=’ as a logical constant?

If it were treated as a non-logical constant, the given valuation
function would assign an arbitary set of ordered pairs to it.

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

 Variations on first-order logic

Identity as a logical constant

What does it mean to treat ‘=’ as a logical constant?

If it were treated as a non-logical constant, the given valuation
function would assign an arbitary set of ordered pairs to it.
Instead, we keep the its meaning fixed across interpretations, just as
we do for sentential connectives and quantifiers.
In particular, the truth of a sentence like ‘a = b’ is determined by
whether the objects assigned to ‘a’ and ‘b’ are identical (and not by
which set of ordered pairs is assigned to ‘=’).

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

 Variations on first-order logic

Characterizing first-order logic with identity

Language: we include ‘=’ among the logical constants of the

vocabulary and add the following clause in the definition of an atomic
formula:
If α and β are terms, then α = β is an atomic formula.
Deductive system: we extend the deductive system with the
characteristic axioms or rules for identity.
Semantics: we add the following clause in the definition of truth in
an interpretation:
If ϕ is an atomic sentence α = β then ϕ is true in I iff V(α) is
identical to V(β).

Luca Incurvati ([email protected]) Basic Logic 4 33 / 42

 Variations on first-order logic

Identity introduction

We expand the deductive system of FOL with one introduction rule

and two elimination rules for identity to obtain the deductive system
for FOL= .

Rule of identity introduction

=I
β=β

where β is any constant.

Luca Incurvati ([email protected]) Basic Logic 4 34 / 42

 Variations on first-order logic

Identity elimination

Rules of identity elimination

α=β ϕ(. . . α . . . α . . . ) α=β ϕ(. . . β . . . β . . . )
=E =E
ϕ(. . . β . . . α . . . ) ϕ(. . . α . . . β . . . )

Luca Incurvati ([email protected]) Basic Logic 4 35 / 42

 Variations on first-order logic

Symmetry

Given our rules, we can prove that identity is symmetric:

a=a =I [a = b]1
=E
b=a → I1
a=b→b=a
∀I
∀y (a = y → y = a)
∀I
∀x∀y (x = y → y = x)

Luca Incurvati ([email protected]) Basic Logic 4 36 / 42

 Variations on first-order logic

Symmetry

We can also prove that identity is transitive:

[a = b ∧ b = c]1 [a = b ∧ b = c]1
∧E ∧E
a=b b=c
a=c = E
→ I1
(a = b ∧ b = c) → a = c
∀I
∀z((a = b ∧ b = z) → a = z)
∀I
∀y ∀z((a = y ∧ y = z) → a = z)
∀I
∀x∀y ∀z((x = y ∧ x = z) → x = z)

Luca Incurvati ([email protected]) Basic Logic 4 37 / 42

 Variations on first-order logic

Increase in expressive power

First-order logic with identity has more expressive power than its
counterpart without identity.
For instance, we can now say things like ‘There are exactly two
things’: ∃x∃y ((x 6= y ) ∧ ∀z(x = z ∨ y = z)).

Luca Incurvati ([email protected]) Basic Logic 4 38 / 42

 Variations on first-order logic

Increase in expressive power

First-order logic with identity has more expressive power than its
counterpart without identity.
For instance, we can now say things like ‘There are exactly two
things’: ∃x∃y ((x 6= y ) ∧ ∀z(x = z ∨ y = z)).
This sentence will be true in all and only those interpretations whose
domains contain exactly two elements; there is no such sentence in
first-order logic without identity.
Similar considerations apply to any sentence saying that the domain
has a particular finite size.
However, there is no sentence of first-order logic with identity which
is true in all and only those interpretations whose domain is finite.

Luca Incurvati ([email protected]) Basic Logic 4 38 / 42

 Variations on first-order logic

Functions symbols

We are interested in the formalization of mathematical theories, and

in particular arithmetical theories.
In arithmetic one makes use of function symbols – consider
‘5 + 7 = 12’.

Luca Incurvati ([email protected]) Basic Logic 4 39 / 42

 Variations on first-order logic

Functions symbols

We are interested in the formalization of mathematical theories, and

in particular arithmetical theories.
In arithmetic one makes use of function symbols – consider
‘5 + 7 = 12’.
The language of first-order identity as we have defined it does not
include such symbols.
So the question arises as to how to represent arithmetical sentences
within first-order logic with identity.

Luca Incurvati ([email protected]) Basic Logic 4 39 / 42

 Variations on first-order logic

Eliminating function symbols

Think of a function as a relation R in which every first element is

related to exactly one second element. The value of the function is
the thing which bears the relation R to the argument of the function.

Luca Incurvati ([email protected]) Basic Logic 4 40 / 42

 Variations on first-order logic

Eliminating function symbols

Think of a function as a relation R in which every first element is

related to exactly one second element. The value of the function is
the thing which bears the relation R to the argument of the function.
But Russell has taught us how to eliminate expression such as ‘The x
such that Fx’: we take them to be paraphrased by ‘There is exactly
an x such that Fx’.
And the language of first-order logic with identity has the resources to
translate such paraphrases.

Luca Incurvati ([email protected]) Basic Logic 4 40 / 42

 Variations on first-order logic

Eliminating function symbols

Think of a function as a relation R in which every first element is

related to exactly one second element. The value of the function is
the thing which bears the relation R to the argument of the function.
But Russell has taught us how to eliminate expression such as ‘The x
such that Fx’: we take them to be paraphrased by ‘There is exactly
an x such that Fx’.
And the language of first-order logic with identity has the resources to
translate such paraphrases.
Thus, we take ‘5 + 7 = 12’ as saying ‘There is exactly one thing
which bears the relation of being their sum to 5 and 7 and that thing
is identical to 12’.
So we render ‘5 + 7 = 12’ as
‘∃x(S(5, 7, x) ∧ ∀y (S(5, 7, y ) → y = x) ∧ x = 12)’.

Luca Incurvati ([email protected]) Basic Logic 4 40 / 42

 Variations on first-order logic

Adding function symbols

This process of elimination of function symbols makes it clear

(although this should be proved) that having function symbols does
not increase the expressive power of first-order logic with identity.
Yet, to make things easier, it is sometimes convenient to have
function symbols in the primitive vocabulary.
In that case, they are of course part of the non-logical constants.

Luca Incurvati ([email protected]) Basic Logic 4 41 / 42

 Variations on first-order logic

References

β-variant method
B.Mates, Elementary Logic, Ch. 4, §§1–3.
Tarski’s method:
E.Mendelson, Introduction to Mathematical Logic, Ch. 2 §2.
Logical constants
J.MacFarlane, ‘Logical constants’ Stanford Encyclopedia of Philosophy.
A.Tarski, 2002, ‘On the Concept of Following Logically’, History and
Philosophy of Logic 23: 155196 (translation of 1936 original)
A.Tarski, 1986, ‘What are Logical Notions?’ History and Philosophy of
Logic 7: 143154. (Transcript of a 1966 talk, hard)
Extending first-order logic with identity and functions:
E.Mendelson, Introduction to Mathematical Logic, Ch. 2 §8–9.
Eliminating function symbols:
G.Boolos, J.P.Burgess and R.Jeffrey, Computability and Logic, Ch. 19,
§4.
Luca Incurvati ([email protected]) Basic Logic 4 42 / 42