Отношение эквивалентности

[Vladimir Pliassov]

Цитата:

81. (Теорема Рамсея) Множество всех $k$-элементных подмножеств бесконечного множества $A$ разбито на $l$ классов ($k, l$ — натуральные числа). Докажите, что найдётся бесконечное множество $B\subset A$, все $k$-элементные подмножества которого принадлежат одному классу.

https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf, стр. 43

$\rhd$ Множество $G$ всех $k$-элементных подмножеств множества $A$ бесконечно, а $l$ конечно, поэтому среди всех классов $G_i\in G$ найдется бесконечный класс $G_t \;\; t\in \mathbb N$. Все элементы $k$-элементных подмножеств, являющихся элементами множества $G\setminus G_t$, составляют подмножество $A'\in A$. Множество $A\setminus A'$ бесконечно (как доказать?). Выделим из $A\setminus A'$ бесконечное множество $B$. Множество $G'_t$ всех $k$-элементных подмножеств множества $B$ входит в $G_t$, потому что ни одно из этих подмножеств не принадлежит $G\setminus G_t$, то есть нашлось бесконечное множество $B\subset A$, все $k$-элементные подмножества которого принадлежат одному классу $G_t$. $\lhd$

[svv]

Vladimir Pliassov в сообщении #1578157 писал(а):

Множество $A\setminus A'$ бесконечно (как доказать?).

Никак, к сожалению. Представим для конкретики, что $A=\mathbb N$, мы рассматриваем его $k=3$-элементные подмножества, а классов всего $\ell=2$. В моём примере оба класса бесконечны.
Вашим $G_t$ пусть будет $G_1$. Я опишу сначала $G_2=G\setminus G_t$. Составляем его из подмножеств:
$\{1,2,3\},\{4,5,6\},\{7,8,9\},\{10,11,12\},\{13,14,15\},...$
Ясно, что это далеко не все трёхэлементные подмножества $A$. Тем не менее, в этом $G\setminus G_t$ встречаются все элементы $A,$ так что $A\setminus A'$ оказывается пустым...

[mihaild]

Vladimir Pliassov в сообщении #1578157 писал(а):

поэтому среди всех классов $G_i\in G$ найдется бесконечный класс

Чуть аккуратнее, классы являются не элементами $G$, а являются его подмножествами.

[svv]

Мой пример показывает ещё один момент. Хоть класс $G_2$ и бесконечный, не найдётся даже множества $B$ из 4 натуральных чисел, все 3-элементные подмножества которого принадлежали бы $G_2$. Не говоря о бесконечном $B$.

Возможна ситуация, когда все $\ell$ классов бесконечны, но из них лишь один "подходит" (т.е. все $k$-подмножества некоторого бесконечного $B\subset A$ ему принадлежат).

[Ende]

Оффтоп отделен в тему «Теория категорий применительно к алгебре и геометрии»

[Vladimir Pliassov]

svv в сообщении #1578158 писал(а):

Никак, к сожалению. Представим для конкретики, что $A=\mathbb N$, мы рассматриваем его $k=3$-элементные подмножества, а классов всего $\ell=2$. В моём примере оба класса бесконечны.
Вашим $G_t$ пусть будет $G_1$. Я опишу сначала $G_2=G\setminus G_t$. Составляем его из подмножеств:
$\{1,2,3\},\{4,5,6\},\{7,8,9\},\{10,11,12\},\{13,14,15\},...$
Ясно, что это далеко не все трёхэлементные подмножества $A$. Тем не менее, в этом $G\setminus G_t$ встречаются все элементы $A,$ так что $A\setminus A'$ оказывается пустым...

Попробую привести контрпример:

Пусть $A=\mathbb N$, $G$ -- множество всех его $k$-элементных подмножеств, классов $l$ штук, один из них $G_t$ -- множество всех $k$-элементных подмножеств $A$, не состоящих из одних только четных чисел. Тогда $G\setminus G_t$ -- множество всех $k$-элементных подмножеств $A$, состоящих из одних только четных чисел. Четные числа обозначим через $A'$.

