264а (по Гёделю)
1) Докажите, что на острове G существует по крайней мере один непризнанный рыцарь.
2) Докажите, что на острове существует по крайней мере один неотъявленный лжец.
264б (по Тарскому)
1) Являются ли все лжецы острова G членами одного клуба?
2) Являются ли все рыцари острова членами одного клуба?
Решение задачи 264а. По условию Е>1 все признанные рыцари острова (образующие множество Е) являются членами одного клуба. Следовательно, по условию С все островитяне, входящие в множество ∼Е непризнанных рыцарей, также являются членами одного клуба. Но тогда по условию G существует по крайней мере один островитянин, который утверждает, что является членом клуба Е (иначе говоря, он утверждает, что не принадлежит к множеству непризнанных рыцарей).
Лжец не мог бы утверждать, что он не признанный рыцарь (поскольку утверждение о том, что лжец – не признанный рыцарь, истинно). Следовательно, островитянин, высказавший это утверждение, должен быть рыцарем. Поскольку он рыцарь, то высказываемые им утверждения истинны, поэтому он непризнанный рыцарь. Значит, островитянин, высказавший это утверждение, – рыцарь, но не признанный рыцарь.
По условию Е>2 все отъявленные лжецы являются членами одного клуба. Следовательно (по условию G), существует по крайней мере один островитянин, утверждающий, что он отъявленный лжец (он утверждает, что является членом клуба отъявленных лжецов). Этот островитянин не может быть рыцарем (так как рыцарь не мог бы утверждать, что он лжец). Значит, он лжец. Следовательно, его утверждение ложно, поэтому он не отъявленный лжец. Значит, он лжец, но не отъявленный лжец.
Решение задачи 264б. Если бы все лжецы являлись членами одного клуба, то по крайней мере один островитянин утверждал бы, что он лжец. Но ни рыцарь, ни лжец не могли бы высказать такое утверждение. Следовательно, все лжецы не являлись в одном клубе. Если бы все рыцари являлись членами одного клуба, то (по условию С) все лжецы также являлись бы членами одного клуба, что, как мы доказали, невозможно. Следовательно, все рыцари также не являются членами одного клуба.
Примечания. 1. Задача 264б дает еще одно решение задачи 264а. Хотя оно и неконструктивно, но тем не менее несколько проще предыдущего.
Если бы каждый рыцарь был признанным, то множество всех рыцарей совпадало бы с множеством признанных рыцарей, что невозможно, так как (по условию Е>1) все признанные рыцари состоят в одном клубе, а все рыцари (как показано в решении задачи 264б) не состоят в одном клубе. Таким образом, предположение о том, что все рыцари признанные, приводит к противоречию. Следовательно, должен существовать по крайней мере один непризнанный рыцарь. Аналогично если бы все лжецы были отъявленными, то множество отъявленных лжецов совпадало бы с множеством всех лжецов, что невозможно, так как все отъявленные лжецы являются членами одного клуба, в то время как все лжецы не являются членами одного клуба.