Принцесса или тигр?

Теперь для любого числа x мы будем обозначать через х* число вида М(х, х). Так вот, я хочу, чтобы моя машина обладала следующими тремя свойствами.

Свойство 1. Для любого числа a должно существовать некоторое число b, такое, что при любом x число М(х, b) будет иметь ту же самую четность, что и число М(х*,а).

Свойство 2. Для любого числа b должно существовать некоторое число а, такое, что при любом x число М(х, а) будет иметь другую четность по сравнению с числом М(х, b).

Свойство 3. Должно существовать число h, такое, что при любом x число М(х, h) будет иметь ту же самую четность, что и само х.

— Вот такими свойствами должна обладать моя машина, — заключил Уолтон.

Инспектор Крейг некоторое время молчал, размышляя.

— Ну и в чем же дело? — спросил он наконец.

— Увы! — отвечал Уолтон. — Сначала я построил машину со свойствами 1 и 2, потом — машину со свойствами 1 и 3, наконец, я сконструировал машину со свойствами 2 и 3. Все три машины прекрасно работают — вон там, в портфеле, у меня подробные схемы… Но когда я пытаюсь объединить все три свойства в одной машине, у меня ничего не получается.

— Что же именно у вас не получается? — поинтересовался Крейг.

— Да она вообще не работает! — воскликнул Уолтон с отчаянием. — Когда я ввожу в нее пару чисел (х, у), то вместо того, чтобы выдать мне результат, машина вдруг начинает странно гудеть, как будто в ней происходит нечто вроде короткого замыкания. Как вы думаете, отчего это может быть?

— Да-а, — покачал головой Крейг. — Здесь есть над чем подумать. Правда, сейчас мне надо уйти, меня ждут, но если вы оставите мне свою визитную карточку или просто фамилию и адрес, то я немедленно дам знать, как только во всем этом разберусь.

Через несколько дней инспектор Крейг написал Уолтону письмо. Начиналось оно так:

Дорогой мистер Уолтон!

Благодарю Вас за то, что вы посетили меня и рассказали о машине, которую пытались построить. Честно говоря, я не совсем понимаю, каким образом ваша машина, даже если бы вам действительно удалось ее создать, могла бы решать любые математические задачи, — хотя вы, несомненно, разбираетесь в этом лучше меня. Однако должен вам сказать, что ваш замысел напоминает мне попытку создания вечного двигателя — он также неосуществим! Фактически же дело обстоит гораздо хуже, чем с вечным двигателем. Ведь последний, несмотря на то что он невозможен в нашем физическом мире, все же не является логически невозможным. Машина же, которую хотите создать вы, невозможна не только физически, но и логически, поскольку те три свойства, о которых вы упоминали, содержат в себе определенное логическое противоречие.

Дальше Крейг объяснял, почему существование подобной машины логически невозможно. Можете ли вы сообразить, почему?

Полезно разбить решение этой задачи на три этапа:

1) показать, что для любой машины, обладающей свойством 1, при любом числе а должно существовать по крайней мере одно число х, такое, что число М(х, а) будет иметь ту же самую четность, что и само х;

2) показать, что для любой машины, обладающей свойствами 1 и 2, при любом числе b найдется некоторое число х, такое, что число М(х, b) будет иметь иную четность по сравнению с этим х;

3) ни одна машина не может объединить в себе свойства 1, 2 и 3.

Решение

а) Рассмотрим машину, обладающую свойством 1. Возьмем произвольное число а; тогда, согласно свойству 1, найдется число b, такое, что при любом x число М(х, b) будет иметь ту же самую четность, что и число М(х^#, а). В частности, если положить x равным b, то число M(b, b) будет обладать той же самой четностью, что и число М(b^#, а). Однако число М(b, b) — это просто b^#, и, значит, число b^# должно иметь ту же самую четность, что и число М(b^#, а). Таким образом, положив x равным числу b^#, мы видим, что число М(х, а) имеет ту же самую четность, что и само число х.