КИТ ДЕВЛИН: Приложение "Введение в математическое мышление"
Элементы теории множеств
НЕ ТРЕБУЕТСЯ ДО БОЛЕЕ ПОЗДНЕГО ЭТАПА КУРСА
В последующих частях этого курса предполагается, что вы (студент) знакомы с базовой теорией множеств. В этом кратком документе кратко изложено, что требуется. Хотя вам не понадобится этот материал, пока вы не углубитесь в курс (когда вы познакомитесь с различными понятиями и терминами, используемыми в этом кратком изложении), вероятно, будет хорошей идеей просмотреть приложение в начале курса, чтобы получить общий обзор, а затем просмотреть его как и когда вам это нужно. (В частности, выполнение многих упражнений в этом кратком изложении предполагает материал, который будет рассмотрен в первой части курса, поэтому вы можете быть не в состоянии выполнить их. Это не должно быть проблемой. К тому времени, когда вам понадобятся знания теории множеств, в последнюю неделю лекций, вы должны быть в состоянии выполнить все упражнения.)
Концепция множества чрезвычайно проста и пронизывает всю современную математическую мысль. Любая четко определенная коллекция объектов является набором. Например, у нас есть:
- набор всех учеников в вашем классе
- множество всех простых чисел
- набор, единственным членом которого являетесь вы.
Что требуется для определения набора, - это какой-то способ определения коллекции.
Допускаются произвольные наборы, где нет определяющего свойства.)
Если A является множеством, то объекты в коллекции A называются либо членами A, либо элементами A. Мы пишем
x ∈ A
для обозначения того , что x является элементом A.
Некоторые множества часто встречаются в математике, и для них удобно использовать стандартные обозначения:
N : множество всех натуральных чисел (т.Е. чисел 1, 2, 3 и т.д.) ноль не участвует 0.
Z : множество всех целых чисел (0 и все положительные и отрицательные целые числа).
- : множество всех рациональных чисел (дробей)
- : множество всех действительных чисел
Таким образом, например,
x ∈ R
означает, что x - действительное число. И
(x ∈ Q) ∧ (x> 0)
означает, что x - положительное рациональное число.
Существует несколько способов задания набора. Если в нем есть небольшое количество элементов, мы можем перечислить их. В этом случае мы обозначаем множество, заключая список элементов в фигурные скобки; так, например,
{1,2,3,4,5}
обозначает множество, состоящее из натуральных чисел 1, 2, 3, 4 и 5.
Используя ‘точки’, мы можем распространить это обозначение на любое конечное множество; например
{1,2,3,...,n}
обозначает множество первых n натуральных чисел. Снова
{2,3,5,7,11,13,17,...,53}
может (при правильном контексте) использоваться для обозначения набора всех простых чисел до 53.
Некоторые бесконечные множества также могут быть описаны с помощью точек (только теперь точки не имеют конца), например
{2,4,6,8,...,2n,...}
обозначает множество всех четных натуральных чисел. Снова,
{...,−8,−6,−4,−2,0,2,4,6,8,...}
обозначает множество всех четных целых чисел.
Однако в целом, за исключением конечных множеств с небольшим числом элементов, множества лучше всего описываются с помощью свойства, которое определяет множество. Если A(x) является некоторым свойством, то множество всех тех x, которые удовлетворяют A(x), обозначается как
{x |A(x)}
Или, если мы хотим ограничить x теми, которые являются членами определенного множества X, мы бы написали
{x ∈ X | A(x)}
Это читается как “множество всех x в X такое, что A(x)”. Например:
Два множества, A, B равны, записываются A = B, если они имеют точно такие же элементы. Как показывает приведенный выше пример, равенство множеств не означает, что они имеют идентичные определения; часто существует много разных способов описания одного и того же множества. Определение равенства скорее отражает тот факт, что множество - это просто набор объектов.
Если нам нужно доказать, что множества A и B равны, мы обычно разбиваем доказательство на две части:
(a) Покажите, что каждый член A является членом B. (b) Покажите, что каждый член B является членом A.
Взятые вместе, (a) и (b) явно подразумевают A = B. (Доказательство обоих (a) и (b) обычно имеет вид ‘взять произвольный элемент’. Например, чтобы доказать (a), мы должны доказать (∀x ∈ A)(x ∈ B); поэтому мы берем произвольный элемент x из A и показываем, что x должен быть элементом B.)
Введенные обозначения набора имеют очевидные расширения. Например, мы можем написать
Q = {m/n | m, n ∈ Z, n ≠ 0}
и так далее.
В математике удобно ввести множество, не имеющее элементов: пустое множество (или нулевое множество). Конечно, будет только один такой набор, поскольку любые два таких набора будут иметь точно такие же элементы и, следовательно, будут (по определению) равны. Пустое множество обозначается скандинавской буквой
∅
[Обратите внимание, что это не греческая буква φ.] Пустой набор может быть задан многими способами; например,
∅={x ∈ R | x 2 < 0}
∅={x ∈ N | 1 < x < 2}
∅={x | x ≠ x}
Обратите внимание, что ∅ и {∅} - это совершенно разные множества. ∅ - пустое множество: оно имеет НЕТ Участники. {∅} - это множество, которое имеет один Участник. Следовательно
∅ = {∅}
Дело здесь в том, что
∅ ∈ {∅}
(Тот факт, что единственный элемент {∅} является пустым множеством, в этой связи не имеет значения: {∅} имеет элемент, ∅ нет.)
Множество A называется подмножеством множества B, если каждый элемент A является членом B. Например, {1,2} является подмножеством {1,2,3}. Мы пишем
A ⊆ B
чтобы означать , что A является подмножеством B. Если мы хотим подчеркнуть, что A и B здесь неравны, мы пишем
A ⊂ B
и скажем, что A является собственным подмножеством B (это использование сравнивается с отношениями упорядочения ≤ и < на R.) Очевидно, что для любых множеств A,B мы имеем
A = B, если (A ⊆ B) ∧ (B ⊆ A)
Упражнения 1
- Что это за хорошо известный набор:
{n ∈ N | (n > 1) ∧ (∀x,y ∈ N)[(xy = n) ⇒ (x = 1 ∨ y = 1)]}
- Пусть
P = {x ∈ R | sin(x) = 0} , Q = {nn | n ∈ Z}
Какова связь между P и Q ?
- Пусть
A = {x ∈ R | (x> 0) ∧ (x2 = 3)}
Дайте более простое определение множества A.
- Докажите, что для любого множества A:
∅ ⊆ A и A ⊆ A
- Докажите, что если A ⊆ B и B ⊆ C, то A ⊆ C
- Перечислите все подмножества множества {1,2,3,4}.
- Перечислите все подмножества множества {1,2,3,{1,2}}.
- Пусть A = {x|P(x)},B = {x| Q(x)}, где P,Q - такие формулы, что ∀x[P(x) ⇒ Q(x)]. Докажите , что A ⊆ B.
- Докажите (по индукции), что множество с ровно n элементами имеет 2 n подмножеств.
- Пусть
A = {o,t,f, s,e,n}
Дайте альтернативное определение множества A. (Подсказка: это связано с N, но не является полностью математическим.)
Существуют различные естественные операции, которые мы можем выполнять на множествах. (Они примерно соответствуют сложению, умножению и отрицанию целых чисел.)
Учитывая два множества A, B, мы можем сформировать множество всех объектов, которые являются членами любого из A и B. Это множество называется объединением A и B и обозначается
A ∪ B
Формально этот набор имеет определение
A ∪ B = {x | (x ∈ A) ∨ (x ∈ B)}
(Обратите внимание, насколько это согласуется с нашим решением использовать слово ‘или’ для обозначения инклюзивного-или.)
Пересечение множеств A,B - это множество всех членов, которые A и B имеют общие. Это обозначается
A ∩ B
и имеет формальное определение
A ∩ B = {x | (x ∈ A) ∧ (x ∈ B)}
Два множества A,B называются непересекающимися, если у них нет общих элементов, то есть если A ∩ B = ∅.
Теоретико-множественный аналог отрицания требует понятия универсального множества. Часто, когда мы имеем дело с наборами, все они состоят из объектов одного и того же вида. Например, в теории чисел мы можем сосредоточиться на множествах натуральных чисел или множествах рациональных чисел; в реальном анализе мы обычно фокусируемся на множествах действительных чисел. Универсальный набор для конкретного обсуждения - это просто набор всех объектов рассматриваемого вида. Часто это область, в которой варьируются квантификаторы.
Как только мы определили универсальный набор, мы можем ввести понятие дополнения множества A. Относительно универсального множества U дополнением множества A является множество всех элементов U, которых нет в A. Этот набор обозначается символом 0 и имеет формальное определение
A0 = {x ∈ U | x ∉ A}
[Обратите внимание, что для краткости мы пишем x ∉ A вместо (x ∈ A).]
Например, если универсальным множеством является множество N натуральных чисел, а E - множество четных (натуральных) чисел, то E0 - это множество нечетных (натуральных) чисел.
Следующая теорема суммирует основные факты о трех только что рассмотренных операциях с множествами.
Теорема Пусть A,B,C - подмножества универсального множества U.
- A ∪ (B ∪ C) = (A ∪ B) ∪ C
- A ∩ (B ∩ C) = (A ∩ B) ∩ C
((1) и (2) являются ассоциативными законами)
- A ∪ B = B ∪ A
- A ∩ B = B ∩ A
((3) и (4) являются коммутативными законами)
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
((5) и (6) являются законами распределения)
- (A ∪ B)0 = A 0 ∩ B 0
- (A ∩ B)0 = A 0 ∪ B 0
((7) и (8) называются законами Де Моргана)
- A ∪ A 0 = U
- A ∩ A 0 = ∅
((9) и (10) являются законами дополнения)
- (A 0)0 = A
(закон самоинверсии)
Доказательство: Оставлено в качестве упражнения.
Упражнения 2
- Докажите все части приведенной выше теоремы.
- Найдите ресурс, который объясняет диаграммы Венна, и используйте их, чтобы проиллюстрировать и помочь вам понять приведенную выше теорему.
0 Обратите внимание, что в этом курсе 0 не рассматривается как натуральное число. Эта проблема может вызвать путаницу, поскольку некоторые авторы включают 0 в число натуральных чисел.