Skip to content

Instantly share code, notes, and snippets.

@cswiercz
Created May 17, 2016 23:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cswiercz/5b70a1249fa56e212d977cdb5916dd5f to your computer and use it in GitHub Desktop.
Save cswiercz/5b70a1249fa56e212d977cdb5916dd5f to your computer and use it in GitHub Desktop.
A problem from my Advanced Mathematical Logic final when I was an undergraduate.

On the island of Tautologos, all of the inhabitants are either knights, who always tell the truth, or knaves, who always lie. In addition, some of the knights are called “established knights” and some of the knaves are called “established knaves”. Now, the inhabitants of this island form 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 they are a member of C or they claim they’re not a member of C.

We are also given the following four facts:

  • E1: The set of all established knights forms a club.
  • E2: The set of all established knaves forms a club.
  • C (The Complementation Condition): Given any club C, the set of all inhabitants of the island who are not members of C form a club of their own, CBar.
  • G (The Godelian Condition): Given any club C, there is at least one inhabitant of the island who claim that they are a member of C. (Of course, this claim might be false: they could be a knave.)

Prove the following:

  1. There is at least one unestabished knight on the island.
  2. 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?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment