Пусть G={p 0 =e, p 1 , …, p r } есть некоторая группа подстановок, определенная на множестве X = {1, 2, …, n} с единицей e=p 0 тождественной подстановкой. Определим отношение x~y, положив x~y равносильно, что существует p принадлежащее G(p(x)=y). Введенное отношение есть отношение эквивалентности, то есть оно удовлетворяет трем аксиомам:
1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;
Пусть А – произвольное множество.
Определение
: Бинарное отношение δ=A*A есть отношение эквивалентности (обозначается a ~ b), если они удовлетворяет следующим аксиомам:
∀ a, b, c ∈ A
1) a ~ a – рефлексивность;
2) a ~ b ⇒ b ~ a – коммутативность;
3) a ~ b & b ~ c → a ~ c — транзитивность
обозначается a ~ b, σ(a,b), (a,b) ∈ σ, a σ b
Определение
: Разбиение множества А есть семейство попарно не пресекающихся подмножеств из А, в объединении (в сумме) дающих все А.
А= ∪А i , А i ∩А j = ∅, ∀i ≠ j.
Подмножества А i называются смежными классами разбиения.
Теорема : каждое отношение эквивалентности, определенное на А, соответствует некоторому разбиению множества А. Всякое разбиение множества А соответствует некоторому отношению эквивалентности на множестве А.
Коротко: между классами всех определенных на множестве А отношений эквивалентностей и классом всех разбиений множества А существует взаимнооднозначное соответствие.
Доказательство : пусть σ — есть отношение эквивалентности на множестве А. Пусть а ∈ А.
Построим множество: К a ={x ∈ A,: x~a } – всех элементов, эквивалентных а. Множество (обозначение) называется классом эквивалентности относительно эквивалентности σ. Заметим, что если b принадлежит K a , то b~a. Покажем, что a~b⇔K a =K b . В самом деле, пусть a~b. Возьмем произвольный элемент c принадлежит K a . Тогда c~a, a~b, c~b, c принадлежит K b и потому K b принадлежит K a . То, что K a принадлежит K b , показывается аналогично. Следовательно, K b =K a .
Пусть теперь K b =K a . Тогда a принадлежит K a = K b , a принадлежит K b , a~b. Что и требовалось показать.
Если 2 класса K a и K b имеют общий элемент с, то K a = K b . В самом деле, если с принадлежит K a и K b , то b~c, c~a, b~a => K a = K b .
Поэтому различные классы эквивалентности либо не пересекаются, либо пересекаются и тогда совпадают. Всякий элемент с из А принадлежит только одному классу эквивалентности К с. Поэтому система непересекающихся классов эквивалентности в пересечении дает все множество А. И потому эта система есть разбиение множества А на классы эквивалентности.
Обратное: Пусть А = сумма по или A i – есть разбиение А. Введем на А отношение a~b, как a~b ⇔ a,b принадлежат одному и тому же классу разбиения. Это отношение удовлетворяет следующим аксиомам:
1) a ~ a (лежат в одном классе);
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, т.е. введенное отношение ~ есть отношение эквивалентности.
Замечание
:
1) разбиение множества А на одноэлементные подмножества и разбиение А, состоящие только из множества А, называется тривиальными (несобственным) разбиением.
2) Разбиение А на одноэлементные подмножества соответствует отношению эквивалентности которое есть равенство.
3) Разбиение А, состоящие из одного класса А, соответствует отношению эквивалентности, содержащему A x A.
4) a σ b → [a] σ = [b] σ — всякое отношение эквивалентности определенное на некотором множестве разбивает это множество на попарно не пересекающиеся классы называемые классами эквивалентности.
Определение : Совокупность классов эквивалентности множества А называется фактор-множеством A/σ множества А по эквивалентности σ.
Определение : Отображение p:A→A/σ, при котором p(A)=[a] σ , называется каноническим (естественным) отображением.
Всякое отношение эквивалентности, определенное на некотором множестве, разбивает это множество на попарно не пересекающиеся классы, называемые классами эквивалентности.
Пусть 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, £) нет ни наибольшего, ни максимального элемента.
Теория множеств. Основные понятия
Теория множеств является основополагающим определением современной математики. Она была создана Георгом Кантором в 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} .Факторизацию множества разумно применять для получения нормированных пространств из полунормированных, пространств со скалярным произведением из пространств с почти скалярным произведением и пр. Для этого вводится соответственно норма класса, равная норме произвольного его элемента, и скалярное произведение классов как скалярное произведение произвольных элементов классов. В свою очередь отношение эквивалентности вводится следующим образом (например для образования нормированного факторпространства): вводится подмножество исходного полунормированного пространства, состоящее из элементов с нулевой полунормой (кстати, оно линейно, то есть является подпространством) и считается, что два элемента эквивалентны, если разность их принадлежит этому самому подпространству.
Если для факторизации линейного пространства вводится некоторое его подпространство и считается, что если разность двух элементов исходного пространства принадлежит этому подпространству, то эти элементы эквивалентны, то фактормножество является линейным пространством и называется факторпространством.
Фактор множества
Множества.
Отношением частичного порядка на множестве x называется бинарное отношение, которое является антисимметричным, рефлексивным и транзитивным и обозначается в
виде пары:
Бинарное отношение называется толерантностью, если оно рефлексивно и симметрично.
Бинарное отношение называется квазипорядком, если оно иррефлексивно, антисимметрично и транзитивно (предпорядок).
Бинарное отношение называется строгим порядком, если оно рефлексивно и транзитивно.
Энарной алгебраической операцией на множестве М называется функция
– унарная операция;
– бинарная операция;
– триарная операция.
Бинарная алгебраическая операция –
– операция, ставящая в соответствие каждой упорядоченной паре из множества М некоторые элемент множества М.
Свойства:
1) Коммутативность:
2) Ассоциативность:
Нейтральный элемент
Множества М для бинарной алгебраической операции
Называется элемент:
-
Фактор множества – совокупность классов эквивалентности этого множества . Отношением частичного порядка на множестве x называется бинарное отношение... -
Следующий вопрос ». Фактор множества . Фактор множества – совокупност. Мультипликативные и аддитивные формы. -
Фактор множества – совокупност.
Множество – совокупность определённых и различных между собой объектов мыслимых как единое целое. -
Мультипликативная функция ― а... подробнее ». Фактор множества . Фактор множества – совокупность классов эквивалентности этого множества . -
В реальной действительности процесс производства протекает сложнее, а его продукт результат использования множества факторов . -
Качество управленческих решений зависит от множества факторов , наиболее значимыми из которых можно н. -
Оптимизация решений по привлечению капитала – это процесс исследования множества факторов , воздействующих на ожидаемые результаты...