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


 

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

24588. Контроль якості роботи аудиторів 29 KB
  Контроль якості роботи аудиторів Аудиторська фірма зобов'язана дотримуватися політики і процедур контролю якості аудиторських послуг які гарантують що всі аудиторські перевірки проводяться у відповідності з Національними стандартами аудиту та Законом України Про аудиторську діяльність . Зміст строки й обсяг аудиторських процедур та політики аудиторської фірми щодо контролю якості залежать від таких чинників як розміри і характер діяльності аудиторської фірми її дислокація рівень організації перевірки і відповідних суджень про...
24589. Поняття аудиторської діяльності та її правове забезпечення 32 KB
  Основними нормативними документами що визначають головні засади аудиторської діяльності є Закон України Про аудиторську діяльність Національні стандарти аудиту та Кодекс професійної етики аудиторів України. Згідно з Законом України Про аудиторську діяльність до аудиторської діяльності належить організаційне і методичне забезпечення аудиту практичне виконання аудиторських перевірок аудиту та надання інших аудиторських послуг. За національним законодавством На жаль національне законодавство обмежує рамки аудиту аудитом фінансової...
24590. Суб’єкти аудиторської діяльності 37.5 KB
  Субєкти аудиторської діяльності Аудиторська діяльність це один із видів підприємницької діяльності суб'єктами якої можуть бути як фізичні так і юридичні особи. Для здійснення аудиторської діяльності одноособово аудитор повинен маючи чинний сертифікат аудитора зареєструватися як суб'єкт підприємницької діяльності у виконавчому комітеті міської районної ради або районній міст Києва і Севастополя державній адміністрації за місцем проживання даного суб'єкта та в Аудиторській палаті України як суб'єкт аудиторської діяльності. Порядок...
24593. Аудит доходів та фінансових результатів 32 KB
  Перевірка звіту про фінансові результати У процесі підтвердження достовірності інформації звіту з фінансових результатів який здійснюється аудитором під час аудиту фінансової звітності можуть виникнути три ситуації коли: ♦ інформація зафіксована у звіті відображає реальний результат від фінансовогосподарської діяльності; ♦ інформація у звіті викривлена ненавмисне тобто через помилки обліку неправильне тлумачення законів неправильну інтерпретацію господарських фактів і з інших причин; ♦ інформація у звіті викривлена через неправильне...
24594. Мета і завдання аудиту доходів і результатів діяльності 33 KB
  Тому всі об'єкти підприємницької діяльності прагнуть одержати якнайкращі результати за цими показниками. Аудитору необхідно пам'ятати що у Звіті про фінансові результати доходи відображають за видами діяльності. У ринкових умовах господарювання результати діяльності суб'єктів підприємницької діяльності є інформацією яка цікавить широке коло користувачів фінансових звітів.
24595. Аудит витрат діяльності 38.5 KB
  До таких витрат за ПсБО № 16 відносять: ♦ адміністративні витрати; ♦ витрати на збут; ♦ інші операційні витрати. До адміністративних витрат належать такі загальногосподарські витрати спрямовані на обслуговування та управління підприємством: ♦ загальні корпоративні витрати організаційні витрати витрати на проведення річних зборів представницькі витрати тощо; ♦ витрати на службові відрядження й утримання апарату управління підприємством та іншого загальногосподарського персоналу; ♦ витрати на утримання основних засобів інших матеріальних...
24596. Аудит витрат на виробництво, собівартості виробленої і реалізованої продукції 31.5 KB
  Одним з основних показників роботи будьякого підприємства є випуск продукції та її собівартість. Вивченні організаційнотехнологічних особливостей клієнта Перед початком перевірки в першу чергу аудитор повинен ознайомитися з організаційними і технологічними особливостями виробництва видами продукції що випускається ресурсами що використовуються підприємством. Під організаційними особливостями необхідно розуміти етапи проходження технологічного процесу від одержання сировини та матеріалів зі складу до здавання на склад готової продукції...