Бинарные отношения

Сентябрь 13, 2022

Главная
Математика
Бинарные отношения

Содержание

2. Бинарное отношение f определенное на паре не пустых множеств А и В, называется функцией, определенной на
3. Функция (отображение) F: X →Y называется инъекцией (или инъективным ), если различным элементам из множества X
4. Функция F: X → Y называется сюръективной (или сюръекцией), если каждый элемент множества Y является образом
5. Функция F: X → Y называется биективной (или биекцией), если она одновременно и инъективна, и сюръективна.
6. 5
7. 6
8. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ Бинарное отношение α, определенное на множестве А, называется отношением эквивалентности или просто эквивалентностью на
9. Пусть Р – бинарное отношение на множестве А: Р ⊆ А2. Отношение Р называется: 1. рефлексивным,
10. Примеры отношений эквивалентности: отношение подобия в множестве треугольников в евклидовой плоскости; отношение равенства в произвольной системе
11. Лемма Теорема Пусть σ — отношение эквивалентности на множестве А. 10 Определение
12. Совокупность всех различных смежных классов множества А по эквивалентности σ называется фактор-множеством множества А по эквивалентности
13. 12
14. Если σ — отношение эквивалентности на множестве А, то совокупность всех различных смежных классов множества А
15. Бинарное отношение ρ, определенное на множестве А, называется частичным порядком, или отношением частичного порядка, если оно:
16. Бинарное отношение ρ, определенное на множестве А, называется частичным порядком, или отношением частичного порядка, если оно
17. Примеры: отношение включения на множестве подмножеств некоторого множества; отношение ≤ на множестве действительных чисел; отношение «х
18. Частичный порядок на множестве А будем обозначать символом ≤, и если a ≤ b для некоторых
19. Элементы а, b множества А называются сравнимыми относительно частичного порядка ≤ на этом множестве, если a
20. Частично упорядоченное множество может обладать или не обладать наименьшим или наибольшим элементом. Примеры: Множество действительных чисел
21. 3.Множество неотрицательных целых чисел с отношением делимости в качестве отношения частичного порядка (т.е. т ≤ n
22. Максимальным элементом частично упорядоченного множества А называется такой элемент, что каждый элемент х из А либо
23. В отличие от наибольшего (наименьшего) элемента частично упорядоченное множество может содержать несколько максимальных (минимальных) элементов. Так,
24. Всякий наибольший элемент частично упорядоченного множества является максимальным, а всякий наименьший — минимальным. Обратное, вообще говоря,
25. Частичный порядок на множестве А называется линейным порядком, если любые два элемента из А сравнимы относительно
26. Если всякое непустое подмножество линейно упорядоченного множества А является частично упорядоченным множеством, содержащим минимальные элементы, то
27. Множество всех целых чисел относительно естественного порядка не будет вполне упорядоченным, так как оно не имеет
28. МОЩНОСТЬ МНОЖЕСТВА Понятие мощности возникает при сравнении множеств по числу элементов. Множество X назовем равномощным множеству
29. Отношение равномощности множеств удовлетворяет следующим условиям: рефлексивности: X ~ X; симметричности: если X ~ Y, то
30. Мощностью множества X называется класс всех множеств, равномощных множеству X. Если А ~ {a1,…,an} для некоторого
31. Множество, не являющееся конечным, называется бесконечным. Если А ~ N, т.е. если множество равномощно множеству натуральных
32. На мощность множества A можно смотреть и как на новый объект, называемый кардинальным числом или кардиналом.
34. Скачать презентацию

Слайд 2

Бинарное отношение f определенное на паре не пустых множеств А и

В, называется функцией, определенной на множестве А со значениями в В (или отображением из А в В), если для любого элемента x ∈ А существует один и только один элемент y ∈ B, удовлетворяющий условию x f y.
Другими словами, отношение f, заданное на паре непустых множеств А и В, является функцией из А в В, если из того, что
(x, y1) ∈ f и (x, y2) ∈ f следует y1 = y2.

8 ФУНКЦИЯ

Определение

Слайд 3

Функция (отображение) F: X →Y называется инъекцией (или инъективным ), если

различным элементам из множества X соответствуют различные элементы из множества Y при отображении F: X → Y, т.е. если для любых x1и x2 из X выполняется следующее условие:
Другое название инъективного отображения
F: X →Y — взаимно однозначное отображение из X вY.

x1 ≠ x2 ⇒ F(x1) ≠ F(x2).

Определение

Слайд 4

Функция F: X → Y называется сюръективной (или сюръекцией), если каждый

элемент множества Y является образом хотя бы одного элемента из Х при отображении F: X → Y (или: если каждый элемент множества Y имеет хотя бы один прообраз в множестве Х при отображении F).
Иными словами, отображение F: X → Y называется сюръективным, если образ F(X) множества Х при отображении F: X → Y совпадает с Y, т.е. F(X) = Y.
Другое название сюръективного отображения F: X → Y — отображение множества Х на множество Y.

Определение

Слайд 5

Функция F: X → Y называется биективной (или биекцией), если она

одновременно и инъективна, и сюръективна.
Другое название биективного отображения
F: X → Y — взаимно однозначное отображение множества Х на множество Y.

Определение

Слайд 6

5

Слайд 7

6

Слайд 8

ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ
Бинарное отношение α, определенное на множестве А, называется отношением эквивалентности

или просто эквивалентностью на множестве А, если α:
рефлексивно,
симметрично,
транзитивно.

Определение

Слайд 9

Пусть Р – бинарное отношение на множестве А: Р ⊆ А2.

Отношение Р называется:
1. рефлексивным, если (x,x) ∈ P для всех x ∈ А.
2. симметричным, если для любых x, y ∈ А из (x, y) ∈ P следует (y, x) ∈ P, т.е. Р-1 = Р.
3. антисимметричным, если из (x, y) ∈ P и (y, x) ∈ P следует x = y, т.е. Р ∩ Р-1 ⊆ idA.
4. транзитивным, если из (x, y) ∈ P и (y, x) ∈ P следует (x, z) ∈ P, т.е. Р°Р ⊆ Р.
Отметим, что антисимметричность не совпадает с несимметричностью.

Определение

Слайд 10

Примеры отношений эквивалентности:
отношение подобия в множестве треугольников в евклидовой плоскости;
отношение равенства

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

Слайд 11

Лемма
Теорема
Пусть σ — отношение эквивалентности на множестве А.

10
Определение

Слайд 12

Совокупность всех различных смежных классов множества А по эквивалентности σ называется

фактор-множеством множества А по эквивалентности σ и обозначается А/σ.
Разбиением (или расслоением) множества А называется система S непустых подмножеств множества А таких, что каждый элемент из А принадлежит одному и только одному подмножеству из системы S.

Определение

Слайд 13

12

Слайд 14

Если σ — отношение эквивалентности на множестве А, то совокупность всех

различных смежных классов множества А по эквивалентности σ является разбиением множества А.
Пусть S — разбиение множества А, а σ — бинарное отношение на множестве А такое, что, по определению, хσу истинно тогда и только тогда, когда в S есть подмножество М, которое совпадает с каким-либо классом эквивалентности отношения σ.
Тогда σ — отношение эквивалентности на множестве А. Эта эквивалентность σ называется эквивалентностью, отвечающей разбиению S.

Теорема

Слайд 15

Бинарное отношение ρ, определенное на множестве А, называется частичным порядком, или

отношением частичного порядка, если оно:
1) рефлексивно;
2) транзитивно;
3) антисимметрично.
Множество А, на котором задан какой-нибудь частичный порядок, называется частично упорядоченным.

