Exercises
Peter Suber, Philosophy Department, Earlham College
This is an abridged version of Suber's exercise file (tailored for use in this course).
It was created and posted here by Branden Fitelson with Peter Suber's permission.
This page is best viewed with a unicode compatible browser.
I recommend Firefox, which has been tested on these pages.
Selected exercises are answered in a separate handout.
Page and theorem numbers refer to Geoffrey Hunter, Metalogic, University of California Press, 1971.
See our schedule for guidance on when to do these exercise sets.
Set 1

If we specify a formal system by giving only its language, axioms, and rules, then we are omitting its theorems. Why isn't this inadequate?
[Answer]

Explain why two formal systems with the same set of theorems might not be identical.
[Answer]
Set 2

Which of these statements is true?

"If a method is programmable (written in a programming language and executable
on a machine), then it is effective."

"If a method is effective, then it is programmable."
[Answer]

What's wrong with this statement: "Onetoone correspondence makes no sense applied to infinite sets, for the method of pairingoff can only be effective for a finite number of steps"?

Explain how it is that an infinite set can be put into 11 correspondence with one of its own proper subsets. An example is not enough. Why is this kind of 11 correspondence not a contradiction?

Prove that a set is infinite iff it can be put into 11 correspondence with at least one of its proper subsets.
Set 3

In the proof of 11.2, could we "verticalize" rather than "diagonalize" on the yeses and noes, and get the same result?

Prove that all sequences contain countably many members.

What consequences would flow from the decision to permit infinitely long wffs?

Use the reasoning in the proof of metatheorem 14.1 to prove that only countably many things can be said, named, or described, whether in a formal language or in a natural language like English.

Why must enumerations of a set be countable?
 Even though Hunter says at the bottom of p. 25 that all sequences are countable by definition, don't answer this exercise by saying "by definition". What considerations would lead us to adopt such a definition?

Hunter leaves the proofs for 13.4 and 13.5 to the reader. Can you supply them?

Can there be an enumerable set that is not effectively enumerable?
 This is difficult from where we are now. We will prove an answer on Set 25
(metatheorem 51.9), so you have a while to think about it.

Can there be an effectively enumerable set that is not decidable?
 This is also difficult from where we are now. The answer is coming on Set 29 (metatheorem 57.4).
Set 4

Is either of the following statements true? If not, why? If one is true, which one and why?

Because ℵ_{1}
is defined as the first cardinal greater than
ℵ_{0}, to say that c =
ℵ_{1} assumes
the continuum hypothesis.
[Answer]

Because ℵ_{1}
is defined as 2 raised to the power of ℵ_{0}, to say that c =
ℵ_{1} assumes
the continuum hypothesis.
[Answer]

For a period in his career, Kurt Gödel believed that c = ℵ_{2}. Was this belief
compatible with the continuum hypothesis? With the generalized continuum
hypothesis?

Study the proof of the uncountability of the real numbers in Hunter's theorem A4. Why can't a similar proof be constructed for the rationals?
[Answer]

In the proof of theorem A4, why must we convert (for example), 0.5000... to 0.4999...?
[Answer]

In his proof of A7, Hunter leaves the proof of an important lemma to the reader, namely, that the set of all strings of 1's and 0's that consist of all 0's after a certain point are enumerable. Can you prove this?

A set of numbers is dense if (in their natural order) between any two such numbers, there is a third. The reals are dense because between any two reals numbers there is another real number. Note that if there is a third in this way, then there will also be infinitely many.

True or false: If a set of numbers is dense, then it is continuous.
[Answer]

True or false: If a set of numbers is dense and uncountable, then it is continuous.
[Answer]

Explain why transfinite cardinals do not comply with the ordinary rules of arithmetic. For example, ℵ_{0}
+ 1 = ℵ_{0}.
ℵ_{0} + ℵ_{0} = ℵ_{0}. c·c = c.

NonCantorian set theory is set theory in which Cantor's Continuum Hypothesis
(CH) is replaced by its negation. (It might have ~GCH instead of ~CH as an
axiom.) Try to imagine life without CH or with ~CH. What sets could be larger
than the rationals and smaller than c? What could fall between density and
continuity?

