Q and QS

Question 1

What is the Enumeration Theorem for P?

Answer 1

The formulas of P are effectively enumerable

Question 2

Lindenbaum’s Lemma for P

Answer 2

Any p-consistent set of PS is a subset of some maximal p-consistent set of PS.

Question 3

Finiteness Theorem for P

Answer 3

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

Question 4

How do we prove that, if every finite subset of Γ is p-consistent, then Γ is p-consistent.

Answer 4

Proof (by reduction ad absurdum argument):

1. Assume that (i) every finite subset of Г is p-consistent, but that (ii) Г is p-inconsistent.
2. If (ii) Γ is p-inconsistent, then there is a formula A such that both Γ⊢A and Γ⊢∽A.
3. But these two derivations each have only a finite number of steps.
4. And so in total they will only depend on using a finite n formulas of Γ.
5. 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.
6. Therefore there is a finite subset (namely, Δ) of Γ that is p-inconsistent.
7. And this contradicts the assumption that (i) every finite subset of Г is p-consistent.

Question 5

Compactness Theorem for P

Answer 5

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.

Question 6

What is the alphabet of Q?

Answer 6

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: ∧

Question 7

What is Q+?

Answer 7

Q+ is the same as Q but with denumerably many extra individual constants added.

Question 8

What counts as a term for Q+?

Answer 8

1. A constant
2. A variable
3. an n-place function symbol followed by n terms
4. nothing else

Question 9

What’s the definition of a formula of Q?

Answer 9

1. Definition: Some string of symbols is a formula if it is a…
2. Propositional symbol
3. n-place predicate symbol followed by n terms
4. if A is a formula of Q and v is a variable, then ∧vA is a formula of Q
5. if A is a formula of Q, then ~A is a formula of Q
6. if A and B are each formulas of Q, then (A ⊃ B) is a formula of Q
7. nothing else

Question 10

Are propositional symbols terms?

Answer 10

No.

Question 11

What is a closed term?

Answer 11

Terms with no variables.

Question 12

What is an example of an occurrence of a variable being in the scope of a quantifier?

Answer 12

∧vA

Question 13

What is an example of an occurrence of a variable not being in the scope of a quantifier?

Answer 13

((∧vA) ⊃ B) In this case, B is not within the scope of the quantifier.

Question 14

What is the difference between a free variable and a bound variable?

Answer 14

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.

Question 15

What’s the difference between an occurrence of a variable being free as opposed to a variable being free?

Answer 15

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.

Question 16

What does it mean for a formula to be open or closed?

Answer 16

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.

Question 17

What is a sentence of Q?

Answer 17

A closed formula of Q.

Question 18

What is the closure of a formula?

Answer 18

1. 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.
2. If A is a closed formula, then A is a closure of itself.
3. If A is a closed formula, then ΛvA is a closure of A, where v is any variable.
4. Any closure of a closure of formula A is itself a closure of A.

Question 19

What is substitution?

Answer 19

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.

Question 20

What does it mean for a term to be free for a variable in a formula?

Answer 20

1. 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.
2. If t is a function symbol in which variables u1, u2,…un occur:
3. 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.
4. If t is a closed term

Question 21

What is an interpretation of Q?

Answer 21

1. Specify some non-empty set, as the domain (or the universe of discourse) of the interpretation.
2. 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.

Question 22

How do we specify an n-place relation?

Answer 22

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.

Question 23

How do we specify an n-place function?

Answer 23

For each ordered n-tuple of elements of the domain as input, we can specify one element of the domain as its output.

Question 24

What is a sequence?

Answer 24

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.

Question 25

What is an n-variant of a sequence?

Answer 25

1. 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.)

Question 26

What is t*s?

Answer 26

1. 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. 2. 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. 3. Case (iii) If term t is an n-place function symbol f, followed by n terms t1, t2, …tn [t is f t1t2…tn]: t*s = f (t1*s, t2*s, …tn*s), where f is the function that interpretation I has assigned to function symbol f.

Question 27

