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,…


 

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

46261. Значения параметров по умолчанию. Перегрузка функций и операторов. Дружественные функции 13.3 KB
  Дружественная функция объявляется внутри класса, к элементам которого ей нужен доступ, с ключевым словом friend. Дружественная функция может быть обычной функцией или методом другого ранее определенного класса.
46262. Правовая охрана изобретений, полезных моделей и промышленных образцов 13.27 KB
  Патент удостоверяет приоритет авторство изобретения полезной модели или промышленного образца и исключительное право на их использование.В отличие от функций патента срок его действия различается в зависимости от вида объекта промышленной собственности. Так патент на изобретение действует в течение двадцати лет считая с даты поступления заявки в Патентное ведомство.
46263. А.В. Запорожец «Основные проблемы онтогенеза психики» 13.19 KB
  Психологии – сложная динамическая система взаимосвязанных процессов и явлений отдельные процессы развиваются не самостоятельно а в системе. психологии направлены на констатацию происходящих в психике возрастных изменений на изучение причин и законов на установление зависимости изменений от условий жизни ребенка. психологии – наблюдение беседы сбор и анализ продуктов деятти разные виды эксперимента.
46264. Сбор и обработка статистической информации для расчета показателей надежности 13.19 KB
  Для буровых и нефтегазопромысловых машин очень характерно рассеивание хначений показателей надежности. Наряду с особенностями конструкции машин технологии их изготовления большое влияние на разброс показателей надежности оказывают условия эксплуатации техники. Учитывая рассеивание информации о надежности следует установить необходимое количество машин над которыми нужно взять наблюдение как при сборе сведений при эксплуатации оборудования в реальных условиях так и при проведении специальных исследований.
46265. Основные принципы генетического исследования психического развития 13.17 KB
  Основные принципы генетического исследования психического развития. Понятия условий источников и движущих сил психического развития. Генетическая психология интересуется проблемами возникновения и развития психических процессов. Применяемый нами метод писал он может быть методом экспериментально генетическим в том смысле что он искусственно вызывает и создает генетический процесс психического развитияЗадача сводится к тому чтобы экспериментально представить всякую высшую форму поведения не как вещь а как процесс взять ее в...
46266. Выбoр рaциoнaльнoгo спoсoбa вoсстaнoвления детaлей 13.17 KB
  При выборе способа восстановления необходимо учитывать конструктивные особенности детали условия ее работы величину и характер износа материал и термическую обработку размеры восстанавливаемой поверхности технологические возможности ремонтного предприятия надежность работы детали после восстановления затраты на восстановление и т. Определив приемлемые способы ремонта необходимо подробно разработать технологию восстановления детали и определить затраты на восстановление по каждому технологическому процессу. Для того чтобы решить вопрос...
46267. Понятие стадий развития в концепции Пиаже 13.15 KB
  Понятие стадий развития в концепции Пиаже Стадии – это ступени или уровни развития последовательно сменяющие друг друга причем на каждом уровне достигается относительно стабильное равновесие. Пиаже не раз пытался представить интеллектуальное развитие ребенка как последовательность стадий.Процесс развития интеллекта согласно Пиаже состоит из трех больших периодов в течение которых происходит зарождение и становление трех основных структур. Развитие по Пиаже это переход от низшей стадии к высшей.
46268. Этические основы связей с общественностью 13.13 KB
  Существует и ряд кодексов где проф. Это международные и национальные кодексы профессиональной этики: Кодекс профессионального поведения и этики ИПРА 1961 ИПРА МЕЖДУНАРОДНАЯ АССОЦИАЦИЯ ПАБЛИК РИЛЕЙШНЗ Афинский кодекс 1965 Кодекс профессионального поведения института PR ИПР 1986 Европейский Лиссабонский кодекс 1978 кодекс Американского общества паблик рилейшнз 1954 В сентябре 2001 Российская ассоциация по связям с общественностью приняла Российский кодекс профессиональных и этических принципов в области связей с...
46269. Зависимость психического развития от содержания структуры деятельности ребенка. Понятие ведущей деятельности. (Эльконин, Леоньтев) 13.07 KB
  Зависимость психического развития от содержания структуры деятельности ребенка. Понятие ведущей деятельности. То что непосредственно определяет развитие психики ребенка это сама его жизнь развитие реальных процессов этой жизни иначе говоря развитие деятельности ребенка как внешней так и внутренней. Значит в изучении развития психики ребенка следует исходить из анализа развития его деятельности так как она складывается в данных конкретных условиях его жизни.