Интересная задачка

Gugumot

Пусть [math][res=100]{$\mathbb N=\{1,2,3,\ldots\}$} [/math]
На множестве наборов [math][res=100]{$\mathbb N^{k}$} [/math] вводится отношение частичного порядка
[math][res=100]{$$(a_{1},\ldots,a_{k})\le (b_{1},\ldots,b_{k}) \Longleftrightarrow ( \forall i \; a_{i}\le b_{i}) $$} [/math]
Существует ли бесконечное множество попарно несравнимых наборов?

lena1978

при к=1 очевидно, нет :p

den81

Опять домашку за кого-то решать?

gr_nik

А дальше по индукции. :)
Если два вектора не сравнимы, то по какой-то координате один строго больше другого, а по-какой-то - строго меньше. От противного, если есть бесконечный набор, возьмём из него любой вектор (назовём его "начальным" тогда все остальные векторы можно разделить на k множеств, i-ое множество соответствует тому, что в i-ой координате вектор строго меньше, чем "начальный" (при этом некоторые векторы попадут сразу в несколько множеств). Очевидно, что в каком-то множестве будет бесконечно много векторов. Без ограничения общности можно считать, что это k-ое множество. Тогда если [math]$v_k$[/math] - это k-ая координата "начального" вектора, то для какого-то из значений [math]$1, 2, ..., v_k-1$[/math] будет бесконечно много векторов, k-ая координата которых равна этому значению (поскольку всего их было бесконечно много, а их k-ые координаты были меньше [math]$v_k$[/math]). Таким образом, получили бесконечное множество попарно несравнимых векторов, у которых k-ые координаты совпадают. Значит, есть бесконечное множество попарно несравнимых векторов в (k-1)-мерном пространстве. Знаем, что для k=1 не верно, значит, применив индукцию, получим, что и для любых k не верно.
Оставить комментарий
Имя или ник:
Комментарий: