Basic Logic, Lecture 11

Luca Incurvati

[email protected]

Luca Incurvati ([email protected]) Basic Logic 11 1 / 28

 Outline

1 Theories

2 Theories of arithmetic

3 First-order group theory

Luca Incurvati ([email protected]) Basic Logic 11 2 / 28

 Theories

The definition of a theory

A theory is a special set of sentences, namely a set which is closed

under logical consequence.
In other words:

Definition (Theory)
A set of sentences T is a theory iff for any sentence ϕ, if T |= ϕ, then
ϕ ∈ T.

Thus, T is a theory iff T = {ϕ : T |= ϕ}.

Luca Incurvati ([email protected]) Basic Logic 11 3 / 28

 Theories

The underlying logic

The definition of a theory makes it clear that a theory has an

underlying logic (language + semantics).
The underlying logic defines the set of sentences (language) and the
relation of logical consequence (semantics).
The logic may (but need not) include a deductive system.

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

 Theories

An alternative definition of a theory

There is a syntactic analogue of the semantic definition of a theory

we gave.
This definition takes a theory to be a set of sentences closed under
deducibility (rather than logical consequence):

Definition (Theory (syntactic))

A set of sentences T is a theory iff for any sentence ϕ, if T ` ϕ, then
ϕ ∈ T.

Luca Incurvati ([email protected]) Basic Logic 11 5 / 28

 Theories

The underlying logic (syntactic)

Again, the syntactic definition of a theory makes it clear that a theory

has an underlying logic (language + deductive system).
The underlying logic defines the set of sentences (language) and the
relation of deducibility (deductive system).
The logic may (but need not) include a semantics.

Luca Incurvati ([email protected]) Basic Logic 11 6 / 28

 Theories

On the relation between the two notions of a theory

If an underlying logic (taken to be language + semantics) is strongly

axiomatised by some deductive system, then the semantic notion and
the syntactic notion coincide, since the logical consequence relation
and the deducibility relation are co-extensive.
But since some logics are not strongly axiomatizable, the two notions
may come apart.

Luca Incurvati ([email protected]) Basic Logic 11 7 / 28

 Theories

On the relation between the two notions of a theory

If an underlying logic (taken to be language + semantics) is strongly

axiomatised by some deductive system, then the semantic notion and
the syntactic notion coincide, since the logical consequence relation
and the deducibility relation are co-extensive.
But since some logics are not strongly axiomatizable, the two notions
may come apart.
In what follows, by ‘theory’ we will mean theory according to the
semantic definition.

Luca Incurvati ([email protected]) Basic Logic 11 7 / 28

 Theories

Theorems

The theorems of a theory are its members:

Definition (Theorem)
ϕ is a theorem of a theory T iff ϕ ∈ T. We write ‘`T ϕ’ for ‘ϕ is a
theorem of T’.

It follows that `T ϕ iff T |= ϕ.

Luca Incurvati ([email protected]) Basic Logic 11 8 / 28

 Theories

Theorems

The theorems of a theory are its members:

Definition (Theorem)
ϕ is a theorem of a theory T iff ϕ ∈ T. We write ‘`T ϕ’ for ‘ϕ is a
theorem of T’.

It follows that `T ϕ iff T |= ϕ.

N.B.: a theorem of a theory should not be confused with a theorem
of some logic (i.e. a sentence ϕ such that ` ϕ).

Luca Incurvati ([email protected]) Basic Logic 11 8 / 28

 Theories

Special cases

(i) The empty set is not a theory since there are sentences which follow
from any set of sentences, including the empt set, namely the logical
truths of the underlying logic.
(ii) The smallest theory for any given underlying logic is the set of logical
truths of the logic.
(iii) The largest theory for any given underlying logic is the set of all
sentences of the language.

(ii) justifies viewing a logic as a degenerate theory.

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

 Theories

Axioms

We have defined a theory simply as a set of sentences closed under

