Докажите, что в частично упорядоченном множестве нет бесконечного подмножества

Докажите, что в частично упорядоченном множестве N^k (порядок покоординатный) нет бесконечного подмножества, любые два элемента которого были бы несравнимы.

0

Сообщение от Svetochka14 порядок покоординатный

Уточните, пожалуйста.

0

А ваше N это с обычным порядком?

0

Сообщение от Svetochka14 порядок покоординатный

Лесксикографический, что ли?

0

Сообщение от Байт Лесксикографический, что ли?

Вряд ли. Тогда все векторы были бы сравнимыми. Скорее всего, если по каждой координате наблюдается тогда и сами векторы

Добавлено через 45 минут
Svetochka14, Вот здесь задача 90 является обобщением вашей.
http://www.intuit.ru/studies/c... 986?page=2

Добавлено через 26 минут
Вообще-то в предыдущем посте я не прав насчет обобщения. Там одно другого не исключает. Теория Рамсея сбила с толку. Надо доказывать непосредственно.

0

Вот такое решение пришло в голову (наверно, неоптимальное). Предположим, что такое множество А существует. Пусть b = (b1, ..., bk) — элемент A, для которого координата bk достигает наименьшего значения. Тогда для любого другого элемента a = (a1, ..., ak) найдётся ai < bi, иначе a и b были бы сравнимы.

Я хочу показать, что для некоторого i в A есть бесконечное число элементов с одинаковым значением ai. Предположим, что это не так. Тогда в A есть только конечное число элементов, для которых a1 = 1; только конечное число элементов, для которых a1 = 2; ...; только конечное число элементов, для которых a1 = b1 - 1. То есть в A есть только конечное число элементов, для которых a1 < b1. Аналогично, в A есть только конечное число элементов, для которых a2 < b2 и т. д. То есть в A есть только конечное число элементов, у которых хотя бы одна координата меньше, чем у b. Однако по предыдущему предположению у всякого элемента из A, отличного от b, есть координата, меньшая, чем у b, а число элементов A бесконечно. Противоречие. Значит, действительно для каких-то i и c множество A' = {a ∈ A: a_i = c} бесконечно (и состоит из несравнимых элементов).

Ограничение порядка на A' изоморфно порядку на N^{k-1}, по индукции A' не может существовать. Противоречие.

1