Понятие множество

Множество
Понятие «множество» относится к базовым неопределяемым научным понятиям.
Множество может состоять из любых различимых объектов.
Множество однозначно определяется набором составляющих его объектов.
Любое свойство определяет множество объектов, которые этим свойствам обладают.

Элементы множества
A = { x | P(x) } – эта запись означает, что множество A состоит из всех объектов, которые обладают свойством P.
Объекты, составляющие множество, называются его элементами.
Если x – элемент множества A, то говорят «x принадлежит A» и пишут «x ∈ A».
Иначе говорят «x не принадлежит A» и пишут «x ∉ A».

Отношения множеств
Если множества A и B состоят из одних и тех же элементов, то эти множества равны. В этом случае пишут «A = B».
Если любой элемент множества A является элементом множества B, то говорят «A лежит в B» или «B включает в себя A» и пишут «A ⊂ B». В этом случае A называется подмножеством множества B.
Если A ⊂ B, но A ≠ B, то говорят, что включение строгое. В этом случае A называется собственным подмножеством B.
Если A лежит в B или совпадает с ним, то пишут «A ⊆ B».

Отношения множеств
Если множества A и B состоят из одних и тех же элементов, то эти множества равны. В этом случае пишут «A = B».
Если любой элемент множества A является элементом множества B, то говорят «A лежит в B» или «B включает в себя A» и пишут «A ⊂ B». В этом случае A называется подмножеством множества B.
Если A ⊂ B, но A ≠ B, то говорят, что включение строгое. В этом случае A называется собственным подмножеством B.
Если A лежит в B или совпадает с ним, то пишут «A ⊆ B».

Отношения множеств
Т.о. A = B <=> A ⊂ B и B ⊂ A.
Обозначение «<=>» или «⬄» читается «тогда и только тогда, когда» или «в том и только в том случае, если».
Множество, не содержащее в себе элементов, называется пустым множеством и обозначается ∅.

Операции над множествами
Объединением множеств A и B называется множество AUB, состоящее из тех и только тех элементов, которые содержатся хотя бы в одном из множеств A или B.
AUB = { x | x ∈ A или x ∈ B }
Пример: A = {1, 2, 3, 4, 5}, B = {4, 5, 6}.
Тогда AUB = {1, 2, 3, 4, 5, 6}.

Операции над множествами
Пересечением множеств A и B называется множество A∩B, состоящее из тех и только тех элементов, которые содержатся одновременно в множествах A и B.
A∩B = { x | x ∈ A и x ∈ B }
Пример: A = {1, 2, 3, 4, 5}, B = {4, 5, 6}.
Тогда A∩B = {4, 5}.

Операции над множествами
Разностью между множеством A и множеством B называется множество A\B, состоящее из тех элементов множества A, которые не содержатся в множестве B.
A\B = { x | x ∈ A и x ∉ B }
Если B ⊂ A, то A\B называется дополнением множества B в множестве A.
Пример: A = {1, 2, 3, 4, 5}, B = {4, 5, 6}.
Тогда A\B = {1, 2, 3}.
B\A = {6}.

Операции над множествами
Симметрической разностью множеств A и B называется множество AΔB, состоящее из тех элементов, которые содержатся только в множестве A или только в множестве B.
AΔB = { x | (x ∈ A и x ∉ B) или (x ∈ B и x ∉ A) }
AΔB = (A\B)U(B\A) = (AUB)\(A∩B)
Пример: A = {1, 2, 3, 4, 5}, B = {4, 5, 6}.
Тогда AΔB = {1, 2, 3, 6}.

