Лемма о конечном покрытии.

Понятия множества. Логические символы

Определение 1. Множества A и B называются равными, если каждый элемент множества A является элементом

множества B и наоборот, каждый элемент множества B является элементом множества A.

Равенство множеств A и B обозначают A = B. Равные множества состоят из одних и тех же элементов.

Равенство множеств обладает следующими свойствами:

1) A = A (рефлексивность);

2) A = B, B = C⇒A = C (транзитивность);

3) A = B⇒B = A (симметричность).

Если множество A не равно множеству B, то пишут A<= B.

Определение 2. Множество A (A<= ∅) называетсяподмножествоммножестваB (B<= ∅), есликаждыйэлемент

множества A является элементом множества B, и обозначают A⊂B.

 

 

Операции над множествами. Отображение множеств

1Объединением множеств A и B называется множество A ∪ B, содержащеетеитолькотеэлементы,

которые принадлежат хотя бы одному из множеств A или B (или обоим одновременно):

A ∪ B = {x | x ∈ A или x ∈ B или (x ∈ A и x ∈ B)}

2Пересечением множеств A и B называется множество A ∩ B, состоящее из всех тех и только тех

элементов, каждый из которых принадлежит обоим множествам одновременно:

A ∩ B = {x | x ∈ A и x ∈ B}.

3. Разностью двух множеств B и A называется множество B \ A, состоящее из всех тех и только тех

элементов, которые принадлежат B, но не принадлежат A:

B \ A = {x | x ∈ B и x ∈/ A}.

4Два элемента x и y называются упорядоченной парой, если указано, какой из этих элементов первый,

какой второй и обозначают (x, y), при этом считается (x1, y1) = (x2, y2) ⇔ (x1 = x2, y1 = y2).

5. Декартовым произведением двух множеств A и B называется множество, обозначаемое A Ч B,

состоящее из всевозможных упорядоченных пар (x,y):

A х B = {(x,y) | ∀x ∈ A, ∀y ∈ B}.

1.1 Отображение f : A → B называют взаимно однозначным или биективным, если каждый элемент

b ∈ B являетсяобразомтолькоодногоэлемента a ∈ A.

1.2 Отображение f^(-1) называют обратным к отображению f, если a→b, b→ a, т.е. элементу b ∈ B

ставится в соответствие тот элемент a ∈ A, образомкоторогоприотображении f является b:

1.3Два множества A и B называются эквивалентными (равномощными), если существует хотя бы одно

взаимно однозначное отображение одного множества на другое, и обозначаются A ∼ B.

 

 

Аксиоматика множества действительных чисел.

Определение 1. Множество R называется множеством действительных чисел, а его элементы действительными чис-

лами, если выполняется следующая система аксиом:

I. Аксиомы сложения.

I1. ∀x,y∈R :x + y = y + x (коммутативныйзакон).

I2. ∀x,y,z∈R : (x + y) + z = x + (y + z) (ассоциативный закон).

I3. ∃0 ∈R :∀x∈R⇒x + 0 = x (существованиевRнуля).

I4. ∀x∈R∃(−x) ∈R :x + (−x) = 0 (существованиевRпротивоположногоэлемента).

II. Аксиомы умножения.

II1. ∀x, y∈R \ {0} :x·y = y·x (коммутативныйзакон).

II2. ∀x, y, z∈R \ {0} :x · (y · z) = (x · y) · z (ассоциативный закон).

II3. ∃1 ∈R : 1 ·x = x∀x∈R (существованиенейтральногоэлемента).

II4. ∀x∈R \ {0} ∃x−1 :x·x−1 = 1 (существованиеобратногоэлемента).

II5. ∀x,y, z∈R : (x + y) ·z = x·z + y·z (дистрибутивный закон относительно сложения).

III. Аксиомы порядка.

III1. ∀x,y∈R :x =/ y⇒x<yилиy<x.

III2. ∀x,y∈R :x<=y и y<=x⇒x = y.

III3. ∀x,y,z∈R :x<=yиy<=z⇒xꯈz.

IV. Аксиомы полноты (непрерывности).

IV1. Если непустые множества X,Y⊂Rтаковы, что∀x∈Xи∀y∈Yвыполняетсянеравенствоx<=y, то ∃c∈R,такое, что x<=c<=y.

 

4.Лемма о верхней грани числового множества.

Всякое ограниченное сверху непустое подмножество действительных чисел X имеет единственную точ-

Ную верхнюю грань.

