Metatheorems

Question 1

40.1

Answer 1

If A is logically valid, then ~A is not satisfiable.

Question 2

40.2

Answer 2

If a sequence s satisfies A and also A ⊃ B, then it also satisfies B.

Question 3

40.3

Answer 3

If A and A ⊃ B are both true for an interpretation I, then B is also true for I.

Question 4

40.4

Answer 4

If A and A ⊃ B are both logically valid, then so is B.

Question 5

40.5

Answer 5

A is false for a given interpretation iff ~A is true; and A is true for I iff ~A is false for I.

Question 6

40.6

Answer 6

A is true for I iff ∧vA is true for I for any arbitrary variable v.

Question 7

40.7

Answer 7

A is true for I iff any arbitrary closure of A is true for I.

Question 8

40.8

Answer 8

A is logically valid iff Ac is.

Question 9

40.9

Answer 9

∨vA is satisfiable for an interpretation iff A is satisfiable for the same interpretation.

Question 10

40.13

Answer 10

If vk does not occur free in A, then A ⊃ ∧vkA is logically valid.

Question 11

40.14

Answer 11

Let t and u be terms. Let t′ be the result of replacing each occurrence of vk in t by u. Let s be a sequence, and let us = d. In other words, let the member of D assigned by I to u for the sequence s be d. Let s′ be the sequence that results from substituting d for the kth term of s. Then, t′s = t*s′. In other words, the member of D assigned by I to t′ is the same as the member of D assigned by I to t for sequence s′.

Question 12

40.15

Answer 12

Let A be a wff, vk a variable, t a term that is free for vk in A. Let s be a sequence, and let s′ be the sequence that results from replacing the kth term of s by t*s. Then, s satisfies At/vk iff s′ satisfies A.

Question 13

40.16

Answer 13

∧vkA ⊃ At/vk is logically valid if t is free for vk in A.

Question 14

40.17

Answer 14

If A is a closed wff, then exactly on of A and ~A is true, and exactly one false.

Question 15

43.5

Answer 15

Every theorem of QS is logically valid.

Question 16

43.7

Answer 16

If A is a syntactic consequence of Γ in QS, then A is a semantic consequence of Γ in Q.

Question 17

45.4

Answer 17

If A is a theorem of K, then ∧vA is a theorem of K.

Question 18

45.5

Answer 18

A is a theorem of k iff Ac is a theorem of K.

Question 19

45.6

Answer 19

If A is a closed wff of K that is not a theorem of K, then K + {~A} is a consistent first order theory.

Question 20

45.8

Answer 20

If a first order theory has a model, then it is consistent.

Question 21

45.11

Answer 21

If K is a consistent first order theory, then the system that results from adding a denumerable set of new individual constants to K, with an effective enumeration of those
constants, is a consistent first order theory that is an extension of K.

Question 22

45.13

Answer 22

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

Question 23

45.14

Answer 23

Any consistent, closed, negation-complete first order theory has a denumerable model. (Alternative in 45.16): Any consistent set of closed wff of a first order theory has a denumerable model.

Question 24

45.16

Answer 24

Any consistent set of closed wff of a first order theory has a denumerable model.

Question 25

45.15 (The Key Theorem)

Answer 25

Any consistent first order theory has a denumerable model.

Question 26

45.17 (Godel’s Theorem)

Answer 26

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

Lemma 1: If Γ is a consistent set of a first order theory K, and K′ is a first order theory that results from merely adding denumerably many new individual constants to K, then Γ is a consistent set of K′.

Lemma 2: Let A be a wff in which some variable v has one or more free occurrences. Let c be a constant that does not occur in A or in any proper axiom of K. Then if Ac/v is a theorem of K, A is a theorem of K.

Question 27

45.18 (Lowenheim-Skolem Theorem)

Answer 27

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

Question 28

45.19

Answer 28

If there is an interpretation I for which every proper axiom of a first order theory K is true, then K has a model.

Question 29

45.20 (The compactness theorem for K)

Answer 29

If every finite subset of the set of proper axioms of a first order theory K has a model, then K has a model.

Question 30

45.21

Answer 30

If A is a syntactic consequence of Γ in K, and v does not occur free in Γ, then ∧vA is a syntactic consequence of Γ in K. (An extension of 45.4)

Question 31

45.22

Answer 31

If v has no free occurrence in B, then ∧v(A ⊃ B) ⊃ (∨vA ⊃ B) is a theorem of K.

Question 32

45.23

Answer 32

If a variable u does not occur in A, then ∨vA ⊃ ∨uAu/v.

Question 33

45.25

Answer 33

If t is a closed term of K, then At/v ⊃ ∨vA is a theorem of K.

Question 34

46.1 (The Semantic Completeness Theorem for QS)

Answer 34

Every logically valid formula of Q is a theorem of QS.

Question 35

46.2 (The Strong Completeness Theorem for QS)

Answer 35

If A is a semantic consequence of Γ in Q, then A is a syntactic consequence of Γ in QS.

Question 36

46.4

Answer 36

QS is negation-complete.

Question 37

47.1

Answer 37

QS= is consistent.

Question 38

47.2

Answer 38

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

Question 39

47.3

Answer 39

Any formula of Q that is true for every normal interpretation of Q is a theorem of QS=.

Question 40

48.2

Answer 40

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

Question 41

48.3

Answer 41

If all normal models of a first order theory with identity are isomorphic, then the theory is negation complete. In other words, if a first order theory with identity is 2-categorical (All its normal models are isomorphic, then it is negation-complete).