Можно доказать следующие теоремы.

Теорема 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).

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

Математическим анализом называется раздел математики, занимающийся исследованием функций на основе идеи бесконечно малой функции.

Основными понятиями математического анализа являются величина, множество, функция, бесконечно малая функция, предел, производная, интеграл.

Величиной называется все что может быть измерено и выражено числом.

Множеством называется совокупность некоторых элементов, объединенных каким-либо общим признаком. Элементами множества могут быть числа, фигуры, предметы, понятия и т.п.

Множества обозначаются прописными буквами, а элементы множество строчными буквами. Элементы множеств заключаются в фигурные скобки.

Если элемент x принадлежит множеству X , то записывают x ∈ Х (∈ — принадлежит).
Если множество А является частью множества В, то записывают А ⊂ В (⊂ — содержится).

Множество может быть задано одним из двух способов: перечислением и с помощью определяющего свойства.

Например, перечислением заданы следующие множества:

• А={1,2,3,5,7} — множество чисел
• Х={x 1 ,x 2 ,...,x n } — множество некоторых элементов x 1 ,x 2 ,...,x n
• N={1,2,...,n} — множество натуральных чисел
• Z={0,±1,±2,...,±n} — множество целых чисел

Множество (-∞;+∞) называется числовой прямой , а любое число — точкой этой прямой. Пусть a — произвольная точка числовой прямой иδ — положительное число. Интервал (a-δ; a+δ) называется δ-окрестностью точки а .

Множество Х ограничено сверху (снизу), если существует такое число c, что для любого x ∈ X выполняется неравенство x≤с (x≥c). Число с в этом случае называется верхней(нижней) гранью множества Х. Множество, ограниченное и сверху и снизу, называется ограниченным . Наименьшая (наибольшая) из верхних (нижних) граней множества называется точной верхней (нижней) гранью этого множества.

Основные числовые множества

N	{1,2,3,...,n} Множество всех
Z	{0, ±1, ±2, ±3,...} Множество целых чисел. Множество целых чисел включает в себя множество натуральных.
Q	Множество рациональных чисел . Кроме целых чисел имеются ещё и дроби. Дробь — это выражение вида , где p — целое число, q — натуральное. Десятичные дроби также можно записать в виде . Например: 0,25 = 25/100 = 1/4. Целые числа также можно записать в виде . Например, в виде дроби со знаменателем "один": 2 = 2/1. Таким образом любое рациональное число можно записать десятичной дробью — конечно или бесконечной периодической.
R	Множество всех вещественных чисел . Иррациональные числа — это бесконечные непериодические дроби. К ним относятся: Вместе два множества (рациональных и иррациональных чисел) — образуют множество действительных (или вещественных) чисел.

Если множество не содержит ни одного элемента, то оно называется пустым множеством и записывается Ø .

Элементы логической символики

Запись ∀x: |x|<2 → x 2 < 4 означает: для каждого x такого, что |x|<2, выполняется неравенство x 2 < 4.

Квантор

При записи математических выражений часто используются кванторы.

Квантором называется логический символ, который характеризует следующие за ним элементы в количественном отношении.

• ∀- квантор общности , используется вместо слов "для всех", "для любого".
• ∃- квантор существования , используется вместо слов "существует", "имеется". Используется также сочетание символов ∃!, которое читается как существует единственный.

Операции над множествами

Два множества А и В равны (А=В), если они состоят из одних и тех же элементов.
Например, если А={1,2,3,4}, B={3,1,4,2} то А=В.

Объединением (суммой) множеств А и В называется множество А ∪ В, элементы которого принадлежат хотя бы одному из этих множеств.
Например, если А={1,2,4}, B={3,4,5,6}, то А ∪ B = {1,2,3,4,5,6}

Пересечением (произведением) множеств А и В называется множество А ∩ В, элементы которого принадлежат как множеству А, так и множеству В.
Например, если А={1,2,4}, B={3,4,5,2}, то А ∩ В = {2,4}

