67596

Сравнение множеств

Лекция

Математика и математический анализ

Множества и B называются равномощными если между и B существует взаимно однозначное соответствие т. Доказательство Если количество элементов одинаково то перенумеруем их и установим взаимно однозначное соответствие Следовательно множества равномощны.

Русский

2014-09-12

136 KB

2 чел.

Лекция №5

Сравнение множеств

Литература:

1. Бронштейн Е.М. Множества и функции. Методические указания. Уфа: УГАТУ. 1988.

Определение. Множества A и B называются равномощными, если между A и B существует взаимно однозначное соответствие (т.е. биективное отображение ).

Утверждение. Отношение равномощности множеств является отношением эквивалентности.

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

1) Рефлексивность можно установить, отображая множество само на себя с помощью функции f(x)=x. То есть |A|=|A|.

2) Симметричность. Если  взаимно однозначное соответствие, то и  - также взаимно однозначное соответствие.

3) Транзитивность . Т. е. |A|=|B|, |B|=|C| |A|=|C|.

Рассмотрим разные случаи.

Случай 1. A и B конечны.

Утверждение. В случае, когда A и B конечны (содержат конечное число элементов) A и B равномощны тогда и только тогда, когда количество элементов A = количеству элементов B.

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

a) Если количество элементов одинаково, то перенумеруем их и установим взаимно однозначное соответствие

     

Следовательно, множества равномощны.

б) Пусть множества A и B равномощны. Тогда существует взаимно однозначное соответствие между элементами A и B . Следовательно, их количество должно быть одинаковым.

Поэтому для конечных множеств A можно принять, что мощность |A|=количеству элементов A.

Случай 2. Бесконечные множества

Мощность целого может равняться мощности части. Рассмотрим множества

Можно установить () соответствие: . Следовательно, множества равномощны.

Определение. Говорят, что мощность множества A не превосходит мощности множества B (пишут ), если  множество .

В частности, если AB, то B1=A.

Определение. Говорят что A меньше B (  ), если:

1)

2)

Теорема. Отношение  на совокупности множеств есть отношение частичного порядка для мощностей множеств.

1) Рефлексивность .

2) Транзитивность .

Существуют подмножества B1B и C1C и отображения такие, что f:A B1, g:BC1. Тогда gf - соответствие между A и каким-то подмножеством C.

3) Антисимметричность  (без док-ва).

Теорема.   - отношения линейного порядка (без док-ва).

Теорема Кантора. Пусть N – множество натуральных чисел, A=[0,1] – отрезок действительной оси. Тогда N<A.

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

1) Во-первых,, поскольку подмножество множества A  очевидно, равномощно N.

2) Неравенство  докажем от противного.

Допустим, N=A. Тогда   .

Любое число из A можно представить в виде бесконечной десятичной дроби

f(1)=a1=0,a11a12

f(2)=a2=0,a21a22

f(3)=a3=0,a31a32a33

………………..

f(n)=an=0,an1an2an3…ann

………………..

Построим число b=0,b1b2b3… следующим образом:

  b[0,1] и ban, поскольку b отличается от an в n-ном знаке.

Приходим к противоречию. Теорема доказана.

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

Определение. Множество, равномощное множеству натуральных чисел  называется счетным.

Примеры.

{0, 1, 2, 3,…}

N = 1, 2, 3, 4, 5   A = 0, 1, -1, 2, -2, 3, -3

Теоремы о счетных множествах

Теорема 1.  множество содержит счетное подмножество.

Док-во.

Выберем элемент a1A (A не пусто, так как оно бесконечно);

выберем элемент a2A\{a1} (A\{a1} не пусто, так как A бесконечно);

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

Теорема 2.    подмножество B счетного множества A счетно.

Д-во.  Согласно Т1 из множества B можно выделить счетное C.

Тогда CBA. В силу определения мощности |C||B||A|. Так как A и C – счетные, то |A|=|C|. Т. е. |A||B||A|. Отсюда следует, что |B|=|A|.

Тем самым, счетное множество равномощно своей части.

Т-ма 3. Объединение конечного или счетного семейства счетных множеств – есть счетное множество.

Доказательство. Пусть  

A1={a11,a12,…},

A2={a21,a22,…},

A3={a31,a32,a33,…},

………………..

An={an1,an2,an3,…,ann,…},

………………..

Расположим элементы A в следующем порядке

a11,a12,a21,a31,a22, a13,a14,a23,a32,a41,…

Тем самым, получили взаимно однозначное отображение N на A.

Если в множествах A1, A2, A3,… есть общие элементы, то их объединение A есть подмножество рассмотренной выше последовательности. Но согласно теореме 2 оно счетно.

Следствие 1. Если A и B счетные, то A x B – счетное.

Следствие 2. множество рациональных чисел – счетное

1

2

3

4

1

1/1

1/2

1/3

1/4

2

2/1

2/2

2/3

2/4

3

3/1

3/2

3/3

3/4

4

4/1

….

….

….

….

….

….

….

Следующая теорема позволяет утверждать, что не существует «самого большого» по мощности множества.

Теорема. Мощность булеана множества всегда больше мощности самого множества, т.е |M|<|B(M)|.

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

Так как MB(M), то |M||B(M)|.

Допустим, что |M|=|B(M)|. Значит,   соответствие f:MB(M), т.е. каждому эл-ту xM поставлено в соответствие некоторое множество {xi1, xi2,…}=f(x). Возможны ситуации, когда xf(x) и когда xf(x).

