Лемма о разбиениях

[shwedka]

В анализе на пространствах Фока потребовалась следующая 'элементарная' лемма.

Лемма. Пусть Е - множество на плоскости, обладающее свойством, что любая вертикальная прямая и любая горизонтальная прямая пересекают множество не более, чем в 100 точках. Тогда множество Е можно разбить на 200 подмножеств так, что каждое такое подмножество пересекается с любой вертикальной или горизонтальной прямой не более, чем в одной точке.

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

[ozes]

shwedka в сообщении #624316 писал(а):

В анализе на пространствах Фока потребовалась следующая 'элементарная' лемма.

Лемма. Пусть Е - множество на плоскости, обладающее свойством, что любая вертикальная прямая и любая горизонтальная прямая пересекают множество не более, чем в 10 точках. Тогда множество Е можно разбить на 20 подмножеств так, что каждое такое подмножество пересекается с любой вертикальной или горизонтальной прямой не более, чем в одной точке.

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

Всех шведок, наверное, хлебом не корми, а ДАЙ что-нибудь доказать.
Такие вещи очевидны, мне кажется

[nnosipov]

ozes в сообщении #624367 писал(а):

Такие вещи очевидны, мне кажется

Когда кажется --- креститься надо.

[ozes]

nnosipov в сообщении #624387 писал(а):

Когда кажется --- креститься надо.

Вот и СПАМер nnosipov подтянулся.
Правильно, без СПАМА и СПАМеров что за тема может быть?

[Toucan]

ozes в сообщении #624367 писал(а):

Всех шведок, наверное, хлебом не корми, а ДАЙ что-нибудь доказать.

ozes в сообщении #624392 писал(а):

Вот и СПАМер nnosipov подтянулся.

Строгое предупреждение за хамство и искажение ника. С учетом предыдущих нарушений -- бан 2 недели.

Хочу также заметить, что не стоит столь самоуверенно лезть в темы, в которых ничего не понимаете, и употреблять термины, значения которых Вы не знаете.

[RIP]

shwedka в сообщении #624316 писал(а):

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

А вот так можно? Раз множество счётное, то перенумеруем его в каком-нибудь порядке. Дальше определим функцию $f\colon\mathbb N\to\mathbb N$ рекурсивно. Считая, что уже знаем $f(0),\ldots,f(n-1)$, определим $f(n)$ как минимальное натуральное число $m$ такое, что для любого $k<n$ выполнено $(f(k)=m)\Rightarrow\text{(точки $k$ и $n$ не лежат на одной (горизонтальной или вертикальной) прямой)}$. Вроде бы существование такой функции можно доказать с помощью теоремы о рекурсии, т.е. без аксиомы выбора, поскольку тут никакого произвола нет. Но это надо у специалистов спрашивать. А смысл простой: заводим 200 пустых списков (для каждого подмножества), перебираем точки подряд и следующую точку заносим в список с минимальным номером, чтобы не нарушалось условие. Вроде бы очевидно, что эта функция будет давать нужное разбиение, так как из определения следует, что $f(n)\leqslant198$.

[shwedka]

RIP
Совершенно верно. Вопрос еще возникает, можно ли без Цорна рассмотреть несчетный случай. Детская формулировка.

На плоскости дано 100 прямых, ни одна не параллельна осям координат.
Доказать, что точки объединения прямых можно раскрасить в 200 цветов так, чтобы никакие 2 точки одного цвета не лежали бы на одной вертикальной или горизонтальной прямой.

[migmit]

Э... последнее совсем тривиально, причём достаточно 100 цветов: красим каждую прямую в свой цвет, а для точек пересечения выбираем цвет одной из пересекающихся в ней прямых, всё равно какой. Любые две точки одного цвета будут принадлежать одной из этих прямой, а потому не будут лежать на одной вертикали или горизонтали.

Вот только как это связано с исходной задачей — я не врубаюсь.

[shwedka]

Да, слишком просто с прямыми получается. Лучше пусть пообщее.

Дано множество на плоскости, такое, что любая прямая, параллельная какой-либо оси координат, пересекает его в не более, чем 100 точкаx. Доказать, что можно раскрасить .....как выше.

[migmit]

А это просто оригинальная задача.

[shwedka]

migmit в сообщении #624962 писал(а):

А это просто оригинальная задача.

Оригинальная в смысле 'исходная'.

[migmit]

Что-то у меня подозрение, что эта штука может оказаться эквивалентной полному упорядочиванию континуума.

[shwedka]

migmit в сообщении #625371 писал(а):

Что-то у меня подозрение, что эта штука может оказаться эквивалентной полному упорядочиванию континуума.

Не знаю. Доказательство с леммой Цорна у меня есть.

[migmit]

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