Мощность множества

Размещено на http://www.allbest.ru/

Российский государственный педагогический университет им. А.И. Герцена

МОЩНОСТЬ МНОЖЕСТВА

Санкт-Петербург 2011



Содержание

Введение

1. Равномощные множества

2. Счетные множества

3. Мощность континуума

4. Сравнение мощностей

5. Решение задач

Заключение

Список используемой литературы



Введение

До XIX века математиками рассматривались в основном конечные множества. Основы теории конечных и бесконечных множеств были заложены Бернардом Больцано, который сформулировал некоторые из её принципов. С 1872 г. по 1897 г. Георг Кантор опубликовал ряд работ, в которых были систематически изложены основные разделы теории множеств. В канторовской теории множеств впервые были развиты конструктивные подходы к анализу проблемы бесконечности.

Теория множеств изучает общие свойства множеств, преимущественно бесконечных. Понятие множества обычно принимается за одно из исходных понятий, то есть не сводимое к другим понятиям, а значит и не имеющее определения. Однако можно дать его описание: множеством называется собрание, совокупность, коллекция вещей, объединенных по какому-нибудь признаку. Например, можно говорить о множестве всех натуральных чисел, множестве всех точек прямой и т.п.

В 1873 г. Кантор поставил задачу классифицировать бесконечные множества. Основная идея Кантора сводилась к установлению взаимнооднозначного соответствия между множествами. Он показал, что можно установить взаимнооднозначное соответствие между точками прямой и точками плоскости. Следуя принципу взаимнооднозначного соответствия, Кантор установил для бесконечных множеств отношение эквивалентности, или равенства («равномощности» двух множеств). Позднее он установил, что множество действительных чисел обладает большей мощностью, чем множество натуральных чисел и тем самым показал, что бесконечные множества могут быть расклассифицированы по их мощности.

При написании данной курсовой работы я задавался целями:

- изучить основные классы равномощных множеств и на основе равномощности вывести понятие мощности множества;

- изучить сравнение мощностей;

- на основании данного материала решить ряд задач.

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

Во втором параграфе вводится понятие счетного множества, указываются свойства счетных множеств, а так же вводится понятие бесконечного множества.

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

В четвертом параграфе вводится понятие мощности множества, доказывается ряд теорем, помогающих выстроить иерархию мощностей.

В пятом параграфе приводится решение задач.



1. Равномощные множества

равномощный множество аксиоматичный

Пусть А и В два конечных множества.

А = a,b,c,d,e, B = ,,,,

Выясним, одинаково ли количество элементов в этих множествах. Для этого расположим элементы этих множеств следующим образом:

a	b	c	d	e

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

Пусть даны два бесконечных множества:

и M = , n

Расположим элементы данных множества так:

1	2	3	4	…
1				…

Отсюда видно, что «количество» элементов в множествах и М одинаково (т.е. между и M так же можно установить биекцию).

Определение 1: множества А и В называются равномощными (эквивалентными), если между ними существует биекция.

Конечные множества А и В равномощны (А В) тогда и только тогда, когда они состоят из одинакового числа элементов. Т.о., понятие одинаковой мощности есть прямое обобщение понятия одинаковой численности конечных множеств. Пример: пусть А и В суть множества точек двух концентрических окружностей. Будем проводить из центра данных окружностей лучи. Тогда видно, что между А и В можно установить биекцию (каждой точке меньшей окружности поставим в соответствие точку пересечения луча, проходящего через данную точку, и большей окружности).

Пример: пусть А множество точек гипотенузы, а В множество точек катета прямоугольного треугольника. Из каждой точки гипотенузы опустим перпендикуляр на катет В. Установим соответствие между точками гипотенузы и основаниями высот, опущенных из них. Т.о., получим биекцию, следовательно А В. Т.е., гипотенуза и катет содержат «равное количество» точек, хотя катет короче гипотенузы.



Свойства равномощных множеств:

1 А А

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

2 А В В А

