Трансфинитная индукция
Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчётного числа значений параметра.
Трансфинитная индукция основана на следующем утверждении:
|
Пусть <math>M</math> — вполне упорядоченное множество, <math>P(x)</math> при <math>x\in M</math> — некоторое утверждение. Пусть для любого <math>x\in M</math> из того, что <math>P(y)</math> истинно для всех <math>y<x</math> следует, что верно <math>P(x)</math>. Тогда утверждение <math>P(x)</math> верно для любого <math>x</math>. |
Связь с математической индукцией
Математическая индукция является частным случаем трансфинитной индукции. Действительно, пусть <math>M</math> — множество натуральных чисел. Тогда утверждение трансфинитной индукции превращается в следующее: если для любого натурального <math>n</math> из одновременной истинности утверждений <math>P(1)</math>, <math>P(2)</math>, <math>\ldots</math>, <math>P(n-1)</math> следует истинность утверждения <math>P(n)</math>, то истинны все утверждения <math>P(n)</math>. При этом база индукции, то есть <math>P(1)</math>, оказывается тривиальным частным случаем при <math>n=1</math>.
Примеры использования
Во многих случаях трансфинитная индукция используется совместно с теоремой Цермело, утверждающей, что любое множество можно вполне упорядочить. Теорема Цермело эквивалентна аксиоме выбора, поэтому доказательство получается неконструктивным.
В качестве примера докажем, что можно провести некоторое множество окружностей так, чтобы через каждую точку плоскости проходило ровно 2 окружности. (В данном случае можно привести и явную конструкцию, однако для случая трёх окружностей доказательство ниже лишь слегка изменяется, а явная конструкция пока не известна.)
Вполне упорядочим точки плоскости так, чтобы мощность множества точек, меньших <math>x</math> была меньше, чем континуум (можно показать, что любое множество можно вполне упорядочить так, чтобы для любого его элемента множество меньших его имело меньшую мощность). В качестве <math>P(x)</math> возьмем следующее утверждение: можно провести менее, чем континуальное множество различных окружностей так, чтобы каждая точка меньшая или равная <math>x</math> была покрыта ровно 2 окружностями, а остальные точки были покрыты не более, чем двумя окружностями, а также для любой точки <math>y<x</math> это множество можно выбрать таким, чтобы оно содержало множество окружностей для точки <math>y</math>. Если <math>x</math> — минимальная точка, то возьмем любые 2 различные окружности проходящие через эту точку. Утверждение <math>P(x)</math> для минимального <math>x</math> доказано. Пусть теперь <math>x</math> — любая точка и известно, что утверждение верно для любого <math>y<x</math>. Возьмем объединение наборов окружностей для всех точек <math>y<x</math>. По предположению индукции можно считать, что наборы окружностей для больших точек включают наборы окружностей для меньших точек, поэтому полученный набор будет покрывать точки плоскости не более двух раз. Так как множество элементов меньших <math>x</math> меньшее, чем континуум и каждое объединяемое множество меньше, чем континуум, то полученное множество будет также иметь мощность меньшую, чем континуум. Построенное множество окружностей уже 2 раза покрывает все точки, меньшие <math>x</math>.
Покажем теперь, как покрыть <math>x</math>. Через <math>x</math> проходит континуум непересекающихся окружностей. Заметим, что любая пара окружностей пересекается не более, чем в двух точках, а значит мощность множества точек плоскости, покрытых 2 раза, меньше, чем континуум (здесь используется утверждение, что <math>A\times A</math> равномощно <math>A</math>, если <math>A</math> — бесконечное множество). Значит найдется континуум окружностей, на которых нет точек, покрытых 2 раза. Возьмем из них одну или две, в зависимости от количества окружностей, уже проходящих через точку <math>x</math>. Утверждение индукции доказано.
См. также
Напишите отзыв о статье "Трансфинитная индукция"
Литература
- Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970. — 416 с.
Отрывок, характеризующий Трансфинитная индукция
Борис чуть заметно улыбался, слушая мать. Он кротко смеялся над ее простодушной хитростью, но выслушивал и иногда выспрашивал ее внимательно о пензенских и нижегородских имениях.Жюли уже давно ожидала предложенья от своего меланхолического обожателя и готова была принять его; но какое то тайное чувство отвращения к ней, к ее страстному желанию выйти замуж, к ее ненатуральности, и чувство ужаса перед отречением от возможности настоящей любви еще останавливало Бориса. Срок его отпуска уже кончался. Целые дни и каждый божий день он проводил у Карагиных, и каждый день, рассуждая сам с собою, Борис говорил себе, что он завтра сделает предложение. Но в присутствии Жюли, глядя на ее красное лицо и подбородок, почти всегда осыпанный пудрой, на ее влажные глаза и на выражение лица, изъявлявшего всегдашнюю готовность из меланхолии тотчас же перейти к неестественному восторгу супружеского счастия, Борис не мог произнести решительного слова: несмотря на то, что он уже давно в воображении своем считал себя обладателем пензенских и нижегородских имений и распределял употребление с них доходов. Жюли видела нерешительность Бориса и иногда ей приходила мысль, что она противна ему; но тотчас же женское самообольщение представляло ей утешение, и она говорила себе, что он застенчив только от любви. Меланхолия ее однако начинала переходить в раздражительность, и не задолго перед отъездом Бориса, она предприняла решительный план. В то самое время как кончался срок отпуска Бориса, в Москве и, само собой разумеется, в гостиной Карагиных, появился Анатоль Курагин, и Жюли, неожиданно оставив меланхолию, стала очень весела и внимательна к Курагину.
– Mon cher, – сказала Анна Михайловна сыну, – je sais de bonne source que le Prince Basile envoie son fils a Moscou pour lui faire epouser Julieie. [Мой милый, я знаю из верных источников, что князь Василий присылает своего сына в Москву, для того чтобы женить его на Жюли.] Я так люблю Жюли, что мне жалко бы было ее. Как ты думаешь, мой друг? – сказала Анна Михайловна.
Мысль остаться в дураках и даром потерять весь этот месяц тяжелой меланхолической службы при Жюли и видеть все расписанные уже и употребленные как следует в его воображении доходы с пензенских имений в руках другого – в особенности в руках глупого Анатоля, оскорбляла Бориса. Он поехал к Карагиным с твердым намерением сделать предложение. Жюли встретила его с веселым и беззаботным видом, небрежно рассказывала о том, как ей весело было на вчерашнем бале, и спрашивала, когда он едет. Несмотря на то, что Борис приехал с намерением говорить о своей любви и потому намеревался быть нежным, он раздражительно начал говорить о женском непостоянстве: о том, как женщины легко могут переходить от грусти к радости и что у них расположение духа зависит только от того, кто за ними ухаживает. Жюли оскорбилась и сказала, что это правда, что для женщины нужно разнообразие, что всё одно и то же надоест каждому.
– Для этого я бы советовал вам… – начал было Борис, желая сказать ей колкость; но в ту же минуту ему пришла оскорбительная мысль, что он может уехать из Москвы, не достигнув своей цели и даром потеряв свои труды (чего с ним никогда ни в чем не бывало). Он остановился в середине речи, опустил глаза, чтоб не видать ее неприятно раздраженного и нерешительного лица и сказал: – Я совсем не с тем, чтобы ссориться с вами приехал сюда. Напротив… – Он взглянул на нее, чтобы увериться, можно ли продолжать. Всё раздражение ее вдруг исчезло, и беспокойные, просящие глаза были с жадным ожиданием устремлены на него. «Я всегда могу устроиться так, чтобы редко видеть ее», подумал Борис. «А дело начато и должно быть сделано!» Он вспыхнул румянцем, поднял на нее глаза и сказал ей: – «Вы знаете мои чувства к вам!» Говорить больше не нужно было: лицо Жюли сияло торжеством и самодовольством; но она заставила Бориса сказать ей всё, что говорится в таких случаях, сказать, что он любит ее, и никогда ни одну женщину не любил более ее. Она знала, что за пензенские имения и нижегородские леса она могла требовать этого и она получила то, что требовала.