Операции над множествами
Декартовым произведением множеств A и B называется множество A×B, состоящее из упорядоченных пар элементов, первый член которых есть элемент из множества A, а второй – элемент из множества B.
A×B = { (x,y) | x ∈ A, y ∈ B }
Множество A×A = A2 называется декартовым квадратом.
Пример: A = {1, 2, 3}, B = {4, 5, 6}.
Тогда A×B = {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)}.
Тогда B×A = {(4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (6,1), (6,2), (6,3)}.

Свойства операций над множествами
AUB = BUA (коммутативность)
A∩B = B∩A (коммутативность)
(AUB)UC = AU(BUC) (ассоциативность)
(A∩B)∩C = A∩(B∩C) (ассоциативность)
(AUB)∩C = (A∩С)U(B∩C) (дистрибутивность)
(A∩B)UC = (AUС)∩(BUC) (дистрибутивность)
A\(BUC) = (A\B)∩(A\C) (закон де Моргана)
A\(B∩C) = (A\B)U(A\C) (закон де Моргана)

Свойства операций над множествами
AUA = A
A∩A = A
A\A = ∅
AΔA = ∅
AU∅ = A
A∩∅ = ∅
A\∅ = A
AΔ∅ = A

Свойства операций над множествами
Если A ⊂ B, то:
AUB = B
A∩B = A
A\B = ∅
AΔB = B\A

Свойства операций над множествами
A×B = ∅ ⬄ A = ∅ и B = ∅
Если A×B ≠ ∅, то:
A×B ⊂ С×D ⬄ A ⊂ C и B ⊂ D
(A×B)U(С×B) = (AUС)×B
(A×B)∩(С×D) ⬄ (A∩C)×(B∩D)

Счетные множества
Утверждение 1: Бесконечное подмножество счетного множества счетно.
Утверждение 2: Объединение конечного или счетного числа счетных множеств счетно.
Если множество конечно или счетно, то говорят, что оно не более чем счетно.
Таким образом, не более чем счетное объединение не более чем счетных множеств не более чем счетно.

Счетные множества
Утверждение: |ℤ| = |ℕ|.
ℤ = {0, 1, –1, 2, –2, 3, –3, …}
Утверждение: |ℚ| = |ℕ|.
Любое рациональное число можно представить в виде m/n, где m ∈ ℤ, n ∈ ℕ и НОД(m, n) = 1.
Можно упорядочить все рациональные число по возрастанию величины |m|+n. А числа, для которых эта величина равна, можно упорядочить по возрастанию m.

Счетные множества
1: 0 = 0/1
2: –1 = – 1/1, 1 = 1/1
3: –2, –1/2, 1/2, 2
4: –3, –1/3, 1/3, 3
5: –4, –3/2, –2/3, 2/3, 3/2, 4
…
Таким образом, можно пронумеровать все рациональные числа.

Несчетные множества
Теорема Кантора: |ℝ| > |ℕ|.
Мощность множества действительных чисел называется мощностью континуума.
Теорема: |ℝ| = |(0, 1)|.

Принцип математической индукции
Числовое множество X называется индуктивным, если ∀ x ∈ X x+1 ∈ X.
Таким образом, ℕ – наименьшее индуктивное множество, содержащее 1.
Принцип математической индукции: Если подмножество E ⊂ ℕ таково, что 1 ∈ E и ∀ x ∈ E x+1 ∈ E, то E = ℕ.
Этот принцип используется для доказательства гипотез о натуральных числах.

Принцип математической индукции
База индукции: Доказываем, что гипотеза верна при некотором начальном n (как правило, n = 1).
Предположение индукции: Предполагаем, что гипотеза верна при некотором k ∈ ℕ.
Шаг индукции: Доказываем, что гипотеза верна при k+1.
Таким образом, мы получаем, что гипотеза верна ∀ n ∈ ℕ.

Эквивалентность
Множества A и B называются эквивалентными, если существует биективное отображение f: A → B.
Обозначение: A ~ B
Отношение эквивалентности обладает следующими свойствами:
Рефлексивность: A ~ A.
Симметричность: A ~ B ⇒ B ~ A
Транзитивность: A ~ B, B ~ C ⇒ A ~ C.
Любое отношение, обладающее этими свойствами, можно назвать эквивалентностью.

Композиция
Пусть f: X → Y, g: Y → Z – функции. Композицией этих функций называется функция g◦f = g(f(x)). Функция g◦f осуществляет отображение X → Z.
Пример: f(x) = x2, g(x) = sin x.
Тогда g◦f = sin x2.
f◦g = sin2 x.
Таким образом, видно, что операция композиции не коммутативна: f◦g ≠ g◦f.

Композиция
Проверим ассоциативность композиции на примере: f(x) = x2, g(x) = sin x, h(x) = 1/x.
(f◦g)◦h = (sin2 x)◦h = sin2 (1/x).
f◦(g◦h) = f◦(sin 1/x) = sin2 (1/x).
Таким образом, операция композиции ассоциативна.
В множестве всех функций существует тождественное отображение – это отображение id(x), удовлетворяющее свойству: f◦id = id◦f = f ∀f.
Это отображение id(x) = x.

Обратная функция
Функция f–1:Y → X называется обратной к функции f: X → Y, если f◦f–1 = f–1◦f = id.
Примеры: f(x) = sin x, g(x) = 2x, h(x) = 1/x, id(x) = x.
f–1(x) = arcsin x, g–1(x) = log2x, h–1(x) = 1/x, id–1(x) = x.