I've recently finished dropping my jaw at Raymond Smullyan's "What is the Name of this Book," and the section on Gödel's incompleteness theorem, involving islands of knights (truthers) and knaves (liars), was absolutely astonishing. Problem 268c in the book is not given a solution; in it, Smullyan posits that "...all these islands can be constructed (which I am morally certain is the case, even though I have not verified it)..." and goes on to leave, as an exercise, the question of minimum characters required to populate any previously-examined island.
My trouble is, I can't seem to come up with a single configuration which deserves to be numbered among these islands. The rules and terminology are as follows:
- "Knights" always tell the truth and "knaves" always lie. Only knights and knaves live on the island.
- An "established" knight is one which has proven a truthful nature. A knave may also be "established."
- The inhabitants of the island may be a part of as many "clubs" as they like (including zero) with any number of other inhabitants (also including zero). Any inhabitant X either claims to be a member of any club C, or to be a nonmember of that club C.
- Each club is named after an inhabitant (John, Jim, Jane, Jill, etc.) and each inhabitant informs the name of a corresponding club. There cannot exist two identically-named inhabitants or clubs.
- "Sociable" inhabitants are those who are part of the club sporting their name. "Unsociable" inhabitants are those who are not part of the club sporting their name.
- Inhabitant X is called a "friend" of Inhabitant Y if Inhabitant X claims that Inhabitant Y is sociable.
And the conditions for an island:
E. The set of all established knights forms an additional club. The set of all established knaves forms an additional club.
C. Given any club C, the set of all inhabitants of the island who are not members of C form an additional club on their own (the "complement" clubs).
G. Given any club C, there is at least one inhabitant of the island who claims to be a member of C (whether that claim is true or false is immaterial).
H. For any club C, there is another club D such that every member of D has at least one friend in C, and every nonmember of D has at least one friend who is not a member of C.
"Constructing" an island entails naming all the inhabitants, specifying which are knaves and which are knights, and denoting which clubs they participate and do not participate in. For the sake of specificity, I will arbitrarily (and without knowing if it is possible) ask that the island contain 7 inhabitants (though any solution involving any number of inhabitants is more than welcome, as is a proof of impossibility).