Функциональный(конспекты и вопросы в конце)

Åñëè A B, то дополнением множества A в множестве B называют

A := B \ A.

Если для некоторых множеств рассматривают их дополнения и при этом не указывают в каких множествах эти дополнения рассматривают, то подразумевается, что эти дополнения рассматривают в некотором одном множестве, которое содержит все рассматриваемые множества.

Åñëè A множество и A свойство элементов множества A, то слова свойство A выполнено для почти всех элементов множества A означают, что свойство A выполнено для всех, кроме, быть может, конечного подмножества элементов множества A.

Пусть X множество. Любое подмножество A множества X определяет отображение

биективно, в связи с чем множество подмножеств множества X обозначают через 2X .

Для последовательности {An} подмножеств множества X можно различными способами определить предел, который тоже будет подмножеством в X. Перечислим эти способы.

• Для последовательности подмножеств {An} такой, что

A1 A2 A3 . . .

кратко это записывают формулой An ↑ A.

• Для последовательности подмножеств {An} такой, что

A1 A2 A3 . . .

ее убывающим пределом называют подмножество

∩

A = An;

n>1

кратко это записывают формулой An ↓ A.

• Нижним пределом последовательности {An} называют подмножество

(∩ )

•Если верхний и нижний пределы последовательности {An} равны (скажем, подмножеству A), то говорят, что последовательность {An} сходится к A и пишут

An −→ A èëè lim An = A.

n→∞

Для всякой последовательности {fn} функций на произвольном множестве X определены следующие функции.

Заметим, что эти функции могут принимать значения −∞ è +∞. Кроме того, для последовательности {fn} функций на произвольном множестве X определены понятия равномерной

èпоточечной сходимости.

•Говорят, что последовательность {fn} функций на X поточечно сходится к функции f и пишут

fn −→ f,

если для любого x X и любого ε > 0 существует N такое, что для любого n > N

выполнено

|fn(x) − f(x)| < ε.

•Говорят, что последовательность {fn} функций на X равномерно сходится к функции f и пишут

fn f,

если для любого ε > 0 существует N такое, что для любого n > N выполнено

|fn(x) − f(x)| < ε для любого x X.

Ясно, что если последовательность функций равномерно сходится к некоторой функции, то она сходится к этой функции поточечно.

Пример 1.1.1. Последовательность функций {fn(t) = tn} на отрезке [0, 1] поточечно схо-

Равномерно эта последовательность не сходится ни к одной функции.

Мощности множеств.

Для всякого конечного множества X естественным образом определено число элементов в нем, которое называют мощностью множества X и обозначают через |X|. Оказывается,

мощность можно определить для всякого, не обязательно конечного, множества. При этом мощности множеств можно сравнивать. А именно, если X è Y произвольные множества,

òî

•говорят, что X è Y имеют одинаковую мощность, и пишут |X| = |Y |, если существует биективное отображение φ : X → Y ;

•говорят, что мощность множества X не больше мощности множества Y и пишут |X| 6 |Y |, если существует инъективное отображение φ : X → Y .

•говорят, что мощность множества X строго меньше мощности множества Y и пишут

|X| < |Y |, åñëè |X| 6 |Y | è |X| ≠ |Y |.

Нетрудно заметить, что если существует сюръективное отображение φ : X → Y , òî |X| > |Y |. Действительно, из сюръективности φ следует, что для любого y Y существует xy X такой, что φ(xy) = y; тогда отображение

ψ : Y → X, ψ(y) = xy

инъективно и, следовательно, |X| > |Y |.

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

Теорема 1.1.2. (1) Для любых множеств X è Y выполнено или |X| > |Y | èëè |X| = |Y | èëè |X| < |Y | (другими словами, любые два множества можно сравнить по

мощности);

(2) Для любых множеств X è Y , åñëè |X| > |Y | è |X| 6 |Y |, òî |X| = |Y | (другими словами, если мощность X не меньше мощности Y и мощность Y не меньше мощности X, òî X è Y имеют одинаковые мощности);

(3)Для любых множеств X, Y è Z, åñëè |X| > |Y | è |Y | > |Z|, òî |X| > |Z| (другими словами, если мощность X не меньше мощности Y , а мощность Y не меньше мощности Z, то мощность X не меньше мощности Z).