Review. Which of the following theorems do we know by the definition of the
symbols, and which do we know by proof?

N = ℵ_{0}
[Answer]

*N = c
[Answer]

*N = ℵ_{1}
[Answer]

*N = 2^{ℵ0}
[Answer]

c = ℵ_{1}
[Answer]

2^{ℵ0} =
ℵ_{1}
[Answer]

2^{ℵa} =
ℵ_{a+1}
[Answer]

c = 2^{ℵ0}
[Answer]

c > ℵ_{0}
[Answer]

If S = n, then *S = 2^{n} (where S is a set)
[Answer]

2^{n} > n, even if n is infinite
[Answer]

c = R (where R is the set of real numbers)
[Answer]
Set 5

Why are computable functions limited to total functions?

Prove that all total functions with a finite domain are computable.

No monadic connective (operator) can express all truthfunctions. Many triadic connectives can, but all of them are reducible to dyadic connectives. Dyadic connectives can express all truthfunctions and cannot be further reduced. Why this privilege or special status for twoness?
[Answer]

Invent a triadic connective that can express all truthfunctions and prove that it can. Then show how it can be reduced to (replaced by) some set of dyadic connectives.

Explain how a finite set of connectives can express an infinite number of truth functions.

If the truth function symbolized by "" were triggered by a
button on a calculator, then its "inputs" and "output" would be (respectively):

propositions, propositions

propositions, truthvalues

truthvalues, propositions

truthvalues, truthvalues
[Answer]
Set 6

Prove that if "~A" is a wff of P, then "A" is a wff of P.

Prove that if "(A B)" is a wff of P, then
both "A" and "B" are wffs of P.

Prove that there is an effective method for testing formulas of language P for wffhood.

The grammar of language P has four rules. The fourth is "Nothing else is a wff." What is the significance of this rule?
[Answer]

Must we use a metalanguage to state the alphabet and grammar of a formal language?

Restate the grammatical rules of P as functions.

Why must we define "truth for an interpretation" separately for each connective in the language?

Why introduce "" when we already have ""?

Why should we adopt the convention that the null set of wffs is logically valid, rather than the opposite convention?

Prove that there is an effective method for testing any wff of P for logical validity.
[Answer]

Why is mconsistency a kind of consistency? If a set of wffs has a model, how do we know that the set contains no contradictions?

Why does the logical validity of wffs belong to the formal language, as opposed to the deductive apparatus, of a formal system? Why is it semantic rather than syntactic?
Set 7

In proving that any wff of language P (in fact, any truthfunction) can be expressed in disjunctive normal form, we implicitly appeal to the premise that distinct truth table columns correspond to distinct truthfunctions. (Hence any set of connectives that can determine all truthtable columns can express all truthfunctions.) How can we justify this premise?

Hunter gives an effective method for translating any wff of P into DNF. Can you describe an effective method for doing the same with CNF (conjunctive normal form)? (Where DNF is a disjunction of conjunctions of atoms and negated atoms, CNF is a conjunction of disjunctions of atoms and negated atoms.)

Explain in informal English how it is possible that a finite set of connectives can express all truthfunctions, given that the set of truthfunctions is infinite.

Write p, ~p, pq, p · q,
pq, and
pq, using
only the connective "". Then do the same using only "[dagger]".

The great length and complexity of wffs written only with "" or "[dagger]" are motives to use more than one connective, i.e. to tolerate some redundancy or inelegance. Did anything in recent reading suggest a motive for using fewer rather than more connectives, apart from elegance?
[Answer]

Hunter proved in metatheorem 21.1 that the set of truthfunctions {~, } is adequate to
express all truthfunctions. This set is of special interest because it is the set of truthfunctions used by his language P. Using only these truthfunctions, express each of the following:

p · q
[Answer]

p q
[Answer]

p q
[Answer]

p q
[Answer]

p  q
[Answer]

p † q
[Answer]

~ (p · q)

~ (pq)

