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.
How do we specify an n-place function?
For each ordered n-tuple of elements of the domain as input, we can specify one element of the domain as its output.
What is a sequence?
A sequence (for a given interpretation I) is a denumerable ordered sequence of elements of the domain for interpretation I. A denumerable sequence tells us which element of the domain is to be assigned to each variable in our formal language.
Note that the same object may occupy more than one place in the sequence, or an object in the domain may occupy no place in the sequence.
What is an n-variant of a sequence?
- For an interpretation I, sequence s′ is an n-variant of sequence s iff (i) s′ is the same as sequence s except for the element (of the domain of I) assigned to the nth member of the sequence s.
(Hunter doesn’t use the term “n-variant”. He does use the symbolism s(d/n), which stands for the sequence you get from s when you replace its nth member with the object d.)
What is t*s?
- Case (i) If term t is a constant: t*s is the element of the domain of I that I has assigned to that constant.
- Case (ii) If term t is the nth variable: t*s is the element of the domain of I that occupies the nth place in sequence s.
- Case (iii) If term t is an n-place function symbol f, followed by n terms t1, t2, …tn [t is f t1t2…tn]: ts = f (t1s, t2s, …tns), where f is the function that interpretation I has assigned to function symbol f.
Some sequence s satisfies a formula A for interpretation I if…?
- A is a propositional symbol.
a. If A is a propositional symbol, sequence s satisfies formula A for interp I iff interp I assigns true to A. - A is of the form Ft1t2…tn, where F is an n-place predicate symbol, and t1, t2, …tn are terms.
a. If A is an atomic wff of the form Ft1. . . tn… where F is an n-place predicate symbol and t1, . . ., tn are terms, then s satisfies A iff is a member of the set of ordered n-tuples assigned by I to F. (See Hunter 147) - A is a formula of the form ∼B
a. If A is a formula of the form ∼B, sequence s satisfies formula A for interpretation I iff sequence s does not satisfy formula B for interpretation I. - A is a formula of the form (B⊃C)
a. If A is a formula of the form (B⊃C), sequence s satisfies formula A for interpretation I iff sequence s does not satisfy formula B for interp I or sequence s does satisfy formula C for interp I. - A is of the form ΛvB, where v is a variable.
a. If A is of the form ΛvB, where v is the nth variable in our list, sequence s satisfies formula A for interpretation I iff every n-variant of s satisfies formula B for interpretation I.
When is a formula satisfiable in Q?
Formula A is satisfiable iff there is some interpretation for which A is satisfied by at least one (denum.) sequence of elements for that interp.
When is a set of formulas Γ simultaneously satisfiable in Q?
A set of formulas Г is simultaneously satisfiable iff there is some interp for which at least one (denum.) sequence of elements for that interp. satisfies all the formulas in Г.
When is a formula A true for an interpretation in Q?
Formula A is true for an interpretation I iff every denumerable sequence of elements of the domain of I satisfies A.
Note that in Q we only say that every closed formula is either true or false under an interpretation I. Note, however, that an open formula can be true under an interp. E.g. (F′x′ ⊃ F′x′) is true under any interp.
What is a model of a formula in Q?
A model of a formula A is an interpretation that makes formula A true.
What is a model of a set of formulas in Q?
A model of a set Γ of formulas is an interpretation that makes all the formulas in Γ true.
When is a formula logically valid?
A formula is logically valid iff it is true for every interpretation.
When is a formula B a semantic consequence of a formula A?
Formula B is a semantic consequence of a formula A iff for every interpretation, every sequence that satisfies A also satisfies B. Symbolized: A⊨Q B
When is formula B a semantic consequence of a set Γ of formulas?
Formula B is a semantic consequence of a set Г of formulas iff for every interp, every sequence that simult’ly satisfies every formula in Г also satisfies B. Symbolized: Г⊨Q B
What is k-validity?
Formula A is k-valid iff A is true for every interpretation that has a domain of exactly k elements.
What is our convention concerning the empty set and denumerable sequences?
Every denumerable sequence satisfies the empty set.
A formula A′ is an instance of a tautological schema of Q iff…
- There is a formula A that is a tautological formula of formal language P
whose only propositional symbols are P1, P2, …, Pn , and - Formula A′ is the result of substituting formulas Q1, Q2, … Qn (of Q) for P1, P2, … Pn , respectively, in formula A.
What are some model-theoretic metatheorems we need to show the soundness of QS?
- Every instance of a tautological schema of Q is logically valid.
- For arbitrary formulas A, B, and for any variable v, (Λv(A⊃B) ⊃ (ΛvA⊃ ΛvB)) is logically valid.
- For an arbitrary formula A, and for any variable v, if a term t is free for v in A, then (ΛvA ⊃ At/v) is logically valid.
- For arbitrary formulas A, and for any variable v, if A lacks free v, then (A⊃ ΛvA) is logically valid.
- For arbitrary formulas A, and for any variable v, if A is logically valid, then ΛvA is logically valid.
- If A and A⊃B are both logically valid formulas of Q, then B is also a logically valid formula of Q.
- For arbitrary formula A, A is true under an interpretation I iff Ac is true under that interpretation (where Ac is a closure of A). (Not necessary for soundness)
What are the axioms of QS?
[QS 1] (A⊃(B⊃A))
[QS 2] ((A⊃(B⊃C)) ⊃ ((A⊃B)⊃(A⊃C)))
[QS 3] ((∼A⊃∼B)⊃ (B⊃A))
[QS 4] (ΛvA ⊃ At/v) if t is free for v in A
[QS 5] (A ⊃ ΛvA) if v is not free in A
[QS 6] (Λv(A⊃B) ⊃ (ΛvA ⊃ ΛvB))
[QS 7] If A is an axiom, then ΛvA is an axiom.
Note, 1-6 are axiom schemata. QS7 is a recursive clause in stipulating what counts as an axiom of QS.
What is the only rule of inference for QS?
‘immediate consequence’ aka modus ponens
Can the deduction theorem of PS be applied to QS?
Yes. This is because the proof of the deduction theorem depended on three facts, (a) it has axiom schema PS1 (which corresponds to QS1), (b) it has axiom schema PS2 (which corresponds to QS2), and (c) modus ponens is the only rule of inference. QS has all these properties. So, the deduction theorem applies to QS.
What’s a proof in QS?
A proof in QS is a finite sequence of formulas of Q, each of which is
either…
1. an axiom of QS .
2. an immediate consequence (by the rule of inference of QS) of two formulas preceding it somewhere in the sequence.
A proof in QS of formula A is a proof in QS in which A is the last formula in the proof.
What is a theorem in QS?
Formula A is a theorem of QS iff there is a proof in QS of formula A. This is symbolized: ⊢QS A
What is a derivation in QS?
A derivation in QS of formula A (of Q) from a set Г of formulas of Q is a finite sequence of formulas of Q, the last of which is formula A, such that each formula in the sequence is either…
- an axiom of QS
- an immediate consequence (by the rule of inference of QS) of two formulas preceding it somewhere in the sequence
- a member of set Г
When is a formula a syntactic consequence in QS of a set Γ?
Formula A is a syntactic consequence in QS of a set Г of formulas of Q iff there is a derivation in QS of A from the set Г
This is symbolized: Г⊢QS A
When is a set of formulas Γ proof-theoretically consistent of QS?
A set Г of formulas of Q is a (proof-theoretically) consistent set of QS iff there is no formula A such that both A is a syntactic consequence of Г and ∼A is a syntactic consequence of Г.
When is a set of formulas Γ a proof-theoretically inconsistent set of QS?
A set Г of formulas of Q is a (proof-theoretically) inconsistent set of QS iff it is not a proof-theoretically consistent set of QS.
When is a formal system consistent?
Formal system S is consistent iff there is no formula A such that both A is a theorem of S and ∼the negation of A is a theorem of S.
When is QS consistent?
Formal system QS is consistent iff there is no formula A such that both A is a theorem of QS and ∼A is a theorem of QS.
When does QS has a model?
Formal system QS has a model iff the set of all the theorems of QS has a model
What is the deduction theorem for QS? What is its converse?
- Deduction Theorem for QS: If Г, A⊢QS B, then Г⊢QS (A⊃B).
a. Converse of the Deduction Theorem for QS: If Г⊢QS (A⊃B), then Г, A⊢QS B.
What is the deduction theorem for QS? What is its converse?
- Deduction Theorem for QS: If Г, A⊢QS B, then Г⊢QS (A⊃B).
2. Converse of the Deduction Theorem for QS: If Г⊢QS (A⊃B), then Г, A⊢QS B.
What is strong soundness for QS?
(Strong) soundness of QS: If Г⊢QS A , then Г⊨Q A
If Г ∪ {~A} is an inconsistent set of formulas of QS, then Г⊢QS A
If Г ∪ {A} is an inconsistent set of formulas of QS, then Г⊢QS ~A
What is strong soundness for QS?
(Strong) soundness of QS:
- If Г⊢QS A , then Г⊨Q A
- If Г ∪ {~A} is an inconsistent set of formulas of QS, then Г⊢QS A
- If Г ∪ {A} is an inconsistent set of formulas of QS, then Г⊢QS ~A
Is QS strongly semantically complete?
Yes.