Пусть $B\subset A\setminus A'$ это множество всех нечетных чисел, которые делятся на $3$, тогда множество всех $k$-элементных подмножеств множества $B$ входит в $G_t$.

Все классы, кроме $G_t$, состоят из подмножеств, которые состоят из одних только четных чисел.

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

svv в сообщении #1578162 писал(а):

Мой пример показывает ещё один момент. Хоть класс $G_2$ и бесконечный, не найдётся даже множества $B$ из 4 натуральных чисел, все 3-элементные подмножества которого принадлежали бы $G_2$. Не говоря о бесконечном $B$.

Да, правда.

svv в сообщении #1578162 писал(а):

Возможна ситуация, когда все $\ell$ классов бесконечны, но из них лишь один "подходит" (т.е. все $k$-подмножества некоторого бесконечного $B\subset A$ ему принадлежат).

Что же это за ситуация?

mihaild в сообщении #1578159 писал(а):

Чуть аккуратнее, классы являются не элементами $G$, а являются его подмножествами.

Да, я опять: не $G_i\in G$, а $G_i\subset G$.

mihaild в сообщении #1578061 писал(а):

Транзитивность нам никто не гарантирует.

Задача о шестерых помещена у Верещагина-Шеня в связи с теоремой Рамсея -- теоремой о подмножествах. И я думаю, что эту задачу можно решать не как задачу на отношения, а как задачу на множества: о рефлексивности и транзитивности речь не идет, а симметричная пара может здесь рассматриваться как просто пара, то есть как неупорядоченная пара, то есть как множество из двух элементов.

Я предполагаю, что эта задача: "Доказать, что среди любых шести людей есть либо три попарно знакомых, либо три попарно незнакомых, " -- это частный случай более общей задачи. Еще один частный случай: "Доказать, что среди любых восьми людей есть либо пять попарно знакомых, либо три попарно незнакомых". Так ли это?

Geen в сообщении #1577863 писал(а):

Есть такая штука под названием конечная геометрия. Например, имеется ровно 4 точки и 6 прямых (образованных парами этих точек). Это полноценная геометрия... но о каких длинах и углах тут можно говорить?...

Я посмотрел, интересная геометрия. Я думаю, что это обобщение школьной геометрии: все, что есть в конечной геометрии, есть в школьной геометрии (но не наоборот).

mihaild в сообщении #1577974 писал(а):

Vladimir Pliassov в сообщении #1577964 писал(а):

И к тому же, если строк до этого доказательства бесконечно много, то на него так и не наткнешься.

Так не бывает. Множество строк счетно, соответственно его можно занумеровать так, что до каждой строки будет только конечное число строк. Перебирая строки по этой нумерации мы рано или поздно найдем доказательство (если оно вообще существует, конечно).

Действительно, об этом я не подумал. Но это подтверждает состоятельность моего взгляда: поскольку ресурс бесконечен, мы рано или поздно найдем доказательство, если оно существует (ну и потом будем его осваивать, сколько понадобится).

Правда, если оно не существует, мы будем идти к нему вечно. Это уже ... Надо подработать мировоззрение.

Подработал: не найдем -- и не надо, жизнь все равно бессмысленна.

[mihaild]

Vladimir Pliassov в сообщении #1578223 писал(а):

Пусть $B\subset A\setminus A'$ это множество всех натуральных чисел, которые делятся на $3$

У вас текст не согласуется с формулой: $6$ делится на $3$, но $6 \not \in A \setminus A'$ - входит $6$ в $B$ или нет?

Vladimir Pliassov в сообщении #1578223 писал(а):

Что же это за ситуация?

Пример при $l = 2$ уже был. Можете попробовать что-то аналогичное придумать для больших $l$? (подсказка: если классу принадлежат все $k$-элементные подмножества некоторого бесконечного множества, то в нём бывают кортежи с произвольно большой разницей элементов)

Vladimir Pliassov в сообщении #1578223 писал(а):