A triadic connective takes three arguments. For example, "*" in *(A,B,C) may express (AB)~C. (See Hunter's exercise 1 at p. 51.) Define two triadic connectives which, like the dyadic stroke and dagger functions, are adequate by themselves to express all truthfunctions, and prove their adequacy.
[Answer]
Set 8

Prove that there is an effective method for testing whether an arbitrary wff of P is an axiom of PS (instantiates one of the axiom schemata). In general, prove that there is an effective test of axiomhood for PS (that the axioms of PS form a decidable set).

Prove that PS has at least ℵ_{0} axioms, hence at least ℵ_{0} theorems.

Prove that PS has at most ℵ_{0} axioms and theorems.
[Answer]

Hunter's system PS has only one rule of inference, modus ponens. But modus ponens has the peculiarity that it always shortens wffs (considered as strings of symbols) and never lengthens them. Yet it is possible in PS for theorem n+1 to be longer than theorem n. How can this be?
[Answer]

Prove that wffhood is closed under modus ponens, that is, that given wffs as input (premises), MP will produce only wffs as output (conclusions).
[Answer]

Would it be interesting to create a nonstandard logic in which wffhood was not closed under the rules of inference? Invent some rules of grammar and inference that would be nonstandard in this way.

Must we use a metalanguage to state the axioms and rules of inference of a formal system?
[Answer]

Restate modus ponens as a function.
[Answer]

Can you generalize your answer and describe an effective method for restating any rule of inference as a function?

Why is it desirable to make proofs finite by definition?
[Answer]

Why define proofs to be nonempty sequences of wffs that meet certain conditions?

Why do we insist on nonemptiness?

Why do we require a sequence rather than a set?

Why do we not refer to 'truth' in our definition of 'proof'?

Given Hunter's metatheorem 23.4, Γ A, Γ AB, Γ B), and its immediate
predecessors, which of the following are also metatheorems? Can you prove that any
are, or that any are not?

A, AB,
B

AB,
AB

A,
(AB), B

A,
AB,
B

A,
AB,
B

A,
(AB), B

AB, AB

AB, (AB)

A, (AB), B

A, (AB), B

(AB) A B

ΓA, AB Γ B

How can a set Γ of wffs be pcon for some system S and pincon for S', when S and S' differ only in their deductive apparatus?
 Why can no set Γ be mcon and mincon in the same circumstances?

Explain why we should generally approve inferences of the type, A A, and disapprove
inferences of the type, A A.
 Under what circumstances should we start to distrust inferences like A A ?

How does PS avoid the infinite regress in the use of modus ponens presented in Lewis Carroll's paradox (in Gödel, Escher, Bach, pp. 4345)?

Before we go further in the book, pause and be creative. How would you even start to prove consistency? completeness? decidability (that there is an effective test of theoremhood)?
 These are all coming up soon. The methods of proof are as interesting and
important as their conclusions.
Set 9

Why is absolute consistency a concept of consistency at all? Why would its presence even come close to satisfying our desire to find consistency?

Is it possible to have simple consistency without absolute consistency or vice versa? If not, prove it. If yes, under what conditions?

Simple consistency is a fact about what is not provable in a system (namely, there is no wff A such that both A and ~A are provable). From the handout on the isomorphism between formal systems and machines we know that theorems about what is not provable can be translated into theorems about what is not computable. What is the "machine equivalent" of simple consistency?

Prove that in PS a contradiction implies everything. Or more precisely, prove that if PS contains a wff A such that both A and ~A are theorems (i.e. if the system is simply inconsistent), then every wff of P is a theorem.
 Remember that the only truthfunctions in PS are ~ and . Hence we cannot directly say (A · ~A) B.

What's wrong with this statement: "We cannot prove that an axiom schema for PS is true for some I, because it would take infinitely many tests (e.g. truth table tests), one for each possible instantiation of the schema"?

In Post's modeltheoretic proof of the consistency of PS, we looked for and found a single interpretation of P that was also a model. Why does just one such interpretation suffice to prove consistency? Couldn't other interpretations show up an inconsistency, in principle?
[Answer]

In our search for the kind of interpretation described in the last exercise, why was it important to limit our search to interpretations in which the connectives bear their "usual meanings"?
[Answer]

Let us say that a set of wffs is "basically consistent" iff the conjunction of its members is not a contradiction. Prove that PS is absolutely consistent iff the set of its theorems is basically consistent.

True or false: A system is simply consistent iff the set of its theorems is a pconsistent set.

Explain why every semantic tautology is a syntactic tautology and vice versa.

Describe in your own words the problem of circularity in consistency proofs. (Hofstadter talks about this more than Hunter; see GEB at pp. 24, 19192, 22930.)

How well or badly do our two proofs of the consistency of PS fare in light of the potential circularity of consistency proofs? Do they use any reasoning validated by TFPL?

The last two questions point to a general distinction of great importance. Try to be specific in describing (1) the reasoning validated by TFPL, or exemplified by proofs of theorems inside PS, and (2) the reasoning in the metatheory of TFPL, or exemplified in our proofs of metatheorems about TFPL.

Explain why "A A" can denote the
consistency of a system, that is, why it implies the simple and absolute consistency of
the system.

Describe in your own words the semantic motivation of the concept of consistency.
[Answer]

In what sense does consistency depend on interpretation and in what sense not?
Set 10

(A review question to help you with mathematical induction.) In many of our proofs we prove pq by assuming p and deriving q. Why is this valid?
[Answer]

Prove that if system PS has a model, then it is simply consistent.

What features of PS are used to prove that the deduction theorem holds in it?
[Answer]
 Every time a metatheorem is proved for some system, it is proved for all systems
that are relevantly similar. Try to be as specific as you can in describing that
class of systems for the deduction theorem and for other important metatheorems
to come.

Hunter's proof of the deduction theorem uses the method of "conditional proof" (or what Hofstadter called the "fantasy rule"). That is, to prove a proposition of the form, "AB" (namely, the induction step), we assumed A and derived B, and as a result of that derivation were justified in asserting "AB". But this is to assume that it is valid reasoning to move from AB (assume A, derive
B) to (AB). But this is the
deduction theorem. Did Hunter use the deduction theorem to prove the deduction
theorem? Is his proof valid?

