2 лек. Отношения. Операции над отношениями. Декартовым произведением
 Скачать 0.72 Mb.
|
|
Таласбаева Ж.Т. Отношения. Операции над отношениями. Декартовым произведением множеств 𝐴 1 , 𝐴 2 , … , 𝐴 𝑚 называется следующее множество упорядоченных m-ок: A 1 …A m = m i i A 1 ={(a 1 ,…,a m )| a i A i (i= 1, m )}. Произвольное подмножество декартового произведения A 1 …A m называется m-местным оношением, определенным на множествах 𝐴 1 , 𝐴 2 , … , 𝐴 𝑚 Если m=2, то отношение называется бинарным. Записи (а,b)R, ( , ) R a b или aRb означают, что пара ( , ) a b принадлежит отношению R. Для любого множества A определим тождественное отношение 𝑖𝑑 𝐴 ⇆ {(𝑥, 𝑥)|𝑥 ∈ 𝐴} и универсальное отношение 𝑈 𝐴 ⇆ {(𝑥, 𝑦)| ∀𝑥, 𝑦 ∈ 𝐴} = 𝐴 2 . Отношение 𝑖𝑑 𝐴 называется диагональю, а 𝑈 𝐴 - полным отношением. Пусть 𝑅 ⊆ 𝐴 × 𝐵, множество 𝐷𝑜𝑚 𝑅 = {𝑥|(𝑥, 𝑦) ∈ 𝑅} называется областью определения отношения 𝑅. Множество 𝐼𝑚 𝑅 = {𝑦|(𝑥, 𝑦) ∈ 𝑅} называется областью значений отношения 𝑅. Поскольку отношения можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к отношениям. В то же время на отношения можно распространить операции, определяемые для отображений. Мы рассмотрим здесь две такие операции. Композицией (произведением) отношений 𝑅 ⊆ 𝐴 × 𝐵 и 𝑄 ⊆ 𝐵 × 𝐶 называют отношение 𝑅 ∘ 𝑄 ⊆ 𝐴 × 𝐶, которое вводится следующим образом 𝑅 ∘ 𝑄 = {(𝑎, 𝑐)|∃𝑏 ∈ 𝐵: (𝑎, 𝑏) ∈ 𝑅, (𝑏, 𝑐) ∈ 𝑄}. Приведем некоторые свойства композиции отношений: Таласбаева Ж.Т. 1) ; 2) для любого отношения имеет место ; 3) ; Отношение, обратное к отношению , есть отношение из в , обозначаемое и равное, по определению, Обратное отношение обладает следующими легко проверяемыми свойствами: 1) ; 2) Доказательство свойств СРС. Определим степень отношения 𝑅 ⊆ 𝐴 × 𝐴: 𝑅 1 = 𝑅, 𝑅 𝑛 = 𝑅 ∘ 𝑅 𝑛−1 , если 𝑛 > 1. Функции. Инъекция, сюръекция, биекция. Если для бинарного отношения f ⊆A×B выполнены следующие условия: 1. 𝐷𝑜𝑚 𝑓 = 𝐴 (𝐷𝑜𝑚 𝑓 - область определения); 2. 𝐼𝑚 𝑓 ⊆ 𝐵 (𝐼𝑚 𝑓 − область значений); 3. Из того что ( 𝑥, 𝑦 1 ) ∈ 𝑓, (𝑥, 𝑦 2 ) ∈ 𝑓 следует, что 𝑦 1 = 𝑦 2 , то f называется функцией или отображением из множества A в множество B. Если элементу x соответствует y, то y называется образом элемента x, а x - прообразом элемента y. Пишут: или y = f(x). Множество A всех элементов , имеющих один и тот же образ , называется полным прообразом элемента y. Функция f: A→B называется инъекцией, если для любых 𝑥, 𝑦 ∈ 𝐴 из того, что 𝑥 ≠ 𝑦 следует, что 𝑓(𝑥) ≠ 𝑓(𝑦). Функция f: A→B называется сюръекцией, если 𝐼𝑚 𝑓 = 𝐵. Таласбаева Ж.Т. Функция f: A→B называется биекцией или взаимно однозначным соответствием между множествами A и B, если она является инъекцией и сюръекцией одновременно. Мощность множества. Конечные и бесконечные множества. Два множества X и Y, между которыми можно установить взаимно однозначное соответствие, называются равномощными (или эквивалентными), что обозначается символом Мощностью множества А называется класс всех множеств, эквивалентных множеству А (обозначается через |A|). Если А имеет ровно 𝑛 элементов для некоторого 𝑛 ∈ ℕ, то множество А называется конечным. Таким образом, мощностью конечного множества является число его элементов. Множество, не являющееся конечным, называется бесконечным. Множество, не имеющее равномощного с ним собственного подмножества, а также пустое множество, называется конечным. (второе определение конечного множества) Множество, равномощное множеству натуральных чисел, называется счетным. Множество, не являющееся конечным или счетным, называется несчетным. Говорят, что мощность множества А не превосходит мощности множества B: |𝐴| ≤ |𝐵|, если А равномощно некоторому подмножеству множества В. Мощность множества А меньше мощности множества B: |𝐴| < |𝐵|, если |𝐴| ≤ |𝐵| и |𝐴| ≠ |𝐵|. Теорема Кантора-Бернштейна. Если |𝐴| ≤ |𝐵| и |𝐵| ≤ |𝐴|, то |𝐴| = |𝐵|. Множество рациональных чисел и множество целых чисел счетны. Множество действительных чисел несчетно. Матрица бинарного отношения. Специальные бинарные отношения. Таласбаева Ж.Т. Рассмотрим два конечных множества 𝐴 = {𝑎 1 , 𝑎 2 , … , 𝑎 𝑚 }, 𝐵 = {𝑏 1 , 𝑏 2 , … , 𝑏 𝑛 } и бинарное отношение 𝑃 ⊆ 𝐴 × 𝐵. Определим матрицу [𝑃] = (𝑝 𝑖𝑗 ) размера 𝑚 × 𝑛 бинарного отношения 𝑃 по следующему правилу: 𝑝 𝑖𝑗 = { 1, если (𝑎 𝑖 , 𝑏 𝑗 ) ∈ 𝑃 0, если (𝑎 𝑖 , 𝑏 𝑗 ) ∉ 𝑃. Отметим основные свойства матриц бинарных отношений. 1. Если 𝑃, 𝑄 ⊆ 𝐴 × 𝐵, [𝑃] = (𝑝 𝑖𝑗 ), [𝑄] = (𝑞 𝑖𝑗 ), то [𝑃 ∪ 𝑄] = (𝑝 𝑖𝑗 + 𝑞 𝑖𝑗 ) и [𝑃 ∩ 𝑄] = (𝑝 𝑖𝑗 ∙ 𝑞 𝑖𝑗 ), где сложение осуществляется по правилам 0 + 0 ⇆ 0, 1 + 1 ⇆ 1 + 0 ⇆ 0 + 1 ⇆ 1, а умножение – обычным образом. Итак, [𝑃 ∪ 𝑄] = [𝑃] + [𝑄], а матрица [𝑃 ∩ 𝑄] получается перемножением соответствующих элементов из [𝑃] и [𝑄]: [𝑃 ∩ 𝑄]=[𝑃] ∗ [𝑄]. 2. Если 𝑃 ⊆ 𝐴 × 𝐵, 𝑄 ⊆ 𝐵 × 𝐶, то [𝑃 ∘ 𝑄] = [𝑃] ∙ [𝑄], где умножение матриц [𝑃] и [𝑄] производится по обычному правилу умножения матриц, но произведение и сумма элементов из [𝑃] и [𝑄]- по определенным в п. 1 правилам. 3. Матрица обратного отношения 𝑃 −1 равна транспонированной матрице отнощения P: [𝑃 −1 ] = [𝑃] т 4. Если 𝑃 ⊆ 𝑄, [𝑃] = (𝑝 𝑖𝑗 ), [𝑄] = (𝑞 𝑖𝑗 ), то 𝑝 𝑖𝑗 ≤ 𝑞 𝑖𝑗 5. Матрица тождественного отношения 𝑖𝑑 𝐴 единична. Рассмотрим специальные бинарные отношения. Если для любого x A верно (x,x)R, то отношение R называется рефлексивным. Если для любых x,y A верно ( , ) ( , ) x y R y x R , то отношение R называется симметричным. Если для любых , , x y z A выполнено следующее условие: ( , ) x y R и ( , ) ( , ) y z R x z R , то отношение R называется транзитивным. Если для любого x A верно ( , ) x x R , то отношение R называется иррефлексивным. Если для любых x,y A из того, что верно ( , ) x y R и ( , ) y x R следует, что xy, то отношение R называется антисимметричным. Приведем свойства специальных бинарных отношений. Таласбаева Ж.Т. 1. Отношение R рефлексивно тогда и только тогда, когда 𝑖𝑑 𝐴 ⊆ 𝑃. 2. Отношение R симметрично тогда и только тогда, когда 𝑃 = 𝑃 −1 3. Отношение R антисимметрично тогда и только тогда, когда 𝑃 ∩ 𝑃 −1 ⊆ 𝑖𝑑 𝐴 4. Отношение R транзитивно тогда и только тогда, когда 𝑃 ∘ 𝑃 ⊆ 𝑃. Доказательство свойств СРС. Отметим, что антисимметричность не совпадает с несимметричностью. Тождественнон отношение является одновременно и симметричным и не симметричным. Отношения порядка. Отношение экивалентности. Теорема о разбиении. Отношение R, определенное на множестве А называется предпорядком или квазипорядком, если оно является рефлексивным и транзитивным. Отношение R, определенное на множестве А называется частичным порядком, если оно является рефлексивным, антисимметричным и транзитивным. Частичный порядок обычно обозначается символом ≤, а обратное ему отношение ≤ −1 - символом ≥. Пусть отношение R является частичным порядком на множестве A. Если для любых элементов 𝑎, 𝑏 𝐴 выполняется хотя бы одно из условий (𝑎, 𝑏) 𝑅 или (𝑏, 𝑎) 𝑅, то отношение R называется линейным порядком. Если R является частичным (линейным) порядком, то пара A R называется частично упорядоченным множеством линейно упорядоченным множеством. Бинарное отношение называется отношением эквивалентности, если оно является рефлексивным, симметричным и транзитивным. По другому, отношение R является отношением эквивалентности, если для любых элементов , , x y z A выполняются условия: ( , ) x x R ( , ) ( . ) x y R y x R ( , ) x y R и ( , ) ( , ) y z R x z R Если R является отношением эквивалентности, то его в основном обозначают через (тильда), ( , ) x y R x y Таласбаева Ж.Т. Подмножество x = {y y A , x y } называется классом эквивалентности элемента x. Произвольный элемент множества x называется представителем класса x Примеры: Отношение параллельности прямых на плоскости или в пространстве является рефлексивным, симметричным и транзитивным. Отношение равенства или подобия треугольников являются рефлексивными, симметричными и транзитивными. Отношение быть подмножеством и отношение между действительными числами меньше либо равно являются примерами рефлексивных, антисимметричных и транзитивных отношений. А отношение меньше является иррефлексивным, транзитивным, но не является не симметричным и не антисимметричным. Если для множества А и для непустых множеств … m … выполняются следующие условия 1. i i I A , (I – множество индексов), 2. i j Α Α= при i j , то последовательность множеств … m … называется разбиением множества А. Теорема 1. (о разбиении) Классы эквивалентности произвольного отношения эквивалентности, определенного на множестве А задают разбиение множества А. Обратно, произвольное разбиение множества А определяет отношение эквивалентности на множестве А. |