Задачка по матлогике

andre1941

Доказать, что формула
for every(x) exist(yPxy ^ y <>c) ^ every(x)every(y)every(z) (x=y V not Pxz V not Pyz)
выполнима, но не выполнима для любого конечного предметного множества (universe).
Называется вроде Infinite Pegeonhole Principle - аналог принципа Дирихле для бесконечного числа кроликов .
Есть у кого какие идеи?

Sanych

Речь в формуле всего лишь о том, что можно разбить всё множество на непересекающиеся подмножества в количестве, равном количеству элементов множества. Вторая часть формулы отвечает за непересечение, первая за непустоту. c - это константа, которая дополнительно выбрасывается, и поэтому для конечного множества такое разбиение становится невозможным. А бесконечному один элемент неважен, так как у него есть небиективное вложение в себя.
Непересекающиеся подмножества, занумерованные элементом множества 'a' — это области истинности по переменной x предикатоввида Pax

andre1941

а как формальное доказательство вести,
скажем для бесконечного числа, нужно просто задать множество M объектов пространства (можно взять на пример натуральный ряд). В качестве P принадлежность двух элементов одному множеству, дальше показываем, что такое возможно...
А для конечного числа невозможность как доказать, воспользоваться обычным принципом Дирихле , что типа М элементов, надо разбить на М подмножеств и еще один выброшен, поэтому хотя бы одно множество выйдет пустым ?

Sanych

Я думаю, надо начать с какого-нибудь общепринятого определения бесконечного множества. А дальше, доказать его эквивалентность факту выполнимости формулы. Но это надо думать, откуда задача. Сами ведь лучше знаете , чему Вас учат.

andre1941

еще какие-нить идеи есть у кого?

minatare

Забить.

andre1941

конструктивные я имел ввиду .
странно , что не предложил мне убить себя

minatare

Убей себя! Ап дверь кафедры логики!

andre1941

какой ты предсказуемый .
что касается сути дела, то для бесконечного случая нужно привести пример множества и правила P на этом множестве, которое этим свойствам удовлетворяет.
невозможность выполнения для конечного числа мне доказать таки удалось .
Оставить комментарий
Имя или ник:
Комментарий: