1611678155-8e243485e0094ed4164786c6208411db (П.Е. Алаев - Краткий конспект лекций), страница 2

Тождественно истинная формула не имеет эквивалентной ей с.к.н.ф.,а тождественно ложная — с.д.н.ф.82. ТЕОРИЯ МНОЖЕСТВ2.1. Общие свойства множеств и операции над нимиИзложение математической теории множеств было бы естественно начать сопределения множества. К сожалению, попытки дать строгое и исчерпывающееопределение этого понятия связаны с трудностями, о которых будет сказано несколько слов позже. Интуитивно, общее представление о множествах является обобщением тех конкретных примеров множеств, которые используются в математике:множества натуральных чисел N, его подмножеств, множества вещественных чисел R, множества P (N) всех подмножеств N, множества функций из N в R, и т.д.Любое множество является некоторой совокупностью математических объектов, которые называются его элементами.

Запись x ∈ A означает, что x принадлежит множеству A, т. е. является его элементом. Для множеств выполняетсяАксиома экстенсиональности. Пусть A, B — множества. Тогда A = B ⇔для любого x [x ∈ A ⇔ x ∈ B].Эта аксиома говорит, что множество однозначно определяется своими элементами: если у двух множеств набор элементов один и тот же, то эти множестваравны.Введём несколько стандартных обозначений. Пусть A, B — множества.∅ — единственное множество, не содержащее элементов (пустое множество);A ⊆ B, если для всех x [x ∈ A ⇒ x ∈ B] (A — подмножество B);A ⊂ B, если A ⊆ B и A 6= B (A — собственное подмножество B);A ∪ B — объединение множеств A и B:x ∈ A ∪ B ⇔ x ∈ A или x ∈ B;A ∩ B — пересечение множеств A и B:x ∈ A ∩ B ⇔ x ∈ A и x ∈ B;A \ B = A − B — разность множеств A и B:x ∈ A − B ⇔ x ∈ A и x 6∈ B;{a1 , .

. . , ak } — множество, элементами которого являются a1 , . . . , ak , и только они.Если Φ(x) — некоторое условие, которое в зависимости от x может быть истинным или ложным, то запись {x | Φ(x)} обозначает множество всех x, для которыхΦ(x) истинно (если такое множество существует). Через P (A) обозначим множество всех подмножеств A, т.е. {B | B ⊆ A}.Использование теории множеств в качестве основания математики опирается,в частности, на идею о том, что любой математический объект можно представитьв виде множества. Тем самым понятия “множество” и “математический объект”являются синонимами. Натуральные числа могут быть представлены в виде множеств так:90=∅1 = {0} = {∅}2 = {0, 1} = {∅, {∅}}3 = {0, 1, 2}...n + 1 = n ∪ {n}...Множество натуральных чисел {0, 1, 2, .

. .} будем обозначать N или ω. Иногдавместо термина “множество” будем употреблять его синоним “семейство”.TЕсли S — непустое множество, то S = {x | x ∈ A для всех A ∈ S},SS = {x | существует A ∈ S такое, что x ∈ A}.STИногда эти операции обозначаются как A∈S A и A∈S A.2.2. Упорядоченные пары и n-киУпорядоченный набор (кортеж) длины n (n-ка) определяется индукцией по n:hi = ∅hai = aha, bi = {{a}, {a, b}}ha1 , . .

. , an , an+1 i = hha1 , . . . , an i, an+1 i.Набор ha, bi длины 2 часто называют парой.Предложение (о равенстве n-ок). Если ha1 , . . . , an i = hb1 , . . . , bn i, то все ихкомпоненты попарно равны, т. е. a1 = b1 , . . . , an = bn .Пусть A1 , . . . , An — множества. Их декартово произведение — это множествоA1 × . .

. × An = {ha1 , . . . , an i | a1 ∈ A1 , . . . , an ∈ An }.Если A1 = . . . = An = A, то это декартово произведение называется декартовойстепенью множества A и обозначается An .2.3. ФункцииБинарным отношением называется любое множество R, состоящее из пар.Если при этом R ⊆ A × B, то R называют бинарным отношением между A и B, аесли R ⊆ A2 , то R — бинарное отношение на A. Обратное отношение R−1 равно{hb, ai | ha, bi ∈ R}.Бинарное отношение f называется функцией, если выполняется условие:hx, y1 i, hx, y2 i ∈ f ⇒ y1 = y2 ;dom(f ) = {x | существует y т.ч. hx, yi ∈ f } — область определения функции f ;ran(f ) = {y | существует x т.ч.

hx, yi ∈ f } — множество значений функции f ;10f — функция из A в B, если f — функция, dom(f ) = A и ran(f ) ⊆ B.В последнем случае используется обозначение f : A → B.Замечание. Если f : A → B и x ∈ A, то существует единственный y такой,что hx, yi ∈ f . Этот y лежит в B, называется значением функции f в точке x, иобозначается f (x).Замечание (о равенстве функций).