Множество X называют счетным, если |X| = |N|.

Казалось бы, мощность множества N натуральных чисел примерно в два раза меньше мощности множества Z целых чисел. Однако на самом деле эти множества имеют одинаковые

−

взаимно однозначно и, следовательно, |N| = |Z|.

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

•подмножество счетного множества не более чем счетно;

•объединение не более чем счетного множества множеств, каждое из которых не более чем счетно, является не более чем счетным множеством;

•конечное произведение множеств, каждое из которых не более чем счетно, является не более чем счетным множеством;

•множество рациональных чисел счетно.

Говорят, что множество X имеет мощность континуум, если |X| = |R|. Заметим, что отображение

взаимно однозначно и, следовательно, |(−1, 1)| = |R|. Можно доказать, что

•объединение не более чем счетного множества и множества, имеющего мощность континуум, имеет мощность континуум;

•не более чем счетное объединение множеств, имеющих мощность континуум, имеет мощность континуум;

•произведение непустого не более чем счетного множества и множества, имеющего мощность континуум, имеет мощность континуум;

•не более чем счетное произведение множеств, имеющих мощность континуум, имеет мощность континуум.

Следующая теорема и ее доказательство один из красивейших фрагментов современной математики.

Теорема 1.1.3. |N| < |R|.

Доказательство. Отображение

N → R, n 7→n

инъективно и, следовательно, |N| 6 |R|.

Осталось доказать, что |N| ≠ |R|. Мы докажем это от противного, то есть допустим, что |N| = |R| и получим противоречие. Условие |N| = |R| означает, что существует биективное отображение φ : N → R. Возьмем отрезок [a0, b0] = [0, 1], разделим его на три равные отрезка и возьмем тот, который не содержит точку φ(1); обозначим этот отрезок через [a1, b1]. Отрезок [a1, b1] разделим на три равные отрезка и возьмем тот, который не содержит точку φ(2); обозначим этот отрезок через [a2, b2]. И так далее. По лемме о вложенных отрезках их

пересечение

∩∞

[ai, bi]

i=1

непусто и, следовательно, существует точка (обозначим ее через x), принадлежащая этому

пересечению. Нетрудно заметить, что x ≠ φ(i) для любого i и, следовательно, x / Im(φ). В частности, отображение φ не взаимно однозначно. Противоречие.

В 1877 году Г.Кантором была высказана знаменитая

Континуум гипотеза. Любое бесконечное подмножество в R или сч¼тно или имеет

мощность континуум.

В дальнейшем К.Гедель и П.Д.Коэн доказали, что если система аксиом ZFC непротиворечива, то на ее основе невозможно ни доказать континуум гипотезу, ни опровергнуть ее.

Теорема 1.1.4. Для всякого множества X имеем: |X| < |2X | (другими словами, мощность множества строго меньше мощности множества подмножеств этого множества).

Доказательство. Имеем инъективное отображение

Замечание 1.1.5. Из теоремы 1.1.4 следует, что объединение U всех элементов, которые можно определить в математике, не является множеством. Действительно, если U множество, то, с одной стороны, по определению, имеем 2U U, а с другой стороны, по теореме 1.1.4, имеем |2U| > |U|. Заметим, что существуют теории множеств в которых U является множеством (в этих теориях U называют универсальным множеством ).

нарное отношение R, если определены пары элементов множества X, которые находятся в отношении R. При этом то, что элементы x, y находятся в бинарном отношении R записывают формулой xRy.

Пример 1.2.2. Всякое отображение f : X → X определяет бинарное отношение R при котором xRy тогда и только тогда, когда y = f(x).

Бинарные отношения являются очень общими структурами на множествах. В теории и приложениях почти всегда имеют дело с частными случаями бинарных отношений: отношениями эквивалентности, отношениями частичного (полного) порядка, отношениями предпо- чтения. В этом параграфе мы рассмотрим эти бинарные отношения.

Отношения эквивалентности.

Часто бывает так, что в множестве необходимо отождествить некоторые элементы. Чтобы это сделать используют отношения эквивалентности.

Определение 1.2.3. Пусть X множество. Отношение эквивалентности на X это бинарное отношение , удовлетворяющее следующим аксиомам

(1)x x;

(2)åñëè x x′, òî x′ x;

