Q and QS Flashcards
What is the Enumeration Theorem for P?
The formulas of P are effectively enumerable
Lindenbaum’s Lemma for P
Any p-consistent set of PS is a subset of some maximal p-consistent set of PS.
Finiteness Theorem for P
Definition: Г⊨P A iff there is a finite subset Δ of Г such that Δ⊨P A
Proof:
L=>R: Assume that Г ⊨P A. From strong completeness we get Г ⊢PS A.
But that means that there is a finite subset Δ of Г such that Δ⊢PSA. (Derivations are finitely long.)
And by (strong) soundness we get Δ⊨P A.
R=>L: Assume there is a finite subset Δ of Г such that Δ⊨P A
But a semantic consequence of a subset of Г is also a sematic consequence of Г itself. Thus Г ⊨P A
How do we prove that, if every finite subset of Γ is p-consistent, then Γ is p-consistent.
Proof (by reduction ad absurdum argument):
- Assume that (i) every finite subset of Г is p-consistent, but that (ii) Г is p-inconsistent.
- If (ii) Γ is p-inconsistent, then there is a formula A such that both Γ⊢A and Γ⊢∽A.
- But these two derivations each have only a finite number of steps.
- And so in total they will only depend on using a finite n formulas of Γ.
- Thus, even if Γ is infinite, there is a finite subset of Γ that will suffice for both derivations. I.e., there is a fin subset Δ, such that both Δ ⊢A and Δ ⊢∽A.
- Therefore there is a finite subset (namely, Δ) of Γ that is p-inconsistent.
- And this contradicts the assumption that (i) every finite subset of Г is p-consistent.
Compactness Theorem for P
Definition: If every finite subset of Γ has a model, then Γ has a model.
Proof:
1. Assume that every finite subset of Г has a model, but that Г has no model.
2. We showed in the last part (e) of the Henkin Proof: if Г is p-consistent, then it has a model.
3. From our assumption that Г has no model, we can then conclude that Г is p-inconsistent.
4. From this and our previous theorem (if every finite subset of Г is p-consistent, then Г is p-consistent), we can then conclude that some finite subset of Г is p-inconsistent.
5. And such a finite subset of Г would have no model (since, as was proved earlier [Hunter 32.6], if a set of formulas of P has a model, it is p-consistent in PS).
6. Thus, not every finite subset of Г has a model.
7. Therefore, if every finite subset of Г has a model, then Г has a model.
What is the alphabet of Q?
p ′ ( ) ∼ ⊃ x a f F * ∧
Propositional Symbols: p′ etc… Individual variabes: x′ etc… Individual constants: a′ Function symbols: One place: f*′ Two-place: f**′ etc… Predicate Symbols: One place: F*′ Two-place: F*′ Connectives: ~ , ⊃ Universal Quantifier: ∧
What is Q+?
Q+ is the same as Q but with denumerably many extra individual constants added.
What counts as a term for Q+?
- A constant
- A variable
- an n-place function symbol followed by n terms
- nothing else
What’s the definition of a formula of Q?
- Definition: Some string of symbols is a formula if it is a…
- Propositional symbol
- n-place predicate symbol followed by n terms
- if A is a formula of Q and v is a variable, then ∧vA is a formula of Q
- if A is a formula of Q, then ~A is a formula of Q
- if A and B are each formulas of Q, then (A ⊃ B) is a formula of Q
- nothing else
Are propositional symbols terms?
No.
What is a closed term?
Terms with no variables.
What is an example of an occurrence of a variable being in the scope of a quantifier?
∧vA
What is an example of an occurrence of a variable not being in the scope of a quantifier?
((∧vA) ⊃ B) In this case, B is not within the scope of the quantifier.
What is the difference between a free variable and a bound variable?
An occurrence of a variable is bound if it appears immediately after a quantifier, like ∧x′
Or is within the scope of a quantifier, like (∧v(A ⊃ B)).
An occurrence of a variable is free if it is not bound.
What’s the difference between an occurrence of a variable being free as opposed to a variable being free?
A variable v is free in a formula A iff v has some free occurrences in A. An occurrence of a variable is free if it is not bound.
What does it mean for a formula to be open or closed?
A formula A is closed iff no variable occurs free in A. A formula A is open iff some variable occurs free. A formula A is open iff it is not closed.
What is a sentence of Q?
A closed formula of Q.
What is the closure of a formula?
- If the variables free in a formula A are v1, v2, v3,…vn, then the formula Λv1 Λv2 Λv3…ΛvnA is a closure of A.
- If A is a closed formula, then A is a closure of itself.
- If A is a closed formula, then ΛvA is a closure of A, where v is any variable.
- Any closure of a closure of formula A is itself a closure of A.
What is substitution?
Let A be a formula, v a variable, and t a term. At/v is the formula that results from substituting term t for every free occurrence of v in formula A.
What does it mean for a term to be free for a variable in a formula?
- If t is a variable: t is free for v in A iff t occurs free in At/v wherever v occurs free in A.
- If t is a function symbol in which variables u1, u2,…un occur:
- t is free for v in A iff all occurrences of variables u1, u2, u3,…un are free in At/v wherever v occurs free in A.
- If t is a closed term
What is an interpretation of Q?
- Specify some non-empty set, as the domain (or the universe of discourse) of the interpretation.
- Specify interpretations for propositional symbols, constants, function symbols, and predicate symbols:
a. Each propositional symbol is assigned a truth-value.
b. Each constant is assigned an element of the domain of the interp’n.
c. Each n-place func’n symbol is assigned an n-place func’n whose inputs and outputs are elements of the domain.
d. Each n-place predicate symbol is assigned an n-place relation defined for any elements in the domain.
How do we specify an n-place relation?
By specifying a set of ordered n-tuples of elements from the domain, as the extension assigned to the pred. symbol. The extension of a predicate, unlike the domain, can be the empty set.
