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


 

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

74196. Cloud computing: programming models 35 KB
  Cloud computing: progrmming models1 Cloud computing is computing in which lrge groups of remote servers re networked to llow centrlized dt storge nd online ccess to computer services or resources. Clouds cn be clssified s public privte or hybrid. Cloud computing relies on shring of resources to chieve coherence nd economies of scle similr to utility like the electricity grid over network. t the foundtion of cloud computing is the broder concept of converged infrstructure nd shred services.
74197. History of programming languages and tools 242.5 KB
  History of progrmming lnguges nd tools. PreHistory The first progrmming lnguges predte the modern computer. Figure 1 Punch crd Like mny firsts in history the first modern progrmming lnguge is hrd to identify. To some people the nswer depends on how much power nd humnredbility is required before the sttus of ldquo;progrmming lngugerdquo; is grnted.
74198. Evolution of programming languages and tools 56.5 KB
  The earliest practical form of programming was probably done by Jaquard (1804, France). He designed a loom that performed predefined tasks through feeding punched cards into a reading contraption.
74199. Programming paradigms 45 KB
  Progrmming prdigms. The word progrmming prdigm is used in severl different lthough relted menings in computer science. Progrmming prdigm – pttern tht serves s school of thoughts for progrmming of computers. Progrmming technique – relted to n lgorithmic ide for solving prticulr clss of problems.
74200. Imperative programming languages and tools 78 KB
  Impertive progrmming lnguges nd tools. Progrmming lnguges bsed on the impertive prdigm hve the following chrcteristics: 1 The bsic unit of bstrction is the PROCEDURE whose bsic structure is sequence of sttements tht re executed in succession bstrcting the wy tht the progrm counter is incremented so s to proceed through series of mchine instructions residing in sequentil hrdwre memory cells. Typiclly given vrible my ssume mny different vlues of the course of the execution of progrm just s hrdwre memory cell my contin mny different vlues.1...
74201. Imperative programming languages and tools 56.5 KB
  LGOL gretly influenced mny other lnguges – its mjor contribution is being the root of the tree tht gve rise to mny other progrmming lnguges including BCPL B Pscl PL I Simul C C nd Jv. Niklus Wirth bsed his own LGOL W on LGOL 60 before developing Pscl. This led to the doption of smller nd more compct lnguges such s Pscl...
74202. Functional programming languages and tools 55 KB
  Functional programming languages (FPL) were originally developed specifically to handle symbolic computation and list-processing applications. In FPLs the programmer is concerned only with functionality, not with memory-related variable storage and assignment sequences.
74203. Сылақ және майлау жұмыстарына арналған машиналар 717.44 KB
  Сылақ станциялары мен агрегаттары және қол ысқылауыштарының атқаратын қызметі негізгі параметрлері және қолданылу облысы. Жылжымалы сылау агрегаттары. Еден асты негіздерін дайындауға және шатыр мен гидроизоляциялауға арналған машиналар құрылымы мен жұмысы Жоспар: Сылақ станциялары мен агрегаттары және қол ысқылауыштарының атқаратын қызметі.
74204. Жер жұмыстарына арналған машиналар туралы жалпы мағлұматтар 147.63 KB
  Жұмысшы органдары мен топырақпен өзара әсерлесуі. Топырақтардың физикамеханикалық сипаттамасы Жоспар: Жер жұмыстарына арналған машиналар туралы жалпы мағлұматтар. Жұмысшы органдары мен топырақпен өзара әсерлесуі. Топырақтардың физикамеханикалық сипаттамасы.