Hunter proves the deduction theorem as a metatheorem (26.1). Hofstadter calls it the "fantasy rule" and gets it into his system of TFPL by making it a rule of inference rather than a metatheorem (see GEB at pp. 18384). What considerations might lead one to get the deduction theorem in the one way or in the other?

What does this show about the interchangeability of metatheorems and rules of inference in general? (See GEB at pp. 19394.)

Can you prove the converse of the deduction theorem, i.e. if Γ (AB), then Γ, AB? We will see a proof
in metatheorem 43.2 (Set 19), but it uses only basic TFPL concepts, and does not
require mathematical induction. You are in a position to prove it now, if you can just
see how.
Set 11

Which of the following are true?

Every model of AB is a model of
A.
[Answer]

Every model of AB is a model of
B.
[Answer]

Every model of A is a model of AB.
[Answer]

Every model of B is a model of AB.
[Answer]

Every model of ~A is a model of AB.
[Answer]

Every model of ~B is a model of AB.
[Answer]

Every model of {A, AB} is a model of
B.
[Answer]

Every model of {B, AB} is a model of
A.
[Answer]

Every model of {A,B} is a model of AB.
[Answer]

Every model of {~A,~B} is a model of AB.
[Answer]

Prove that, given AB, every model of A
is a model of B. (This is used in the proof of metatheorem 28.4.)

Given ~AB, can you prove that
for every I in which A is true for I, B is also true for I?

We know that all tautologies are logically equivalent in TFPL. That is, if A and B are arbitrary tautologies, then AB. In light of this
fact:

Why do we demand that a semantically complete system show that all tautologies expressible in P are theorems of the system? Don't we get them all if we get one? Why isn't one enough?
[Answer]

Why do we demand that language P, which lacks conjunction, contain "the equivalent" of the tautology, ~(p · ~p) ?

Describe in your own words the semantic motivation of the concept of completeness.

A formal system is decidable iff there is an effective method for determining whether any given wff is a theorem. Can you prove that PS is decidable?
 You have all the tools and information you need as of today. We'll see a proof
on Set 14, so you have a few days to think and play.
Set 12

Metatheorem 31.14 applies to all compound propositions. In metatheorem 31.15, Hunter applies it to all tautologies. Can you prove that all tautologies are compound?
 (This is not especially hard. But the result is basic to the idea of logical truth and is rarely given an explicit proof.)

Questions about the proof of metatheorem 31.15.

