🗊Презентация Бинарные отношения

Бинарные отношения Лекция 3

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

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

Функция F: X → Y называется сюръективной (или сюръекцией), если каждый элемент множества Y является образом хотя бы одного элемента из Х при отображении F: X → Y (или: если каждый элемент множества Y имеет хотя бы один прообраз в множестве Х при отображении F). Функция 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.

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

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

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

Пусть σ — отношение эквивалентности на множестве А. Множество всех таких элементов x, что хσа истинно, называют смежным классом множества А по эквивалентности σ, или классом эквивалентности, и обозначают [а]σ. Свойство 1: a [а] Свойство 2: если aσb, то [а] = [b]. Любые два смежных класса множества А по эквивалентности σ либо не пересекаются, либо совпадают.

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

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

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

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

Примеры: Примеры: отношение включения на множестве подмножеств некоторого множества; отношение ≤ на множестве действительных чисел; отношение «х делит у» на множестве натуральных чисел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема(основная теорема о конечных множествах) Теорема(основная теорема о конечных множествах) Конечное множество не может быть равномощно никакому собственному подмножеству. Однако эта теорема не применима к бесконечным множествам. Множество точек любого интервала из множества действительных чисел R равномощно всему множеству действительных чисел R. Например, множество точек интервала (0,1) равномощно R.