Отношение на множествах

1.Декартово произведение и его свойства.

Назовем упорядоченной парой (х,у) совокупность 2-х элементов х и у, расположенных в определенном порядке. ( ¾ = (3,4); a+bi = (a,b); y=f(x)(x,f(x))). Аналогично вводятся понятия упорядоченной тройки, четверки и т.д. пусть имеем два множества А и В.

Декартовым (прямым, бинарным) произведением множеств А и В называется множество упорядоченных пар АВ = {(x,y)|xÎA,yÎB}

Пример:1) A={1,2,3},B={3,4}; АВ={(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)}

2) множество точек плоскости есть декартово произведение множества точек осей. Ели А=В, то А´А=А² и говорят: декартова степень множества А.

аналогично можно ввести декартово произведение n множеств.

А1´А2´…´An = {(x1…xn)|x1ÎA1,x2ÎA2,…,xnÎAn}

Если А1=А2=…=An, то А1´А2´…´An = Aⁿ – n –я декартовая степень.

Свойства:

1. А´В= В´А 2. А´(В´С)=( А´В)´С

3. А´(ВUC)=(A´B)U(A´C) 4. (BUC)´A=(B´A)U(C´A)

5. (A´B)∩(C´D)=(A∩C)´(B∩D) 6. A´0=0´A=0

2. Бинарное отношение.

Любое подмножество ρ декартового произведения называется бинарным отношением между элементами множеств А и В. Т.о. бинарное отношение – это множество упорядоченных пар, которые между собой находятся в определенном отношении ρ. ρА´В. Бинарное отношение называют двуместным. Аналогично можно ввести n–местное отношение.

Если (х,у)Îρ, то пишут хρу, если (х,у)ρ, то хρу

Способы задания бинарного отношения:

1) перечисление пар, которые находятся в отношении ρ между собой:

A={1,2},B={1,2,3}; ‘<’ ( вид ρ) = {(1,2),(1,3),(2,3)}

2) c помощью матрицы

C_ij={1, если a_i ρ a_j ; 0, если a_i ρ a_j }

3) графически.

Назовем областью определения отношения ρ множество х, для которых существует у, что хρу (ρ_о={x| y, хρу }). Областью значений: ρ_з={y| x, х`ρу}.

Назовем отношение ρ^-1 обратным к отношению ρ, если есть множество тех пар (х,у), что (у,х)Îρ, т.е. ρ^-1={(x,y)|(y,x)Îρ}. (ρ^-1)^-1=ρ

Композицией отношения ρ₁ и ρ₂ называется отношение, обозначаемое ρ₁• ρ₂, которое означает, что найдется такое z, что (x,z) будет Îρ₁, а (z,y) находиться в отношении ρ₂.

ρ₂• ρ₁={(x,y)| z (x,z)Îρ₁, (z,y)Îρ₂ }

Докажем (ρ₂• ρ₁)^-1= ρ₁^-1•ρ₂^-1 : возьмем пару (х,у)Î (ρ₂• ρ₁)^-1, по определению обратного отношения (у,х)Î ρ₂• ρ₁, по опр-ю композиции существует z, что (y,z)Îρ₁ и (z,x)Îρ₂, по опр-ю обратного отношения (z,у)Îρ₁^-1 и (х,z)Îρ₂^-1 => мы имеем композицию ρ₁^-1•ρ₂^-1.

Свойства бинарных отношений на множестве м.

Замечание: х и у берутся из одного и того же множества М.

Бинарное отношение ρ на множестве М называется общезначимым, если ρ совпадает с декартовым произведением. Если отношение ρ не содержит ни одного элемента, то оно называется пустым.

1. отношение ρ на множестве М называется рефлексивным, если каждый элемент из множества М стоит в отношении ρ сам с собой. х ÎМ хρх. Пример: 1) ‘<=’,’>=’,’=’;2) отношение параллельности на множестве прямых. Не является рефл.: ’<’,’>’,’перпендикулярность’, ’симметричность относительно прямой’. Отношение, не являющееся рефлексивным, называется нерефлексивным. Если отношение задано матрицей, то на главной диагонали матрицы стоят единицы, если отношение нерефлексивное, то нули и единицы. Отношение ρ называется антирефлексивным, если ни один элемент не находится в отношении ρ сам с собой. Если отношение рефлексивное, то все элементы главной диагонали матрицы – нули.

2. отношение ρ на множестве М называется коммутативным (симметричным), если это отношение с каждой парой (х,у) содержит пару (у,х). матрица такого отношения будет симметрична относительно главной диагонали. Пример: ‘=’,’≠’. Не является коммутативным: ‘<=’,’>=’. Отношение коммутативно тогда и только тогда, когда оно совпадает со своим обратным отношением: ρ= ρ^-1. Отношение ρ на множестве М называется антикоммутативным (антисимметричным), если х,у ÎМ пара (х,у) хρу и уρх, т.е. х=у. Замечание: из определения антикоммутативности следует, что пара (х,у) может находиться в отношении ρ, а (у,х) – нет. Если отношение не является коммутативным и антикоммутативным, то оно называется некоммутативным. У обоих последних матрица не симметрична относительно главной диагонали.

3. отношение ρ на множестве М называется транзитивным, если для х,у,z ÎМ имеем: если хρу и уρх, то хρz. Пример: ‘<=’,’>=’,’=’,’<’,’>.