ОТНОШЕНИЯ ПОРЯДКА

Определение

Слайд 16

Бинарное отношение ρ, определенное на множестве А, называется частичным порядком, или

отношением частичного порядка, если оно удовлетворяет следующим условиям:
1) хρх для любого (рефлексивность);
2) из хρу и yρz следует xρz для любых (транзитивность);
3) из хρу и уρх следует х = у для любых (антисимметричность).
Множество А, на котором задан какой-нибудь частичный порядок, называется частично упорядоченным.

Определение

Слайд 17

Примеры:
отношение включения на множестве подмножеств некоторого множества;
отношение ≤ на

множестве действительных чисел;
отношение «х делит у» на множестве натуральных чисел.

Слайд 18

Частичный порядок на множестве А будем обозначать символом ≤,
и если

a ≤ b для некоторых элементов a , b то будем говорить, что а меньше или равно b, а также, что а содержится в b или равно b. Если a ≤ b и а ≠ b, то будем писать а < b и говорить, что а строго меньше b или а строго содержится в b.

Слайд 19

Элементы а, b множества А называются сравнимыми относительно частичного порядка ≤

на этом множестве, если a ≤ b или b ≤ a.
Пусть А — частично упорядоченное множество с частичным порядком ≤.
Элемент x называется наименьшим элементом, если х ≤ а для любого a.
Элемент x называется наибольшим элементом, если b ≤ х для любого b.
Наибольший элемент часто называют единицей, а наименьший — нулем.

