K and Q=

Question 1

How is a first order theory, K, related to Q?

Answer 1

1. It has the same language as Q or Q+, except that…
   a. some or all of the propositional symbols may be absent…
   b. some or all of the function symbols may be absent…
   c. some or all of the constants may be absent…
   d. some but not all of the predicate symbols may be absent…
2. Its axioms will form two groups:
   a. its logical axioms are the same as the axioms of QS,
   b. its proper axioms, which are countable in number, are the members of a fixed set of closed formulas of the language of the system,
3. Its rule of inference is modus ponens.

Question 2

What is a logical axiom?

Answer 2

Its logical axioms are specified by the schemata QS1-7 applied to the wffs of its language, with QS7 re-worded to‘If A is a logical axiom, then AvA is also a logical axiom’. So every first order theory has for its logical axioms all the axioms of QS (and more, if its language is Q+).

Question 3

What are proper axioms?

Answer 3

A closed wff of the language.

Question 4

What is the deduction theorem for K? What about the converse?

Answer 4

The deduction theorem of QS holds for all first-order theories.

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

When is a first order theory K consistent?

Answer 5

A first order theory K is consistent iff there is no formula A such that both A is a theorem of K and ∼A is a theorem of K.

Question 6

What are there effective enumerations of in a first order theory K?

Answer 6

1. The formulas of K
2. The closed formulas of K
3. The formulas of K with exactly one free variable
4. The closed terms of K

Question 7

What are some useful metatheorems about the relationship between closed formulas and the consistency of K?

Answer 7

1. If A is a closed formula of K that is not a theorem of K, then K + {∼A} is a consistent first order theory.
2. If ∼A is a closed formula of K that is not a theorem of K, then K + {A} is a consistent first order theory.

Question 8

What is an extension of a system?

Answer 8

1. A system S′ is an extension of a system S iff every theorem of S is a theorem of S′.
2. If a system S′ is an extension of a system S, then every model of S′ is a model of S.

Question 9

What does it mean to be negation-complete?

Answer 9

A system S is negation-complete iff for every closed formula (sentence) A of S, either A is a theorem of S or ∼A is a theorem of S.

Question 10

What is Lindenbaum’s Lemma for first order theories?

Answer 10

If K is a consistent first order theory, then there is a first order theory K′ that is a consistent, negation-complete extension of K with the same formulas as K.

Question 11

What is K′ (or K∞)?

Answer 11

Let K′ be the system that results from taking as its axioms all the axioms of all the Ki’s. K′ is a first order theory since every new axiom that has been added to K is a closed formula. And since every theorem of K is a theorem of K′, it is an extension of K.

Question 12

What is the Additional Constants Metatheorem?

Answer 12

If K is a consistent first order theory, then the system that results from adding an effectively enumerable, denumerable set of constants to K (with no new proper axioms) is a consistent first order theory that is an extension of K.

Question 13

What is the additional UG Axioms Metatheorem?

Answer 13

1. Let ΛvA be a closed formula of K.
2. Let c be a constant of K that…
   a. does not occur in any in any proper axiom of K, and
   b. does not occur in formula A.
3. Let K′ be the system that results from adding (Ac/v ⊃ ΛvA) as a proper axiom. [K′ is K + {(Ac/v ⊃ ΛvA)}.]
4. If K is a consistent first order theory, then K′ is a consistent first order theory that is an extension of K.

Question 14

When is a system closed?

Answer 14

A system S is closed iff for any formula A having just one free variable, if the result of substituting any closed term for that free variable v is a theorem of S, then ∧vA is a theorem too.

Question 15

What is the closedness metatheorem?

Answer 15

If K is a consistent first order theory, then there is a first order theory that is a consistent, closed, negation-complete extension of K.

Question 16

What is the Key Theorem?

Answer 16

(Metatheorem 45.15): Any consistent first order theory has a denumerable model.

Question 17

What is the Lowenheim-Skolem Theorem?

Answer 17

(Metatheorem 45.18): Any first order theory that has a model has a denumerable model.

Question 18

Is QS semantically complete?

Answer 18

Yes. (Metatheorem 46.1) shows us that every logically valid formula of Q is a theorem of QS.

Question 19

What is the Alt-Key Theorem?

Answer 19

Metatheorem 45.16: Any consistent set of closed formulas of a first order theory has a denumerable model. This is equivalent to the Key Theorem (45.15).

Question 20

What is Godel’s metatheorem 45.17?

Answer 20

Any consistent set of formulas of a first order theory is simultaneously satisfiable in a denumerable domain.

Question 21

What is the compactness metatheorem?

Answer 21

If every finite subset of proper axioms of a first order theory K has a model, then K has a model. (See Hunter p.190 for a proof.)

Question 22

Is QS strongly semantically complete?

Answer 22

Yes.

Question 23

What are the proper axioms for a first order theory with identity?

Answer 23