(3)åñëè x x′ è x′ x′′, òî x x′′.

Пусть есть отношение эквивалентности на множестве X. Разобъем множество X на классы эквивалентности по правилу: элементы x, x′ X лежат в одном классе эквивалент- ности тогда и только тогда, когда x x′. Из свойств (1) - (3) отношения эквивалентности вытекает, что такое разбиение определено корректно и X является дизъюнктным объедине-

нием классов эквивалентности. Множество классов эквивалентности называют фактормножеством множества X по отношению эквивалентности и обозначают через X/ . Åñòå-

ственным образом определено отображение множеств

X → X/ , x 7→класс эквивалентности, содержащий x.

На интуитивном уровне фактормножество X/ состоит из элементов множества X опреде-

ленных с точностью до эквивалентности.

Математика изучает множества со структурами. Для того, чтобы задать множество со структурой необходимо задать множество и структуру на этом множестве, то есть, операции, которые можно производить над элементами этого множества и аксиомы, которым удовлетворяют эти операции. Некоторые множества со структурами интуитивно очевидны. Поэтому с ними работают на интуитивном уровне, а не на основе аксиом. Например, с натуральными числами работают на интуитивном уровне, а не на основе аксиом Пеано натуральных чисел. Более абстрактные множества со структурами интуитивно неочевидны. Поэтому с ними с самого начала работают на уровне аксиом. Например, в линейной алгебре теорию векторных пространств с самого начала развивают на основе восьми аксиом.

Важным обстоятельством является то, что, грубо говоря, если на множестве X имеется некоторая структура и отношение эквивалентности как то согласовано с этой

структурой, то на фактормножестве естественным образом определена "аналогичная" структура. Приведем два примера.

Пример 1.2.4. Фиксируем натуральное число n и на множестве Z целых чисел рассмотрим отношение эквивалентности при котором

a b a − b делится на n.

Классы эквивалентности это n подмножеств

a := a + nZ, a = 0, 1, . . . , n − 1

и, таким образом, фактормножеством является

Z/ = {0, 1, . . . , n − 1},

которое называют кольцом вычетов по модулю n и обозначают через через Zn. Элементы множества Z можно складывать и отношение эквивалентности согласовано со сложением

в том смысле, что

a b, a′ b′ = a + a′ b + b′.

Это позволяет определить сложение элементов множества Zn:

a + b = c, ãäå c = вычет по модулю n числа a + b.

Кроме того, элементы множества Z можно умножать и отношение эквивалентности согласовано с умножением в том смысле, что

a b, a′ b′ = a · a′ b · b′.

Это позволяет определить умножение элементов множества Zn:

a · b = c, ãäå c = вычет по модулю n числа a · b.

Например, в Z5 имеем:

3 + 4 = 2, 2 + 3 = 0, 3 · 4 = 2, 2 · 3 = 1.

Пример 1.2.5. Пусть V является векторным пространством (вещественным или комплексным) и L V подпространство. Определим следующее отношение эквивалентности на V :

v v′ v − v′ L.

Классами эквивалентности являются подмножества вида

v + L, ãäå v V .

Сложение векторов и умножение векторов на числа согласовано с этим отношением эквивалентности, то есть

Это позволяет определить сложение классов и умножение классов на числа, а именно,

(v + L) + (u + L) = (v + u) + L,

λ(v + L) = λv + L.

Нетрудно проверить, что V/L является векторным пространством; его называют факторпространством пространства V по подпространству L. На интуитивном уровне, векторы факторпространства V/L это векторы пространства V с точностью до прибавления векторов из подпространства L.

Отношения порядка.

Пусть X множество. Отношение частичного порядка на X это бинарное отношение 6 , удовлетворяющее следующим аксиомам

•x 6 x для любого x X;

•åñëè x 6 y è y 6 z, òî x 6 z;

•åñëè x 6 y è y 6 x, òî x = y.

Множество X, на котором задано отношение частичного порядка, называют частично упорядоченным. Для частично упорядоченного множества определим бинарное отношение < следующим образом:

x < y x 6 y è x ≠ y.

Элементы x, y частично упорядоченного множества называт сравнимыми, если выполнено или x < y èëè x > y èëè x = y. Частично упорядоченное множество X называют вполне

упорядоченным, а соответствующее отношение порядка называют полным, если любые два элемента множества X сравнимы.

