Logic Flashcards

(114 cards)

1
Q

curly L stands for what?

A

The alphabet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does the alphabet consist of in propositional calculus?

A

propositional variables p_0, p_1, . . . (p_i for each i ∈ N_0), negation ¬, implication
→, conjunction ∧, disjunction ∨, equivalence ↔ and parentheses (, ).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What group are the symbols ¬, ∧, ∨, ↔ part of?

A

They are logical connectives

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a string of curly L?

A

a finite sequence of symbols from curly L

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

The length of a

string is

A

the number of symbols it contains.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

A string of L is a formula of L if and only if

A

• 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

The set of all formulas of L is denoted

A

Form(L).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

State the Unique Readability Theorem

A

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 *.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Prove the Unique Readability Theorem

A

Problem Sheet 1 (By induction on the length of φ)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

A valuation is

A

a function v : {pi : i ∈ N0} → {T, F }, where

the values T, F are called true and false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Given a valuation v, we can __ to a __ ̃v by…

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Recount the table of valuations of the unary and binary connectives ¬ψ, ψ → χ, ψ ↔ χ, ψ ∧ χ, ψ ∨ χ

A
ψ χ ¬ψ ψ → χ ψ ↔ χ 
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

A valuation v satisfies a formula φ if

A

̃v(φ) = T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

A formula

that is satisfied by some valuation is called

A

satisfiable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

A formula that is

satisfied by no valuation is called

A

a contradiction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

A formula φ that is satisfied

by all valuations is called ___, written

A

a tautology, written as |= φ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

A formula φ is a logical consequence of ψ if _____, we write

A

or all valuations
v such that ̃v(ψ) = T we also have ̃v(φ) = T .
We write ψ |= φ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Let Γ be a set of formulas and φ a formula. Then φ is a

logical consequence of Γ if ____, we write

A

or all valuations v such that ̃v(ψ) = T for all
ψ ∈ Γ, we also have ̃v(φ) = T.

We write Γ |= φ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

For any formulas φ and ψ, we have ψ |= φ iff

In fact, for any Γ ⊆ Form(L), Γ ∪ {ψ} |= φ iff

A

|= (ψ → φ)

Γ |= (ψ → φ)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Formulas ψ and φ are logically equivalent iff

We write

A

φ |= ψ and ψ |= φ, i.e. if
̃v(ψ) = ̃v(φ) for all valuations v

We write ψ |==| φ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

For any formulas α, β, γ we have (α ∧ (β ∧ γ)) |==|___ and (α ∧ β) |==|

Therefore, when we are only interested in formulas up to

A

(α ∧ (β ∧ γ)) |==| ((α ∧ β) ∧ γ) 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q
The following equivalences hold:
¬ (∨(n)(i=1) Ai) |==|
¬ (∧(n)(i=1) Ai) |==|
(A → B) |==|
(A ∨ B) |==| \_\_\_ |==|
(A ∧ B) |==|
(A ↔ B) |==|
A
¬ (∨(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))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Let Vn be the set of ___,

then an n-ary truth function is

A

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 }.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Denote by Form_n(L) the ___

If φ ∈ Form_n(L), then φ
determines an ___ J_φ given by v |→ v(φ)

A

set of all formulas of L in which
only the first n propositional variables occur.