Доказательство: Если А В, то между А и В существует биекция, но т.к. биекция есть взаимно однозначное соответствие элементов, то и между В и А существует биекция, т.е. В А.

3 А В, B C А С

Доказательство:

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

Пусть А = , В = , С = .

Т.к. А В, B C, то можно записать следующее

			…
			…
			…
			…

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



2. Счетные множества

Определение 1: множество равномощное множеству натуральных чисел называется счетным. Иногда говорят также, что множество «имеет мощность а».

Пример 1: А = , n

Пример 2: Множество счетно, т.к. каждому целому числу можно сопоставить натуральное число по следующему правилу:

…	2n+1	…	5	3	1	2	4	…	2n	…
…	-n	…	-2	-1	0	1	2	…	n	…

Свойства счетных множеств:

1 из всякого бесконечного множества можно выделить счетное подмножество.

2 всякое бесконечное подмножество счетного множества счетно.

Следствие: если S счетное множество, а А его конечная часть, то S - А S.

3 объединение счетного множества и конечного счетно.

4 объединение двух счетных множеств счетно.

5 объединение конечного числа счетных множеств счетно.

6 объединение счетного числа счетных множеств счетно.

Теорема 1: если М бесконечное множество, а А конечное или счетное множество, то М + А М.

Доказательство: выделим счетное множество D из М (по свойству 2) и пусть



М - D = P, М = Р + D, тогда

Теорема 2: если S бесконечное несчетное множество, а А его конечная или счетная часть, то S - А S.

Доказательство: множество М = S - А бесконечно (в противном случае S было бы конечным или счетным). Тогда М + А М (по теореме 1). Подставив сюда М = S - А, получаем, что S - А S.

Из свойства 2 и теоремы 2 следует, что всякое бесконечное множество имеет равномощное себе подмножество. Конечное множество не обладает таким свойством. Это позволяет дать положительное определение бесконечному множеству.

Определение 2: множество называется бесконечным, если оно содержит равномощное себе подмножество.

Теорема 3: множество счетно.

Теорема 4: множество несчетно.

3. Мощность континуума

Определение: множество равномощное множеству называется множеством мощности континуума. Иногда говорят также, что множество «имеет мощность с».

Теорема 1: всякий отрезок a,b, всякий интервал (a,b) и всякий полуинтервал (a,b или a,b) имеет мощность с.

Теорема 2: \ имеет мощность континуума.

Теорема 3: единичный квадрат имеет мощность континуума.

Следствие: имеет мощность континуума.

Следствие: имеет мощность континуума.

Любое конечномерное пространство имеет мощность континуума. Иначе говоря, мощность множества точек пространства не зависит от числа его измерений.

Теорема 4: объединение континуума множеств мощности континуума имеет мощность множества континуума.

Теорема 5: если элементы множества А определяются с помощью счетного множества значков

А = ,

каждый из которых, независимо от прочих значков, принимает с значений, то множество А имеет мощность с.

Теорема 6: множество Т всех последовательностей вида

(),

где независимо друг от друга, принимают значения 0 и 1, имеет мощность с.

Доказательство:

Пусть S есть множество тех последовательностей из T, в которых, начиная с некоторого места, все равны 1. Каждой последовательности (), входящей в S можно соотнести число, имеющее двоичное разложение 0,… ; это число будет или 1 или (m = 1, 3, … , ), причем полученное соответствие между S и множеством чисел указанного вида, очевидно, взаимооднозначно, откуда следует, что S есть множество счетное.

С другой стороны, если последовательности (), входящей в Т - S, соотнести число с двоичным разложением 0,… , то мы получим взаимооднозначное соответствие между Т - S и полусегментом [0, 1), откуда вытекает, что Т - S, а значит, и Т имеет мощность с.



4. Сравнение мощностей

В предыдущих параграфах был определен смысл выражений «два множества равномощны», «множество имеет мощность а», «множество имеет мощность с». Но само по себе понятие «мощность» еще не определено. Введем формальное определение этого понятия.