Пример 1.2.6. На множестве натуральных чисел N определим следующее отношение

порядка:

x 6 y x меньше либо равно y.

Ясно, что это отношение порядка является полным.

Пример 1.2.7. На множестве натуральных чисел N определим следующее отношение

порядка:

x 6 y x делит y.

Это отношение порядка не является полным так как, например, 4 и 6 несравнимы.

Отношения частичных порядков на множествах X1, . . . , Xn порождают лексикографиче- ское отношение частичного порядка на их прозведении

x1 = y1, . . . , xn−1 = yn−1, xn < yn

Несложно проверить, что лексикографическое отношение порядка на произведении X1 ×

. . . × Xn является полным тогда и только тогда, когда полными являются порождающие его отношения порядков на X1, . . . , Xn.

Отношения предпочтения.

Определение 1.2.8. Бинарное отношение 4 на множестве X называют отношением предпочтения, если оно удовлетворяет следующим аксиомам:

(1)x 4 x для любого x X;

(2)åñëè x 4 y è y 4 z, òî x 4 z;

(3) для любых x, y X выполнено или x 4 y èëè y 4 x или одновременно x 4 y è y 4 x

.

Всякое отношение предпочтения 4 на множестве X определяет отношение эквивалентности на том же множестве X, а именно,

x y x 4 y è x < y

Пример 1.2.9. Вещественнозначная функция u на множестве X определяет отношение предпочтения 4 на X при котором

x 4 y u(x) 6 u(y).

Однако не верно, что на любом множестве всякое отношение предпочтения определяется вещественнозначной функцией.

1.3. Аксиома выбора

Одной из аксиом системы ZFC является

Аксиома выбора. Пусть {Ai}i I множество непустых множеств. Тогда существует

такое, что f(i) Ai (другими словами, одновременно для всех i I можно выбрать элемент f(i) Ai).

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

Единичную сферу в трехмерном евклидовом пространстве можно предствавить как объединение конечного множества непересекающихся подмножеств так, что из этих подмножеств, параллельно перенося и поворачивая их, можно составить две единичные сферы.

Несмотря на следствия типа парадокса Банаха-Тарского, аксиома выбора принята в математике. При этом используют не саму аксиому выбора, а доказываемую на ее основе лемму Цорна, которую мы сейчас сформулируем.

Сначала дадим определения, которые необходимы для понимания формулировки леммы

Цорна.

Пусть (X, > ) - частично упорядоченное множество. Подмножество Y частично упоря-

доченного множества X называется вполне упорядоченным, если ограничение на Y частич- ного порядка > является полным порядком на Y . Элемент xmax частично упорядоченного

множества X называется максимальным, если не существует x X такого, что x > xmax.

Например, в частично упорядоченных множествах из примеров 1.2.6 и 1.2.7 не существует максимальных элементов.

Теперь мы готовы сформулировать лемму Цорна.

Лемма 1.3.1 (Лемма Цорна). Пусть (X, > ) - частично упорядоченное множество,

причем для каждого вполне упорядоченного подмножества Y X существует xY X такой, что xY > y äëÿ âñåõ y Y . Тогда в X существует максимальный элемент xmax.

Приведем типичный пример применения леммы Цорна.

Сначала дадим некоторые определения. Пусть V векторное пространство (не обязательно конечномерное). Системой векторов в векторном пространстве V называют любое вполне

упорядоченное множество векторов. Конечную систему векторов называют линейно независимой, если между векторами этой системы нет нетривиальных соотношений линейной зависимости. Систему векторов (не обязательно конечную) называют линейно независимой, если всякая ее конечная подсистема линейно независима. Базисом Гамеля векторного пространства V называют линейно независимую систему векторов {vi}i I

вектора v V существует разложение

∑

v = civi,

i I

где почти все коэффициенты ci равны нулю (из линейной независимости следует, что такое

разложение единственно). Ясно, что в конечномерных пространствах базисы Гамеля это обычные базисы, определяемые в линейной алгебре.

Лемма 1.3.2. Во всяком (не обязательно конечномерном) векторном пространстве существует базис Гамеля.

Доказательство. Рассмотрим множество X линейно независимых (не обязательно конечных) систем векторов в пространстве V . Будем говорить, что система векторов e является