Доказательство. Единственность верхней грани для множества X обеспечивается аксиомой III2.

Докажем существование верхней грани для множества X. Обозначим через Y множество всех чисел, ограничива-

ющих сверху множество X. Множество X ограничено сверху, поэтому множество Y не пусто. Каждый элемент y ∈ Y

ограничивает сверху множество X, следовательно, для любого элемента x ∈ X выполняетсянеравенство x <= y. Элемен-

ты x и y являются произвольными элементами соответственно множеств X и Y , поэтому, в силу свойства непрерывности

множества действительных чисел, существует такое число β, что для любых x ∈ X и y ∈ Y имеетместонеравенство

x <= β <= y. Выполнение неравенства x <= y β для всех x ∈ X означает, чточислоβограничиваетсверхумножество X,

а выполнение неравенства β <= y для всех y ∈ Y , т.е. всехчисел, ограничивающихсверхумножество X, означает, чточисло β является наименьшим среди всех таких, т.е. верхней гранью множества X.

 

 

Лемма о вложенных отрезках.

Для всякой системы вложенных отрезков существует хотя бы одно число,принадлежащее всем отрезкам

данной системы.

Доказательство. Пусть задана система вложенных отрезков.

a1 <=a2 <=. . . <=an<=. . . <=bn<=. . . <=b2 <=b1

Обозначим через A множество всех левых концов an - отрезков этой системы, а через B - множество их правых концов bn. Для любых номеров m и n выполняется неравенство am<=bn. Поэтому из неравенства в силу свойства непрерывности множества действительных чисел, следует, что существует такое число ξ, для которого при всех номерах m и n выполняется неравенство am <=ξ <=bn, а, в частности, и неравенствоan <=ξ <=bn, n = 1, 2, . . . Последнее и означает, что число ξ принадлежит всем отрезкам [an, bn].

 

Лемма о конечном покрытии.

Из всякой системы интервалов, покрывающей данный отрезок, можно выделить конечную подсистему

интервалов, покрывающих этот отрезок.

Доказательство. Пусть S = {U} - система интервалов, покрывающая отрезок [a,b] = I1. Если бы отрезок I1 не допускал

покрытия конечным набором интервалов системы S, то поделив I1 пополам, мы получили бы, что по крайней мере одна

из его половинок, которую мы обозначим через I2, тоже не допускает конечного покрытия. С отрезком I2 проделаем ту

же процедуру деления пополам, получим отрезок I3 и т.д.

Таким образом, возникает последовательность I1 ⊃I2 ⊃ ... ⊃In⊃ ... вложенныхотрезков, недопускающихко-

нечного покрытия интервалами системы S. Поскольку длина отрезка, полученного на n-м шаге, по построению равна

|In| = |I1|/2n−1, то в последовательности {In} есть отрезки сколь угодно такой длины. По лемме о вложенных отрез-

ках существует точка C, принадлежащая всем отрезкам In, n∈N. ПосколькуC∈I1 = [a,b], тонайдетсяинтервал

(α,β) = U∈SсистемыS, содержащийточкуC, т.еα<C<β. Пустьε = min{C−α,β−C}. Найдемвпостроенной

последовательности такой отрезок In, что |In| <ε. Поскольку C∈Inи |In| <ε, заключаем, чтоIn⊂U = (α,β). Ноэто

противоречит тому, что отрезок In нельзя покрыть конечным набором интервалов системы.

 

7. Лемма о предельной точке числового множества.

Всякое бесконечное ограниченное числовое множество имеет по крайней мере одну предельную точку.

Доказательство. Пусть X-данное подмножество R. Из определения ограниченности множества X следует, что X содержится в некотором отрезке [a,b] = I⊂R. Покажем, чтопокрайнеймереоднаизточекотрезкаIявляетсяпредельной

для X.

Если бы это было не так, то каждая точка x∈IимелабыокрестностьV (x), вкоторойлибовообщенетточек множества X, либо их там конечное число. Совокупность {V (x)} таких окрестностей, построенных для каждой точки x∈I, образуетпокрытиеотрезкаIинтерваламиV (x), изкоторогополеммеоконечномпокрытииможноизвлечь конечную систему V (x1),...,V (xn) интервалов, покрывающую отрезок I. Но поскольку X⊂I, тоэтажесистема покрывает все множество X. Однако в каждом интервале V (xi) только конечное число точек множества X, значит, и в их объединении тоже конечное число точек X, т.е. X-конечное множество. Полученное противоречие завершаетдоказательство.