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


 

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

52991. Використання моделей і моделювання в шкільному курсі фізики 230.5 KB
  Наводиться технологічний ланцюжок вирішення завдань на комп'ютері. Технологія моделювання вимагає від дослідника уміння ставити проблеми і завдання прогнозувати результати дослідження проводити розумні оцінки виділяти головні і другорядні чинники для побудови моделей вибирати аналогії і математичні формулювання вирішувати завдання з використанням комп'ютерних систем проводити аналіз комп'ютерних експериментів. Моделювання експерименту засобами ІКТ Сьогодні коли комп'ютер став основним інструментом дослідника різні види моделей можна...
52993. Найрозумніший (інтелект-шоу з фізики) 127.5 KB
  Стан механічної системи при якому дія на систему зовнішніх сил не викликає взаємного тиску частинок цієї системи називається: 1. Електричний струмом називається: 1 процес хаотичного руху заряджених частинок; 2 процес безперервного руху заряджених частинок; 3 процес напрямленого руху заряджених частинок. Фізична величина яка чисельно рівна добутку швидкості V руху на час t протягом якого він відбувався називається: 1 переміщенням; 2 траєкторією; 3 шляхом; 7. Пристрій який перетворює електричну енергію в енергію обертального руху...
52995. Физкультминутки на уроках русского языка в 5 – 9 классах 164.5 KB
  Когда эти буквы будут обозначать 1 звук вы поднимете голову вверх хлопнете над головой 3 раза и опустите руки вниз. Встаньте ровно руки опущены. Когда вы услышите синонимы поднимите руки вверх и хорошо потянитесь кверху. Когда услышите слово которое пишется с двумя н поднимите руки вверх.
52996. Педагогічний контроль виконання домашніх завдань з фізичної культури 275 KB
  Пропаную добірку вправ, які можуть послужити змістовним наповненням домашніх завдань. Їх виконання не потребує специфічного обладнання та інвентарю, зате забезпечує ефективний розвиток сили, координації рухів, витримки та витривалості. Додаю також нормативи педагогічного контролю виконання домашніх завдань...
52997. Фізкультурно-оздоровчі заходи для учнів молодших класів у режимі навчального дня школи: малі форми активного відпочинку 123 KB
  До цих традиційних заходів додаються психокорекційні: психогімнастика кінесіологічні вправи та ін. Короткочасні фізичні вправи та ігри в процесі уроків і виконання домашнього завдання сприяють підтриманню активної уваги і підвищують працездатність на заняттях. Основні вимоги до вибору вправ до малих форм активного відпочинку: мають відповідати віковим особливостям учнів бути простими цікавими та доступними мати ігровий характер бути зручними для виконання на обмеженій площі емоційними й досить інтенсивними; мають бути знайомі...
52998. Сценарій фізкультурно-оздоровчого Свята «Відкриття шкільної спартакіади» 376 KB
  Ведучий 1: Ми запрошуємо вас в країну шкільної Спартакіади. Ведучий 2: Шановні учні школи. Ведучий 1: Символом Олімпійських ігор є п`ять олімпійських кілець. показовий виступ художньої гімнастики Ведучий 2: Школа До виносу Олімпійського прапора струнко Винос прапора.
52999. Рухливі ігри на уроках фізкультури та в режимі навчального дня 110 KB
  Світ ігор дуже різноманітний: рухливі сюжетні народні рольові спортивні імітаційні командні групові ігриестафети ігриконкурси ігризабави ігризмагання тощо. Найкращими ліками для дітей від рухового голоду є рухливі ігри. Ігри на уроках фізкультури та в режимі навчального дня використовуються для гармонійного поєднання розумових фізичних та емоційних навантажень загального комфортного стану.