Выделим множество P={x | xf(x)}. Тогда эл-т yM такой, что f(y)=P (поскольку соответствие f:MB(M), между эл-тами x и подмнож-вами , а B(M)- булеан, то каждому подмн-ву в том числе и P поставлен в соответствие некоторый эл-т yM).   

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

Пусть yP. Тогда по определению P yP. Противоречие.

Пусть yP. Поскольку в P входят все эл-ты xf(x), то yP. Опять противоречие.

Теорема доказана.

Теорема. Мощность булеана (множества-степени) счетного множества = мощности континуума: |P(N)|=| [0,1] |.

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

Пусть 0,010…1… – запись любого числа из A=[0,1] в 2ой системе счисления.

Сопоставим этому числу подмножество N, состоящее из чисел, равных номерам разрядов, в которых записана единица. Этим устанавливается взаимно однозначное соответствие между B(N) и [0,1].

Примеры. 

Установить равномощность или неравномощность множеств

1) A = [0,1], B [1,2]

    x  A          y  B y = x + 1

2) A = [0,1], B = [0,2] y = 2x

3) A = [0,1], B = [a,b] y = a + x ( b – a )

4) A = [0,1), B = [1,  ) y =

5) A = [0,1], B = [0,1)  y=x, x2-(n-1); y=2-(n-1)/2, x=2-(n-1), n=1,2,3,…


 

А также другие работы, которые могут Вас заинтересовать

35426. Основные направления развития представлений об эмоциях 256.5 KB
  Основные проблемы психологии эмоций 1.Определение эмоций 1. Предметность эмоций 1. Функции эмоций 1.
35427. Феномен мотивации 245.5 KB
  Феномен мотивации 1. Понятия потребности мотива мотивации. Специфика собственно человеческой мотивации 3. Отличительные характеристики мотивации человека 3.
35428. Понятие об ощущении. Роль ощущений в жизнедеятельности людей 223.5 KB
  Любое изменение в среде которое доступно для зрения слуха и других модальностей психологически презентируется в виде ощущения. Если на вкус мы не можем определить продукт сахар мед значит речь идет только об ощущениях. Болевые сигналы почти всегда презентируются как ощущения так как âпостроитьâ образ боли может только человек с очень богатым воображением. âИначе как через ощущения мы ни о каких формах вещества и ни о каких формах движения ничего узнать не можем.
35429. Общее понятие о восприятии. Отличие восприятия от ощущений 264.5 KB
  Отличие восприятия от ощущений 2. Физиологические основы восприятия 3. Свойства восприятия: предметность целостность константность структурность осмысленность избирательность 4. Закономерности восприятия: апперцепция роль моторных компонентов внимание и восприятие 5.
35430. Общие представления о памяти. Круг явлений памяти. Патологии памяти 270 KB
  Процессы памяти проявляются на всех уровнях жизни, поэтому память также называют “общеорганической функцией” (Э. Геринг, Р. Земон); она включает не только процессы сохранения индивидуального опыта, но и механизмы передачи наследственной информации
35431. ПСИХОДИАГНОСТИКА ХАРАКТЕРА И МОТИВАЦИИ 335.5 KB
  В выражении âэто характерно для негоâ содержится смысл что определенные действия поступки человека являются для него типичными закономерными. Еще в IV веке Аристотель сделал попытку описать характер как центральное личностное образование определяющее лицо индивидуальность человека. Характер человека имеет оценочное значение. В психологии характер определяется как совокупность устойчивых индивидуальных свойств человека складывающихся и проявляющихся в деятельности и общении обусловливающая типичные для него способы поведения и...
35432. Психодиагностика. ОБЩЕЕ ПОНЯТИЕ О ПСИХОМЕТРИИ И ОБЛАСТИ ЕЕ ПРИМЕНЕНИЯ 332.5 KB
  Под ВЫБОРКОЙ понимается случайным образом формируемое из генеральной или выборочной совокупности множество заданий или испытуемых. В совокупности сведений характеризующих валидность теста содержится информация об адекватности применяемой модели деятельности с точки зрения отражения в ней изучаемой психологической особенности о степени однородности заданий субтестов включенных в тест их сопоставимости при количественной оценке результатов теста в целом. для проверки нет ли упущений: преобразуйте этот список в перечень заданий...
35433. ОБЩЕЕ ПОНЯТИЕ О ПСИХОДИАГНОСТИКЕ ЛИЧНОСТИ И ПСИХИЧЕСКИХ СВОЙСТВ 378.5 KB
  Понятие о природных особенностях человека Свойства нервной системы находят свое отражение в темпераменте человека. Дальнейшее изучение темперамента развивалось в двух направлениях: изучение индивидуальных свойств и закономерностей работы нервной системы а не телесной организации; применение факторного анализа. В отечественной психологии изучение свойств нервной системы под руководством И.Павлова завершилось выделением типов нервной системы или типов высшей нервной деятельности.
35434. СОЦИАЛЬНАЯ ПСИХОЛОГИЯ 305.5 KB
  Общая характеристика группы в социальной психологии 6 Классификация групп 7 Основные социальнопсихологические характеристики малой группы 10 Структура группы 12 2. Генезис и динамика малой группы 16 Группа как развивающаяся система 16 Механизмы и этапы развития малой группы 16 Проблема коллектива в отечественной социальной психологии . Группа как субъект совместной деятельности 34 Признаки и структура групповой деятельности 34 Социальнопсихологические...