n-ary truth function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
For any n ∈ N and any n-ary truth function J there exists
φ ∈ Formn(L) such that J_φ = J
26
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. ```
27
A formula which is a conjunction of pis and ¬pis is called
a conjunctive clause
28
A formula which is a disjunction of conjunctive clauses | is said to be
in disjunctive normal form (DNF)
29
Similarly, a conjunction of | disjunctive clauses is called
a conjunctive normal form (CNF)
30
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.
31
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. ```
32
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.
33
The set {¬, →} is
adequate
34
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.
35
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 β.
36
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 = α.
37
The sequence α1, . . . , αn where αn = α is called a
proof or a derivation of α.
38
If α is deducible from Γ, we write
Γ ⊢ α
39
If ∅ ⊢ α, we just write __ | and call α a
If ∅ ⊢ α, we just write ⊢ α and call α a theorem (of L0).
40
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. ```
41
For any α, β ∈ Form(L0), the following are theorems.
(α → α) (¬α → (α → β)) (¬¬α → α) and (α → ¬¬α) ((¬α → α) → α)
42
State the Soundness Theorem for L0
The system L0 is sound, i.e. if | Γ ⊢ α, then Γ |= α.
43
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 .
44
State the Deduction Theorem for L0
For any Γ ⊆ Form(L0) and | α ∈ Form(L0), Γ ∪ {α} ⊢ β if and only if Γ ⊢ (α → β).
45
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 Γ ∪ {α} ⊢ β.
46
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, Γ ⊢ (α → γ).
47
A subset Γ ⊆ Form(L0) is consistent if
for no formula α we | have both Γ ⊢ α and Γ ⊢ ¬α.
48
By the soundness theorem, the ___ set is consistent.
empty
49
{φ, ¬φ} ⊢ ψ. Therefore if Γ is inconsistent, then
Γ ⊢ α for any formula | α ∈ Form(L0).
50
Γ ⊢ φ 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.
51
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.
52
Let Γ be consistent. If Γ ⊢ φ, then Γ ∪ {φ} is consistent, | otherwise (ie gamma does not prove phi)
Γ ∪ {¬φ} is consistent.
53
A subset Γ ⊆ Form(L0) is said to be maximal consistent | if
it is consistent, and for all φ ∈ Form(L0) either Γ ⊢ φ or Γ ⊢ ¬φ.
54
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 Γ ⊢ (φ → ψ).
55
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 φ ∈ Γ.
56
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.
57
If Γ is consistent, it is
satisfiable
58
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.
59
State the Completeness Theorem for L0
If Γ |= φ, then Γ ⊢ φ
60
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 Γ |= φ.
61
State the Compactness Theorem for L0
A set of formulas Γ ⊆ | Form(L0) is satisfiable if and only if every finite subset of Γ is satisfiable.
62
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.
63
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 ψ.
64
The systems L0 and SQ are
equivalent, i.e. Γ ⊢ φ (in L0) | if and only if Γ ⊢SQ φ.
65
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.
66
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.
67
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.
68
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.
69
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.
70
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. ```
72
Let L be a language and curly A an L-structure. An assignment in curly A is
a function v : {xi : i ∈ N0} → A.
73
An assignment v* is xi-equivalent to an assignment v if
v(xj ) = v*(xj ) for all j =/= i.
74
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.
75
We will use the following abbreviations: (α ∨ β) for (¬α → β), (α ∧ β) for ¬(α → ¬β), (α ↔ β) for ((α → β) ∧ (β → α)), ∃xiφ for ___
¬∀xi¬φ
76
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
77
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.
78
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(φ)
79
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)
80
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
81
If φ is a statement, then curly A |= φ[v] iff
curly A |= φ[v′] for any | two assignments v and v′.
82
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 ψ ∈ Γ.
83
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 = = is a model of φ iff
it is a group with e being the identity element.
84
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
85
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.
86
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
87
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
88
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.)
89
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.
90
State the Soundness Theorem for K(L):
For any first-order language | L, the system K(L) is sound, i.e. if Γ ⊢ φ then Γ |= φ.
91
Prove the Soundness Theorem for K(L):
Proof pg 15 Theorem 5.3
92
State the Deduction Theorem for K(L):
For any first-order language | L, Γ ⊆ Form(L) and α ∈ Form(L), Γ ∪ {α} ⊢ β if and only if Γ ⊢ (α → β).
93
Prove the Deduction Theorem for K(L):
Proof pg 16 Theorem 5.4
94
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.
95
If φ′ is a tautology of L, then Prove it
⊢ L in K(L) Proof pg 16 Proposition 5.6
96
A set Γ of sentences is consistent if
or no sentence φ we | have both Γ ⊢ φ and Γ ⊢ ¬φ
97
A set Γ ⊆ Sent(L) is called maximal consistent if
it is | consistent and for any sentence φ, either Γ ⊢ φ or Γ ⊢ ¬φ.
98
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].
99
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).
100
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
101
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
102
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 |= Γ.
103
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.
104
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
105
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
106
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).
107
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
108
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 Γ ⊢ φ.
109
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 Γ ⊢ φ.
110
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.)
111
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.
112
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.
113
State the L ̈owenheim-Skolem Theorem
If Γ ⊆ Sent(L) is consistent, | then it has a model with a countable domain.
114
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 =^. .