Какое из свойств может задать соответствие
Тема 1.3. Соответствия и функции
Резюме по теме
Вопросы для повторения
1.Что называется унарным отношением?
2.В чем состоит отличие унарного и бинарного отношений?
3.Перечислите свойства бинарных отношений?
4.Назовите способы задания бинарных отношений?
5.Как выглядит матрица отношения обладающего свойством симметричности?
6.Дайте определение отношению эквивалентности?
7.Что понимают под n-местным отношением?
8.В чем заключается свойство рефлексивности?
9.В чем состоит различие между отношениями строгого и нестрогого порядков?
10.В каком случае отношение называется транзитивным?
11.Есть ли антитранзитивное отношение?
Рассмотрены основные понятия отношений на примере наиболее изученных и чаще употребляемых бинарных отношений. Показаны способы задания бинарных отношений. Приведены свойства бинарных отношений, каждое из которых было охарактеризовано. Рассмотрены отношения эквивалентности и порядка.
Цель: ознакомиться и разобраться с понятиями соответствие и функция.
Задачи:
1. Рассмотреть соответствия и изучить их свойства.
2. Рассмотреть взаимнооднозначные соответствия и мощности множеств.
3. Дать определения понятиям функция и отображение.
4. Рассмотреть понятие операция и виды операций.
5. Разобраться с понятиями гомоморфизм и изоморфизм.
Соответствие – способ задания взаимосвязей, взаимодействий между элементами множества (наряду с отношениями). Частными случаями соответствий являются функции, отображения, преобразования, операции и др.
Соответствием между множествами А и В (рис. 1.7) называется некоторое подмножество G их декартова произведения: .
Если , то говорят, что соответствует а при соответствии .
Область определения соответствия G – множество пр1G={а:(а,b) ÎG}. Область значений соответствия G – множество пр2G={b:(а,b) ÎG}.
Рис. 1.7. Соответствие G между множествами А и B
В принятых обозначениях, каждый элемент , соответствующий данному элементу называется образом при соответствии , наоборот, элемент называется прообразом элемента при данном соответствии.
Свойства соответствий :
1) Соответствие называется полностью определённым, если , то есть каждый элемент множества имеет хотя бы один образ во множестве ; в противном случае соответствие называется частичным.
2) Соответствие называется сюръективным, если , то есть если каждому элементу множества соответствует хотя бы один прообраз во множестве .
3) Соответствие называется функциональным (однозначным), если любому элементу множества соответствует единственный элемент множества .
4) Соответствие называется инъективным, если оно является функциональным, и при этом каждый элемент множества имеет не более одного прообраза.
5) Соответствие называется взаимнооднозначным (биективным), если любому элементу множества соответствует единственный элемент множества , и наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определённым, сюръективным, функциональным, и при этом каждый элемент множества имеет единственный прообраз.
Источник
Основные понятия и правила комбинаторики.
На практике часто встречаются задачи, где необходимо подсчитать число всех возможных способов размещения объектов конечного множества или число всех возможных способов выполнения определенного действия из конечного множества таких действий.
Задачи такого типа называют комбинаторными, а методы их решения – методами комбинаторного анализа. Поскольку комбинаторика имеет дело с конечными множествами, то ее называют теорией конечных множеств.
Определение 2.1. Комбинаторика – раздел дискретной математики, посвященный решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными свойствами.
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило произведения и правило суммы.
Основное правило комбинаторики (правило произведения):
Пусть необходимо выполнить последовательно действий. Если первое действие можно выполнить способами, второе – способами, а -е – способами, то все действий можно выполнить способами.
Правило суммы:
Если элемент может быть выбран способами, а элемент другими способами, то выбор либо , либо может быть выбран способами.
Будем рассматривать задачи, связанные с нахождением числа способов построения кортежей из элементов конечного множества. Простейшими такими кортежами являются: размещения, перестановки и сочетания. Эти задачи образуют часть комбинаторики, называемую перечислительной комбинаторикой или теорией перечислений.
Размещения (arrangement).
Пусть – конечное множество, состоящее из элементов .
Определение 2.2. Кортежи длины , , состоящие из различных элементов -элементного множества (кортежи отличаются один от другого как самими элементами, так и их порядком), называются размещениями из элементов множества по , .
Схема выбора состоит в выборе элементов из -элементного множества без возвращений. Тогда необходимо совершить действий, причем первое действие можно совершить способами, -е – способами, -е – способами и т.д. Согласно комбинаторному правилу умножения, получим формулу:
.
Если умножить и разделить полученное выражение на , получим:
.
Пример:
Дано множество . Выпишем все размещения из трех элементов по два:
.
Число этих размещений можно найти по формуле:
.
Перестановки (permutation).
Пусть – конечное множество из элементов.
Определение 2.3. Будем строить из этого множества размещения в виде кортежей длины . Эти размещения будут отличаться друг от друга только порядком элементов, поскольку в каждом из них встречаются по одному разу все элементы множества . Такие размещения называют перестановками, . Поскольку , то число перестановок вычисляется по формуле .
Пример:
Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая входит в число только один раз.
Составим следующие тройки: – то есть шесть чисел. С помощью введенной формулы можно сразу определить число перестановок, не выписывая их:
.
Сочетания (combination).
Пусть – конечное множество из элементов.
Определение 2.4. Будем строить упорядоченные множества длины , , не учитывая порядок элементов, т. е. размещения с одними и теми же элементами, расположенными в разном порядке, будем считать равными. Такие размещения называются сочетаниями, .
Число сочетаний из элементов по меньше числа размещений из элементов по в раз, т. е.:
.
Пример:
Какие парные сочетания можно составить из цифр 1, 3, 5 и сколько их?
Выпишем эти сочетания: , т. е. или .
Комбинации элементов с повторениями
Все приведенные формулы справедливы в том случае, когда элементов множества различны. Если же некоторые элементы повторяются, то в этом случае рассматриваются комбинации с повторениями,число которых вычисляется по другим формулам.
Размещения с повторениями.
Определение 2.5. Размещениями с повторениями из элементов по называются кортежи длины , составленные из -элементного множества . Число этих кортежей обозначают . Черта указывает на возможность повторения элементов .
Пример:
Сколько пятизначных номеров можно составить из элементов множества ?
Такими номерами являются кортежи длины 5, составленные из девятиэлементного множества, где схема выбора состоит в выборе 5 элементов из девятиэлементного множества с возвращением, т. е. для каждого из пяти элементов есть девять способов выбора: .
Перестановки с повторениями.
Определение 2.6. Перестановкой с повторениями состава из элементов называют любой кортеж длины , в который входит раз, входит раз, – раз. Число таких перестановок:
.
Пример:
Сколько слов можно получить, переставляя буквы в слове “МАТЕМАТИКА”?
В слове “МАТЕМАТИКА” 2 буквы М, 3 буквы А, 2 буквы Т, 1 буква Е, 1 буква И и 1 буква К. Число слов будет равно:
.
Сочетания с повторениями.
Определение 2.7. Пусть имеются предметы видов и из них составляется набор, содержащий элементов, т. е. различными исходами будут всевозможные наборы длины , отличающиеся составом, и при этом отдельные наборы могут содержать повторяющиеся элементы. Такие наборы называются сочетаниями с повторениями, а их общее число определяется формулой:
.
Пример:
Сколько наборов из 7 пирожных можно составить, если в продаже имеются 4 сорта?
Искомое число равно .
Соответствия.
Пусть и – произвольные множества.
Определение 2.8. Соответствием называется произвольное подмножество . В частном случае, когда каждый элемент входит не более, чем в одну пару , получается обычное однозначное отображение из в , или функция. Таким образом, понятие соответствия обобщает понятие функции.
Пример:
Пусть .
Декартово произведение показано на рис.1 в виде прямоугольной таблицы, а элементы представлены заполненными точками.
рис.1. Пример соответствия
Определение 2.9. Образом множества при соответствии называется множество точек , входящих в в паре с некоторым . Для образ одноточечного множества будем также обозначать .
Определение 2.10. Обратным к соответствием называется подмножество , определяемое следующим образом:
.
Пример:
рис.2. Пример обратного соответствия
Образ множества при соответствии называют также прообразом при соответствии . Для обозначения прообразов одноточечных множеств используется то же соглашение, что и для образов . Понятие соответствия оказывается особенно удачным в том смысле, что обратное соответствие всегда существует, и .
В общем случае, рассматриваются множества, элементы которых имеют различную природу. Например: отношение родился в году является подмножеством декартова произведения множества людей и множества лет и ставит в соответствие каждому человеку его год рождения. Для исключения подобных отношений вводятся понятия соответствия, отображения, функции.
Свойства соответствий.
Соответствие называется функциональным, если образ любого элемента , содержит не более одного элемента, то есть график такого соответствия не содержит пар с одинаковыми первыми и разными вторыми элементами.
рис.3. Функциональное соответствие
В противном случае соответствие является нефункциональным, т.е. если образ любого элемента , содержит более одного элемента.
рис.4. Нефункциональное соответствие
В случае, если каждому элементу соответствует более одного элемента из , соответствие называется антифункциональным.
рис.5. Антифункциональное соответствие
Соответствие называется инъективным, если прообраз любого элемента содержит не более одного элемента из , т. е. график такого соответствия не содержит пар с одинаковыми вторыми и разными первыми элементами.
рис.6. Инъективное соответствие
Соответствие называется неинъективным, если прообраз любого элемента содержит более одного элемента из .
рис.7. Неинъективное соответствие
Соответствие называется антиинъективным, если, каждый прообраз любого элемента содержит более одного элемента из .
рис.8. Антиинъективное соответствие
Соответствие называется всюду определенным, если для каждого , его образ не равен пустому множеству, то есть в графике такого соответствия из любой вершины выходит по крайней мере одна стрелка.
рис.9. Всюду определенное соответствие
Соответствие называется сюръектиеным, если для любого его прообраз не равен пустому множеству, то есть в графике такого соответствия в любую вершину входит хотя бы одна стрелка.
рис.10. Сюръективное соответствие
Соответствие называется биективным или взаимооднозначным, если оно функционально, инъективно, всюду определено и сюръективно.
рис.11. Биективное соответствие
Источник
Виды соответствий
Соответствие называется всюду определенным на множестве X, если:
а) , то есть: : у=f(x), или на «языке» полного образа элемента;
б) , или на «языке» графов;
в) из каждого элемента множества X выходит стрелка и приходит в Y.
Соответствие называют сюръективным, если:
а) , то есть : хfу ⇔ у=f(x), или на языке полного прообраза;
б) , или на «языке» графов;
в) в каждый элемент множества Y приходит стрелка из X.
Если f ― всюду определенно на X, то f -1 ― сюръективное соответствие Y на X, если f ― сюрьективно, то f -1 всюду определенно на Y.
Соответствие f называют функциональным, если:
а) R(x) содержит не более одного элемента, то есть ;
б) на языке графов это означает, что из каждого элемента множества X не выходит две стрелки и более.
Соответствие f называется инъективным, если:
а) содержит неболее одного элемента, то есть ;
б) на «языке» графов это означает, что в каждый элемент множества Y приходит не более одной стрелки.
Из этих определений следует, что соответствие, обратное функциональному, ― инъективно, а обратное инъективному ― функционально.
Если f и g ― всюду определенные, функциональные, инъективные и сюръективные соответствия, то ― тоже будет обладать всеми этими свойствами.
П р и м е р 1: Соответствие на рисунке
а) не всюду определено;
б) функционально;
в) инъективно;
г) сюръективно.
П р и м е р 2: Пусть X ― множество студентов в аудитории. Y ― множество стульев. Зададим соответствие x f y «студент x сидит на стуле y».
Это соответствие будет:
а) всюду определенным, если каждый студент будет сидеть;
б) сюрьективным, если все стулья заняты;
в) функциональным, если каждый студент не сидит на двух стульях;
г) инъективным, если на каждом стуле не сидят два студента.
П р и м е р 3: Пусть х f у (у = sin х), X = R, Y = R. Тогда графиком этого соответствия будет синусоида:
Соответствие это будет:
а) всюду определено, так как : (у = sin х) (любая прямая, параллельная оси ОY, пересекает график функции хотя бы в одной точке).
б) функционально, так как состоит из одного элемента (любая прямая, параллельная оси ОУ, пересекает график функции в единственной точке).
в) не инъективно, так как , для которых R -1(у) состоит более чем из одного элемента (существуют прямые, параллельные оси ОХ, которые пересекают график множество раз).
г) не сюръективно, так как , для которых не существует х: у=sinx (существуют прямые, параллельные оси ОХ, которые не пересекают график ни в одной точке).
Рассмотренные выше свойства соответствий (инъективность, сюръективностъ и т.п.) позволяют классифицировать все соответствия на определенные типы. Приведем классификацию соответствий по свойствам в виде таблицы:
| Функциональность | Всюду определенность | Инъективность | Сюръективность | Название |
| + | Функция типа | |||
| + | + | Отображение из X в Y | ||
| + | + | + | Вложение(инъекция) X в Y | |
| + | + | + | Наложение (сюръекция) X на Y | |
| + | + | + | + | Биекция X на Y |
Из этой таблицы видно, например, что отображение ― это всюду определенное функциональное соответствие.
П р и м е р 4: Отображение сюръективно и инъективно, так как: из того, что
и . Следовательно, соответствие ― биекция.
Источник
Соответствие – способ задания взаимосвязей между элементами множества. Частными случаями соответствий являются функции, отображения, преобразования, отношения.
Пусть имеются два множества А и В. Элементы этих множеств могут сопоставляться друг другу, образуя пары (a, b). Если способ сопоставления определен, то говорят, что между множествами A и B установлено соответствие. При этом не обязательно, чтобы в соответствии участвовали все элементы множеств А и В.
Таким образом, чтобы задать соответствие надо задать:
1) множество A;
2) множество B;
3) множество , определяющее правило соответствия, т. е. перечисляющее все пары (a, b), для которых справедливо соответствие.
Записывается соответствие так:
g = (A, B, G)
Множество A называется областью отправления соответствия, множество B – областью прибытия соответствия, G – называется графиком соответствия.
Обычно соответствие обозначается символом графика соответствия, в нашем случае обозначим соответствие G.
С соответствием связаны еще два понятия. Область определения соответствия G – элементы множества A, участвующие в соответствии, обозначается эта область как пр1G = {а🙁a, b) G}, и область значений соответствия G – элементы множества B, участвующие в соответствии, обозначается она как пр2G = {b:{а, b) G}(рис. 4.1 и рис. 4.2 ).
Если (а, b) G,то говорят, что “b соответствует а при соответствии G“. Геометрически это обозначается стрелками (рис. 4.2).
Пусть имеем множества A = {1, 2}, B = {3, 5}. Допустим элементы этих множеств образуют такие пары:
A B = {(1, 3), (1, 5), (2, 3), (2, 5)}.
Из приведенных пар можно составить несколько соответствий, например, такие: G1 = {(1, 3)}. Для этого соответствия Пр1G1 = {1}; Пр2G1 = {3}. G2 = {(1, 3), (1, 5)}. Здесь Пр1G2 = {1}; Пр2G2 = {3, 5}.
Рисунок 4.1 – График соответствия G
Рисунок 4.2 – Геометрическое представление соответствия G
Перечислим свойства соответствий.
соответствие всюду (полностью) определенно, если пр1G = A. Частично определенное соответствие – в противном случае.
соответствие сюръективно, если пр2G = В.
Образом элемента а А в множестве В при соответствии G называется множество всех b В,соответствующих элементу а А.
Прообразом элемента b в множестве А при соответствии G называется множество всех а А,которым соответствует b В.
Образом множества называется объединение образов всех элементов а С.
Прообразом множества называется объединение прообразов всех элементов b D.
соответствие называется однозначным или функциональным, если образом любого элемента а из области определения пр1G является единственный элемент b из области значений пр2G.
Взаимно однозначное соответствие, при котором любой элемент множества A, участвующий в соответствии, имеет единственный образ в множестве B и наоборот, любой элемент множества B, участвующий в соответствии, имеет единственный прообраз в множестве A, называется инъективным.
Соответствие, которое всюду определено, сюръективно и инъективно называется биекцией.
Если между множествами А и В существует взаимно однозначное соответствие, то мощности этих множеств равны, т.е. |А| = |В|. В таком случае говорят, что множества A и В равномощны.
Множества, равномощные множеству натуральных чисел N,называются счетными. Множества, равномощные множеству вещественных чисел R, называются континуальными.
Пусть дано соответствие Тогда соответствие G–1 называется обратным к G,если G–1таково, что (b, а) G–1 тогда и только тогда, когда (а, b) G. обратное соответствие обозначается:
g–1 = (B, A, G–1)
где G–1 (не всегда ).
Геометрически представление обратного соответствия получается из обозначения прямого соответствия заменой направления стрелок. Отсюда следует, что обратное соответствие обратного соответствия будет прямым, т.е.
(g–1)–1 = g.
Последовательное применение двух соответствий называется композицией соответствий.
Композиция соответствий есть операция с тремя множествами A, B, C, на которых определены два соответствия:
g = (A, B, G), ,
p = (B, C, P), ,
причем область значений первого соответствия совпадает с областью определения второго:
Пр2G = Пр1P.
Первое соответствие определяет для любого некоторый (возможно не один) элемент . В соответствии с определением композиции для этого b надо найти по второму правилу. В результате для найдем .
Композицию соответствий g и p обозначают g(p) или g p, или просто gp.
График композиции соответствий обозначают G P.
При этом приведенная выше композиция соответствий запишется так
g(p) = (A, C, G P), G P .
Операцию композиции можно распространить и на большее число (более двух) соответствий.
Композиция ассоциативна:
h(gp) = (hg)p
Но не коммутативна:
gp pg
Даже если рассматриваются соответствия элементов на одном множестве.
Источник