Вопросы и задачи

1.2. Используя методы двух включений и характеристических функций, доказать свойства 1-18.

1.3. Доказать тождества:

а) А × (В ∩ С) = (А × В) ∩ (А × С);

б) (А ∩ В) × (С ∩ D) = (А × С) ∩ (В × D).

Проиллюстрировать графически, приняв в качестве множеств А, B C и D отрезки числовой прямой.

1.4. Доказать, что если (А ⊆ Х) и (В ⊆ У), то (А × В) ⊆ (Х × У).

1.5. Показать, что (A × В) ≠ A × В. Вывести соответствующее тождество.

1.6. Используя ранее доказанные тождества, показать справедливость тождества (А\В) × С = (А × С)\(В × С).

1.7. Доказать, что для любой функции f и любых множеств А и В имеют место соотношения:

a) f(A∪B) = f(A)∪f(B);

б) f(А∩В) ⊆ f(А) ∩ f(B);

в) f(A)\f(B) ⊆ f(A\B).

При каких условиях включения б) и в) превращаются в равенство?

1.8. Доказать, что для любой функции f и любых множеств А и В имеет место равенство:

a) f^-1(А∩В) = f^-1(А) ∩ f^-1(B);

б) f^-1(А∪В) = f^-1(А) ∪ f^-1(B);

в) f^-1(А) = f^-1(А);

г) f^-1(А) = f^-1(А);

1.9. Построить графики и графы следующих бинарных отношений, заданных на множестве X = {1,2,3,4,5,6}:

a)x₁ φ x₂, если x₁ < x₂ + 1;

б)x₁ τ x₂, если x₁ ≤ x₂;

в)x₁ p x₂, если |x₁ - x₂| ≥ 3;

г){(a,b):a+b - четное}.

1.10. Определить, какими свойствами (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность) обладают следующие бинарные отношения:

а) φ = {(а, а), (а, b), (с, а), (b, d), (а, d), (b, с)} на множестве М = {а, b, с, d};

б) p_n, такое, что p_nk, если m-k — к делится на n, где m, k ∈ ℤ, a n ∈ ℤ и фиксировано;

в) φ, такое, что х φ у, если x — у ≤ 2, x ∈ ℝ, у ∈ ℝ.

1.11. Пусть р = {(x, у): х < у и у + х < 1,5} — бинарное отношение на множестве X = [0,1]. Построить графики отношений р и р². Исследовать свойства отношений р и р².

1.12. Найти D(p), R(p), р^-1, p॰p, p^-1॰p, p॰p^-1 для бинарных отношений:

а) р = {(х, y):x,у ∈ [0,1], x + у ≤ 1};

б) р = {(х, у): х,у ∈ [0,1], 2х ≥ 3у}.

1.13. Доказать, что для любого бинарного отношения р ⊆ A × А имеют место равенства:

а) D(p^-1) = R(р);

б) R(p^-1) = D(р);

в) D(p₁॰p₂) = p^-11(R(p₁)∩D(p₂));

г) R(p₁॰p₂) = p₂(R(p₁)∩D(p₂)).

1.14. Доказать, что для любых бинарных отношений p₁, p₂, p₃ ∈ A × A имеют место равенства:

а) p₁ ∩ p₁ = p₁ ∪ p₁ = p₁;

б) p₁॰(p₂॰p₃) = (p₁॰p₂)॰p₃;

в) p₁॰id_A = id_A॰p₁ = p₁;

г) (p₁ ∩ p₂)^-1 = p^-11 ∩ p^-12;

д) (p₁ ∪ p₂)^-1 = p^-11 ∪ p^-12;

е) (p)^-1 = (p^-1);

ж)(p₁॰p₂)^-1 = p^-12॰p^-11.

1.15. Доказать, что для бинарных отношений τ и р_i, i ∈ I, справедливы равенства:

1.16. Доказать, что для бинарного отношения р на А имеет место равенство р॰р^-1 = р^-1॰р = id_A, если и только если р — биекция А на А.

1.17. Найти необходимые и достаточные условия односторонней обратимости бинарного отношения р на множестве A, т.е. условия того, что р॰р^-1 = id_A (или р^-1॰р = id_A).

1.18. Построить бинарное отношение, которое является:

а) рефлексивным, симметричным, но нетранзитивным;

б) рефлексивным, антисимметричным, но нетранзитивным;

в) рефлексивным, транзитивным, но несимметричным;

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

1.19. Доказать, что для любых рефлексивных отношений р и σ на произвольном множестве A p∪σ⊆р॰σ.

