(то есть которое обладает следующими свойствами: каждый элемент множества эквивалентен сам себе; если 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).

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

∼ {\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} .

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

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

Пусть 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, £) нет ни наибольшего, ни максимального элемента.