What if k = ℵ_{0}?
[Answer]

Luckily k cannot equal ℵ_{0}. Why not?
[Answer]
Set 13

Hunter does not prove metatheorem 32.1. Can you?

In light of metatheorem 32.9, will the maximal pconsistent set of theorems of some consistent system always contain all the theorems of that system? Why or why not?

Is the converse of metatheorem 32.10 true or false? Can you prove your answer? (The converse would assert that, for any wff A, and maximal pconsistent set Γ, if A Γ, then Γ A.)

Let Γ be a
maximal pcon set of wffs of PS.

True or false: Γ could contain
all and only the theorems of S.
[Answer]

True or false: Γ could contain
all and only the nontheorems of S.
[Answer]

Will all the maximal pconsistent sets of wffs from the same system have the same cardinality? Can you prove your answer?

Let us say that a "string" of symbols is any sequence of symbols, regardless of length or wffhood. Prove that the enumeration theorem is true for finite strings and false for denumerable strings.

If the enumeration theorem is modified to refer to enumerability, rather than effective enumerability, then prove that it holds for strings in general, not just for wffs.

In the proof of Lindenbaum's lemma, we are told to add the nth wff of our enumeration of wffs to set Γ_{n1}, creating set
Γ_{n}, iff this
addition would not trigger pinconsistency. But how can we tell whether the nth wff
can be added to Γ_{n1}? Is there an
effective method to help us determine whether an addition will trigger pinconsistency?
[Answer]

Henkin's completeness proof actually concludes that every pconsistent set of PS has a model (metatheorem 31.13). Explain why this is equivalent to proving semantic completeness.

Hunter's metatheorem 32.14 is called the "Strong" completeness theorem of PS: if ΓA, then Γ A. Why is it "stronger" than other completeness theorems?

In the finiteness theorem for language P (metatheorem 32.18) we proved that "" possesses a certain
property. We proved that "" possessed the same
property in metatheorem 23.7 (Set 8). Why is the finiteness theorem much more
interesting and hard to prove for "" than for ""?
[Answer]
Set 14

A system has a kind of syntactic completeness iff for each wff A, either A or ~A is a theorem. PS does not possess this kind of completeness, and it would not be desirable for PS to do so.

Why is it undesirable for PS to possess this kind of completeness?

If a system of TFPL did have this kind of completeness, could it be consistent?

For what kinds of systems would it be desirable to possess this kind of completeness? (This is difficult from where we are now.)

A system has another kind of syntactic completeness iff no unprovable schema can be
added as an axiom schema without creating inconsistency.

Why is this kind of completeness syntactic?

Why does this kind of completeness refer only to added unprovables?

Why does this kind of completeness refer only to added schemata?

There are two kinds of unprovable schemata that might be added as axiom schemata, one of which creates inconsistency when added and one of which does
not. Can you think of them?

We give up syntactic completeness, but not semantic completeness, when moving from TFPL to monadic predicate logic (PL). Can you (now) imagine why? When you examine the proof for the syntactic completeness of PS (in 33.1), what in the proof is essentially tied to TFPL or could not be done in monadic PL? If semantic and syntactic completeness are separable for monadic PL, but inseparable for TFPL, then what property of monadic
PL can explain this difference from TFPL?
 Even if you cannot answer these questions now, think about them as we make
the transition to PL on Set 16 and following.

Where in the proof for the syntactic completeness of PS (metatheorem 33.1) are we assured that PS is "full"? Won't adding U to an incomplete system still create inconsistency?

To what extent is syntactic completeness equivalent to maximal pconsistency; or to what extent is the assertion of PS's syntactic completeness equivalent to saying that the set of theorems of PS is a maximal pconsistent set? If they are equivalent, then prove that PS is syntactically complete by proving that its theorems form a maximally pconsistent set, hence without presupposing semantic completeness or consistency.
 In deciding whether this is possible, ponder Hunter at p. 119 on how a decidable
system like PS may have undecidable wffs.

Metatheorem 33.2 shows that we can add the negation of an unprovable wff to a consistent system as an axiom without creating inconsistency. If 33.2 applied only to syntactically incomplete systems, then it would contradict the proof of the syntactic completeness of PS in metatheorem 33.1. Why doesn't this contradiction arise?
[Answer]