logical consequence.
But often one singles out a set of sentences as a set of axioms for the
given theory, and describe the theory as the set of consequences of
the set of axioms:

Definition (Set of axioms for a theory)

A set of axioms for a theory T is a set of sentences Ax such that
T = {ϕ : Ax |= ϕ}.

Thus, a set of sentences is a set of axioms for a given theory just in

case the theory is the set of axioms and their consequences.

Luca Incurvati ([email protected]) Basic Logic 11 10 / 28

 Theories of arithmetic

1 Theories

2 Theories of arithmetic

3 First-order group theory

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

 Theories of arithmetic

The informal theory of arithmetic

The informal theory of arithmetic is the set of sentences which follow

from the Peano axioms:

1 0 is a natural number.
2 If x is a natural number, then there is a natural number which is the
successor of x.
3 For any natural number x, the successor of x 6= 0.
4 For any natural numbers x and y , if the successor of x = the
successor of y , then x = y .
5 For any property P, if (i) 0 has P and (ii) if a natural number has P
so does its successor, then (iii) every natural number has P.

Luca Incurvati ([email protected]) Basic Logic 11 12 / 28

 Theories of arithmetic

The natural number structure

We take the Peano axioms to be truths about a particular structure

— the natural number structure.
Since whatever follows from truths is also true, the sentences which
follow from the Peano axioms are themselves truths about the natural
number structure.

Luca Incurvati ([email protected]) Basic Logic 11 13 / 28

 Theories of arithmetic

The natural number structure

We take the Peano axioms to be truths about a particular structure

— the natural number structure.
Since whatever follows from truths is also true, the sentences which
follow from the Peano axioms are themselves truths about the natural
number structure.
We now need to turn the informal theory of arithmetic into a formal
theory.

Luca Incurvati ([email protected]) Basic Logic 11 13 / 28

 Theories of arithmetic

From the informal theory of arithmetic to PA2

We must choose some underlying logic.

The language of the logic will determine the set of sentences which
are the candidates for being members of the theory.
We then formalize the axioms of the theory using the language of the
logic and keeping in mind the intended interpretation.

Luca Incurvati ([email protected]) Basic Logic 11 14 / 28

 Theories of arithmetic

From the informal theory of arithmetic to PA2

We must choose some underlying logic.

The language of the logic will determine the set of sentences which
are the candidates for being members of the theory.
We then formalize the axioms of the theory using the language of the
logic and keeping in mind the intended interpretation.
The semantics of the logic will give us a relation of logical
consequence.
The theory will then be the set of sentences which logically follow
from the axioms formally expressed.

Luca Incurvati ([email protected]) Basic Logic 11 14 / 28

 Theories of arithmetic

Interlude: the intended interpretation

Roughly, the intended interpretation of a language used to formalise

an informal theory is the interpretation which:
has as its domain the set of objects the informal theory is about;
assigns to the non-logical vocabulary the extensions that its natural
language counterparts are taken to have.

Luca Incurvati ([email protected]) Basic Logic 11 15 / 28

 Theories of arithmetic

Interlude: the intended interpretation

Roughly, the intended interpretation of a language used to formalise

an informal theory is the interpretation which:
has as its domain the set of objects the informal theory is about;
assigns to the non-logical vocabulary the extensions that its natural
language counterparts are taken to have.
For instance, you could imagine a theory about people whose only
axiom is ‘Socrates is mortal’.
The intended interpretation of the language used to formalise the
theory will have the set of people as its domain; and if ‘Fa’ is meant
to translate ‘Socrates is mortal’, the intended interpretation will
assign Socrates to ‘a’ and the set of all people that are mortal to ‘F ’.

Luca Incurvati ([email protected]) Basic Logic 11 15 / 28

 Theories of arithmetic

From the informal theory of arithmetic to PA2

We take the underlying logic to be second-order logic.

We take the language to actually have as its non-logical symbols only
one individual constant 0 and one one-function symbol s.