Определение

Слайд 20

Частично упорядоченное множество может обладать или не обладать наименьшим или наибольшим

элементом.
Примеры:
Множество действительных чисел с обычным отношением ≤ не имеет ни наибольшего, ни наименьшего элемента.
Множество неотрицательных действительных чисел имеет наименьший элемент (число 0), но не имеет наибольшего элемента.

Слайд 21

3.Множество неотрицательных целых чисел с отношением делимости в качестве отношения частичного

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

Слайд 22

Максимальным элементом частично упорядоченного множества А называется такой элемент, что каждый

элемент х из А либо не сравним с а, либо х ≤ а, т.е. другими словами, если А не содержит элементов, строго больших а. Минимальным элементом частично упорядоченного множества А называется такой элемент , что каждый элемент x из А либо не сравним с b, либо b ≤ х, т.е. если А не содержит элементов, строго меньших b.

Определение

Слайд 23

В отличие от наибольшего (наименьшего) элемента частично упорядоченное множество может содержать

несколько максимальных (минимальных) элементов.
Так, например, в множестве целых положительных чисел, отличных от 1, с отношением делимости в качестве отношения частичного порядка (т.е. m ≤ n тогда и только тогда, когда m делит n) минимальными элементами являются простые числа.

Слайд 24

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

— минимальным.
Обратное, вообще говоря, не имеет места. Действительно, предыдущий пример показывает, что в множестве целых положительных чисел, отличных от 1, с отношением делимости минимальными элементами являются простые числа, а наименьшего элемента нет.

Лемма

Слайд 25

Частичный порядок на множестве А называется линейным порядком, если любые два

элемента из А сравнимы относительно ≤.
Множество А, на котором задан какой-либо линейный порядок, называется линейно упорядоченным множеством, или цепью.
Примером линейно упорядоченного множества может служить множество всех действительных чисел с обычным отношением ≤.

Определение

Слайд 26

Если всякое непустое подмножество линейно упорядоченного множества А является частично упорядоченным

множеством, содержащим минимальные элементы, то множество А называется вполне упорядоченным множеством.
Примеры:
Вполне упорядоченными множествами являются конечное линейно упорядоченное множество и множество натуральных чисел, упорядоченное естественным образом.

Определение

Слайд 27

Множество всех целых чисел относительно естественного порядка не будет вполне упорядоченным,

