Теория множеств. Основные понятия
Теория множеств является основополагающим определением современной математики. Она была создана Георгом Кантором в 1860-х гг. Он писал: «Множество есть многое, мыслимое как единое целое». Понятие множества принадлежит к числу основных, неопределяемых понятий математики. Оно не сводится к другим, более простым понятиям. Поэтому его нельзя определить, а можно лишь пояснить. Таким образом, множество – объединение в одно целое объектов, хорошо различимых нашей интуицией или нашей мыслью; совокупность некоторых объектов, определенных общим признаком.
Например,
1. Множество жителей г. Воронежа
2. Множество точек плоскости
3. Множество натуральных чисел ℕи др.
Множества обычно обозначаются большими латинскими буквами(A, B, C и т.д.). Объекты, составляющие данное множество, называются его элементами. Элементы множества обозначаются малыми латинскими буквами(a, b, c и т.д.). Если Х – множество, то запись х∈Х означает, что х есть элемент множества Х или что х принадлежит множеству Х , а запись х∉Х , что элемент х не принадлежит множеству Х . Например, пусть ℕ–множество натуральных чисел. Тогда 5 ℕ , а 0,5∉ℕ .
Если множество Y состоит из элементов множества Х , то говорят, что Y является подмножеством множества Х и обозначают Y⊂Х (или Y⊆Х ). Например, множество целых чисел ℤ является подмножеством рациональных чисел ℚ .
Если для двух множеств Х и Y одновременно имеют место два включения Х Y и Y Х , т.е. Х есть подмножество множества Y и Y есть подмножество множества Х , то множества Х и Y состоят из одних и тех же элементов. Такие множества Х и Y называют равными и пишут: Х=Y .
Часто используется термин пустое множество - Ø - множество, не содержащее ни одного элемента. Оно является подмножеством любого множества.
Для описания множеств могут использоваться следующие способы.
Способы задания множеств
1. Перечисление объектов. Используется только для конечных множеств.
Например, Х={x1, x2, x3… x n } . Запись Y={1, 4, 7, 5} означает, что множество состоит из четырех чисел 1, 4, 7, 5 .
2. Указание характеристического свойства элементов множества.
Для этого задается некоторое свойство Р , позволяющее определить принадлежность элемента множеству. Этот способ является более универсальным.
Х={х: Р(х)}
(множество Х состоит их таких элементов х , для которых выполняется свойство Р (х) ).
Пустое множество можно задать, указав его свойства: Ø={х: х≠х}
Построить новые множества можно с помощью уже заданных, используя операции над множествами.
Операции над множествами
1. Объединением(суммой) называется множество, состоящее из всех тех элементов, каждый из которых принадлежит хотя бы одному из множеств А или В .
А∪ В={х: х А или х В}.
2. Пересечением(произведением) называется множество, состоящее из всех элементов, каждый из которых одновременно принадлежит как множеству А , так и множеству В .
А∩В={х: х А и х В}.
3. Разностью множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В .
А\В={х: х А и х В}
4. Если А – подмножество множества В . То множество В\А называют дополнением множества А до множества В и обозначают А’ .
5. Симметрической разностью двух множеств называют множество А∆В=(А\В) (В\А)
N
- множество всех натуральных чисел;
Z
- множество всех целых чисел;
Q
- множество всех рациональных чисел;
R
- множество всех действительных чисел;
C
- множество всех комплексных чисел;
Z 0
- множество всех неотрицательных целых чисел.
Свойства операций над множествами:
1. А В=В А (коммутативность объединения)
2. А В=В А (коммутативность пересечения)
3. А(В С)=(А В) С (ассоциативность объединения)
4. А (В С)=(А В) С (ассоциативность пересечения)
5. А (В С)=(А В) (А С) (1 закон дистрибутивности)
6. А (В С)=(А В) (А С) (2 закон дистрибутивности)
7. А Ø=А
8. А U= U
9. А Ø= Ø
10. А U=А
11. (А В)’=А’ В’ (закон де Моргана)
12. (А В)’=А’ В’ (закон де Моргана)
13. А (А В)=А (закон поглощения)
14. А (А В)=А (закон поглощения)
Докажем свойство №11. (А В)’=А’ В’
По определению равных множеств, нам необходимо доказать два включения 1) (А В)’ ⊂А’ В’ ;
2) А’ В’⊂(А В)’ .
Для доказательства первого включения, рассмотрим произвольный элемент х∈(А В)’=Х\(А∪В). Это означает, что х∈Х, х∉ А∪В . Отсюда следует, что х∉А и х∉В , поэтому х∈Х\А и х∈Х\В , а значит х∈А’∩В’ . Таким образом, (А В)’⊂А’ В’
Обратно, если х∈А’ В’ , то х одновременно принадлежит множествам А’, В’ , а значит х∉А и х∉В . Из этого следует, что х∉ А В , поэтому х∈(А В)’ . Следовательно, А’ В’⊂(А В)’ .
Итак, (А В)’=А’ В’
Множество, состоящее из двух элементов, в котором определен порядок следования элементов, называется упорядоченной парой. Для ее записи используют круглые скобки. (х 1 , х 2) – двухэлементное множество, в котором х 1 считается первым элементом, а х 2 – вторым. Пары (х 1 , х 2) и (х 2 , х 1), где х 1 ≠ х 2 , считаются различными.
Множество, состоящее из n элементов, в котором определен порядок следования элементов, называется упорядоченным набором из n элементов.
Декартово произведение – произвольное множество X 1 , X 2 ,…,X n упорядоченных наборов из n элементов, где x 1 X 1 , x 2 X 2 ,…, x n X n
Х 1 Х n
Если множества X 1 , X 2 ,…,X n совпадают(X 1 = X 2 =…=X n) , то их произведение обозначается Х n .
Например, ℝ 2 – множество упорядоченных пар вещественных чисел.
Отношения эквивалентности. Фактор-множества
По данному множеству можно строить новые множества, рассматривая множество некоторых подмножеств. При этом обычно говорят не о множестве подмножеств, а о семействе или классе подмножеств.
В ряде вопросов рассматривают класс таких подмножеств данного множества А , которые не пересекаются и объединение которых совпадает с А . Если данное множество А можно представить в виде объединения своих попарно не пересекающихся подмножеств, то принято говорить, что А разбито на классы. Разбиение на классы осуществляют на основе какого-либо признака.
Пусть Х – не пустое множество, тогда любое подмножество R из произведения Х Х называется бинарным отношением на множестве Х . Если пара (х,у) входит в R, говорят, что элемент х находится в отношении R с у .
Например, отношения х=у, х≥у являются бинарным отношениями на множестве ℝ.
Бинарное отношение R на множестве Х называется отношением эквивалентности, если:
1. (х,х) R; х Х (свойство рефлексивности)
2. (х,у) R => (у,х) R (свойство симметричности)
3. (х,у) R, (у,z) R, то (x,z) R (свойство транзитивности)
Если пара (х,у) вошла в отношения эквивалентности, то х и у называют эквивалентными(х~у).
1.Пусть ℤ – множество целых чисел, m≥1 – целое число. Зададим отношение эквивалентности R на ℤ так, чтобы n~k , если n-k делится на m . Проверим, выполняются ли свойства на данном отношении.
1. Рефлексивность.
Для любого n∈ℤ ℤ такого, что (p,p)∈R
р-р=0 . Так как 0∈ ℤ , то (p,p)∈ℤ .
2. Симметричность.
Из (n,k) ∈R следует, что существует такое р∈ ℤ , что n-k=mp ;
k-n =m(-p), -p∈ ℤ , следовательно (k,n) ∈R .
3. Транзитивность.
Из того, что (n,k) ∈R , (k,q) ∈R следует, что существуют такие р 1 и р 2 ∈ ℤ , что n-k=mp 1 и k-q=mp 2 . Сложив данные выражения, получаем, что n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ . Поэтому (n,q) ∈ ℤ .
2.Рассмотрим множество Х всех направленных отрезков пространства или плоскости. =(А, В) . Введем отношение эквивалентности R на Х .
∼ {\displaystyle \sim } . Тогда множество всех классов эквивалентности называется фактормножеством и обозначается . Разбиение множества на классы эквивалентных элементов называется его факторизацией .Отображение из X {\displaystyle X} в множество классов эквивалентности X / ∼ {\displaystyle X/\!\sim } называется факторотображением . Благодаря свойствам отношения эквивалентности, разбиение на множества единственно. Это означает, что классы, содержащие ∀ x , y ∈ X {\displaystyle \forall x,\;y\in X} , либо не пересекаются, либо совпадают полностью. Для любого элемента x ∈ X {\displaystyle x\in X} однозначно определён некоторый класс из X / ∼ {\displaystyle X/\!\sim } , иными словами существует сюръективное отображение из X {\displaystyle X} в X / ∼ {\displaystyle X/\!\sim } . Класс, содержащий x {\displaystyle x} , иногда обозначают [ x ] {\displaystyle [x]} .
Если множетво снабжено структурой, то часто отображение X → X / ∼ {\displaystyle X\to X/\!\sim } можно использовать чтобы снабдить фактормножество X / ∼ {\displaystyle X/\!\sim } той же структурой, например топологией. В этом случае множество X / ∼ {\displaystyle X/\!\sim } с индуцированной структурой называется факторпространством .
Энциклопедичный YouTube
1 / 4
✪ 3. Классы эквивалентности
✪ Теория множеств Лекция 3 Часть 1
✪ Теория множеств Лекция 3 Часть 2
✪ Теория множеств Лекция 3 Часть 3
Субтитры
Факторпространство по подпространству
Часто отношение эквивалентности вводят следующим образом. Пусть X {\displaystyle X} - линейное пространство , а L {\displaystyle L} - некоторое линейное подпространство. Тогда два элемента x , y ∈ X {\displaystyle x,\;y\in X} таких, что x − y ∈ L {\displaystyle x-y\in L} , называются эквивалентными . Это обозначается x ∼ L y {\displaystyle x\,{\overset {L}{\sim }}\,y} . Получаемое в результате факторизации пространство называют факторпространством по подпространству L {\displaystyle L} . Если X {\displaystyle X} разлагается в прямую сумму X = L ⊕ M {\displaystyle X=L\oplus M} , то существует изоморфизм из M {\displaystyle M} в X / ∼ L {\displaystyle X/\,{\overset {L}{\sim }}} . Если X {\displaystyle X} - конечномерное пространство , то факторпространство X / ∼ L {\displaystyle X/\,{\overset {L}{\sim }}} также является конечномерным и dim X / ∼ L = dim X − dim L {\displaystyle \dim X/\,{\overset {L}{\sim }}=\dim X-\dim L} .
Примеры
. Можно рассмотреть фактормножество X / ∼ {\displaystyle X/\!\sim } . Функция f {\displaystyle f} задаёт естественное взаимноднозначное соответствие между X / ∼ {\displaystyle X/\!\sim } и Y {\displaystyle Y} .Факторизацию множества разумно применять для получения нормированных пространств из полунормированных, пространств со скалярным произведением из пространств с почти скалярным произведением и пр. Для этого вводится соответственно норма класса, равная норме произвольного его элемента, и скалярное произведение классов как скалярное произведение произвольных элементов классов. В свою очередь отношение эквивалентности вводится следующим образом (например для образования нормированного факторпространства): вводится подмножество исходного полунормированного пространства, состоящее из элементов с нулевой полунормой (кстати, оно линейно, то есть является подпространством) и считается, что два элемента эквивалентны, если разность их принадлежит этому самому подпространству.
Если для факторизации линейного пространства вводится некоторое его подпространство и считается, что если разность двух элементов исходного пространства принадлежит этому подпространству, то эти элементы эквивалентны, то фактормножество является линейным пространством и называется факторпространством.
Пусть R – бинарное отношение на множестве X. Отношение R называется рефлексивным , если (x, x) Î R для всех x Î X; симметричным – если из (x, y) Î R следует (y, x) Î R; транзитивным числу 23 соответствует вариант 24 если (x, y) Î R и (y, z) Î R влекут (x, z) Î R.
Пример 1
Будем говорить, что x Î X имеет общее
с элементом y Î X, если множество
x Ç y не пусто. Отношение иметь общее будет рефлексивным и симметричным, но не транзитивным.
Отношением эквивалентности на X называется рефлексивное, транзитивное и симметричное отношение. Легко видеть, что R Í X ´ X будет отношением эквивалентности тогда и только тогда, когда имеют место включения:
Id X Í R (рефлексивность),
R -1 Í R (симметричность),
R ° R Í R (транзитивность).
В действительности эти три условия равносильны следующим:
Id X Í R, R -1 = R, R ° R = R.
Разбиением множества X называется множество А попарно непересекающихся подмножеств a Í X таких, что UA = X. С каждым разбиением А можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого a Î A.
Каждому отношению эквивалентности ~ на X соответствует разбиение А, элементами которого являются подмножества, каждое из которых состоит из находящихся в отношении ~. Эти подмножества называются классами эквивалентности . Это разбиение А называется фактор-множеством множества X по отношению ~ и обозначается: X/~.
Определим отношение ~ на множестве w натуральных чисел, полагая x ~ y, если остатки от деления x и y на 3 равны между собой. Тогда w/~ состоит из трёх классов эквивалентности, соответствующих остаткам 0, 1 и 2.
Отношение порядка
Бинарное отношение R на множестве X называется антисимметричным , если из x R y и y R x следует: x = y. Бинарное отношение R на множестве X называется отношением порядка , если оно рефлексивно, антисимметрично и транзитивно. Легко видеть, что это равносильно выполнению следующих условий:
1) Id X Í R (рефлексивность),
2) R Ç R -1 (антисимметричность),
3) R ° R Í R (транзитивность).
Упорядоченная пара (X, R), состоящая из множества X и отношения порядка R на X, называется частично упорядоченным множеством .
Пример 1
Пусть X = {0, 1, 2, 3}, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}.
Поскольку R удовлетворяет условиям 1 – 3, то (X, R) – частично упорядоченное множество. Для элементов x = 2, y = 3, неверно ни x R y, ни y R x. Такие элементы называют несравнимыми . Обычно отношение порядка обозначают £. В приведенном примере 0 £ 1 и 2 £ 2, но неверно, что 2 £ 3.
Пример 2
Пусть < – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.
Элементы x, y Î X частично упорядоченного множества (X, £) называются сравнимыми , если x £ y либо y £ x.
Частично упорядоченное множество (X, £) называется линейно упорядоченным или цепью , если любые два его элемента сравнимы. Множество из примера 2 будет линейно упорядоченным, а из примера 1 – нет.
Подмножество A Í X частично упорядоченного множества (X, £) называется ограниченным сверху , если существует такой элемент x Î X, что a £ x для всех a Î A. Элемент x Î X называется наибольшим в X, если y £ x для всех y Î X. Элемент x Î X называется максимальным, если нет отличных от x элементов y Î X, для которых x £ y. В примере 1 элементы 2 и 3 будут максимальными, но не наибольшими. Аналогично определяются ограничение снизу подмножества, наименьший и минимальный элементы. В примере 1 элемент 0 будет и наименьшим и минимальным. В примере 2 этими свойствами также обладает 0, но в (w, £) нет ни наибольшего, ни максимального элемента.
Пусть (X, £) – частично упорядоченное множество, A Í X – подмножество. Отношение на А, состоящее из пар (a, b) элементов a, b Î A, для которых a £ b, будет отношением порядка на А. Это отношение обозначают тем же символом: £. Таким образом, (A, £) – частично упорядоченное множество. Если оно является линейно упорядоченным, то будем говорить, что А – цепь в (X, £).
Принцип максимальности
Некоторые математические утверждения невозможно доказать без аксиомы выбора. Про эти утверждения говорят, что они зависят от аксиомы выбора или справедливы в теории ZFC , на практике вместо аксиомы выбора для доказательства используют обычно либо аксиому Цермело, либо лемму Куратовского-Цорна, либо любое другое утверждение, равносильное аксиоме выбора.
Лемма Куратовского-Цорна . Если каждая цепь в частично упорядоченном множестве (X, £) ограничена сверху, то в X есть по крайней мере один максимальный элемент.
Эта лемма равносильна аксиоме выбора, и поэтому её можно принять в качестве аксиомы.
Теорема. Для любого частично упорядоченного множества (X, £) существует отношение, содержащее отношение £ и превращающее X в линейно упорядоченное множество.
Доказательство . Множество всех отношений порядка, содержащих отношение £, упорядочено отношением включения Í. Поскольку объединение цепи отношений порядка будет отношением порядка, то по лемме Куратовского-Цорна существует максимальное отношение R, такое, что x £ y влечет x R y. Докажем, что R – отношение, линейно упорядочивающее X. Предположим противное: пусть существуют a, b Î X такие, что ни (a, b), ни (b, a) не принадлежат R. Рассмотрим отношение:
R¢ = R È {(x, y): x R a и b R y}.
Оно получается добавлением пары (a, b) к R и пар (x, y), которые должны быть добавлены к R¢ из условия, что R¢ – отношение порядка. Легко видеть, что R¢ рефлексивно, антисимметрично и транзитивно. Получаем R Ì R¢, противоречащее максимальности R, следовательно, R – искомое отношение линейного порядка.
Линейно упорядоченное множество X называется вполне упорядоченным, если всякое его непустое подмножество A Í X содержит наименьший элемент a Î A. Лемма Куратовского-Цорна и аксиома выбора эквивалентны также следующему утверждению:
Аксиома Цермело . Для каждого множества существует отношение порядка, превращающее его во вполне упорядоченное множество.
Например, множество w натуральных чисел является вполне упорядоченным. Принцип индуктивности обобщается следующим образом:
Трансфинитная индукция . Если (X, £) – вполне упорядоченное множество и F(x) – свойство его элементов, верное для наименьшего элемента x 0 Î X и такое, что из истинности F(y) для всех y < z следует истинность F(z), то F(x) верно для всех x Î X.
Здесь y < z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.
Понятие мощности
Пусть f: X à Y и g: Y à Z – отображения множеств. Поскольку f и g – отношения, то определена их композиция g ° f(x) = g(f(x)). Если h: Z à T – отображение множеств, то h ° (g ° f) = (h ° g) ° f. Отношения Id X и Id Y – функции, стало быть, определены композиции Id Y ° f = f ° Id x = f. При X = Y определим f 2 = f ° f, f 3 = f 2 ° f, …, f n+1 = f n ° f.
Отображение f: X àY называется инъекцей , если для любых элементов x 1 ¹ x 2 множества X справедливо f(x 1) ¹ f(x 2). Отображение f называется сюръекцией , если для каждого y ÎY существует такой x Î X, что f(x) = y. Если f является и сюръекцией, и инъекцией, то f называется биекцией . Легко видеть, что f – биекция тогда и только тогда, когда обратное отношение f -1 Í Y ´ X является функцией.
Будем говорить, что справедливо равенство |X| = |Y|, если существует биекция между X и Y. Положим |X| £ |Y|, если существует инъекция f: X à Y.
Теорема Кантора-Шредера-Бернштейна . Если |X| £ |Y| и |Y| £ |X| , то |X| = |Y|.
Доказательство . По условию, существуют инъекции f: X à Y и g: Y à X. Пусть A = g¢¢Y = Img – образ множества Y относительно отображения g. Тогда
(X \ A) Ç (gf)¢¢(X \ A) = Æ,
(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,
(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, …
Рассмотрим отображение j: X à A, заданное как j(x) = gf(x), при
x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È …, и j(x) = x в остальных случаях. Легко видеть, что j – биекция. Искомая биекция между X и Y будет равна g -1 ° j.
Антиномия Кантора
Положим |X| < |Y|, если |X| £ |Y| и не существует биекции между X и Y.
Теорема Кантора . Для любого множества X справедливо |X| < |P(X)|, где P(X) – множество всех подмножеств множества X.
(то есть которое обладает следующими свойствами: каждый элемент множества эквивалентен сам себе; если x эквивалентно y , то y эквивалентно x ; если x эквивалентно y , а y эквивалентно z , то x эквивалентно z ).
Тогда множество всех классов эквивалентности называется фактормножеством и обозначается . Разбиение множества на классы эквивалентных элементов называется его факторизацией .
Отображение из X в множество классов эквивалентности называется факторотображением .
Примеры
Факторизацию множества разумно применять для получения нормированных пространств из полунормированных, пространств со скалярным произведением из пространств с почти скалярным произведением и пр. Для этого вводится соответственно норма класса, равная норме произвольного его элемента, и скалярное произведение классов как скалярное произведение произвольных элементов классов. В свою очередь отношение эквивалентности вводится следующим образом (например для образования нормированного факторпространства): вводится подмножество исходного полунормированного пространства, состоящее из элементов с нулевой полунормой (кстати, оно линейно, то есть является подпространством) и считается, что два элемента эквивалентны, если разность их принадлежит этому самому подпространству.
Если для факторизации линейного пространства вводится некоторое его подпространство и считается, что если разность двух элементов исходного пространства принадлежит этому подпространству, то эти элементы эквивалентны, то фактормножество является линейным пространством и называется факторпространством.
Примеры
См. также
Wikimedia Foundation . 2010 .
Смотреть что такое "Фактормножество" в других словарях:
Логический принцип, лежащий в основе определений через абстракцию (См. Определение через абстракцию): любое Отношение типа равенства, определённое на некотором исходном множестве элементов, разбивает (делит, классифицирует) исходное… …
Форма мышления, отражающая существенные свойства, связи и отношения предметов и явлений в их противоречии и развитии; мысль или система мыслей, обобщающая, выделяющая предметы некоторого класса по определённым общим и в совокупности… … Большая советская энциклопедия
Когомологии Галуа группы. Если М абелева группа и группа Галуа расширения, действующая на М, то когомологии Галуа есть группы когомологии определяемые комплексом состоит из всех отображений, a d кограничный оператор (см. Когомологии групп).… … Математическая энциклопедия
Конструкция, к рая впервые появилась в теории множеств, а затем стала широко использоваться в алгебре, топологии и других областях математики. Важный частный случай И. п. это И. п. направленного семейства однотипных математических структур. Пусть … Математическая энциклопедия
Точки хотносительно группы G, действующей на множестве X(слева), множество Множество является подгруппой в G и наз. стабилизатором, или стационарной подгруппой точки хотносительно G. Отображение индуцирует биекцию между G/Gx и орбитой G(x). О.… … Математическая энциклопедия
В этой статье слишком короткое вступление. Пожалуйста, дополните вводную секцию, кратко раскрывающую тему статьи и обобщающую её содержимое … Википедия
Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики. Булевой алгеброй называется непустое множество A с двумя бинарными операциями (аналог конъюнкции),… … Википедия
Пусть на множестве задано отношение эквивалентности. Тогда множество всех классов эквивалентности называется фактор множеством и обозначается. Разбиение множества на классы эквивалентных элементов называется его факторизацией. Отображение из в… … Википедия
Под направленным отрезком в геометрии понимают упорядоченную пару точек, первая из которых точка A называется его началом, а вторая B его концом. Содержание 1 Определение … Википедия
В различных разделах математики ядром отображения называется некоторое множество kerf, в некотором смысле характеризующее отличие f от инъективного отображения. Конкретное определение может различаться, однако для инъективного отображения f… … Википедия
Можно доказать следующие теоремы.
Теорема 1.4. Функция f имеет обратную функцию f -1 тогда и только тогда, когда f биективна.
Теорема 1.5. Композиция биективных функций является функцией биективной.
Рис. 1.12 показывают различные отношения, все они, кроме первой, являются функциями.
отношение, но |
инъекция, но |
сюръекция, но |
||||||||||||||
не функция |
не сюръекция |
не инъекция |
||||||||||||||
Пусть f : А→ В – функция, а множества А и В - конечные множества, положим А = n , B = m . Принцип Дирихле гласит, что если n > m , то, по крайней мере, одно значение f встречается более одного раза. Иными словами, найдется пара элементов a i ≠ a j , a i , a j A, для которых f(a i )= f(a j ).
Принцип Дирихле легко доказать, поэтому оставляем его читателю в качестве тривиального упражнения. Рассмотрим пример. Пусть в группе более 12 студентов. Тогда, очевидно, что, по крайней мере, у двоих из них день рождения в одном и том же месяце.
§ 7. Отношение эквивалентности. Фактор- множество
Бинарное отношение R на множестве А называется отношением эквивалентности, если R рефлексивно, симметрично и транзитивно.
Отношение равенства на множестве чисел обладает указанными свойствами, поэтому является отношением эквивалентности.
Отношение подобия треугольников, очевидно, является отношением эквивалентности.
Отношение нестрогого неравенства (≤ ) на множестве действительных чисел не будет отношением эквивалентности, ибо не является симметричным: из 3≤ 5 не следует, что 5≤ 3.
Классом эквивалентности (классом смежности) , порожденным элементом а при данном отношении эквивалентности R, называется подмножество тех х А, которые находятся в отношении R с а. Указанный класс эквивалентности обозначается через [ а] R , следовательно, имеем:
[ а] R = {х A: а, х R }.
Рассмотрим пример. На множестве треугольников введено отношение подобия. Ясно, что все равносторонние треугольники попадают в один смежный класс, ибо каждый из них подобен, например, треугольнику, все стороны которого имеют единичную длину.
Теорема 1.6. Пусть R - отношение эквивалентности на множестве А и [ а] R смежный класс, т.е. [ а] R = {х A: а, х R }, тогда:
1) для любого а А : [ а] R ≠ , в частности, а [ а] R ;
2) различные смежные классы не пересекаются;
3) объединение всех смежных классов совпадает со всем множеством А;
4) совокупность различных смежных классов образуют разбиение множества А.
Доказательство. 1) В силу рефлексивности R получим, что для любого а, а А, имеем a,a R , следовательно а [ а] R и [ а] R ≠ ;
2) допустим, что [ а] R ∩ [b] R ≠ , т.е. существует элемент с из А и с [ а] R ∩ [b] R . Тогда из (cRa)&(cRb) в силу симметричности R получаем, что (аR с)&(cRb), а из транзитивности R имеем аRb.
Для любого х [ а] R имеем: (хRa)&(аRb) , тогда в силу транзитивности R получим хRb, т.е. х [b] R , поэтому [ а] R [b] R . Аналогично для любого у, у [b] R , имеем: (уRb)&(аRb) , а в силу симметричности R получим, что (уRb)&(bR а), затем, в силу транзитивности R, получим, что уR а, т.е. у [ а] R и
поэтому [b] R [ а] R . Из [ а] R [b] R и [b] R [ а] R получаем [ а] R = [b] R , т. е. если смежные классы пересекаются, то они совпадают;
3) для любого а, а А, как доказано, имеем а [ а] R , тогда, очевидно, что объединение всех смежных классов совпадет с множеством А.
Утверждение 4) теоремы 1.6 следует из 1)-3). Теорема доказана. Можно доказать следующую теорему.
Теорема 1.7 . Различные отношения эквивалентности на множестве А порождают различные разбиения А.
Теорема 1.8 . Каждое разбиение множества А порождает отношение эквивалентности на множестве A , причем различные разбиения порождают различные отношения эквивалентности.
Доказательство. Пусть дано разбиение В= {B i } множества A . Определим отношение R : а,b R тогда и только тогда, когда существует B i такое, что а и b оба принадлежат этому B i . Очевидно, что введенное отношение является рефлексивным, симметричным и транзитивным, следовательно, R – отношение эквивалентности. Можно показать, что если разбиения различны, то и отношения эквивалентности, ими порождаемые, тоже различны.
Совокупность всех классов смежности множества А по данному отношению эквивалентности R называется фактор- множеством и обозначается через А/R . Элементами фактор-множества являются классы смежности. Класс смежности [ а] R , как известно, состоит из элементов А, которые находятся между собой в отношении R .
Рассмотрим пример отношения эквивалентности на множестве целых чисел Z = {…, -3, -2, -1, 0, 1, 2, 3, …}.
Два целых числа а и b называют сравнимыми (конгруэнтными) по модулю m , если m делитель числа a-b , т. е. если имеем:
a=b+km , k=…, -3, -2, -1, 0, 1, 2, 3, ….
В этом случае записывают a≡ b(mod m) .
Теорема 1.9. Для любых чисел a , b , c и m>0 имеем:
1) a ≡ a(mod m) ;
2) если a ≡ b(mod m), то b ≡ a(mod m);
3) если a ≡ b(mod m) и b ≡ c(mod m), то a ≡ c(mod m).
Доказательство. Утверждения 1) и 2) очевидны. Докажем 3). Пусть a=b+k 1 m , b=c+k 2 m , тогда a=c+(k 1 +k 2 )m , т.е. a ≡ c(mod m) . Теорема доказана.
Таким образом, отношение сравнимости по модулю m является отношением эквивалентности и делит множество целых чисел на непересекающиеся классы чисел.
Построим бесконечно раскручивающуюся спираль, которая на рис. 1.13 изображена сплошной линией, и бесконечно скручивающуюся спираль, изображенную штриховой линией. Пусть задано целое неотрицательное число m . Все целые числа (элементы из множества Z ) расположим в точках пересечения этих спиралей с m лучами, как показано на рис. 1.13.
Для отношения сравнимости по модулю m (в частности и для m =8) класс эквивалентности – это числа, лежащие на луче. Очевидно, что каждое число попадает в один и только один класс. Можно получить, что для m= 8 имеем:
[ 0] ={…, -8, 0, 8, 16, …}; |
|||||
[ 1] ={…, -7, 1, 9, 17, …}; |
|||||
[ 2] ={…, -6, 2, 10, 18, …}; |
|||||
[ 7] ={…, -9, -1, 7, 15, …}. |
|||||
Фактор-множество множества Z по отношению сравнения по модулю m обозначается как Z/m или как Z m . Для рассматриваемого случая m =8
получим, что Z/8 = Z8 = { , , , …, } .
Теорема 1.10. Для любых целых a, b, a * , b * , k и m :
1) если a ≡ b(mod m), то ka ≡ kb(mod m);
2) если a ≡ b(mod m) и a* ≡ b* (mod m), то:
а) a+а * ≡ b+b* (mod m); б) аа * ≡ bb* (mod m).
Доказательство приведем для случая 2б). Пусть a ≡ b(mod m) и a * ≡ b * (mod m) , тогда a=b+sm и a * =b * +tm для некоторых целых s и t . Перемножив,
получим: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. Следовательно,
aa* ≡ bb* (mod m).
Таким образом, сравнения по модулю можно почленно складывать и умножать, т.е. оперировать точно также как и с равенствами. Например,