Logic Flashcards
curly L stands for what?
The alphabet
What does the alphabet consist of in propositional calculus?
propositional variables p_0, p_1, . . . (p_i for each i ∈ N_0), negation ¬, implication
→, conjunction ∧, disjunction ∨, equivalence ↔ and parentheses (, ).
What group are the symbols ¬, ∧, ∨, ↔ part of?
They are logical connectives
What is a string of curly L?
a finite sequence of symbols from curly L
The length of a
string is
the number of symbols it contains.
A string of L is a formula of L if and only if
• it is a propositional variable (i.e. it consists of a single symbol, which
is a propositional variable),
• it is of the form ¬A, where A is a formula,
• it is of the form (A → B), (A ∧ B), (A ∨ B) or (A ↔ B), where A and
B are formulas.
The set of all formulas of L is denoted
Form(L).
State the Unique Readability Theorem
For each formula φ of L,
exactly one of the following holds. Either φ is a propositional variable p_i for
a unique i ∈ N_0, or it is ¬ψ for a unique formula ψ, or it is (ψ * χ) for
unique formulas ψ, χ and a unique binary connective *.
Prove the Unique Readability Theorem
Problem Sheet 1 (By induction on the length of φ)
A valuation is
a function v : {pi : i ∈ N0} → {T, F }, where
the values T, F are called true and false.
Given a valuation v, we can __ to a __ ̃v by…
Given a valuation v, we can extend it to a function ̃v :
Form(L) → {T, F } by letting ̃v(φ) = v(φ) is φ is a propositional variable,
and using the table below for the cases φ = ¬ψ and φ = (ψ * χ). This
extension is well-defined and unique by the Unique Readability Theorem.
Recount the table of valuations of the unary and binary connectives ¬ψ, ψ → χ, ψ ↔ χ, ψ ∧ χ, ψ ∨ χ
ψ χ ¬ψ ψ → χ ψ ↔ χ T T... F..... T ..........T T F... F..... F.......... F F T... T..... T ......... F F F... T..... T......... T ψ ∧ χ ψ ∨ χ .....T.......... T .....F......... T .....F......... T .....F......... F
A valuation v satisfies a formula φ if
̃v(φ) = T
A formula
that is satisfied by some valuation is called
satisfiable
A formula that is
satisfied by no valuation is called
a contradiction
A formula φ that is satisfied
by all valuations is called ___, written
a tautology, written as |= φ.
A formula φ is a logical consequence of ψ if _____, we write
or all valuations
v such that ̃v(ψ) = T we also have ̃v(φ) = T .
We write ψ |= φ.
Let Γ be a set of formulas and φ a formula. Then φ is a
logical consequence of Γ if ____, we write
or all valuations v such that ̃v(ψ) = T for all
ψ ∈ Γ, we also have ̃v(φ) = T.
We write Γ |= φ.
For any formulas φ and ψ, we have ψ |= φ iff
In fact, for any Γ ⊆ Form(L), Γ ∪ {ψ} |= φ iff
|= (ψ → φ)
Γ |= (ψ → φ)
Formulas ψ and φ are logically equivalent iff
We write
φ |= ψ and ψ |= φ, i.e. if
̃v(ψ) = ̃v(φ) for all valuations v
We write ψ |==| φ.
For any formulas α, β, γ we have (α ∧ (β ∧ γ)) |==|___ and (α ∧ β) |==|
Therefore, when we are only interested in formulas up to
(α ∧ (β ∧ γ)) |==| ((α ∧ β) ∧ γ) and (α ∧ β) |==| (β ∧ α).
Therefore, when we are only interested in formu-
las up to logical equivalence, we will often write ∧n
i=1 Ai (generic and between 1 and n of all Ai) instead of (A1 ∧ (A2 ∧ . . . (An−1 ∧ An) . . . )). Similarly with ∨. We will also sometimes drop
parentheses in formulas, provided that unique readability is preserved.
The following equivalences hold: ¬ (∨(n)(i=1) Ai) |==| ¬ (∧(n)(i=1) Ai) |==| (A → B) |==| (A ∨ B) |==| \_\_\_ |==| (A ∧ B) |==| (A ↔ B) |==|
¬ (∨(n)(i=1) Ai) |==| ∧(n)(i=1) ¬Ai ¬ (∧(n)(i=1) Ai) |==| ∨(n)(i=1) ¬Ai (A → B) |==| (¬A ∨ B) (A ∨ B) |==| (¬A → B) |==| ((A → B) → B) (A ∧ B) |==| ¬(A → ¬B) (A ↔ B) |==| ((A → B) ∧ (B → A))
Let Vn be the set of ___,
then an n-ary truth function is
Let Vn be the set of partial valuations
v′ : {p0, . . . , pn−1} → {T, F }. Then an n-ary truth function is a function
J : Vn → {T, F }.
Denote by Form_n(L) the ___
If φ ∈ Form_n(L), then φ
determines an ___ J_φ given by v |→ v(φ)
set of all formulas of L in which
only the first n propositional variables occur.
n-ary truth function
For any n ∈ N and any n-ary truth function J there exists
φ ∈ Formn(L) such that J_φ = J
Prove that for any n ∈ N and any n-ary truth function J there exists
φ ∈ Form_n(L) such that Jφ = J.
If J(v) = F for all v ∈ Vn, then φ = (p0 ∧ ¬p0) works.
Otherwise the set U = {v ∈ Vn | J(v) = T } is nonempty. For each v ∈ U
and i < n we can define ψᵛᵢ as pᵢ if v(pᵢ) = T and as ¬pᵢ if v(pᵢ) = F . Then
define ψᵛ = ∧(n−1)(i=0) ψᵛ
i , so that u(ψᵛ) = T if and only if u(pᵢ) = v(pᵢ) for all i,
which is when u = v. Finally if we put φ = ∨_(v∈U) ψᵛ, then u(φ) = T if and
only if u = v for some v ∈ U . By the definition of U , that is when J(u) = T .
Therefore Jφ(u) = u(φ) = J(u) for all u, i.e. Jφ = J.A formula which is a conjunction of pis and ¬pis is called
a conjunctive clause
A formula which is a disjunction of conjunctive clauses
is said to be
in disjunctive normal form (DNF)
Similarly, a conjunction of
disjunctive clauses is called
a conjunctive normal form (CNF)
What is the important thing about DNF and CNF?
any formula is equivalent to one in dis-
junctive normal form. It can also be shown (using the first two equivalences
in Proposition (1.11)) that any formula is equivalent to one in conjunctive
normal form.
Let S be a set of logical connectives on which the extension
of a valuation is given by a truth table, Then
L[S] denotes
the alphabet consisting of propositional variables, parentheses,
and the connectives in S. Similarly as for L = L[{¬, ∧, ∨, → ↔}] we define
formulas Form(L[S]), with proper parenthesising, so that unique readability
is preserved.A set S of logical connectives is adequate if
for any n ∈ N
and any n-ary truth function J there exists a formula φ ∈ Form_n(L[S]) such
that Jφ = J.
The set {¬, →} is
adequate
Prove the set {¬, →} is adequate.
the set {¬, →, ↔, ∧, ∨} is adequate, so for any
truth function J we can find a formula φ with Jφ = J. Using the logical
equivalences from Proposition (1.11), we can find a logically equivalent for-
mula ψ using only the connectives ¬ and →.
But if ψ |==| φ then Jψ = Jφ,
so we have found a formula ψ ∈ Form(L[{¬, →}]) such that Jψ = J.
Let L0 = L[{¬, →}]. The system L0 is defined as follows: As in what we can use to prove in L0
An axiom of L0 is any formula of L0 of the form
(α → (β → α)) (A1)
((α → (β → γ)) → ((α → β) → (α → γ))) (A2)
((¬β → ¬α) → (α → β)) (A3)
where α, β, γ ∈ Form(L0).
The only rule of inference in L0 will be the modus
ponens rule: from α and (α → β) we infer β.
Let Γ ⊆ Form(L0) and α ∈ Form(L0). We say α is deducible
from the hypoheses Γ if
There exists a finite sequence α1, . . . , αn of formulas
of L0 such that for each i, either
• αi is an axiom,
• αi ∈ Γ, or
• αi follows from αj and αk by modus ponens (MP) for some j, k < i,
and αn = α.
The sequence α1, . . . , αn where αn = α is called a
proof or a derivation of α.
If α is deducible from Γ, we write
Γ ⊢ α
If ∅ ⊢ α, we just write __
and call α a
If ∅ ⊢ α, we just write ⊢ α and call α a theorem (of L0).
Prove for any φ, ψ ∈ Form(L0), {φ, ¬φ} ⊢ ψ.
We give a full derivation of ψ: ¬φ → (¬ψ → ¬φ) (A1) ¬φ ∈ Γ (¬ψ → ¬φ) MP from 1,2 (¬ψ → ¬φ) → (φ → ψ) (A3) (φ → ψ) MP from 1,2 φ ∈ Γ ψ MP from 5,6.
For any α, β ∈ Form(L0), the following are theorems.
(α → α)
(¬α → (α → β))
(¬¬α → α) and (α → ¬¬α)
((¬α → α) → α)
State the Soundness Theorem for L0
The system L0 is sound, i.e. if
Γ ⊢ α, then Γ |= α.
Prove the Soundness Theorem for L0
Suppose that Γ ⊢ α and let α1, . . . , αn = α be a derivation of α in L0.
Let v be any valuation for which ̃v(ψ) = T for all ψ ∈ Γ. By induction, we
show that for each i ≤ n, ̃v(αi) = T . Then also ̃v(α) = T.
It is easy to check that all axioms are tautologies, so if αi is an axiom,
̃v(αi) = T . If αi ∈ Γ, then ̃v(αi) = T by the assumption on v. Finally, if
αi follows by modus ponens from some αj , αk with j, k < i, then WLOG we
can assume αk = (αj → αi). And since ̃v(αj ) = T and ̃v(αj → αi) = T by
the induction hypothesis, we also get ̃v(αi) = T .
State the Deduction Theorem for L0
For any Γ ⊆ Form(L0) and
α ∈ Form(L0), Γ ∪ {α} ⊢ β if and only if Γ ⊢ (α → β).
Prove the Deduction Theorem for L0
Suppose that Γ ∪ {α} ⊢ β and let β1, . . . , βn = β be a derivation of β
from Γ ∪ {α}. By induction on k we can prove that Γ ⊢ (α → βk).
Suppose that Γ ⊢ (α → βi) for all i < k. If βk is an axiom or is in Γ, we
can proceed as follows:
Γ ⊢ βk Axiom or ∈ Γ
Γ ⊢ (βk → (α → βk)) (A1)
Γ ⊢ (α → βk) MP from 1,2.
If βk = α, it is easy to show that Γ ⊢ (α → βk), since we know from
Proposition (2.5) that ⊢ (α → α). Finally if βk follows from βi and βj
by MP (in the derivation of β from Γ ∪ {α}), we can WLOG assume that
βj = (βi → βk), and then
Γ ⊢ (α → βi) IH
Γ ⊢ (α → βj ) = (α → (βi → βk)) IH
Γ ⊢ ((α → (βi → βk)) → ((α → βi) → (α → βk))) (A2)
Γ ⊢ (α → βk) MP used twice.
Therefore, in any case, (α → βk) is provable from Γ. By induction we get
that also Γ ⊢ (α → βn) = (α → β).
The converse is easy. If Γ ⊢ (α → β), then following the same derivation
we can prove Γ ∪ {α} ⊢ (α → β). But also Γ ∪ {α} ⊢ α, and by modus
ponens we get Γ ∪ {α} ⊢ β.
If Γ ⊢ (α → β) and Γ ⊢ (β → γ), then ___
Prove it
Γ ⊢ (α → γ)
By following the same derivations as from Γ, we can prove Γ ∪ {α} ⊢
(α → β) and Γ ∪ {α} ⊢ (β → γ). We also have Γ ∪ {α} ⊢ α, so using MP
twice, we get Γ ∪ {α} ⊢ γ. By the deduction theorem, Γ ⊢ (α → γ).
A subset Γ ⊆ Form(L0) is consistent if
for no formula α we
have both Γ ⊢ α and Γ ⊢ ¬α.
By the soundness theorem, the ___ set is consistent.
empty
{φ, ¬φ} ⊢ ψ. Therefore if Γ is inconsistent, then
Γ ⊢ α for any formula
α ∈ Form(L0).
Γ ⊢ φ if and only if ___ is inconsistent.
Prove it
Γ ∪ {¬φ}
If Γ ⊢ φ, then Γ ∪ {¬φ} ⊢ φ. But also Γ ∪ {¬φ} ⊢ ¬φ, so Γ ∪ {¬φ}
is inconsistent.
Conversly, suppose that Γ ∪ {¬φ} is inconsistent, so that Γ ∪ {¬φ} ⊢ α
and Γ ∪ {¬φ} ⊢ ¬α for some α. Then
Γ ⊢ (¬φ → α) and
Γ ⊢ (¬φ → ¬α) by the deduction theorem,
Γ ⊢ ((¬φ → ¬α) → (α → φ)) (A3)
Γ ⊢ (α → φ) MP 2,3
Γ ⊢ (¬φ → φ) by Proposition (2.8) from 1,4
Γ ⊢ ((¬φ → φ) → φ) by Proposition (2.5)
Γ ⊢ φ MP 5,6.
If Γ is consistent and Γ ⊢ φ, then ___ is consistent
Prove it
Γ ∪ {φ}
Suppose that Γ ∪ {φ} is inconsistent, so that Γ ∪ {φ} ⊢ α and ¬α.
By deduction theorem, we get that Γ ⊢ (φ → α) and (φ → ¬α). But since
Γ ⊢ φ, by MP we get Γ ⊢ α and Γ ⊢ ¬α, and hence Γ is inconsistent.
Let Γ be consistent. If Γ ⊢ φ, then Γ ∪ {φ} is consistent,
otherwise (ie gamma does not prove phi)
Γ ∪ {¬φ} is consistent.
A subset Γ ⊆ Form(L0) is said to be maximal consistent
if
it is consistent, and for all φ ∈ Form(L0) either Γ ⊢ φ or Γ ⊢ ¬φ.
Let Γ ⊆ Form(L0) be a maximal consistent set. Then for all
formulas φ, ψ ∈ Form(L0),
Prove it
- Γ ⊢ ¬φ iff Γ ⊢/⊢ φ, and
- Γ ⊢ (φ → ψ) iff either Γ ⊢ ¬φ or Γ ⊢ ψ.
By consistency of Γ we cannot have both Γ ⊢ ¬φ and Γ ⊢ φ, and by
maximality we have at most one. Therefore Γ ⊢ ¬φ iff Γ ⊢/⊢ φ.
For the second claim, first suppose that Γ ⊢ (φ → ψ), but Γ ⊢/⊢ ¬φ and
Γ ⊢/⊢ ψ. Then by maximality, Γ ⊢ φ and Γ ⊢ ¬ψ. But by MP, Γ ⊢ ψ, which
contradicts consistency of Γ.
Conversely, if Γ ⊢ ¬φ, using Γ ⊢ ¬φ → (φ → ψ) from Proposition
(2.5) and MP we get that Γ ⊢ (φ → ψ). And if Γ ⊢ ψ, axiom 1 says
Γ ⊢ ψ → (φ → ψ), and from MP we get Γ ⊢ (φ → ψ).
Any maximal consistent set Γ is ___
Prove it
satisfiable
Define the valuation v by v(pi) = T if Γ ⊢ pi and v(pi) = F if Γ ⊢ ¬pi.
It is well-defined by maximality and consistency of Γ.
This serving as the basis, we can prove by induction on the length of φ
that ̃v(φ) = T if and only if Γ ⊢ φ:
If φ = ¬ψ, then ̃v(φ) = T when ̃v(ψ) = F , which is exactly when Γ ⊢/⊢ ψ
by the induction hypothesis. By the above lemma this is when Γ ⊢ ¬ψ = φ.
Similarly if φ = (ψ → χ), then ̃v(φ) = T when ̃v(ψ) = F or ̃v(χ) = T ,
which by the induction hypothesis is exactly when Γ ⊢/⊢ ψ or Γ ⊢ χ. By the
above lemma this is when Γ ⊢ (ψ → χ) = φ, which is what we wanted to
prove.
Therefore ̃v(φ) = T exactly for those φ, for which Γ ⊢ φ, in particular
for φ such that φ ∈ Γ.
If Γ is a consistent set of formulas, then there exists a
maximal consistent set Γ′ such that___
Prove it
such that Γ ⊆ Γ′.
The set of all formulas Form(L0) is countable, so let φ1, φ2, . . . be an
enumeration. Inductively, construct sets Γi by setting
Γ0 = Γ and Γn =
Γn−1 ∪ {φn} if Γn−1 ⊢ φn
or
Γn−1 ∪ {¬φn} if Γn−1 ⊢/⊢ φn.
Using Γ is consistent and Γ ⊢ φ, then Γ ∪ {φ} is consistent, and Γ ⊢ φ if and only if Γ ∪ {¬φ} is inconsistent, Γn is consistent for all n.
Now put Γ′ = ⋃(∞)(n=0) Γn. Clearly, Γ′ is maximal, in fact for any φ ∈ Form(L0), either φ ∈ Γ or ¬φ ∈ Γ.
Also, Γ′ is consistent; suppose it was not, so that Γ′ ⊢ α and Γ′ ⊢ ¬α for some α. Since the proofs of α and ¬α are of
finite length, they would use only finitely many formulas from Γ′, so there
would exist some n such that all formulas from Γ′ they use are actually in
Γn. But then Γn would also be inconsistent, which is a contradiction.
If Γ is consistent, it is
satisfiable
If Γ is inconsistent, it is
Prove it
not satisfiable
If Γ ⊢ α and Γ ⊢ ¬α for some formula α, then by the Soundness theorem also Γ |= α and Γ |= ¬α. If Γ is satisfiable by a valuation v, we would also have ̃v(α) = T and ̃v(¬α) = T , which is a contradiction.
State the Completeness Theorem for L0
If Γ |= φ, then Γ ⊢ φ
Prove the Completeness Theorem for L0
If Γ is inconsistent, then immediately Γ ⊢ φ for any formula φ. So
suppose that Γ is consistent, Γ |= φ but Γ ⊢/⊢ φ. Then by Γ ⊢ φ if and only if Γ ∪ {¬φ} is inconsistent, Γ ∪ {¬φ} is consistent, so it is satisfiable. Let v be a satisfying assignment,
so that ̃v(ψ) = T for all ψ ∈ Γ and also ̃v(¬φ) = T . But then ̃v(φ) = F ,
which is a contradiction to Γ |= φ.
State the Compactness Theorem for L0
A set of formulas Γ ⊆
Form(L0) is satisfiable if and only if every finite subset of Γ is satisfiable.
Prove the Compactness Theorem for L0
Clearly if Γ is satisfiable, then every its subset is satifiable.
If Γ is not satisfiable, then by If Γ is consistent, it is satisfiable it is not consistent, i.e.
there exists α such that Γ ⊢ α and Γ ⊢ ¬α. However, since both of these
proofs are finite, there exists a finite subset Γ′ ⊆ Γ such that Γ′ ⊢ α and
Γ′ ⊢ ¬α. By the Soundness theorem, Γ′ |= α and Γ′ |= ¬α, so Γ′ cannot be
satisfiable.
A formula φ ∈ Form(L0) is provable from a set of formulas
Γ in the system SQ, if
if there exists a finite sequence of sequents of the form
∆ ⊢SQ ψ (∆ ⊆ Form(L0) and ψ ∈ Form(L0)), where each sequent follows
from the previous ones using one of the following rules, and the last sequent
is Γ ⊢SQ φ.
(AS) If ψ ∈ ∆, we can always infer ∆ ⊢SQ ψ.
(MP) If ∆ ⊢SQ ψ and ∆′ ⊢SQ (ψ → φ), we can infer ∆ ∪ ∆′ ⊢SQ φ.
(DT) If ∆ ∪ {ψ} ⊢SQ χ, we can infer ∆ ⊢SQ (ψ → χ).
(PC) If ∆ ∪ {¬ψ} ⊢SQ χ and ∆′ ∪ {¬ψ} ⊢SQ ¬χ, we can infer ∆ ∪ ∆′ ⊢SQ ψ.
The systems L0 and SQ are
equivalent, i.e. Γ ⊢ φ (in L0)
if and only if Γ ⊢SQ φ.
The language L(FOPC) consists of
the logical symbols: vari-
ables x0, x1, . . . (xi for i ∈ N0), connectives ¬ and →, the universal quantifier
∀, parentheses, a comma, and an equality symbol
=^. (dot above the equals), and the non-logical symbols: k-ary predicate symbols P (k)
n , k-ary function symbols f (k)
n and constant
symbols cn for any k ∈ N, n ∈ N0.
A string of L(FOPC) is called a term if
it is a variable symbol,
a constant symbol, or of the form f_n^(k) (t1, . . . , tk), where ti are terms.
A string of L(FOPC) is called an atomic formula if
it is of the
form P_n^(k)(t1, . . . , tk) or t1
=^. t2, where all ti are terms.
A string of L(FOPC) is a formula if
it is an atomic
formula, if it is of the form ¬φ or (φ → ψ) where φ and ψ are formulas, or
if it is of the form ∀xiφ, where xi is a variable and φ is a formula.
State the Unique Readability Theorem for L(FOPC)
Any term, atomic formula
or a formula can be interpreted in a unique way according to the above for-
mation rules, similarly as in the language L of propositional formulas.
A first-order language (by a
language we will automatically mean a first-order language) L is
a subset of L(FOPC) containing all the logical symbols and possibly only some of the non-logical symbols. The terms, atomic formulas and formulas of L are defined similarly as for L(FOPC) . The sets of function, predicate and constant symbols of L will be denoted as Fct(L), Pred(L) and Const(L), respectively.
Let L be a language. An interpretation of L, or an L-
structure, is
a tuple curly A = <a>, where</a>
- the nonempty set A is the domain of curly A,
- for each f_n^(k) ∈ Fct(L), ⁻(f_n^(k)) is a function A^k → A,
- for each P_n^(k) ∈ Pred(L), ⁻P_n^(k) is a k-ary relation on A, and
- for each cn ∈ Const(L), ⁻c ∈ A.</a>
Let L be a language and curly A an L-structure. An assignment
in curly A is
a function v : {xi : i ∈ N0} → A.
An assignment v* is xi-equivalent to an assignment v if
v(xj ) = v*(xj ) for all j =/= i.
An assignment v in curly A induces an assignment on the terms of L: ___
Also, v induces a valuation on the for-
mulas of L, ̃v : Form(L) → {T, F }, given by ___
If ̃v(φ) = T , we also write
̃v : Terms(L) → A, defined by ̃ ̃v(xi) = v(xi),
̃v(ci) = ⁻ci and
̃v(f (t1, . . . , tk)) =
⁻f ( ̃v(t1), . . . , ̃v(tk)).
• ̃v(P (t1, . . . , tk)) = T
iff ⁻P( ̃v(t1), . . . , ̃v(tk)),
• ̃v(t1 =^. t2) = T
iff ̃v(t1) = ̃v(t2),
• ̃v(¬φ) = T iff ̃v(φ) = F
and ̃v(φ → ψ) = T iff ̃v(φ) = F or ̃v(ψ) = T,
• ̃v(∀xiφ) = T iff ̃v(φ) = T for all assignments v xi-equivalent to v
curly A |= φ[v], and say that φ is true in curly A under the
assignment v.
We will use the following abbreviations:
(α ∨ β) for (¬α → β),
(α ∧ β) for ¬(α → ¬β),
(α ↔ β) for ((α → β) ∧ (β → α)),
∃xiφ for ___
¬∀xi¬φ
A formula φ of a language L is logically valid, written as ___ if ___
A formula φ is satisfiable if ___
|= φ
curly A |= φ[v] for all L-structures curly A and all assignments v in curly A.
curly A |= φ[v] for some curly A and v
For any φ ∈ Form(L) and Γ ⊆ Form(L), φ is a logical
consequence of Γ, written as ___ if ___
Formulas φ and ψ are
logically equivalent ___ if ___
Γ |= φ, if for all L-structures A and all assignments v such that A |= ψ[v] for all ψ ∈ Γ, A |= φ[v].
(φ |==| ψ) if both {φ} |= ψ and {ψ} |= φ
Note. The symbol |= is now used in two different meanings, but this should
not cause any trouble.
An occurence of a variable xi in a formula φ is called bound if ___
Otherwise it is called
a ___
The set of variables occuring _ in φ
will be denoted as ___
it is contained in a (sub-)formula of the form ∀xiψ.
free
Free(φ)
A formula with no free occurences of variables is said to be ___, and is called a ___.
The set of all _ of
L is denoted as
closed
statement or a sentence
Sent(L)
Let L be a language, curly A an L-structure, φ a formula of L and v, v′ assignments in curly A such that v(xi) = v′(xi) for all variables xi with a free
occurence in φ. Then A |= φ[v] iff
Prove it.
curly A |= φ[v′]
Proof pg 12 Lemma 4.16
If φ is a statement, then curly A |= φ[v] iff
curly A |= φ[v′] for any
two assignments v and v′.
If φ is a statement we write curly A |= φ if ___
We say that φ is ___
or that curly A is ___
For a set of statements Γ, we say that curly A is a model of Γ (cutly A |= Γ) if
curly A |= φ[v] for some
(and thus for all) assignment v in curly A.
true in curly A
a model of φ
curly A |= ψ for all ψ ∈ Γ.
The only Example. Let L be a language containing a binary function symbol f and
a constant symbol c. Define the statements
φ1 = ∀x0∀x1∀x2f (x0, f (x1, x2)) =^. f (f (x0, x1), x2)
φ2 = ∀x0∃x1(f (x0, x1) =^. c ∧ f (x1, x0) =^. c)
φ3 = ∀x0(f (x0, c) =^. x0 ∧ f (c, x0) =^. x0)
and Γ = {φ1, φ2, φ3}. Then an L-structure A = <a> = </a><a> is a
model of φ iff</a>
it is a group with e being the identity element.
Let L be a language and α, β be formulas of L. If xi has
no free occurence in α, then |=
Prove it
|= (∀xi(α → β) → (α → ∀xiβ)).
Proof pg 13 Corollary 4.19
Let L be a language, φ be a formula in L, t be a term and
xi a variable. Then we say that t is free for xi in φ if ___
If t is free for xi in φ, we
define the substitution ___ by ___
no free occurence of
xi in φ is quantified over a variable occuring in t.
φ[t/xi]
replacing every free occurence of xi in φ
by the term t.
Let L be a language, A an L-structure, φ ∈ Form(L) and t a term free for xi in φ. Let v be any assignment in A and define
v′(xj ) =
{ v(xj ) if j =/= i}
{ ̃v(t) if j = i.}
Then A |= φ[v′] iff
Prove it
A |= φ[t/xi][v].
Proof pg 13-14 Lemma 4.21
If φ is a formula and t is a term free for xi in φ, then |=
Prove it
|= (∀xiφ → φ[t/xi]).
Proof pg 14 Corollary 4.22
To each first-order language L we associate the formal system ___ consisting of:
K(L), consisting of the axioms
(α → (β → α)) (A1)
((α → (β → γ)) → ((α → β) → (α → γ))) (A2)
((¬β → ¬α) → (α → β)) (A3)
(∀xiα → α[t/xi]) if t is free for xi in α (A4)
(∀xi(α → β) → (α → ∀xiβ)) if xi /∈ Free(α) (A5)
∀xi(xi =^. xi) (A6)
(xi =^. xj → (φ → φ′)) where φ is atomic and φ′ is obtained
from φ by replacing some occurences of xi by xj , (A7)
and the two rules of inference:
(MP) From α and (α → β) infer β.
(∀) From α infer ∀xiα. This is called the generalisation rule.
(In all of the axioms and rules of inference, α, β, γ are arbitrary formulas of
L, t is an arbitrary term and xi, xj are arbitrary variables.)
As before, we say that a formula α of L is a theorem of K(L) if ___
However, for the definition of a formula α being derivable from a set
of formulas Γ, we end up with: We say that α is derivable from Γ, and write
Γ ⊢ α, if ___
There exists a finite sequence of formulas α1, . . . , αn = α, such that
each αk is either an axiom or follows from the previous αis by one of the two
deduction rules.
There exists a finite sequence Γ1 ⊢ α1, . . . , Γ = Γn ⊢ αn = α, such
that each αk is either an axiom, belongs to Γk, or follows from the previous
αis by one of the three deduction rules:
(MP) from Γ ⊢ α and Γ ⊢ (α → β) infer Γ ⊢ β,
(∀) if xi does not appear free in Γ, then from Γ ⊢ α infer Γ ⊢ ∀xiα,
(TR) if Γ ⊢ α and Γ ⊆ Γ′, then Γ′ ⊢ α. This is called the thinning rule.
State the Soundness Theorem for K(L):
For any first-order language
L, the system K(L) is sound, i.e. if Γ ⊢ φ then Γ |= φ.
Prove the Soundness Theorem for K(L):
Proof pg 15 Theorem 5.3
State the Deduction Theorem for K(L):
For any first-order language
L, Γ ⊆ Form(L) and α ∈ Form(L), Γ ∪ {α} ⊢ β if and only if Γ ⊢ (α → β).
Prove the Deduction Theorem for K(L):
Proof pg 16 Theorem 5.4
If φ ∈ Form_n(L0) is a tautology of propositional calculus and ψ1, . . . , ψn are formulas of a first-order language L, thenthe formula φ′ obtained from φ by
replacing each pi by ψi is called a tautology of L.
If φ′ is a tautology of L, then
Prove it
⊢ L in K(L)
Proof pg 16 Proposition 5.6
A set Γ of sentences is consistent if
or no sentence φ we
have both Γ ⊢ φ and Γ ⊢ ¬φ
A set Γ ⊆ Sent(L) is called maximal consistent if
it is
consistent and for any sentence φ, either Γ ⊢ φ or Γ ⊢ ¬φ.
A set Γ ⊆ Sent(L) is called witnessing if
for all formulas φ
with no free variables other than xi, and such that Γ ⊢ ∃xiφ, there exists a constant cj ∈ Const(L) such that Γ ⊢ φ[cj /xi].
Let L be a first-order language without the equality sign and
let Γ be a set of sentences of L. Then the term model of Γ is
the L-structure
curly A whose domain is the set A = {t ∈ Terms(L) : t is closed}, the function
interpretations are given by
⁻f(t1, . . . , tk) = f(t1, . . . , tk), the constant interpretations by
⁻c = c, and the predicate interpretations by
⁻P (t1, . . . , tk) iff
Γ ⊢ P (t1, . . . , tk).
Let A be the term model of Γ ⊆ Sent(L) and let v be an
assignment in A given by v(xi) = si. Then for any term u, ̃v(u) =
Prove it
u[→s/→x]
(Note that by u[→s/→x] we mean replacing each xi by si simultaneously.)
Proof pg 17 Lemma 6.5
Let L be a first-order language without the equality sign. Let
curly A be the term model of a maximal consistent witnessing set Γ ⊆ Sent(L) and let v be an assignment in curly A given by v(xi) = si. Then for any formula φ of
L, curly A |= φ[v] if and only if
Prove it
Γ ⊢ φ[→s/→x]
(By by φ[→s/→x] we mean doing the usual substitutions [si/xi] simulta-
neously. Note that each si is free for xi in φ, since si are all closed terms.)
Proof pg 17-18 Lemma 6.6
Let L be a first-order language without the equality sign and
let curly A be the term model of a maximal consistent witnessing set Γ ⊆ Sent(L).
Then
Prove it
curly A |= Γ, i.e. curly A is really a model of Γ
For any ψ ∈ Γ and for any closed terms si, ψ[→s/→x] = ψ since ψ is just a sentence. Trivially Γ ⊢ ψ, so by the above lemma, curly A |= ψ[v] for any valuation v, and hence curly A |= ψ. This holds for any ψ ∈ Γ, so curly A |= Γ.
For any α, β ∈ Form(L) such that xi /∈ Free(β) we have
Prove it
⊢ (∀xi(α → β) → (∃xiα → β)
We have
∀xi(α → β) ⊢ (α → β) by (A4) and MP,
∀xi(α → β) ⊢ (¬β → ¬α) by tautology and MP,
∀xi(α → β) ⊢ ∀xi(¬β → ¬α) by (∀),
∀xi(α → β) ⊢ (¬β → ∀xi¬α) by (A5) and MP,
∀xi(α → β) ⊢ (¬∀xi¬α → β) by tautology and MP,
the result follows by the deduction theorem.
Let Γ ⊆ Form(L) and φ ∈ Form(L) with only xi occurring free
in φ. If cj is a constant symbol not occurring in Γ nor φ, and Γ ⊢ φ[cj /xi],
then
Prove it
Γ ⊢ φ
Proof pg 18 Lemma 6.9
If Γ ⊆ Sent(L) is consistent, ∃xiψ ∈ Sent(L), Γ ⊢ ∃xiψ, and cj does not occur in ψ nor in Γ, then Γ ∪ {ψ[cj /xi]} is
Prove it
consistent
Proof pg 19 Lemma 6.10
If Γ ⊆ Sent(L) is a consistent and φ ∈ Sent(L), then either
Γ ∪ {φ} or Γ ∪ {¬φ} is
Prove it
consistent
This follows easily from Lemma (2.11) (If Γ is consistent and Γ ⊢ φ, then Γ ∪ {φ} is consistent)
and
Lemma (2.10) (Γ ⊢ φ if and only if Γ ∪ {¬φ} is inconsistent.),
since all
the deductions in L0 apply in K(L).
Let L be a first-order language without the equality sign.
Then every consistent set of sentences of L has
Prove it
a model
Proof pg 19 Theorem 6.12
State the Completeness Theorem for K(L), reduced version
Let L be a first-order language without the equality sign, let Γ ⊆ Sent(L) and φ ∈ Sent(L). If Γ |= φ, then Γ ⊢ φ.
Prove the Completeness Theorem for K(L), reduced version
If Γ is inconsistent, the claim is trivial, so suppose Γ is consistent.
Since Γ |= φ, Γ ∪ {¬φ} does not have a model, and hence Γ ∪ {¬φ} is
inconsistent.
By Corollary (2.12) (Let Γ be consistent. If Γ ⊢ φ, then Γ ∪ {φ} is consistent,
otherwise Γ ∪ {¬φ} is consistent.)
(which applies just as well in K(L) as in
L0), or using the tautology ((¬φ → α) → ((¬φ → ¬α) → φ)), we get that
Γ ⊢ φ.
State the G ̈odel’s Completeness Theorem, 1930
Let L be a first-
order language, let Γ ⊆ Form(L) and φ ∈ Form(L). If Γ |= φ, then Γ ⊢ φ.
Proving this was 3/16 lectures worth of stuff, hopefully we don’t have to do that? Please chase this up.)
State the Compactness Theorem for K(L)
Let L be a first-order
language and Γ ⊆ Sent(L). Then Γ has a model if and only if every finite
subset of Γ has a model.
Prove the Compactness Theorem for K(L)
The forward direction is trivial. Conversely suppose that Γ does not
have a model, so that Γ |= φ for every φ ∈ Form(L), i.e. it is inconsistent.
Taking α such that Γ ⊢ α and Γ ⊢ ¬α, these two proofs only use a finite
subset Γ′ of Γ. But this means that Γ′ ⊢ α and Γ′ ⊢ ¬α, so that Γ′ is also
inconsistent. Therefore Γ′ does not have a model either.
State the L ̈owenheim-Skolem Theorem
If Γ ⊆ Sent(L) is consistent,
then it has a model with a countable domain.
Prove the L ̈owenheim-Skolem Theorem
If L does not contain the equality sign, this follows easily from
Corollary (6.7) (Let L be a first-order language without the equality sign and
let curly A be the term model of a maximal consistent witnessing set Γ ⊆ Sent(L). Then curly A |= Γ, i.e. curly A is really a model of Γ.)
and
Theorem (6.12)(Let L be a first-order language without the equality sign.
Then every consistent set of sentences of L has a model.):
there are only countably many closed terms
of L, so the term model is countable. If we include the equality sign, the
proof of the above results is slightly more technical; we need to factor the
elements of the term model up to equality =^. .