Определение 1: пусть все множества разбиты по классам, так что два множества попадают в один класс тогда и только тогда, когда они равномощны. Соотнесем каждому такому классу множеств какой-либо символ и будем его называть мощностью любого множества данного класса. При этом, если мощность некоторого множества А есть , то пишут

А = .

Например, классу, содержащему множество А = {a, b, c}, соотнесен символ «3». Тогда можно сказать, что любое множество, равномощное множеству А, имеет мощность 3. Отсюда видно, что понятие количества элементов конечного множества есть частный вид более общего понятия мощности.

Определение 2: если А В* В, то говорят, что А В.

Определение 3: если А В* В и А не В, то АВ.

Теорема 1: множество F всех вещественных функций, заданных на отрезке 0,1, имеет мощность, большую, чем с.

Доказательство:

1) покажем, что F не U, где U = 0,1

(от противного) пусть F U, : F U ((t) = , t[0,1])

Положим, F (t,x) = . Это есть некоторая определенная функция двух переменных, заданная в области 0t1, 0x1.

Положим теперь, (x) = F (x,x) + 1 (1) . Эта функция задана для 0x1, т.е. (x)=F. Тогда aU: (x) = (2)

= F (a,x) (3)

Подставив в (2) равенства (1) и (3) получим

F (x,x) + 1 = F (a,x) x[0,1],

что невозможно, например, для x = a.

Т.о., F не U.

2)покажем, что F*F: F* U

Например, возьмём F* = {Sin x + c} (0c1). Множество F* имеет с функций, а множество U имеет с точек. Т.е., F* U.

Т.о., FU

Определение 4: мощность множества всех функций, заданных на отрезке [0,1], обозначается символом . С помощью этого символа теорему 1 можно формулировать так: c.

Теорема 2: пусть М какое-либо множество. Если Т есть множество всех подмножеств М, то ТМ. Иначе говоря, для каждого множества существует множество большей мощности. Замечание: пусть М конечное множество, состоящее из n элементов. Тогда множество Т содержит элементов.

Определение 5: если множество М имеет мощность , а множество всех его подмножеств Т имеет мощность , то говорят, что = Теорема 3: с = Доказательство: пусть Т есть множество всех подмножеств , а L множество всех последовательностей вида



Из определения 5 следует, что Т=

Из теоремы 6 §3 следует, что L= c

Возьмём элемент N* Т (N* - некоторое множество натуральных чисел). Соотнесем N* последовательность () по такому правилу: если k N*, то = 1, а если N*, то = 0.

Т.о., мы получаем биекцию между T и L, а значит с =

Из теорем 2 и 3 следует, что c a.

Континуум - гипотеза: не существует мощности промежуточной между a и c.

Теорема 4 (Кантора - Бернштейна): если АВи ВА, то АВ.

Теорема 5: множество всех непрерывных функций, заданных на отрезке [0,1], имеет мощность с.

Доказательство: а) пусть * = {sin x + k}.

* ? * = c с.

Осталось показать, что с.

б) пусть H множество всех последовательностей вида [], где , независимо друг от друга, принимают все вещественные значения. По теореме 5 §3 H= с.

Перенумеруем все рациональные числа отрезка [0,1]:



1) и каждой функции (x) соотнесем последовательность

= [(), (), (), … ]

2)Обозначим множество последовательностей за H*

H* H, т.к. () .

3) (x) g(x) . Действительно, если бы было , то равенство (x) = g(x) выполнялось бы для любого рационального значения x из [0,1], откуда в силу непрерывности обеих функций, следовало бы, что это равенство верно для всякого x из [0,1], и функции (x) и g(x) были бы тождественны.

Из 1), 3) следует, что Н*

Из а) и б) следует (по теореме 4), что с.



5. Решение задач

1) Можно ли на плоскости построить континуум попарно непересекающихся окружностей?

Решение:

Возьмем окружность произвольного радиуса a и все концентрические с ней окружности внутри её (окружности эти пересекаться не будут). Каждой окружности поставим в соответствие длину ей радиуса. Радиус может иметь любую длину от 0 до а. Таким образом, множество таких радиусов равномощно отрезку [0, а], т.е. имеет мощность с. А значит и множество концентрических окружностей имеет мощность с. А значит, на плоскости можно построить континуум попарно непересекающихся окружностей.

2) Можно ли написать на доске континуум попарно непересекающихся букв (размеры букв могут быть произвольными) а) Г; б) N; в) А?

Решение:

а) Дополним букву Г до прямоугольника и проведем его диагональ из левого верхнего угла (обозначим длину диагонали за a). Зафиксируем правый нижний угол и будем уменьшать диагональ (стороны, образующие букву Г, одного прямоугольника не будут пересекаться со сторонами другого прямоугольника). Каждому прямоугольнику поставим в соответствие длину его диагонали. Длина диагонали может иметь любое вещественное значение от 0 до а. Т.о., множество таких диагоналей имеет мощность с, а значит и множество таких прямоугольников есть мощность континуума. Следовательно, и множество пар левых боковых и верхних сторон прямоугольников (т.е. букв Г) имеет мощность континуума. Т.о., на доске можно написать континуум попарно непересекающихся букв Г.



Размещено на http://www.allbest.ru/

б) Напишем под небольшим наклоном букву N. Эта буква состоит из трех отрезков. Проведем четыре вертикальные параллельные прямые через конец каждого отрезка. Ниже данной N изобразим ещё одну N, заключенную между вертикальными прямыми (стороны букв будут попарно параллельны). Эти две буквы отсекают от вертикальных прямых четыре отрезка (обозначим их за a, b, c, d). Установим биекцию между точками отрезков a и b, b и c, c и d при помощи отрезков параллельных сторонам N (отрезки имеют мощность континуума). Т.о., получаем континуум букв N, не пересекающихся между собой и нарисованных на части плоскости.

Размещено на http://www.allbest.ru/



в) В каждом треугольнике буквы А выберем точку с рациональными координатами и поставим эту точку в соответствие букве, внутри которой она находится. Т.к. множество рациональных чисел счетно, то и множество пар рациональных чисел счетно (по шестому свойству счетных множеств), т.е. счетно множество точек с рациональными координатами. Поскольку буквы А не пересекаются, точки совпасть не могут. Т.е. на доске можно написать не больше чем счетное «количество» букв А.

3) Можно ли построить на плоскости континуум попарно непересекающихся восьмерок?

Решение:

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



Заключение

Понятие мощности множества есть обобщение понятия количества элементов в множестве. Очевидно, что количество элементов конечных множеств можно сравнивать. В данной работе было показано, что можно сравнивать и «количество» элементов бесконечных множеств. Наименьшая мощность, которая может быть у множества, это ноль (в случае пустого множества). А ссылаясь на теорему 2 §4 можно утверждать, что наибольшей мощности не существует, т. к. для любого множества существует множество всех его подмножеств (мощность которого больше мощности данного множества, если данное множество не пустое и не одноэлементное), а из полученного множества так же можно составить множество всех его подмножеств (мощность опять же возрастет) и т.д. Обобщая вышеизложенное, можно сказать, что мощности множеств представляют собой особую иерархию. Особенность её состоит в том, что она имеет такие ступени иерархии, между которыми бесконечно много ступеней, а есть и такие, между которыми ничего нет. Например, между мощностями n и n+1, где n, или между мощностями c и a не существует промежуточных мощностей, а между мощностью n и a бесконечно много мощностей (мощность a является наименьшей мощностью среди бесконечных множеств). Формально это можно записать так: 0 1 2 … n … a c … …



Список используемой литературы

1. Натансон И.П. Теория функций вещественной переменной. - М. : Издательство «Наука», 1974.

2. Петров В.А. Элементы функционального анализа. - М. : Издательство «Просвещение», 1978.

3. Малая Советская Энциклопедия. - М. : Издательство «Большая Советская Энциклопедия», 1959.

Размещено на Allbest.ru