Если f , g — функции, то f = g ⇔dom(f ) = dom(g) и f (x) = g(x) при любом x ∈ dom(f ).Для любого множества A существует тождественная функцияidA = {hx, xi | x ∈ A}. Ясно, что idA : A → A и idA (x) = x при x ∈ A.Если f и g — функции, то их композиция g ◦ f определяется так:g ◦ f = {hx, zi | существует y т.ч. hx, yi ∈ f и hy, zi ∈ g}.Лемма (о композиции функций).

Пусть f , g и h — функции. Тогдаa) h ◦ (g ◦ f ) = (h ◦ g) ◦ f ;b) если f : A → B, g : B → C, то g ◦ f : A → C и [g ◦ f ](x) = g(f (x)) при x ∈ A.Пусть f : A → B. Говорим, чтоf — функция из A на B (сюрьекция), если для любого y ∈ B найдётся x ∈ A такой,начто f (x) = y; будем обозначать это как f : A −→ B;f — разнозначная функция (1–1 функция, инъекция), если для любых x1 , x2 ∈ A из1−1f (x1 ) = f (x2 ) следует, что x1 = x2 ; пишем, что f : A −−→ B;f — биекция из A на B, если f — одновременно инъекция и функция из A на B.Лемма (о свойствах биекций).1−11−1нанаa) если f : A −−→ B, то f −1 : B −−→ A, f −1 (f (x)) = x при любом x ∈ A иf (f −1 (y)) = y при любом y ∈ B;1−11−11−1нананаb) если f : A −−→ B, g : B −−→ C, то g ◦ f : A −−→ C и (g ◦ f )−1 = f −1 ◦ g −1 .Функция f −1 в (a) называется обратной функцией к f .2.4.

Отношения эквивалентностиПусть R — бинарное отношение на множестве A, т.е. R ⊆ A2 . Говорим, чтоR симметрично, если ha, bi ∈ R ⇒ hb, ai ∈ R,R антисимметрично, если ha, bi, hb, ai ∈ R ⇒ a = b,R транзитивно, если ha, bi, hb, ci ∈ R ⇒ ha, ci ∈ R,R иррефлексивно, если ha, ai 6∈ R для любого a,R рефлексивно на A, если ha, ai ∈ R для любого a ∈ A.Бинарное отношение R ⊆ A2 называется отношением эквивалентности на A,если оно симметрично, транзитивно и рефлексивно на A.Вместо записи hx, yi ∈ R часто будем использовать краткое обозначение xRy иговорить, что x и y эквивалентны относительно R.11Если x ∈ A, то множество x/R = {y ∈ A | xRy} называется классом эквивалентности элемента x.

Множество всех классов эквивалентности A/R = {x/R | x ∈ A}называется фактор-множеством A по R.Семейство D ⊆ P (A) назовём разбиением множества A, если1) любое множество B ∈ D непусто;2) если B1 , B2 ∈ D и B1 6= B2 , то B1 ∩ B2 = ∅;3) для любого x ∈ A существует B ∈ D такое, что x ∈ B.Лемма (о классах эквивалентности). Если R — отношение эквивалентностина A, то A/R — разбиение множества A.Теорема (об отношениях эквивалентности). Для любого множества A существует биекция между множеством всех отношений эквивалентности на A имножеством всех разбиений A.2.5.

Частично упорядоченные множестваБинарное отношение R ⊆ A2 — частичный порядок на A, если оно антисимметрично, транзитивно и рефлексивно на A. Частично упорядоченное множество(ч.у.м.) — это пара (A, R), где R — частичный порядок на A.В дальнейшем, как правило, для частичных порядков будет использоватьсясимвол 6 и его модификации.

Как и раньше, вместо записи hx, yi ∈ 6 используемсокращение x 6 y.Пусть 6 — частичный порядок на A, x ∈ A. Говорим, чтоx — наибольший элемент в A, если y 6 x для всех y ∈ A;x — наименьший элемент, если x 6 y для всех y ∈ A;x — максимальный элемент, если для любого y ∈ A из x 6 y следует, что x = y;x — минимальный элемент, если для любого y ∈ A из y 6 x следует, что x = y;Замечание.

Наибольший элемент (если он существует) единственен и является максимальным, а наименьший (если существует) единственен и является минимальным.Обозначим через x < y то, что x 6 y и x 6= y.Замечание. Если 6 — частичный порядок на A, то < — иррефлексивное итранзитивное отношение на A.Пусть (A, 6A ) — ч.у.м. и B ⊆ A.

Тогда мы можем перенести порядок 6A на B,определяя 6B как 6A ∩ B 2 : это просто означает, что x 6B y ⇔ x 6A y при x, y ∈B. Отношение 6B называется индуцированным порядком на B; легко проверить,что это действительно частичный порядок на B. Иногда мы будем говорить омножестве B как о ч.у.м., подразумевая под этим ч.у.м. (B, 6A ∩ B 2 ).12Частичный порядок 6 на A называется фундированным, если любое непустоеX ⊆ A содержит минимальный (в X) элемент.Предложение (критерий фундированности порядка).