Luca Incurvati ([email protected]) Basic Logic 11 16 / 28

 Theories of arithmetic

From the informal theory of arithmetic to PA2

We take the underlying logic to be second-order logic.

We take the language to actually have as its non-logical symbols only
one individual constant 0 and one one-function symbol s.
The intended interpretation of the language is as follows:
The domain is the set of natural numbers.
0 is assigned the natural number 0.
s is assigned the successor function from natural numbers to natural
numbers.

Luca Incurvati ([email protected]) Basic Logic 11 16 / 28

 Theories of arithmetic

From the informal theory of arithmetic to PA2

We do not have a predicate constant corresponding to ‘. . . is a natural

number’ because we are taking the domain of our theory to be set of
natural numbers.
We do not need an axiom corresponding to the first Peano axiom,
since whatever object is assigned to 0, it will be a natural number.
We do not need an axiom corresponding to the second Peano axiom,
since s is a function symbol, and we require that any function
assigned to a function symbol be a total function on the domain of
interpretation (i.e. a function which takes every member of the
domain to some value.).

Luca Incurvati ([email protected]) Basic Logic 11 17 / 28

 Theories of arithmetic

From the informal theory of arithmetic to PA2

Thus, the axioms of our theory will be:

Axioms of PA2
∀x(0 6= sx)
∀x∀y (sx = sy → x = y )
∀X ((X 0 ∧ ∀x(Xx → X sx)) → ∀x(Xx))

PA2 is the set of sentences which logically follow from these three
axioms in the underlying logic specified (i.e. second-order logic).

Luca Incurvati ([email protected]) Basic Logic 11 18 / 28

 Theories of arithmetic

From PA2 to PA

Suppose now we want our theory of arithmetic to be first-order. How

to proceed?

Luca Incurvati ([email protected]) Basic Logic 11 19 / 28

 Theories of arithmetic

From PA2 to PA

Suppose now we want our theory of arithmetic to be first-order. How

to proceed?
One natural way is to ‘first-orderise’ PA2 and proceed from there.
Obviously, we let the underlying logic be first-order logic with identity.
We then note that PA2 ’s Induction Axiom is second-order; so we need
to amend it.

Luca Incurvati ([email protected]) Basic Logic 11 19 / 28

 Theories of arithmetic

From PA2 to PA

In particular we make it first-order by ‘schematizing’ it, i.e. we take as

axioms all instances of the schema

(ϕ(0) ∧ ∀x(ϕ(0) → ϕ(sx))) → ∀xϕ(x)

(One instance for each formula ϕ(x) in the language of the theory.)

Luca Incurvati ([email protected]) Basic Logic 11 20 / 28

 Theories of arithmetic

From PA2 to PA

In particular we make it first-order by ‘schematizing’ it, i.e. we take as

axioms all instances of the schema

(ϕ(0) ∧ ∀x(ϕ(0) → ϕ(sx))) → ∀xϕ(x)

(One instance for each formula ϕ(x) in the language of the theory.)
This schema has denumerably infinitely many instances, so it is
weaker than the second-order induction axiom.
For the monadic predicate variable in the second-order axiom ranges
over all subsets of the natural numbers, and there are
non-denumerably infinitely many of those (by Cantor’s Theorem).

Luca Incurvati ([email protected]) Basic Logic 11 20 / 28

 Theories of arithmetic

From PA2 to PA

Are we done? In PA2 one can define addition and multiplication (for
details, see Shapiro, Foundations without Foundationalism, p. 95, fn.
3).

Luca Incurvati ([email protected]) Basic Logic 11 21 / 28

 Theories of arithmetic

From PA2 to PA