If we generalize Hunter's metatheorem 33.2, we might get something like this: Any undecidable wff can be added as an axiom to a consistent system, and the result will be a consistent system. Is this proposition true in general? Is it true for PS? Can you prove it true or false for PS or more generally?

Variation: Any undecidable wff can be added as an axiom schema to a consistent system, and the result will be a consistent system. Can you prove or disprove this? (This is more difficult.)

Prove that for some consistent system S, there is no wff A such that both S + A and S + ~A are inconsistent. Or: for every consistent system S, and arbitrary wff A, either A or ~A can consistently be added to the axiom set of S.
[Answer]

Do you think PS has an effective proof procedure? Can you prove your answer? If your answer is yes, can you sketch the method you have in mind?
[Answer]

Can you put your finger on the feature of Hiz's system that allows it to be simply inconsistent and absolutely consistent at the same time?

To prove that PS is decidable, would it suffice to have A A? Do we also
need A
A?

Explain why a decidable system need not have an effective proof procedure.

We give up decidability when we move from TFPL and monadic PL to polyadic PL. Why? What in the proof of the decidability of PS (34.1) is essentially tied to TFPL or monadic PL, and cannot be done in polyadic PL?
 Even if you can't answer this question now, think about it as we encounter
monadic and then polyadic PL.

If a formal system is undecidable, then what can we say about the computer program isomorphic with it?

How does this differ from a formal system with undecidable wffs? What can we say about its isomorphic program?

Explain how a decidable system can have undecidable wffs.

Explain how every wff in an undecidable system can be decidable.
Set 15

Let A be an axiom of S and a theorem of SA. (SA denotes system S minus axiom A.) Let both S and SA be consistent.

Is ~A independent of S?

Is ~A undecidable in S?

(Easy question for review.) If we know that A is not a theorem of S, then how do we know that A is not a theorem of SA?

(Easy question for review.) If S is consistent, then how we know that SA is consistent, regardless of A?

What is the relationship between the independence ("I") and undecidability ("U") of a wff?

I U
?

U I
?

I
U ?

None of the above?

In metatheorem 28.5 (Set 11), Hunter proved that modus ponens preserved truth for I, for standard sorts of I. Why does that suffice to show that modus ponens preserves truth for I for the nonstandard sorts of I (and nonstandard sorts of "truth") in today's independence proofs?

In metatheorem 36.3, Hunter assumes without proof that (A B)* (A* B*), where A* is identical to A but for the removal of all negation signs. Can you prove this?

Prove that metatheorem 33.2 (the "nonstandardness theorem") holds for independent wffs, not just for undecidable wffs and the negations of theorems.

In proving the independence of an axiom (say, Axiom 1 in metatheorem 36.1) how would one decide on the exotic 3value definitions of "~" and "" that allow us to
discriminate between Axiom 1 and the other axioms?

The strange 'truth table' constructed in the proof of metatheorem 36.1 helps us contrive a strange interpretation I such that axiomschema #1 is false for I while the other two axiomschemata of PS are true for I. But this I is so strange that, e.g. the connectives no longer take their standard meanings. How can we be sure, then, that axiomschema #1 doesn't follow from the other two axiomschemata in an ordinary or standard interpretation?

Is AB a system in which not everything follows from a contradiction? Can you prove that AB is or is not such a system?
Set 16

How is a predicate like and unlike a function?

How is a predicate like and unlike a set?

Why is predicate logic in general not truthfunctional?

Can you describe a subset of predicate logic that would be truthfunctional?

In a consistent system of predicate logic, can there be any theorems that are open wffs (other than instances of tautological schemata)?

In a consistent system of predicate logic, can there be any theorems that are atomic wffs?
[Answer]

Explain why the members of a set Γ of PL wffs may be
simultaneously satisfiable while Γ has no model.
[Answer]

How can we use the universal quantifier, negation, and the concept of identity (carried by the traditional symbol "=") to express all the quantities expressed by the natural numbers?
[Answer]
Set 17