1. QS= 1 Λx′F**′x′x′
2. QS= 2 Every universal closure of (F**′x′x″ ⊃ (A⊃ A′)), where A and A′ are formulas of Q, and they are alike except that, in A′, x″ may replace all, or some (or none) of the free occurrences of x′ in A, provided that x″ is free for x′ in A
3. QS= 1 is the reflexivity of identity; QS= 2 is Leibniz’s law (principle of the indistinguishability of identicals)

Question 24

What is a normal interpretation?

Answer 24

I is a normal interpretation of Q iff I is an interpretation of Q that assigns to the predicate symbol F**′ the identity relation, defined on the domain of I.

Question 25

What is a normal model of a first order theory?

Answer 25

I is a normal model of a first order theory K iff I is a normal interpretation of the language of K, and I is a model of K.

Question 26

What does it mean for K to be a first order theory with identity?

Answer 26

K is a first order theory with identity iff K is a first order theory whose proper axioms include the proper axioms of QS=.

Question 27

Is QS= consistent? (Metatheorem 47.1)

Answer 27

Yes. There is no formula of Q such that both it and its negation are theorems of QS=.

Question 28

Is QS= semantically complete? (Metatheorem 47.3)

Answer 28

Yes. Any formula of Q that is true under all normal interpretations is a theorem of QS=.

Question 29

Is QS= sound with respect to normal interpretations?

Answer 29

Yes. Every theorem of QS= is true under all normal interpretations of Q.

Question 30

Does K have a countable normal model? (The Key Theorem for first order theories with identity)

Answer 30

If K is a consistent first order theory with identity, then K has a countable normal model.

Question 31

What is the Lowenheim-Skolem Theorem for first order theories with identity?

Answer 31

If K is a first order theory with identity that has a normal model, it has a countable normal model.

Question 32

If a first order theory with identity has a normal model, does it have a denumerable normal model?

Answer 32

No, but we can say that any first order theory with identity that has a normal model has a countable normal model.

Question 33

What is an isomorphic model of a first order theory K?

Answer 33

1. M and M′ are models of K.
2. There is a 1-1 correspondence between D (the domain of M) and D′ (the domain of M′), pairing each member d of D with a member d′ of D′.
3. M assigns d to a constant c iff M′ assigns d′ to c
4. f(d1, d2,…dn) = d in M iff f ′(d1′, d2′,…dn′) = d′ in M′.
5. < d1, d2,…dn> is in the extension assigned by M to F iff
   a. is in the extension assigned by M′ to F.

Question 34

Are isomorphic models distinguishable? (Metatheorem 48.2)

Answer 34

Yes. If M and M′ are isomorphic models of K, then a formula A of K is true for M iff it is true for M′.

Question 35

What does it mean for a first order theory with identity to be categorical?

Answer 35

A first order theory is categorical iff all its normal models are isomorphic.

Question 36

What is the Downward Lowenheim-Skolem Theorem? (Metatheorem 45.18)

Answer 36

If a first order theory has a model, it has a denumerable model.

Question 37

What is the Upward Lowenheim-Skolem Theorem?

Answer 37

If a first order theory has an infinite model, it has a model of any arbitrary (higher) infinite cardinality.

Question 38

If a first-order theory with identity is categorical is it negation-complete? (Metatheorem 48.3)

Answer 38

Yes.

Question 39

What is a non-standard model?

Answer 39

A model of a formal system is non-standard iff it is not isomorphic to the intended model.

Question 40

What’s an intended model?

Answer 40

It’s the intuitive interpretation of the language. It’s ‘intended’ in-so-far as it concerns our motivations to interpret the language in certain ways.

Question 41

What is the Skolem Paradox?

Answer 41

How could the formula that says that there are uncountably many sets be a theorem, and yet the theory admits of countable models? How could a formula that is provable in axiomatic set theory come out true in a countable (specifically, denumerable) model if that formula says there are an uncountable number of sets?

What is Hunter’s solution?

1. In part, his response is that it’s not quite right to say the formula that says that there are uncountably many sets is a theorem. It “says” this on the theory’s intended interpretation. The formula is a theorem, but what it means depends on the model under consideration.
2. In part, Hunter’s response is that what we’ve shown in proving the Löweheim-Skolem Theorem is that there’s a model in which the formulas of the first order theory are not about sets at all. And so in that model, it doesn’t say there are uncountably many sets. Rather (in that model) it says something true, but it’s about whatever the domain of that model is.

Question 42

What is the Henkin proof? (Metatheorem 32.13)

Answer 42

Proof: Let T be any p-consistent set of PS. By Lindenbaum’s Lemma there is some maximal p-consistent set, F , that has Γ as a subset. If F has a model then so does Γ, since every formula in Γ is also in F . We show that F has a model. Two stages: (1) We give an interpretation I for P. (2) We show that, for any arbitrary formula A, if A is in F then A is true for the interpretation I. In fact we prove something stronger: we prove that A is true for I iff A is in F . We prove this stronger proposition not just for the fun of it, but because we need an ‘iff’ in the induction hypothesis in the proof of the weaker one. We have to prove the strong proposition in order to get the weak one.