Разностью множеств А и В называется множество АВ, элементы которого принадлежат множесву А, но не принадлежат множеству В.
Например, если А={1,2,3,4}, B={3,4,5}, то АВ = {1,2}

Симметричной разностью множеств А и В называется множество А Δ В, являющееся объединением разностей множеств АВ и ВА, то есть А Δ В = (АВ) ∪ (ВА).
Например, если А={1,2,3,4}, B={3,4,5,6}, то А Δ В = {1,2} ∪ {5,6} = {1,2,5,6}

Свойства операций над множествами

Свойства перестановочности

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Сочетательное свойство

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Счетные и несчетные множества

Для того, чтобы сравнить два каких-либо множества А и В, между их элементами устанавливают соответствие.

Если это соответствие взаимооднозначное, то множества называются эквивалентными или равномощными, А В или В А.

Пример 1

Множество точек катета ВС и гипотенузы АС треугольника АВС являются равномощными.

Источник задания: Задание 10_20. ЕГЭ 2018 Обществознание. Решение

Задание 20. Прочитайте приведённый ниже текст, в котором пропущен ряд слов (словосочетаний). Выберите из предлагаемого списка слова (словосочетания), которые необходимо вставить на место пропусков.

«Качество жизни зависит от множества факторов, начиная от места проживания человека и заканчивая общей социально-экономической и (А) ситуацией, а также состоянием политических дел в стране. На качество жизни в той или иной степени могут влиять демографическая ситуация, жилищно-бытовые и производственные условия, объём и качество _____(Б) и т. д. В зависимости от степени удовлетворения потребностей в экономике принято выделять разные уровни жизни населения: достаток - пользование (В), обеспечивающими всестороннее развитие человека; нормальный уровень _____(Г) по научно обоснованным нормам, обеспечивающий человеку восстановление его физических и интеллектуальных сил; бедность - потребление благ на уровне сохранения работоспособности как низшей границы воспроизводства _____(Д); нищета - потребление минимально допустимого по биологическим критериям набора благ и услуг, которые позволяют лишь поддерживать жизнеспособность человека.

Население, адаптируясь к рыночным условиям, использует различные дополнительные источники получения доходов, включая поступления из личных подсобных хозяйств, прибыль от _____(Е)».

Слова (словосочетания) в списке даны в именительном падеже. Каждое слово (словосочетание) может быть использовано только один раз.

Выбирайте последовательно одно слово (словосочетание) за другим, мысленно заполняя каждый пропуск. Обратите внимание на то, что слов (словосочетаний) в списке больше, чем Вам потребуется для заполнения пропусков.

Список терминов:

1) капитал

2) экологическая

3) рациональное потребление

4) потребительские товары

5) средства производства

7) рабочая сила

8) предпринимательская деятельность

9) социальная мобильность

Решение.

Вставим термины в текст.

«Качество жизни зависит от множества факторов, начиная от места проживания человека и заканчивая общей социально-экономической и экологической (2) (А) ситуацией, а также состоянием политических дел в стране. На качество жизни в той или иной степени могут влиять демографическая ситуация, жилищно-бытовые и производственные условия, объём и качество потребительских товаров (4) (Б) и т. д. В зависимости от степени удовлетворения потребностей в экономике принято выделять разные уровни жизни населения: достаток - пользование благами (6) (В), обеспечивающими всестороннее развитие человека; нормальный уровень рационального потребления (3) (Г) по научно обоснованным нормам, обеспечивающий человеку восстановление его физических и интеллектуальных сил; бедность - потребление благ на уровне сохранения работоспособности как низшей границы воспроизводства рабочей силы (7) (Д); нищета - потребление минимально допустимого по биологическим критериям набора благ и услуг, которые позволяют лишь поддерживать жизнеспособность человека.

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

Пусть 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] σ , называется каноническим (естественным) отображением.

Всякое отношение эквивалентности, определенное на некотором множестве, разбивает это множество на попарно не пересекающиеся классы, называемые классами эквивалентности.