The First Four Problems of the Last Problem Set
Logic and Infinity

Problem 1
A man was being prosecuted for participation in a robbery. The prosecutor and the defense attorney made the following statements:

Why was this the worst thing the defense attorney could have said?

Problem 2 (from "Godel Escher Bach", an excellent intro to logic)
Our system has three symbols: M, I, U. We are allowed to make any string of these three letters, for example:

You can probably think of others.

We have four rules for tinkering with these strings:

  1. If a string has I as its last letter, you can add a U on the end.
  2. If you have a string Mx, then you can add the string 'x' on the end, to create Mxx.
  3. If III occurs in a string, you can replace it with U.
  4. If UU occurs in a string, you can drop it from the string.
Examples for each of these rules:
  1. From the string 'IMUI', rule 1 lets me create 'IMUIU'.
  2. The string 'MUIUMI' is of the form Mx, with x = UIUMI. And so rule 2 lets me create the string Mxx = MUIUMIUIUMI.
  3. From the string 'UIIIUM', rule 3 lets me create the string 'UUM'.
  4. From the string 'UUMUI', rule 4 lets me create the string 'MUI'
The question: if you start with the string 'MI', can you create the string 'MU'? If it can be done, do so; if it can't be done, prove that it can't.

Problem 3 (from Steve Walk)
A system different from the system in Problem 2 has five symbols:

-- , P , N , ( , )

We have a machine that can print strings of these five symbols (not necessarily all strings though). And of course, there are rules:

  1. If X represents any string, then the norm of X is the string X(X).
As an example, the norm of the string P( is the string P((P() .

If a string has one of the following forms, then it is a sentence . These are the forms, and their interpretations; the symbol X represents any string at all.

  1. P(X) ; this means "the string X is printable by the machine".
  2. --P(X) ; this means "the string X is not printable by the machine".
  3. PN(X) ; this means "the norm of the string X is printable by the machine".
  4. --PN(X) ; this means "the norm of the string X is not printable by the machine".
As an example, the string P(((--)))--PNP) is a sentence, because it's of the form P(X) , with X standing for ((--)))--PNP (note that parenthesis here don't mean what they usually do; here, they are just symbols).

Here's the question: Suppose it's known that the machine can only print true statements; ie the following statement is true:

Every sentence that is printable by the machine is true.

Does the converse hold? Or, to put it another way, is the following statement also true:

Every true sentence is printable by the machine

And note that the term 'sentence' means strings of the forms listed above.

Problem 4 (The Godelian Island Problem from Raymond Smullyan.)
A certain island G is inhabited exclusively by knights who always tell the truth and by knaves who always lie. In additions, some of the knights are called established knights (these are knights who have in a certain sense proved themselves) and some of the knaves are called established knaves .

Now, the inhabitants of this island have formed various clubs. It is possible that an inhabitant may belong to more than one club. Given any inhabitant X and any club C, either X claims that he is a member of C or he claims that he is not a member of C. (Note, incidentally, that this seems to be an island devoid of women...)

And we have the following four conditions:

  1. The set of all established knights forms a club.
  2. The set of all established knaves forms a club.
  3. Given any club C, the set of all inhabitants of the island who are not members of C form a club of their own. This club is called the complement of C
  4. Given any club C, there is at least one inhabitant of the island who claims to be a member of C.
So there are four questions, two from Godel and two from Tarski:
  1. Prove there is at least one unestablished knight on the island.
  2. Prove there is at least one unestablished knave on the island.
  3. Does the set of all knaves on the island form a club?
  4. Does the set of all knights on the island form a club?