И я думаю, что эту задачу можно решать не как задачу на отношения, а как задачу на множества: о рефлексивности и транзитивности речь не идет, а симметричная пара может здесь рассматриваться как просто пара, то есть как неупорядоченная пара, то есть как множество из двух элементов.

Я бы сказал, что "на самом деле" это вообще задача на графы. Но тут всё же важно, что нам задано отношение.

Vladimir Pliassov в сообщении #1578223 писал(а):

Я предполагаю, что эта задача: "Доказать, что среди любых шести людей есть либо три попарно знакомых, либо три попарно незнакомых, " -- это частный случай более общей задачи. Еще один частный случай: "Доказать, что среди любых восьми людей есть либо пять попарно знакомых, либо три попарно незнакомых". Так ли это?

Да, это вопрос о так называемых числах Рамсея: число Рамсея $R(x, y)$ - это минимальный размер группы, в которой заведомо найдется либо $x$ попарно знакомых, либо $y$ попарно незнакомых людей. И исходная задача в этих терминах формулируется как "доказать, что $R(x, y) \leq 6$".
При этом известно, что $R(5, 3) = 14$, так что среди $8$ людей может не найтись ни $5$ попарно знакомых, ни $3$ попарно незнакомых. Но это довольно сложная наука. И например значение $R(5, 5)$ или $R(4, 6)$ неизвестны (хотя известно, что $R(x, y)$ конечно для любых $x$ и $y$).

Vladimir Pliassov в сообщении #1578223 писал(а):

Действительно, об этом я не подумал. Но это подтверждает состоятельность моего взгляда: поскольку ресурс бесконечен, мы рано или поздно найдем доказательство, если оно существует (ну и потом будем его осваивать, сколько понадобится).

Я бы сказал, что это означает, что ваш взгляд не позволяет отличить перебор всех строчек подряд от более осмысленной деятельности.

[Vladimir Pliassov]

mihaild в сообщении #1578227 писал(а):

Vladimir Pliassov в сообщении #1578223 писал(а):

Пусть $B\subset A\setminus A'$ это множество всех натуральных чисел, которые делятся на $3$

У вас текст не согласуется с формулой: $6$ делится на $3$, но $6 \not \in A \setminus A'$ - входит $6$ в $B$ или нет?

Исправил:

Пусть $B\subset A\setminus A'$ это множество всех нечетных чисел, которые делятся на $3$

[Vladimir Pliassov]

mihaild в сообщении #1578227 писал(а):

Я бы сказал, что "на самом деле" это вообще задача на графы. Но тут всё же важно, что нам задано отношение.

Если среди шестерых найдутся шестерка, пятерка, четверка или тройка попарно знакомых между собой или если никто ни с кем не знаком, то условия выполняются. Пусть исключаются тройки попарно знакомых между собой, тогда в каждой тройке есть, по крайней мере, двое незнакомых между собой.

Дальше буду решать задачу так, как будто это задача не на отношения, а на множества.

Пусть дано множество $\lbrace a, b, c, d, e, f\rbrace$. В нем можно выделить $20$ трехэлементных и $15$ двухэлементных подмножеств.

Выделим произвольное двухэлементное подмножество в каждом из тех трехэлементных подмножеств, в котором оно есть (таких подмножеств всего четыре). Затем выделим второе произвольное двухэлементное подмножество в каждом из тех трехэлементных подмножеств, в котором оно есть (таких подмножеств тоже четыре), и так далее. На шестом ходу в одном из трехэлементных подмножеств выделится три двухэлементных подмножества, что означает, что из троих, составляющих это подмножество, либо все попарно знакомы, либо все попарно незнакомы (в зависимости от того, какое отношение полагается под двухэлементным подмножеством: "быть знакомыми" или "быть незнакомыми").

[mihaild]

Vladimir Pliassov в сообщении #1578302 писал(а):

Выделим произвольное двухэлементное подмножество в каждом из тех трехэлементных подмножеств, в котором оно есть (таких подмножеств всего четыре).

