Алексей (abel) wrote,
Алексей
abel

Category:
  • Music:

О кошках

Вчера под конец занятия позабавил слушателей 2-го образования, "доказав" им такую "теорему":
Теорема. Все кошки одного цвета.
Доказательство. Индукция по n - числу кошек. Базис (n=1) очевиден. Предположим, что утверждение теоремы верно для любого числа кошек, не превосходящего n-1 для какого-то фиксированного n > 1. Берем произвольно n-1 кошек, обозначим их множество через M. По предположению индукции все они имеют один цвет. Добавляем к ним n-ю кошку. Из кошек множества M выбираем произвольную кошку и удаляем ее. Тогда оставшиеся кошки вместе с новой кошкой, в силу предположения, будут одного цвета. Возвращая удаленную кошку, получим, что поскольку она и все остальные кошки множества M одного цвета, а новая кошка со всеми неудаленными кошками множества M тоже одного цвета, все n кошек имеют один и тот же цвет. Итак, все кошки одного цвета.

Спрашивается, где ошибка? Конечно, никто не ответил. Подожду некоторое время тут. Может быть, кто-то откликнется забавы ради. Комментарии временно скрываю.
Считаю, что пора опубликовать решение.
Обман - в базисе индукции.
Наименьшее натуральное n, для которого утверждение "теоремы" имеет смысл, равно двум, ибо отношение "x и y имеют одинаковый цвет" бинарное (нетрудно понять, что оно есть эквивалентность). И ясно тогда, что правильно выбранный базис, т.е. n=2, сразу даст утверждение, истинность которого нельзя доказать (а из содержательных соображений понятно, что оно ложно). Именно этот неправильно выбранный базис приводит к некорректному индукционному переходу от n=1 к n=2, что было точно замечено некоторыми коллегами.
Если перевести содержательное утверждение "теоремы" на язык исчисления предикатов 1-го порядка, то получится такая формула:

(x)(y)(КОШКА(x)&КОШКА(y) --> ОДНОГО_ЦВЕТА(x,y))

(напомню, что индивидная переменная в скобках есть одно из обозначений квантора общности по этой переменной).
В написанной формуле КОШКА есть унарный предикатный символ (т.е. в форме, принятой в общей логике, атомарная формула КОШКА(x) записявается как "x есть кошка"), а ОДНОГО_ЦВЕТА - бинарный, что отвечает бинарному отношению "x и y имеют одинаковый цвет".
Можно использовать в интерпретации и многосортную модель, записав утверждение в виде такой формулы:

(x)(y)(КОШКА(x)&КОШКА(y) --> ЦВЕТ(x)=ЦВЕТ(y)),

где ЦВЕТ есть унарный функциональный символ, обозначающий отображение множества индивидов в множество цветов.

Вот и все. :)
Я искренне благодарю всех, кто откликнулся!
Все комментарии разморожены.
Tags: Гете, Пастернак, загадки, математика, работа
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 47 comments