Are we done? In PA2 one can define addition and multiplication (for
details, see Shapiro, Foundations without Foundationalism, p. 95, fn.
3).
But the PA2 definition of addition and multiplication makes use of
quantification over functions, so it is not available in a first-order
setting.
Thus, if we think that facts about addition and multiplications should
follow from a theory of arithmetic, we need axioms whose role is to
define addition and multiplication.
These are effectively the recursion equations for addition and
multiplication; it is then a result of Gödel’s that this suffices to obtain
a theory which is adequate to express all the primitive recursive and
indeed general recursive functions.

Luca Incurvati ([email protected]) Basic Logic 11 21 / 28

 Theories of arithmetic

From PA2 to PA

First, we expand the language: besides 0 and s, the non-logical

vocabulary of PA includes the two place function symbols + and ×.
Then, we add to the theory the following axioms:

∀x(x+0 = x)
∀x∀y (x+sy = s(x+y ))
∀x(x×0 = 0)
∀x∀y (x×sy = (x×y +x))

Luca Incurvati ([email protected]) Basic Logic 11 22 / 28

 Theories of arithmetic

From PA2 to PA

Thus, the axioms of our theory will be:

Axioms of PA
∀x(0 6= sx)
∀x∀y (sx = sy → x = y )
∀x(x+0 = x)
∀x∀y (x+sy = s(x+y ))
∀x(x×0 = 0)
∀x∀y (x×sy = (x×y +x))
(ϕ(0) ∧ ∀x(ϕ(0) → ϕ(sx))) → ∀xϕ(x) (for each formula ϕ(x))

PA is the set of sentences which logically follow from these axioms in

the underlying logic specified (i.e. first-order logic).
Luca Incurvati ([email protected]) Basic Logic 11 23 / 28
 First-order group theory

1 Theories

2 Theories of arithmetic

3 First-order group theory

Luca Incurvati ([email protected]) Basic Logic 11 24 / 28

 First-order group theory

A different kind of theory

PA2 and PA are presented as the set of consequences of a set of

axioms, where the axioms are truths about an intended interpretation.
But certain mathematical theories are understood as not being about
a particular structure, but about a certain class of structures.
Thus the purpose of the set of axioms is to characterize a class of
interpretations, namely the class whose members are all and only
those interpretations in which all of the axioms are true.
The theory tells us what is common to all and only the members of
the class.

Luca Incurvati ([email protected]) Basic Logic 11 25 / 28

 First-order group theory

A different kind of theory

PA2 and PA are presented as the set of consequences of a set of

axioms, where the axioms are truths about an intended interpretation.
But certain mathematical theories are understood as not being about
a particular structure, but about a certain class of structures.
Thus the purpose of the set of axioms is to characterize a class of
interpretations, namely the class whose members are all and only
those interpretations in which all of the axioms are true.
The theory tells us what is common to all and only the members of
the class.
An example is group theory (briefly described below), but there are
many others, such as the theory of fields, the theory of rings, etc.

Luca Incurvati ([email protected]) Basic Logic 11 25 / 28

 First-order group theory

Characterizing first-order group theory

The underlying logic is first-order logic with identity.

The language has as its non-logical symbols one individual constant 0
and one two-place function symbol +.
The axioms are:

Axioms of first-order group theory

∀x∀y ∀z(x+(y +z)) = ((x+y )+z) (associativity of +)
∀x(x+0 = x) (0 is an identity element)
∀x∃y (x+y = 0) (existence of an inverse element)

Luca Incurvati ([email protected]) Basic Logic 11 26 / 28

 First-order group theory

On first-order group theory

Any interpretation which makes the axioms of first-order group theory

true corresponds to a structure which we call a ‘group’.
The structure will consist of a non-empty set S, a function which is
total on the set of all ordered pairs of element from S, and a
distinguished element 0.
An example of a group is the structure consisting of the set of
integers, the addition function, and the distinguished element 0.

Luca Incurvati ([email protected]) Basic Logic 11 27 / 28

 First-order group theory

References

Theories of arithmetic:
S.Shapiro, Foundations without Foundationalism, pp. 80–82.
P.Smith, Introduction to Gödel’s Theorems, Ch. 10.

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