67596

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

Лекция

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

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

Русский

2014-09-12

136 KB

1 чел.

Лекция №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,…


 

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

40582. Разработка диаграмм по методу Баркера 46 KB
  Организационный момент 23 мин: Приветствие фиксация отсутствующих проверка санитарного состояния аудитории заполнение журнала рапортички проверка подготовленности студентов к занятию. Напоминание правил техники безопасности при работе с ПК; 2. Сообщение темы цели и задач практикума 23 мин: Цели: Приобретение навыков моделирования по методу Баркера для построения моделей информационной системы. Актуализация опорных знаний и умений студентов 1015 мин: устный опрос занятие 18 п.
40583. Общие принципы и подходы к разработке ПО 869.44 KB
  Итерация N Унифицированный процесс разработки программного обеспечения USDP Модель вариантов использования описывает случаи в которых приложение будет использоваться. Аналитическая модель описывает базовые классы для приложения. Модель проектирования описывает связи и отношения между классами и выделенными объектами Модель развертывания описывает распределение программного обеспечения по компьютерам.
40584. Структурный подход 30 KB
  Все наиболее распространенные методологии структурного подхода [9111213] базируются на ряде общих принципов [3]. В качестве двух базовых принципов используются следующие: принцип разделяй и властвуй принцип решения сложных проблем путем их разбиения на множество меньших независимых задач легких для понимания и решения; принцип иерархического упорядочивания принцип организации составных частей проблемы в иерархические древовидные структуры с добавлением новых деталей на каждом уровне. Выделение двух базовых принципов не означает...
40585. Проблема сложности больших систем 21.96 KB
  Единственно эффективный подход к решению этой проблемы заключается в построении сложной системы из небольшого количества крупных частей каждая из которых в свою очередь строится из частей меньшего размера и т. по отношению к проектированию сложной программной системы это означает что ее необходимо разделять декомпозировать на небольшие подсистемы каждую из которых можно разрабатывать независимо от других. Это позволяет при разработке подсистемы любого уровня держать в уме информацию только о ней а не обо всех остальных частях системы....
40586. Методология функционального моделирования SADT. Состав и функции моделей SADT 61.84 KB
  Состав и функции моделей SDT. Взаимодействие блоков друг с другом описываются посредством интерфейсных дуг выражающих ограничения которые в свою очередь определяют когда и каким образом функции выполняются и управляются; строгость и точность. отделение организации от функции т. Методология SDT может использоваться для моделирования широкого круга систем и определения требований и функций а затем для разработки системы которая удовлетворяет этим требованиям и реализует эти функции.
40587. Методология функционального моделирования SADT. Состав и функции моделей SADT. Типы связей 40.5 KB
  Вендрова Проектирование ПО Ход урока Организационный момент 24 мин: Приветствие оформление документов к занятию Повторение пройденного материала применяемая методика выводы1520 минзанятие 22 п.5 Сообщение темы урока постановка цели и задачи:13 мин: Методология функционального моделирования SDT; Состав и функции моделей SDT. Изложение нового материала применяемая методика: 5060 мин. лекция: Состав функциональной модели Иерархия диаграмм Типы связей между функциями Моделирование потоков данных процессов...
40588. Психологические особенности профессионального общения сотрудников ОВД 92 KB
  Чтобы профессиональное общение сотрудника ОВД было эффективным и успешным, он обязан разбираться в психологии общения, обладать умением делать выводы на основании фактов и собственных наблюдений.
40589. Создание SADT-диаграмм по произвольным проектам 48 KB
  Организационный момент 23 мин: Приветствие фиксация отсутствующих проверка санитарного состояния аудитории заполнение журнала рапортички проверка подготовленности студентов к занятию. Напоминание правил техники безопасности при работе с ПК; 2. Сообщение темы цели и задач практикума 23 мин: Цели: Приобретение навыков создания SDT моделей по методологии IDEF0. Актуализация опорных знаний и умений студентов 1015 мин: устный опрос занятие 24 п.
40590. Метод моделирования IDEF1 35.48 KB
  Сущность в методологии IDEF1X является независимой от идентификаторов или просто независимой если каждый экземпляр сущности может быть однозначно идентифицирован без определения его отношений с другими сущностями. Сущность называется зависимой от идентификаторов или просто зависимой если однозначная идентификация экземпляра сущности зависит от его отношения к другой сущности рисунок 1. Сущности Каждой сущности присваивается уникальное имя и номер разделяемые косой чертой и помещаемые над блоком. Связь может дополнительно определяться с...