To interpret Q, we assign truthvalues to p', p'', ... , but not to wffs whose internal structure is visible, e.g. Fx, Fs, Ffcc... For these, we assign a meaning to the predicate, and an object to the term, and then appeal to an extralogical procedure to determine its truth value (e.g. we hire a private detective). Hence, a structured proposition is not necessarily T or F just from the assignments that interpret the language. Why not just assign truthvalues to such propositions?

Why does the concept of satisfaction refer to sequences of members of the domain, and not simply to members or to sets of members of the domain?

Why must we define satisfaction separately for each connective, quantifier, and type of
term?

If a set of wffs is simultaneously satisfiable, does it follow that it has a model?

If a wff is not satisfiable, is its negation logically valid? Can you prove that it is or that it is not?

If a wff is logically valid, then is its negation unsatisfiable? Can you prove that it is or that it is not?

The consistency of an arbitrary finite set of PL wffs is an "NPcomplete" problem. This means roughly: while there is an effective method to solve the problem, there is no tractable method or method which will solve it in useful time. This is a very important result for the theory of computation. Yet we have methods that are both effective and tractable to prove the simple and absolute consistency of systems with ℵ_{0} theorems. Can you explain this disparity?

How does the problem of the consistency of an arbitrary set of wffs differ from TFPL (TFPL wffs) to PL (PL wffs)?

How does semantic consequence for language P differ from semantic consequence for language Q? Why?

Why does the definition of semantic consequence, but not syntactic consequence, change from TFPL to PL?

Describe the "border" between TFPL and (monadic) PL. What changes when we cross the border that might explain the metatheoretic results of crossing it?
Set 18

Hunter does not provide proofs for any of the metatheorems 40.1 through 40.8. Can you prove any of them?

Questions about the proof of Hunter's metatheorem 40.13:

Why is it important that v_{k} not be free in A?

What if A is unsatisfiable?

Is the quantifier superfluous?

In 40.21, why generalize only from wffs with exactly one free variable? Why use only open wffs, and why use open wffs with exactly one free variable?

Explain how some wffs of PL can be kvalid for every positive integer k and yet not be logically valid.

Which metatheorems in today's reading show that QS has the features we knew from elementary logic as "universal generalization" and "universal instantiation"?
Set 19

In proving the consistency of QS (in 42.1), why is the "reduction" of PL to TFPL legitimate? Why does this create no important distortions?

Does the consistency proof for QS (in 42.1) suffer from the circularity problems that beset many consistency proofs?
Set 20

At p. 178 Hunter says that adding new constants adds new logical axioms but not new proper axioms. Why is this the case?

Why add new proper axioms instead of proper axiom schemata?

How true is "1 + 2 = 3"? Is it:

satisfiable

true for I, or

logically valid?

Go back to metatheorem 26.1 and explain why the deduction theorem applies to AFOTs.

In Hunter's metatheorem 45.5, we are told to use K4 (in the form vA A) on A^{c} as often as
necessary until we get A.

Spell out "as often as necessary". Do we stop when we have removed all quantifiers from A, leaving A an open wff? If not, when do we stop?

What would be strange about continuing until A became an open wff?

Questions about Hunter's metatheorem 45.6.

Why limit 45.6 to closed wffs?

Does 45.6 presuppose that K is consistent? Have we been given that?

Extend Hunter's metatheorem 45.6 (c and b) by proving that any undecidable closed wff can be added to a consistent FOT without creating inconsistency.

Which kinds of predicate logic will find negation completeness desirable? Which kinds will find it undesirable?

How does the restriction to closed wffs in the definition of negation completeness bear on its desirability?

Why is negation completeness undesirable to all kinds of TFPL?

Why is it desirable to some FOTs but not to QS?

Consider these propositions:
A.
S is negationincomplete.
B.
S is absolutely consistent.
C.
S has some undecidable wffs.

Is it true that AB ?
[Answer]

Is it true that AC ?
[Answer]

Is it true that BC ?
[Answer]

Compare Lindenbaum's lemma for TFPL (Hunter at p. 110) with Lindenbaum's lemma for a FOT (Hunter at p. 177). What similarities justify us giving them the same name?
Set 21

