MTH 355
Homework 3
Assigned 29 Oct, due 10 Nov

    Translation from English

  1. For each of the following English sentences, define a language suitable for talking about the subject at hand (specifying the constant symbols, function symbols, and relation symbols), define the intended structure (specifying the universe and the interpretations of the constant symbols, function symbols, and relation symbols), and translate the sentence into the language. If the English sentence is ambiguous or hard to translate, explain the problem and why you think your translation is a good one.
    (Most of these problems are taken from Barwise & Etchemendy's textbook Language Proof and Logic.)

    I'll do the first one for you as an example.

    1. "AIDS is less contagious than influenza, but more deadly."

      Language: constant symbols a and i; two-place relational symbols LC(_,_) and LD(_,_); no function symbols.
      Intended structure: universe is the set of diseases. a stands for AIDS, i stands for influenza, LC(x,y) means x is less contagious than y, and LD(x,y) means x is less deadly than y.
      Translation of sentence: LC(a,i) ∧ LD(i,a)

    2. "Sean or Brad admires Meryl and Harrison."
    3. "Daisy is a jolly miller, and lives on the River Dee."
    4. "Polonius's eldest child was neither a borrower nor a lender."
    5. "If Abe can fool Stephen, he can fool Ulysses."
    6. "France will sign the treaty only if Germany does."
    7. "If Tweedledee gets a party, so will Tweedledum, and vice versa."
    8. "If John and Mary went to the concert together, they must like each other."
    9. "Only the brave know how to forgive."
    10. "Every nation has the government it deserves."
    11. "All that glitters is not gold."
    12. "All the students in the class live in the same ZIP code."
    13. "All the students in the class, except Anne and Bob, live in different ZIP codes." (same language and structure)
    14. "Everybody loves somebody."
    15. "Everybody loves Raymond." (same language and structure)
    16. "There is somebody whom everybody loves." (same language and structure)
    17. "Everybody loves a lover." (same language and structure)
    18. "Every farmer who owns a donkey beats it."
    19. "Only the King has nobody telling him what to do."
    20. "There's a sucker born every minute."
    21. "If you always do right, you will gratify some people and astonish the rest."
    22. "You can fool all of the people some of the time, and some of the people all of the time, but you can't fool all of the people all of the time."
    23. "If everyone comes to the party, I'll have to buy more food."
    24. "There is a person who, if (s)he comes to the party, will make it necessary for me to buy more food." (same language, same structure). What is the logical difference between these two statements?

    2. Translation from mathematical English

  2. As above, except that these problems should all use the same language and structure, so you only need to define them once. Read all the statements before defining the language and structure; then translate each statement into that language. Note: I'm not asking wheteher the statements are true, only to translate them into first-order logical language. Feel free to put "even" and "prime" in your language, although technically they can both be defined from simpler things.

    1. "2 is prime."
    2. "Every even number is prime."
    3. "No even number is prime."
    4. "Some prime is even."
    5. "Some prime is not even."
    6. "2 is the only even prime."
    7. "If something is prime, then it's either 2 or not even."
    8. "No square is prime."
    9. "Some square is odd."
    10. "The square of any prime is prime."
    11. "The square of any prime other than 2 is odd."
    12. "The square of any number greater than 1 is greater than the number itself."
    13. "There is no largest prime."
    14. "There is no largest pair of twin primes (i.e. two primes whose difference is 2)."
    15. "The sum of any two numbers greater than 1 is smaller than their product."
    16. "If x2 = 1 then x = 1." (Hint: in mathematical English, this is a sentence, so x should not be translated as a free variable.)
    17. "For all ε > 0, there is a δ > 0 such that for all x within δ of x0, f(x) is within ε of f(x0)."
    18. "If 0 has property P, and whenever a number has property P, its successor also has property P, then all numbers have property P."
    19. "Suppose that for all numbers x, if all numbers less than x have property P, then x has property P. Then all numbers have property P."
    20. "There is a c such that for all sufficiently large x, f(x) < c * g(x)." (Hint: "Sufficiently large" is tricky.)

    3. Truth, models, and logical implication

  3. Problem 2.2.1: connections between logical implication and validity of conditional statements
  4. Problem 2.2.2: find structures satisfying various combinations of sentences
  5. Problem 2.2.9: find sentences defining various properties of a structure
  6. Problem 2.2.11: find formulæ defining various relations on the natural whole numbers.
  7. Problem 2.4.4: write an explicit formal proof of ∀ x φ → ∃ x φ.
  8. Problem 2.4.6: interaction between conditionals and quantifiers in formal proofs
  9. Problem 2.4.11: formal proof of the transitivity of equality
  10. Problem 2.4.15: interaction between ∨ and quantifiers in formal proofs
  11. Problem 2.4.16: interaction between ∧ and quantifiers in formal proofs
  12. Problem 2.4.17: interaction among ∨, ∧, →, and quantifiers in formal proofs
Last modified: 
Stephen Bloch / bloch@adelphi.edu