так как оно не имеет наименьшего элемента.
Однако оно станет вполне упорядоченным, если установить порядок следующим образом: 1 < 2 < 3 < … < 0 < –1 < –2 < –3 < … .
Другим примером не вполне упорядоченной цепи служит отрезок [0, 1], ибо, например, интервал ]1/2, 1[ не содержит минимального элемента.

Слайд 28

МОЩНОСТЬ МНОЖЕСТВА
Понятие мощности возникает при сравнении множеств по числу элементов.
Множество X

назовем равномощным множеству Y (символически: X ~ Y), если существует биективное отображение X в Y.

Определение

Слайд 29

Отношение равномощности множеств удовлетворяет следующим условиям:
рефлексивности: X ~ X;
симметричности: если X

~ Y, то Y ~ X;
транзитивности: если X ~ Y и Y ~ Z, то X ~ Z,
т. е. оно является отношением эквивалентности.

Слайд 30

Мощностью множества X называется класс всех множеств, равномощных множеству X.
Если А

~ {a1,…,an} для некоторого n = 1,2,…, т. е. А имеет ровно n элементов, то множество А называется конечным.
В таком случае пишут: |A| = n. Таким образом, мощностью конечного множества является число его элементов.

Определение

Слайд 31

Множество, не являющееся конечным, называется бесконечным.
Если А ~ N, т.е.

если множество равномощно множеству натуральных чисел, то множество А называется счетным.
Множество Q рациональных чисел счетно.
Если А ~ 2N, т.е. если множество равномощно множеству действительных чисел, то множество A называется континуальным или континуумом.

Слайд 32

На мощность множества A можно смотреть и как на новый объект,

называемый кардинальным числом или кардиналом.
В качестве примеров кардиналов можно взять любое натуральное число n, а также N, 2N, и т. д.
Эти числа можно рассматривать как имена, обозначающие соответствующие мощности.

Бинарные отношения

Содержание

Бинарное отношение f определенное на паре не пустых множеств А и

Функция (отображение) F: X →Y называется инъекцией (или инъективным ), если

Функция F: X → Y называется сюръективной (или сюръекцией), если каждый

Функция F: X → Y называется биективной (или биекцией), если она

5

6

ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ Бинарное отношение α, определенное на множестве А, называется отношением эквивалентности

Пусть Р – бинарное отношение на множестве А: Р ⊆ А2.

Примеры отношений эквивалентности: отношение подобия в множестве треугольников в евклидовой плоскости;отношение равенства

ЛеммаТеорема Пусть σ — отношение эквивалентности на множестве А. 10Определение

Совокупность всех различных смежных классов множества А по эквивалентности σ называется

12

Если σ — отношение эквивалентности на множестве А, то совокупность всех

Бинарное отношение ρ, определенное на множестве А, называется частичным порядком, или

Бинарное отношение ρ, определенное на множестве А, называется частичным порядком, или

Примеры: отношение включения на множестве подмножеств некоторого множества; отношение ≤ на

Частичный порядок на множестве А будем обозначать символом ≤, и если

Элементы а, b множества А называются сравнимыми относительно частичного порядка ≤

Частично упорядоченное множество может обладать или не обладать наименьшим или наибольшим

3.Множество неотрицательных целых чисел с отношением делимости в качестве отношения частичного

Максимальным элементом частично упорядоченного множества А называется такой элемент, что каждый

В отличие от наибольшего (наименьшего) элемента частично упорядоченное множество может содержать

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

Частичный порядок на множестве А называется линейным порядком, если любые два

Если всякое непустое подмножество линейно упорядоченного множества А является частично упорядоченным

Множество всех целых чисел относительно естественного порядка не будет вполне упорядоченным,

МОЩНОСТЬ МНОЖЕСТВА Понятие мощности возникает при сравнении множеств по числу элементов.Множество X

Отношение равномощности множеств удовлетворяет следующим условиям:рефлексивности: X ~ X;симметричности: если X

Мощностью множества X называется класс всех множеств, равномощных множеству X.Если А

Множество, не являющееся конечным, называется бесконечным. Если А ~ N, т.е.

На мощность множества A можно смотреть и как на новый объект,

Похожие презентации

ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ
Бинарное отношение α, определенное на множестве А, называется отношением эквивалентности

Примеры отношений эквивалентности:
отношение подобия в множестве треугольников в евклидовой плоскости;
отношение равенства

Лемма
Теорема
Пусть σ — отношение эквивалентности на множестве А.

10
Определение

Примеры:
отношение включения на множестве подмножеств некоторого множества;
отношение ≤ на

Частичный порядок на множестве А будем обозначать символом ≤,
и если

МОЩНОСТЬ МНОЖЕСТВА
Понятие мощности возникает при сравнении множеств по числу элементов.
Множество X

Отношение равномощности множеств удовлетворяет следующим условиям:
рефлексивности: X ~ X;
симметричности: если X

Мощностью множества X называется класс всех множеств, равномощных множеству X.
Если А

Множество, не являющееся конечным, называется бесконечным.
Если А ~ N, т.е.