Philosophy 106B Problem Set 1
Due: Monday February 22 at 6pm
Please submit your solutions to the course Gradescope page (link on Latte),
and remember the course collaboration policy :)
1. Devise formation rules for a language whose alphabet consists of the three
letters ‘a’, ‘b’, and ‘c’ and whose formulas are palindromes (that is, the
strings that read the same forward and backward).
Hint: Don’t forget that palindromes can be of odd and even length!
2. Rewrite the following assertion so that the formulas are mentioned in
pedantic style, without use-mention or shorthand conventions:
for every formula F of L=, the formula ∼ (F. ∼ F ) is derivable in Σ=.
3. Prove the assertion of the previous problem by showing how to obtain a
formal derivation using axioms (T1)–(T5) and modus ponens. (Here you
may avail yourself of the conventions, i.e. use abbreviations etc.)
4. Show using axioms (T1) and (T2) and modus ponens that for any formulas
F,G and H,
(a) if ` F ⊃ G and ` G ⊃ H then ` F ⊃ H
(b) if ` F ⊃ (G ⊃ H) then ` G ⊃ (F ⊃ H)
5. Using the result of problem (4a) and other axioms of (T1)–(T5), show
that for any formulas F and G, ` F ⊃ (∼ F ⊃∼ G).
6. Show that if Σ is a formal system that is truth-functionally complete and
contains modus ponens as a rule of inference, then Σ is consistent if and
only if it is consistent*.
7. Using the derivability of ∼ x = 0 ⊃ ∃z(x = Sz) but no further invocation
of the induction axiom, show that the following formulas are derivable in
PA:
(a) y + x = 0 ⊃ x = 0 . y = 0
(b) x ≤ 0 ⊃ x = 0
1
Extra Credit. Let F be a formula of LS containing no quantifiers and
only the one variable ‘x’. Show that F is true in the intended interpreta-
tion for either a finite number of values of ‘x’ or for all but a finite numbers
of values of ‘x’.
Hint: Do this first for atomic formulas, then show the property is pre-
served by negation and conditional.
2




































学霸联盟