What's wrong with this proof?
 Let S be a firstorder theory.
 If S has a model, then S is consistent. (45.8)
 Some consistent sets of wffs of firstorder theories have no models. (Hunter at
p. 186.)
 Therefore, consistency doesn't imply modelhood.
 Therefore, consistency modelhood. (The implication works right to left but not left to right.)
 But the negation of material equivalence is another way to express exclusive
disjunction. (Hunter at p. 69.)
 Therefore, if S is consistent, then it must not have a model, and if it has a model then it is inconsistent.

Why is it legitimate to infer from the closure of a system that its domain is countable?

Prove that a system of arithmetic with an intended uncountable model (hence, with a nonstandard countable model as well, under the LöwenheimSkolem theorem) is not closed.

In Hunter's metatheorem 45.13, is there a limiting case at which K' = K?

Why is metatheorem 45.16 limited to closed wffs?

In light of the LöwenheimSkolem theorem, in what sense (if any) must we qualify our assertion that the cardinality of the reals is greater than the cardinality of the naturals?

Explain how a consistent set of wffs of an AFOT can fail to have a model.

Explain why a consistent set of closed wffs of an AFOT must have a model and why a consistent set of open wffs need not.

Explain why a consistent set of open wffs of an AFOT might lack a model but must be simultaneously satisfiable in a denumerable domain.

Explain why modelhood and consistency are biconditional in TFPL but not in PL. What was added in PL that created this disparity with TFPL?

The LöwenheimSkolem theorem doesn't rule out the possibility that a consistent FOT can have an uncountable model. It merely says that a consistent FOT will also have a countable model. Prove that a consistent FOT with an uncountable model will not be closed.
Set 22

How can QS be semantically but not syntactically complete? That is, how can QS have all logically valid wffs as theorems and yet not be "full"? (The word "ullage" means the empty space in a bottle above the liquid it contains. What is the ullage of QS?)

How can QS be semantically complete but not negation complete?

Why can't we "reduce" PL to TFPL to prove syntactic completeness as we did to prove consistency?

Why is it undesirable for QS to be syntactically complete? Compare this undesirability with the undesirability of negation completeness for QS.

Why is Axiom 9 of QS^{=} limited to closures of [(x=y)(AA')]?

How does Axiom 9 of QS^{=} make Axiom 8 useful?

In TFPL and with earlier FOT's we proved systems consistent if for an arbitrary wff A, A A, that is, if all their
theorems were logically valid. But QS^{=} has proper axioms; hence not all its theorems
are logically valid. Yet in 47.1 we proved that it was consistent. Do we need A A to prove
consistency or not?

Which of the following systems are extensions of which?

QS of PS?

QS^{=} of PS?

QS^{=} of QS?

QS^{=} of FOT=?

FOT= of QS^{=}?

Why do we need "normal interpretations" in order to add identity to QS?

Why do we need the new notion of "adequacy" to evaluate systems with identity like QS^{=}?

Why does PL with identity have wffs as theorems that are not logically valid for PL without identity? Why is this desirable?

Describe the "border" between PL with identity and PL without identity. What changes when we cross the border that might explain the metatheoretic results of crossing it?
Set 23

What is the motivation for redefining FOTs here (dropping propositional symbols)?

Or, why not leave propositional symbols in the system and not use them?

To determine isomorphism, why don't we pairup variables? Is the reason related to the
reason why variables get no assignment in interpreting language Q?

Hunter omits the proof of metatheorem 48.2. Can you provide one?

Would metatheorem 48.3 be true of FOTs without identity (changing "normal models" to "models")? Why or why not?

We can answer this question, but why is it "merely academic"?

Give an example of an English sentence using a numeral as an adjective, and an
example of a sentence using a numeral as a noun.

Why is language Q adequate to express numeral adjectives but not numeral nouns?

How can a FOT with identity have models of infinite cardinality and normal models all of whose cardinalities are finite?

Why is the socalled Skolem paradox not really paradoxical?
This file is an electronic handout for the course, Logical Systems.
Some of the logic symbols in this file are GIFs; see my Notes on Logic Notation on the Web. Some are HTML characters using the Symbol Font; see Alan Wood's guide to its symbols.
Peter Suber, Department of Philosophy, Earlham College, Richmond, Indiana, 47374, U.S.A.
peters@earlham.edu. Copyright © 19992002, Peter Suber.