Задание 3.

ТЕОРЕТИЧЕСКАЯ ОСНОВА:

ПРАКТИЧЕСКАЯ ЧАСТЬ:

• Пример 1.

Метод взаимного включения:

1. Прямое включение.

∀ (x,y) ∈ (A°C)\(B°C) →(x,y) ∈ (A°C) & (x,y) ∉( B°C) →(∃a)(x,a) ∈A & (a,y) ∈C & (∃b)(<x,b>∉B v <b,y>∉C) → (x,a)∈A & (a,y)∈C & (x,b) ∉B v (x,a)∈A & (a,y)∈C & (b,y)∉C → (поскольку в общем случае компанирующие элементы не обязательно совпадают) → M⊈N.

2. Обратное включение.

∀(x,y) ∈ (A\B)°C →(∃a)(x,a) ∈ A\B & (a,y) ∈ C →(x,a) ∈A & (x,a) ∉B & (a,y) ∈C →(объединяем с нулем) →(x,a)∈A & (a,y)∈C & (x,a)∉B v (x,a)∈A & (a,y)∈C & (a,y)∉C → (x,a)∈A & (a,y)∈C & ((x,a)∉B v (a,y)∉C) →(x,y) ∈A°C & (x,y) ∉B°C → (A°C)\(B°C) → N⊆M.

Первоначальное утверждение неверно, имеем:

((A\B) °C)⊆ ((A°C)\ (B°C));

• Пример 2.

Метод взаимного включения:

1. Прямое включение.

∀x∈Пр₂А^-1\Пр₂В^-1→(∃у) (y,х)∈ А^-1 & (y,x)∉В^-1 → (х,y)∈А & (x,y)∉В →x∈Пр₁А & x∉Пр₁В → х∈Пр₁А\Пр₁В → M⊆N.

2. Обратное включение.

∀x∈ Пр₁А\Пр₁В → х∈ Пр₁А & x∉Пр₁В → (∃у) (х, у) ∈А & (х, у) ∉В →х∈Пр₁А & x∉Пр₁B → x∈ Пр₂А^-1 & x∉ Пр₂В^-1 → x∈ Пр₂А^-1\ Пр₂В^-1 → N⊆M.

⇒Равенство множеств доказано.

Задание 4.

ТЕОРЕТИЧЕСКАЯ ОСНОВА:

Множество X с бинарным отношением ɸ  называется полным, если для любых двух различных элементов x и y из X: 

• либо x ɸ y

• либо y ɸ x

ПРАКТИЧЕСКАЯ ЧАСТЬ:

• Пример 1.

Задать отношение:

Антирефлексивное, симметричное, нетранзитивное.

	а1	а2	а3	а4
а1	0	1	1	0
а2	1	0	1	0
а3	1	1	0	0
а4	0	0	0	0

• Антирефлексивное, т.к. .

• Симметричное, т.к. .

• Нетранзитивное, т.к. в матрице R°R хоть один кортеж совпадает с исходным.

• Пример 2.

Задать отношение:

Рефлексивное, несимметричное, связное.

	а1	а2	а3	а4
а1	1	1	1	1
а2	0	1	1	1
а3	0	0	1	1
а4	0	0	0	1

*Аналогично с прошлым примером*

Задание 5.

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

• Доказательство №1(интуитивное):

Пусть дан произвольный элемент a. Предположим, что не существует максимального элемента, большего или равного a. Это значит, что для любого b>=a  найдется c>b. Тогда c>a  и потому найдется d>c  и т.д. Продолжая этот процесс достаточно долго, мы исчерпаем все элементы Z  и придем к противоречию. Утверждение доказано.

• Доказательство №2:

Пусть {S_i:i∊I} — произвольное линейно упорядоченное множество, составленная из элементов k. Положим S=⋃_i∊IS_i. Покажем, что S является верхней границей {S_i:i∊I} в k.

Достаточно показать, что S принадлежит k. Ясно, что S состоит из открытых подмножеств x. Остается показать, что в S нет конечных покрытий пространства x. Предположим, вопреки доказываемому, что S содержит конечное покрытие {U₁…..U_n}.

У нас U₁…..U_n ∊ S =⋃_i∊IS_i , а значит, найдутся такие i₁…..i_n∊I, что  U₁∊ S_i1, U_n∊ S_in. Поскольку {S_i:i∊I} является линейно упорядоченным множеством, среди S_i1…..S_in есть наибольшее.

Пусть это будет S_im. Заметим, что S_im принадлежит k , т.е. в S_im нет конечных покрытий пространства x. С другой стороны, U₁…..U_n∊ S_im, а значит, S_im все же содержит конечное покрытие пространства x.

Возникает противоречие, которое доказывает теорему.