MATH0037 Lecture Notes

Samuel Coskey

Part I: Introduction to logic and set theory

Logic is the area of study that concerns reasoning. It has of course been studied by
both philosophers and mathematicians for several millennia.

In this module we will study mathematical logic, which has been studied since late
1800s. During that period mathematics itself was rapidly evolving and modernising,
and mathematical logic was developed to help provide a rigorous foundation for
contemporary mathematics.

Mathematical logic helps us understand what language we can use when

discussing mathematics, what makes theorem statements meaningful, and what
forms of reasoning are appropriate to use in proofs. It also helps us build and
understand mathematical structures like groups, rings, graphs, and so on.

The modern field of mathematical logic now consists of three interconnected

subfields: first order logic, set theory, and computability theory.

In this module we will focus primarily on first order logic. However we will begin our
study with the much simpler propositional logic, along with some elementary set
theory to support our studies. We will conclude with an introduction to
computability theory and the incompleteness phenomenon.

1. Propositional logic
We begin our study of mathematical logic with the relatively simple theory of
propositional logic. This theory deals with the boolean connectives (P implies Q,
and so forth) but excludes quantifiers (for all, there exists).

In the next part we will study first order logic, which adds the quantifiers back in.
While that means the material of this section will soon be eclipsed, we include it to
help us transition from commonly used logic to true mathematical logic.

We begin by introducing the language of propositional logic. Every language has an

alphabet, or set of symbols we may write. The alphabet of propositional logic
includes:

the boolean connective symbols: ¬, ∧, ∨, →, ↔

 propositional variable symbols: P1 , P2 , P3 , … (or sometimes P , Q, R, …,
A, B, C, …, etc)
brackets, also called parentheses: '(', ')'

We will see later on that the connective symbols ∨, →, ↔ may all be avoided.
Moreover, even the brackets may be avoided if one uses prefix notation instead of
infix notation. (That is, if one writes ∧PQ instead of (P ∧ Q).) For the moment we
will continue with the more familiar infix notation.

Next, a language should tell us how to put symbols from the alphabet together.

Definition An expression is any finite sequence of symbols using the alphabet of

propositional logic.

For example, both of the following are expressions:

(P ∧ Q) ∨ R
((P →)

Clearly some expressions are more useful than others! The following definition
helps us pick out the expressions which are more likely to have a useful meaning.

Definition An expression is called a well-formed formula (or wff, or simply formula)

if it can be constructed using the following base case and recursive rule:

Every propositional variable symbol is a formula

If α and β are formulas, then so are (¬α), (α ∧ β), (α ∨ β), (α → β), (α ↔ β)

For example, the following are all well-formed formulas:

((P ∧ Q) ∨ R)
(P → ((¬Q) ∨ (R → P )))

The following are not well-formed formulas:

((P →)
P ∧Q¬R

The expression (P ∧ Q) ∨ R mentioned above technically is not a well-formed

formula because it has too few brackets. As humans we can infer it intends to mean
the same as ((P ∧ Q) ∨ R). When there is no cause for confusion we will sometimes
write such incorrect expressions, and ask the reader to mentally insert the needed
brackets.
Many authors introduce an order of operations. For example if we state that ∧ takes
precedence over ∨ (which is standard for many authors), then P ∧ Q ∨ R may again
be interpreted as ((P ∧ Q) ∨ R). We will try to avoid this and include enough
brackets to make it clear .

In logic we often separate the syntax and the semantics of formulas. Syntax is all
about rules, you can think of it as analogous to grammar for languages. for example,
what is and isn’t considered a well-formed formula, much like grammar. On the
other hand, semantics is all about meaning, for example, which formulas might be
considered true or false.

The semantics of propositional logic is governed by truth tables. In the following, let
α and β be well-formed formulas.

α (¬α)
T F
F T

α β (α ∧ β)
T T T
T F F
F T F
F F F

The boolean connective → always sparks a little bit of discussion.

α β (α → β)
T T T
T F F
F T T
F F T

Sometimes called material conditional, the truth table is meant to capture the idea
of “P implies Q”, but without any of the causation one would normally understand
from natural language. Instead the formula α → β may be thought of as a kind of
promise, that if α is true then β will be true also. If α is not true, then the promise
will not be broken, so the conditional is "vacuously true". We will see later that this
definition is the most useful way to study deductions in mathematics.

We invite the reader to fill in truth tables for the rest of the boolean connectives.

While these truth tables are certainly familiar, we still need to describe how they are
used. We will say the set of truth values is {T , F }.

Definition A truth assignment is a function v from the set of propositional symbols

to the set of truth values. That is, v : {P1 , P2 , …} → {T , F }.
In other words, a truth assignment v says whether each propositional symbol is true
or false. Since the propositional symbols are the simplest well-formed formulas,
intuitively we should be able to use v together with the truth tables for the boolean
connectives to determine whether v says any well-formed formula α is true or false.
The following definition makes this idea formal.

Definition Let v be a truth assignment and α be a well-formed formula. We define

v ⊨ α, read aloud "v satisfies α", using the following base case and recursive rules.

If α = P and v(P ) = T , let v ⊨ α. If v(P ) = F let v 

⊨ α.
If α = ¬β and v ⊨ β then let v 
⊨ α. If v 
⊨ β then let v ⊨ α.
If α = β ∧ γ and v ⊨ β and v ⊨ γ then let v ⊨ α; otherwise let v 
⊨ α.
We invite the reader to add an additional recursive rule for each boolean
connective using truth tables described above.

For the record, we state that the above definition is well-defined, meaning that for
any v and α it follows from these rules that either v ⊨ α or v 
⊨ α, and not both.
While this assertion may seem intuitively true or unnecessary, it should be proved,
and we will postpone the proof until the next part.

When v ⊨ α we think to ourselves that α is true under the assumptions contained

within v . This is the semantic meaning of a well-formed formula α: if we know the
truth values of the propositional symbols then we can use the structure of α to
derive the truth value of α.

Example In lectures we will give examples of how to inductively decide whether

v ⊨ α for various truth assignments v and well-formed formulas α.

Typically, different truth assignments will give rise to different truth values for α.
However for some very special formulas α, the truth assignment may have no
impact on the outcome. For instance, if α is the formula P ∨ ¬P , then it is easy to
check that every truth assignment v results in v ⊨ α.

Definition A well-formed formula α is a tautology if for every truth assignment v we

have v ⊨ α.

The tautologies are thus little bits of reasoning that are always true, regardless of
the truth values of the propositional variables. Another example of a tautology is
(P ∧ Q) → P . This is because any truth assignment that makes P ∧ Q true must
also make P true.

Definition We say that α ⊨ β , read aloud "α semantically implies β ", if for every
truth assignment v , if v ⊨ α then v ⊨ β .
Semantic implication in propositional logic is sometimes also called "tautological
implication". We invite the reader to verify that α ⊨ β if and only if α → β is a
tautology.

Example In lectures we will present one or two examples of semantic implications.

We next generalise the ⊨ notation once more to allow sets of formulas to be used.

Definition Let v be a truth assignment and let Σ be a set of well-formed formulas.

We say v ⊨ Σ, read "v satisfies Σ", if for all σ ∈ Σ we have v ⊨ σ .

Definition Let Σ be a set of well-formed formulas, and α be a well-formed formula.

We say Σ ⊨ α if for every truth assignment v , if v ⊨ Σ then v ⊨ α.

Example In lectures we will present one or two examples of semantic implications

where the left-hand side is a set of formulas.

The semantic implication Σ ⊨ α is more interesting when Σ is infinite (why is this?).

The next result states that even when Σ is infinite, just a finite subset of Σ is
needed.

Theorem (The compactness theorem). Let Σ be a set of well-formed formulas. If

Σ ⊨ α, then there exists a finite subset Σ0 ⊂ Σ such that Σ0 ⊨ α.

The compactness theorem for propositional logic is one of the cornerstones of the
theory, as will be the more general compactness theorem for first order logic. The
name of the compactness theorem is due to its relationship to the idea of
compactness in analysis, something which will become a little clearer later on.

The compactness theorem can be restated as a statement about consistency.

Definition Let Σ be a set of well-formed formulas. We say Σ is consistent if there

exists a truth assignment v such that v ⊨ Σ.

We invite the reader to verify that Σ is consistent if and only if Σ 

⊨ (P ∧ (¬P )).
Sometimes the symbol ⊥ is used for a tautologically false formula such as
(P ∧ (¬P )). Thus we may say Σ is consistent if and only if Σ 
⊨ ⊥.

Theorem (The compactness theorem again). Let Σ be a set of well-formed

formulas. If every finite subset of Σ is consistent, then Σ is consistent.

We leave it to the reader to establish an equivalence between the two statements of

the compactness theorem.

The compactness theorem has many interesting applications, to give a taste of this
we explore just one of them from combinatorial graph theory. Recall that if
G = (V , E) is a graph with vertex set V and edge set E , then a proper coloring of G
with n colors is a function χ : V → {c1 , … , cn } such that whenever (v, v ′ ) ∈ E we
= χ(v ′ ).
have χ(v) 

Theorem Let G be a combinatorial graph, finite or infinite. Suppose that every finite
subgraph G0 ⊂ G has a proper coloring using n colors. Then G has a proper
coloring using n colors. In particular, every planar graph (finite or infinite) has a
proper coloring using 4 colors.

Proof: They key is that proper colorability can be encoded using well-formed
formulas. For convenience we will use the propositional variable symbols Pv,i , where
v ranges over the vertices V and i ∈ 1, … , n. We then let Σ consist of the following
axioms:

Pv,1 ∨ ⋯ ∨ Pv,n for each v ∈ V and each i

¬(Pv,i ∧ Pv,j ) for each v ∈ V and each i.j such that i 
=j
¬(Pv,i ∧ Pw,i ) for each v, w ∈ V such that (v, w) ∈ E and each i

The reader should verify that there exists a truth assignment v that satisfies Σ if and
only if there exists a proper coloring χ using n colors.

We claim Σ is finitely satisfiable. To see this let Σ0 ⊂ Σ be a finite subset. Note that
since Σ0 is finite and each sentence is finite in length, there exists a finite susbest
V0 ⊂ V of vertices appearing in the subscript of a propositional symbol in Σ0 . If we
let G0 be the subgraph of G induced by V0 , then by hypothesis there exists a proper
coloring χ0 of G0 using n colors. As observed in the previous paragraph, this implies
that Σ0 is consistent.

Therefore by the compactness theorem, Σ is satisfiable. Again, as we have seen,

this implies there exists a proper coloring of G using n colors. ■

Deductions

The concept of Σ ⊨ α is a kind of implication, that is, we understand it to mean that

if the formulas in Σ are taken as true, then α is true. But the "proof" of α is tedious
and unenlightening: go through every prossible truth assignment v , check whether
v satisfies each of the well-formed formulas in Σ, and if so, check whether v
satisfies α.

How can we show that the truth of Σ implies the truth of α using logical reasoning.
The answer is a deduction, which is a sequence of steps, together with justification
that each step follows from the previous ones.
Definition Let α, β be well-formed formulas. Modus ponens is the deductive rule
that if α is true, and α → β is true, then β is true.

We leave it to the reader to verify that the modus ponens rule is true semantically,
that is, {α, α → β } ⊨ β . This should help shed some light on the reasons for the
truth table for the connective →.

Definition Let Σ be a set of well-formed formulas, and let α be a well-formed

formula. We define Σ ⊢ α, read "Σ syntactically implies α", if there exists a
sequence of well-formed formulas α1 , … , αn such that αn = α, and for every i ≤ n
at least one of the following is true:

(a) αi is a hypothesis, that is, an element of Σ

(b) αi is a tautology
(c) αi follows from two of the previous formulas in α1 , … , αi−1 by modus
ponens

In other words, a deduction is a very simple kind of proof that the hypotheses Σ
imply the conclusion α. While Σ ⊨ α must be verified abstractly using truth tables,
Σ ⊢ α may be verified by checking the steps. The deduction includes its own
reasoning.

We remark that it is overkill to allow all tautologies to be included in part (b) of the
definition. Those who study deductions typically include only tautologies from a
selected list of approved templates. For example, you can imagine including
¬(¬α) ↔ α, (α ∧ β) → α, and so on. By the same token, some authors use a minimal
set of tautologies in (b) but expand the deductive rules allowed in (c).

Since studying propositional logic is not our primary goal, we will stick with the
simple definition (a)–(c) above in order to exposit a few key results. We invite the
interested reader to to look up other standard deductive systems.

Example Let Σ = {(¬S) ∨ R, R → P , S } and let α = P . We show that Σ ⊢ α using the

following deduction.

1. (¬S) ∨ R — (hypothesis)
2. ((¬S) ∨ R) → (S → R) — (tautology)
3. S → R — (modus ponens)
4. S — (hypothesis)
5. R (modus ponens)
6. R → P (hypothesis)
7. P (modus ponens)
We have now introduced two distinct ways of understanding logical consequence,
semantic implication Σ ⊨ α and syntactic implication Σ ⊢ α. We should naturally try
to understand how the two are connected, and in fact we will see that the two are
equivalent. What's provable is true, and what's true is provable.

Theorem (Soundness and completeness theorems) Let Σ be a set of well-formed

formulas and α a well-formed formula. Then Σ ⊨ α if and only if Σ ⊢ α.

Proof: The soundness portion says that if Σ ⊢ α then Σ ⊨ α, that is, deductions are
valid or sound. This is due to the fact that every step in a deduction is valid. The
steps of the form (a) and (b) are evidently valid, and the reader should have already
checked that modus ponens (c) is valid. The result follows using induction along the
length of the deduction.

The completeness portion says that if Σ ⊨ α then Σ ⊢ α, that is, the deductions
witness all the semantic implications and so are complete. To accomplish this, we
first note that if Σ ⊨ α then by the compactness theorem there exists a finite subset
Σ0 ⊂ Σ such that Σ0 ⊨ α.

Since Σ0 is finite, we may enumerate now the well-formed formulas in Σ0 as

σ1 , … , σn . We leave it to the reader to show there is a deduction from Σ0 of the well-
formed formula σ1 ∧ ⋯ ∧ σn (insert brackets appropriately). Furthermore, it follows
from Σ0 ⊨ α that (σ1 ∧ ⋯ ∧ σn ) → α is a tautology. The last two claims plus modus
ponens show that Σ0 ⊢ α, and therefore that Σ ⊢ α. ■

We see from the proof above that the compactness theorem implies the
completeness theorem. We invite the reader to prove that the reverse is also true.
The key is that ⊢ automatically satisfies the compactness-like property: if Σ ⊢ α,
then there exists a finite subset Σ0 ⊂ Σ such that Σ0 ⊢ α. This is true because any
deduction of α from Σ has finitely many steps, and therefore may only use finitely
many of the well-formed formulas in Σ.