Some sequence s satisfies a formula A for interpretation I if…?

Answer 27

1. 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. 2. 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) 3. 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. 4. 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. 5. 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.

Question 28

When is a formula satisfiable in Q?

Answer 28

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.

Question 29

When is a set of formulas Γ simultaneously satisfiable in Q?

Answer 29

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

Question 30

When is a formula A true for an interpretation in Q?

Answer 30

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.

Question 31

What is a model of a formula in Q?

Answer 31

A model of a formula A is an interpretation that makes formula A true.

Question 32

What is a model of a set of formulas in Q?

Answer 32

A model of a set Γ of formulas is an interpretation that makes all the formulas in Γ true.

Question 33

When is a formula logically valid?

Answer 33

A formula is logically valid iff it is true for every interpretation.

Question 34

When is a formula B a semantic consequence of a formula A?

Answer 34

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

Question 35

When is formula B a semantic consequence of a set Γ of formulas?

Answer 35

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

Question 36

What is k-validity?

Answer 36

Formula A is k-valid iff A is true for every interpretation that has a domain of exactly k elements.

Question 37

What is our convention concerning the empty set and denumerable sequences?

Answer 37

Every denumerable sequence satisfies the empty set.

Question 38

A formula A′ is an instance of a tautological schema of Q iff…

Answer 38

1. There is a formula A that is a tautological formula of formal language P whose only propositional symbols are P1, P2, …, Pn , and 2. Formula A′ is the result of substituting formulas Q1, Q2, … Qn (of Q) for P1, P2, … Pn , respectively, in formula A.

Question 39

What are some model-theoretic metatheorems we need to show the soundness of QS?

Answer 39

1. Every instance of a tautological schema of Q is logically valid. 2. For arbitrary formulas A, B, and for any variable v, (Λv(A⊃B) ⊃ (ΛvA⊃ ΛvB)) is logically valid. 3. 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. 4. For arbitrary formulas A, and for any variable v, if A lacks free v, then (A⊃ ΛvA) is logically valid. 5. For arbitrary formulas A, and for any variable v, if A is logically valid, then ΛvA is logically valid. 6. If A and A⊃B are both logically valid formulas of Q, then B is also a logically valid formula of Q. 7. 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)

Question 40

What are the axioms of QS?

Answer 40

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

Question 41

What is the only rule of inference for QS?

Answer 41

‘immediate consequence’ aka modus ponens

Question 42

Can the deduction theorem of PS be applied to QS?

Answer 42

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.

Question 43

What’s a proof in QS?

Answer 43

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.

Question 44

What is a theorem in QS?

Answer 44

Formula A is a theorem of QS iff there is a proof in QS of formula A. This is symbolized: ⊢QS A

Question 45

What is a derivation in QS?

Answer 45

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… 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 3. a member of set Г

Question 46

When is a formula a syntactic consequence in QS of a set Γ?

Answer 46

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

Question 47

When is a set of formulas Γ proof-theoretically consistent of QS?

Answer 47

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

Question 48

When is a set of formulas Γ a proof-theoretically inconsistent set of QS?

Answer 48

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.

Question 49

When is a formal system consistent?

Answer 49

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.

Question 50

When is QS consistent?

Answer 50

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.

Question 51

When does QS has a model?

Answer 51

Formal system QS has a model iff the set of all the theorems of QS has a model

Question 52

What is the deduction theorem for QS? What is its converse?

Answer 52

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

Question 53

What is the deduction theorem for QS? What is its converse?

Answer 53

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

Question 54

What is strong soundness for QS?

Answer 54

(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

Question 55

What is strong soundness for QS?

Answer 55

(Strong) soundness of QS: 1. If Г⊢QS A , then Г⊨Q A 2. If Г ∪ {~A} is an inconsistent set of formulas of QS, then Г⊢QS A 3. If Г ∪ {A} is an inconsistent set of formulas of QS, then Г⊢QS ~A

Question 56

Is QS strongly semantically complete?

Answer 56

Yes.