Это что-то непонятное. Тут уже стоит как-то обозначить объекты, и использовать эти обозначения, иначе слишком много ссылок.
Т.е. пусть $X_1$ - двухэлементное подмножество, такое что для любого $Y$ - трехэлементного подмножества, такого что $X_1 \subset Y$, выполнено что-то там.

[Vladimir Pliassov]

Пусть дано множество $X=\lbrace a, b, c, d, e, f\rbrace$. Тогда имеем множество $G$ всех его трехэлементных подмножеств $X^3_i$ (их всего $20$) и множество $H$ всех его двухэлементных подмножеств $X^2_j$ (их всего $15$).

Произвольное двухэлементное подмножество $X^2_1\subset X$ является подмножеством некоторых четырех из всех $20$ трехэлементных подмножеств $X^3_i\subset X$.

Также и произвольное двухэлементное подмножество $X^2_2\subset X$ является подмножеством некоторых четырех из $20$ трехэлементных подмножеств $X^3_i\subset X$.

Переберем шесть разных таких вхождений двухэлементных подмножеств $X^2_j$ в трехэлементные подмножества $X^3_i$ и каждый раз будет отмечать, какие двухэлементные подмножества входят в какие трехэлементные подмножества.

На шестом ходу в одном из трехэлементных подмножеств обнаружится три из шести произвольно выбранных двухэлементных подмножеств, что означает, что из троих, составляющих это подмножество, либо все попарно знакомы, либо все попарно незнакомы (в зависимости от того, какое отношение полагается под двухэлементным подмножеством: "быть знакомыми" или "быть незнакомыми").

Я все это проделал три раза, (не поленился каждый раз выписывать все $20$ трехэлементных подмножеств), при этом каждый раз выбирал разные двухэлементные подмножества -- совершенно произвольно -- и каждый раз на шестом ходу получал один и тот же результат: обнаруживалось, что в некоторое трехэлементное подмножество $X$ входит три из выбранных шести двухэлементных подмножеств $X$. (Всего трехэлементное подмножество имеет три двухэлементных подмножества.)

[mihaild]

Т.е. вы утверждаете, что для любых $6$ двухэлементных $X^2_1, \ldots, X^2_6$ существует трехэлементное подмножество $X^3$, такое что есть три разных числа $p, q, v$ такие что $X_p^2, X_q^2, X_v^2$ являются подмножествами $X^3$?
Это неправда. Довольно легко (попробуйте) строится набор даже из $8$ двухэлементных подмножеств, для которого такого трехэлементного подмножества не найдется.
Искать ИМХО удобно так: рисуете на плоскости 6 точек, рисуете 8 соединяющих их ребер так, чтобы не было ни одного треугольника.

[Vladimir Pliassov]

Попробовал еще раз и с удивлением обнаружил, что за шесть ходов не получилось. Но получилось за девять.

Значит, в первые три раза получилось (за шесть ходов) благодаря совпадению -- три раза подряд! (Может, мне надо играть в рулетку?)

Но за пятнадцать ходов точно получится: какое бы ни взять трехэлементное подмножество множества $X$, все его двухэлементные подмножества есть среди всех (пятнадцати) двухэлементных подмножеств множества $X$.

Может получиться и за три хода, если, например, взять подмножества $\lbrace a, b\rbrace$, $\lbrace a, c\rbrace$ и $\lbrace b, c\rbrace$ -- они являются подмножествами подмножества $\lbrace a, b, c\rbrace$.

[mihaild]

Vladimir Pliassov в сообщении #1578340 писал(а):

Значит, в первые три раза получилось (за шесть ходов) благодаря совпадению -- три раза подряд!

Вы же не случайные выписывали, а как-то руками подбирали, при этом очень легко пропустить даже бОльшую группу случаев.

К сожалению просто подсчетом числа ходов результат получить не удастся, т.к. за 8 ходов может не получиться, а гарантировать наличие 9 ходов нельзя (может быть что у нас 8 пар знакомых и 7 пар незнакомых).

[krum]