1.20. Пусть А и В — конечные множества, содержащие m и n элементов. Сколько существует различных соответствий из А в В? Сколько можно задать функций из А в B, а среди последних — инъекций? При каких m и n существуют биекции и сколько их?

1.21. Пусть в ℝ³ задана плоскость ах + by + cz = 0. Точки с радиус-векторами r₁ и r₂ связаны отношением τ, если (r₁ - r₂),n) = 0, где n — нормаль к плоскости, а (⋅, ⋅) — скалярное произведение векторов. Показать, что τ — отношение эквивалентности. На какие классы эквивалентности разбивается ℝ³? Указать фактор-множество множества ℝ³ по данному отношению эквивалентности.

1.22. Пусть А — конечное множество. Какое отношение эквивалентности на нем дает наибольшее число классов эквивалентности? Сколько классов эквивалентности при этом будет? Сколькими способами можно задать отношение эквивалентности, разбивающее А на два класса?

1.23. Доказать, что число различных отношений эквивалентности на n-элементном множестве удовлетворяет формуле

где p_i — число различных отношений эквивалентности на i-элементном множестве.

1.24. Доказать, что композиция p₁॰p₂ двух эквивалентно стей p₁ и p₂ является эквивалентностью тогда и только тогда, когда p₁॰p₂ = p₂॰p₁

1.25. Описать наименьшее по включению отношение эквивалентности, содержащее данные эквивалентности р и σ на А. Каким будет это отношение, если p॰σ = σ ॰ p?

1.26. Пусть бинарное отношение v определено на множестве положительных рациональных чисел следующим образом: (a/b) v (c/в), если ad ≤ bс. Показать, что v является отношением линейного порядка.

1.27. Пусть А — произвольное множество и р, σ — бинарные отношения на множестве 2^A × 2^A: (Р, Q) σ (X, У), если Р ⊆ X и Q ⊆ У, а (Р, Q) р (X, У), если (PΔQ) ⊆ (XΔY). Являются ли р и σ отношениями порядка?

1.28. Пусть М — множество квадратных матриц типа 2x2, элементами которых являются целые числа. Выяснить, является ли бинарное отношение τ, заданное на множестве М, отношением порядка или отношением линейного порядка:

а) А τ B, если а_ij, i,j, = 1,2,A,B ∈ M;

б) А τ B, если а_ij, i,j, = 1,2 и хотя бы для одной пары элементов неравенство строгое, А В ∈ М.

1.29. Пусть F — множество функций, непрерывных на отрезке [а, b]. Проверить, является ли заданное отношение отношением указанного вида:

1.30. Пусть p₁ и p₂ — линейные порядки на множестве А. Когда p₁ ॰ p₂ — линейный порядок? У к а з а н и е: докажите, что если p₁ ≠ p₂, то p₁ ॰ p₂ не является линейным порядком.

1.31. Всегда ли транзитивна композиция транзитивных бинарных отношений?

У к а з а н и е: постройте пример конечного упорядоченного множества, в котором композиция исходного и двойственного порядка не является транзитивным отношением.

1.32. Пусть А и В — конечные множества. Используя метод математической индукции, доказать, что |А × В| = |А||В|. Пусть A₁, ..., А_n — конечные множества. Доказать, что |A₁× ...× А_n| = |A₁|...| А_n|.

1.33. Какую мощность имеет множество простых чисел?

1.34. Пусть А — множество всех многочленов степени не выше n, имеющих коэффициенты заданного вида. Определить мощность этого множества, если: а) все коэффициенты многочленов рациональные; б) свободный член действительный, а все остальные коэффициенты рациональные.

1.35. Доказать счетность следующих множеств:

а) множества всех многочленов с рациональными коэффициентами;

б) множества всех попарно непересекающихся открытых шаров в ℝⁿ;

в) множество всех цифр 8, расположенных на плоскости так, что ни одна пара цифр не имеет общих точек, кроме, может быть, точек касания.

1.36. Определить мощность множество всех точек плоскости, у которых:

а) обе координаты рациональные;

б) первая координата рациональная, а вторая — иррациональная.

1.37. Доказать, что следующие множества имеют мощность континуума:

а) множество ℕ^ω всех бесконечных последовательностей натуральных чисел;

б) множество №° всех последовательностей натуральных чисел;

в) множество ℕ^∞ всех (конечных или бесконечных) последовательностей элементов из конечного множества А.

1.38. Доказать, не используя теорему 1.20, что множество 2^[0,1] имеет мощность большую, чем мощность континуума.

У к а з а н и е: установите биекцию множества 2^[0,1] на множество всех функций из [0,1] в (0,1) (характеристических функций подмножеств отрезка [0,1]), а затем обобщите „диагональную" конструкцию из доказательства теоремы 1.15.