8
$\begingroup$

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:

  1. "Knights" always tell the truth and "knaves" always lie. Only knights and knaves live on the island.
  2. An "established" knight is one which has proven a truthful nature. A knave may also be "established."
  3. 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.
  4. 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.
  5. "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.
  6. 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).

$\endgroup$
  • 3
    $\begingroup$ Rule G disallows the empty island (because there exists a club, due to rule E). Just pointing it out in case anyone wanted to go that route. $\endgroup$ – msh210 Jan 30 at 6:54
  • $\begingroup$ Since no knight would claim to be an established knave, and an established knave would not claim to be an established knave, it must be that the people claiming to be established knaves are all unestablished knaves. Thus, claiming to be an established knave proves you are a knave, and thus the claim establishes you as a knave. Thus, no one can remain who claims to be an established knave. Am I missing something? $\endgroup$ – user3294068 Jan 31 at 14:26
  • $\begingroup$ Suppose all knaves form club C. By G, someone must claim to be part of C, which none can do, so the supposition is actually impossible. Further, by E, all est. knaves do in fact form a club, and so it cannot be that every knave is est., because in that case the club of all est. knaves would be equivalent to C, which we've determined cannot exist. Therefore, some knave(s) must be "unestablished." Smullyan designed this set of rules containing this seeming contradiction as a way to demonstrate Gödel's incompleteness theorem; an unest. inhabitant is analagous to an unprovable statement. $\endgroup$ – Justin Jan 31 at 17:37
4
$\begingroup$

Ok. I have a solution with

4

inhabitants. One question I wasn't sure how to answer was, are we allowed to have more clubs than inhabitants? If so then what would you call the extra clubs, just random names? Anyway, from all the rules I have concluded that

you need at least one of each knight and knave as well as an established knight and knave. This is because from E and C you are creating 4 clubs, and from H, each club needs at least one member in it - so you need at least an established knight and knave.
Established knave isn't going to say he belongs to the club he is in, so you need at least one unestablished knave. Now, the complement of established knight club has only knaves so far - they won't admit they're in that club, so you also need at least one unestablished knight. So you need 4, you can add more people I suppose, but that just complicates things.

Next

The established knight will either be sociable or unsociable. Since he is the only inhabitant in the established knight club, the club D from rule H will need to either be all knights or all knaves for them to be able to be his friend. Right now we only have 4 clubs - established knights and knaves and their complements. So club D can only be the established knaves club. For the established night to be a friend of an established knave he needs to be unsociable.

Same reasoning applies to the established knave club, except his club D will be the established knight club and thus he will need to be sociable.

Fore ease of explanation I will name the inhabitants now:

The established night is Alex, unestablished knight is Bob, established knave is Charlie and unestablished knave is David.

Alex is in the established knight club, Bob, Charlie and David are in the complement to that club. Charlie is in the established knave club and the name of that club is Charlie, because he needs to be sociable, and Alex, Bob and David are in the complement to that club.

Now, Alex cannot be in any club named Alex, and since Charlie is already in a club named Charlie, that means the only club named Alex is the club that contains Bob, Charlie and David.

Because of rule H, when looking at the established knight club, the nonmembers of club D need to have at least one friend who is not a member of C. Charlie club is the club D in this scenario, so David needs to be friends with either Charlie or Bob. David is a knave. He is not friends with Charlie, so he needs to be friends with Bob, so Bob needs to be unsociable. That means the club that contains Alex, Bob and Charlie has to be called David, and that only leaves the established knight club to be named Bob.

Ok, here is the breakdown of inhabitants and clubs:

Alex is the established knight
Bob is unestablished knight
Charlie is established knave
David is unestablished knave

Established knight club is Bob and has Alex in it
Complement to established knight club is Alex and has Bob, Charlie and David in it
Established knave club is Charlie and has Charlie in it
Complement to established knave club is David and has Alex, Bob and David in it

Just a note: Alex and Bob are unsociable, Charlie and David are sociable.

And all the rules:

Rule E and C are met from above.
Rule G: David, being a knave, will say he is in club Bob and Charlie. Bob, being a knight, will say he is in club Alex and David, covering all the clubs.

Rule H:
For club Bob, D is club Charlie. Charlie is friends with Alex. Nonmembers of D are Alex, Bob and David. Alex is friends David, Bob with Charlie, and David with Bob.

For club Charlie, D is club Bob. Alex is friends with Charlie. Nonmembers of D are Bob, Charlie and David. Bob is friends with David, Charlie with Alex, and David with Bob.

For club Alex, D is club David. Alex is friends with David, Bob with David, and David with Bob. Nonmembers of D are Charlie. Charlie is friends with Alex.

For club David, D is Alex. Bob is friends with David, Charlie with Bob, and David with Alex. Nonmembers of D are Alex. Alex is friends with Charlie.

Ok, all the rules are met.

EDIT: Upon review of my answer, I can see that I misinterpreted the H rule a bit. I thought each member of D had to be a friend of at least one inhabitant in C, not that each member of D had to have a friend in C. The "friend" rule does not work both ways, X can be a friend of Y, but Y does not have to be a friend of X. So my reasoning for the solution may be a little flawed, however, as it happens, the solution I have come up with is such that each inhabitant that has a friend, is also a friend of that friend, so this works out for the problem and the solutions is still valid.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Smullyan specifies no method to invent clubs, but I suspect your intuition is correct; I don't see a problem with creating and naming a club with whatever conditions you like (in fact, Smullyan does this exact thing when explaining a few solutions). I believe this answer satisfies the rules, and is just asymmetric enough to satisfy me on a superficial level as well. Thank you very much! $\endgroup$ – Justin Jan 31 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.