Теоремы существования, доказанные от противного

[gefest_md]

В начальном курсе анализа встречал пару теорем, в процессе доказательства которых надо доказывать предложение о существовании, и которое доказывается от противного построением отношения или функции. Сейчас могу вспомнить теорему: Если функция имеет предел по Гейне, то она имеет предел по Коши. Чтобы доказать, что $\exists \delta >0\forall x\,\dots\, ,$ допускается $\forall \delta>0\exists x\neg\,\dots\,$ и на основе последнего задаётся последовательность, которая помогает прийти к противоречию.

Ещё пример.
Пусть $n\in \omega$, $E\subseteq n^+$, $E\not=\varnothing.$ Докажите, что $E$ имеет наибольший элемент, т.е. существует $m\in E$, что для любого $e\in E$, $e\,\underline{\in}\, m.$
В другой теме к этой задаче было предложено тоже доказательство от противного, т.е., как я понимаю, на основе отрицания задаётся некоторое отношение $R$ и доказывается, возможно с помощью индукции, что $\text{ran}(R)$ неограниченно.

Предлагаю вспомнить ещё учебные теоремы такого же рода.

[bot]

gefest_md в сообщении #1641216 писал(а):

Предлагаю вспомнить ещё учебные теоремы такого же рода

Это какого такого? Теоремы из анализа, доказываемые от противного?

[gefest_md]

bot в сообщении #1641220 писал(а):

Это какого такого? Теоремы из анализа, доказываемые от противного?

Учебные теоремы, где нужно доказать существование от противного, из учебников по любым математическим дисциплинам. Ради поддержания интереса.

[gefest_md]

Процитирую из интернета ещё одну теорему такого типа. Доказательство не пересматривал пока.

Теорема. Если функция непрерывна на отрезке, то она ограничена на этом отрезке.

Upd Теорему про максимум и минимум убрал.

[EminentVictorians]

gefest_md в сообщении #1641227 писал(а):

Теорема. Если функция непрерывна на отрезке, то она имеет на этом отрезке максимальное и минимальное значение.
Теорема. Если функция непрерывна на отрезке, то она ограничена на этом отрезке.

Тут можно без метода от противного.

Отрезки в $\mathbb R$ - это в точности связные компакты. Непрерывный образ компакта - компакт; непрерывный образ связного - связный. Поэтому, непрерывный образ отрезка - отрезок (теорема Дарбу). Ну, а из этого уже вытекают обе Ваши теоремы в 1 шаг.

[Geen]

gefest_md в сообщении #1641222 писал(а):

нужно доказать существование

gefest_md в сообщении #1641227 писал(а):

Если функция непрерывна на отрезке, то она ограничена на этом отрезке.

И существование чего тут доказывается?

[gefest_md]

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

И существование чего тут доказывается?

Заключение теоремы: $\exists C>0\forall x(|f(x)|<C).$

[gris]

Такие теоремы иногда приводятся в качестве задач для более глубоко проникновения в предмет. Например, теоремы о промежуточном значении непрерывной функции или о нуле производной между нулями гладкой функции. Это вроде упражнений на нахождение предела по определению, когда уже дошли до дифуров. Немного искусственно.

[Geen]

gefest_md в сообщении #1641238 писал(а):

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

И существование чего тут доказывается?

Заключение теоремы: $\exists C>0\forall x(|f(x)|<C).$

Простите? Во-первых, в теореме доказывается не это. Во-вторых, в любой (ну почти) теореме, если развернуть все определения, можно насчитать с десяток кванторов существования. В-третьих, а что, без этой теоремы нам не известно о существовании $C$???

[gefest_md]

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

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

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

[gefest_md]

Задачу 1 могу доказать по индукции. По другому не получается. Зато вторая задача доказывается без индукции, от противного.

1. Любое непустое конечное множество из $\omega$ имеет наибольший элемент.

2. Пусть $n\in\omega$ и $f\colon n\to\omega.$ Тогда $\text{ran}(n)\subseteq k,$ для некоторого $k\in\omega.$
Док-во. Допустим заключение неверно, т.е. $\forall k\in\omega\exists x\in\text{ran}(f)(x\notin k).$ Кажется ситуация не стала лучше. Что подставить вместо $k?$ Но всё же можно задать объект.

$$R=\{(k,x)\in\omega\times\omega\mid x\in \text{ran}(f)\wedge k\,\underline{\in}\,x\}.$$

Дальше, от противного, по задаче 1, выводится, что $\text{ran}(R)$ бесконечно. Из соотношения $\text{ran(R)}\subseteq\text{ran}(f)$ следует, что $\text{ran}(f)$ бесконечно.

С другой стороны, $g\colon n\to \text{ran}(f),$ $g(x)=f(x).$ Зададим функцию $h\colon \text{ran}(f)\to n$ так:

$h(i)=\text{ наименьшее }i\in n\text{ такое, что }f(i)=x.$

$h$ инъективна. Поэтому $\text{ran}(f)$ конечно. Противоречие.

[drzewo]

gefest_md в сообщении #1641216 писал(а):

В начальном курсе анализа встречал пару теорем, в процессе доказательства которых надо доказывать предложение о существовании, и которое доказывается от противного построением отношения или функции. Сейчас могу вспомнить теорему: Если функция имеет предел по Гейне, то она имеет предел по Коши. Чтобы доказать, что $\exists \delta >0\forall x\,\dots\, ,$ допускается $\forall \delta>0\exists x\neg\,\dots\,$ и на основе последнего задаётся последовательность, которая помогает прийти к противоречию.

Ещё пример.
Пусть $n\in \omega$, $E\subseteq n^+$, $E\not=\varnothing.$ Докажите, что $E$ имеет наибольший элемент, т.е. существует $m\in E$, что для любого $e\in E$, $e\,\underline{\in}\, m.$
В другой теме к этой задаче было предложено тоже доказательство от противного, т.е., как я понимаю, на основе отрицания задаётся некоторое отношение $R$ и доказывается, возможно с помощью индукции, что $\text{ran}(R)$ неограниченно.

Предлагаю вспомнить ещё учебные теоремы такого же рода.

Если определять компактность в метрическом пространстве в терминах последовательностей, то терорема <<всякое открытое покрытие содержит конечное подпокрытие>> доказывается от противного