Задачи для самостоятельной работы

МОДУЛЬ ОЧП ОТНОШЕНИЕ ЧАСТИЧНОГО ПОРЯДКА

Вход

Модули ОСП, ОТН.

Выход

Понятия

 

Параметры	Понятие, обозначение	Определяющее понятие и видовые признаки
<X, £ >, AÍ X	Мажоранта A	ЭлементxÎX ½ a £ x " aÎA
<X, £ >, AÍ X	Наибольший элемент A	Мажоранта AÎ A
<X, £ >, AÍ X	Миноранта A	ЭлементxÎX ½ x £ a " aÎA
<X, £ >, AÍ X	Наименьший элемент A	Миноранта AÎ A
<X, £ >, AÍ X	Супремум A, supA	Мажорантa A, наименьшая во множестве всех мажорант А
<X, £ >, AÍ X	Инфимум A, infA	Минорантa A,наибольшая во множестве всех минорант А
<X, £ >, AÍ X	Максимальный элемент A, maxA	Элемент maxA Î A½ aÎA & a ³ maxA Þ a = maxA
<X, £ >, AÍ X	Минимальный элемент A, minA	ЭлементminA Î A½ aÎA & a £ minA Þ a = minA
<X, £ >, AÍ X	Ограниченное сверху подмножество	ПодмножествоA, для которого существует мажоранта
<X, £ >, AÍ X	Ограниченное снизу подмножество	ПодмножествоA, для которого существует миноранта
<X, £ >, AÍ X	Цепь	Подмножество A, в котором любые два элемента сравнимы (т.е. <A, £ > - ЛУМ)
<X, £ >, AÍ X	Cквозное подмножество	Подмножество A, у которого нет строгой мажоранты: не$ xÎX½ a < x "aÎA
<X, £ > - ЛУМ	Вполне упорядоченное множество	ЛУМ<X, £ > ½ ƹA Í X Þ A содержит наименьший элемент А
X,YÎ ObS	Многозначное отображение (м.о.)	ОтображениеF: X ® Ã(Y)
F: X® Ã(Y) - м. о.	Oднозначная ветвь м. о. F	Отображениеf: X ® Y½ xÎX Þ fx Î Fx

 

Элемент с.

 

Элемент м. Множество

Мажоранта Мах Миноранта Мin Подмножество Бинарное Упорядоченная

элемент элемент (п/м) отношение пара

 

Наибольший Супремум Наименьший Инфимум Отображение ЧУМ

элемент элемент

ЛУМ

 

Ограниченное Ограниченное Цепь Сквозное п/м Вполне

сверху п/м снизу п/м упорядоченное м.

 

Многозначное о. Однозначная ветвь м.о.

Утверждения

УТВ ОЧП-1 Аксиома сквозной цепи

B любом ЧУМ существует сквозная цепь

УТВ ОЧП-2 Лемма Цорна Пусть < X, £ > - ЧУМ. Тогда:

(" цепь в X ограничена сверху) Þ в X $ maxX

Если в ЧУМ < X, £ > всякая цепь ограничена сверху, то в X существует
максимальный элемент

УТВ ОЧП-3 Аксиома выбора Пусть F: X® Ã(Y) - м. о. Тогда:

(Fx ¹ Æ " xÎX) Û F имеет однозначную ветвь

Всякое м. о. с непустыми значениями имеет однозначную ветвь

УТВ ОЧП-4 Теорема о вполне упорядоченности

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

УТВ ОЧП-5 Принцип индукции Пусть < X, £ > - вполне упорядоченное м. A:X® Pr -параметрическое высказывание ½1) X'1 - наименьший элемент в X Þ A(1) истинно;

2) (1¹yÎX & A(x) истинно для "x < y) Þ A(y) истинно. Тогда A(x) истинно для "xÎX.

 

Умения

УМ ОЧП-1 Пусть A Í < X, £ > - ЧУМ. Найти (изобразить):

1.1 A;

1.2 Множество мажорант и минорант A (если $);

1.3 supA, infA (если $);

1.4 Наибольший и наименьший элементы A (если $);

1.5 Множества всех maxA и minA (если $);

1.6 Цепь в A, содержащую не менее 2 элементов (если $);

1.7 Cквозную цепь в X;

1.8 Два несравнимых элемента в A (если $).

 

Примеры

ПР ОЧП-1 Пусть X = < R², £ >; < x₁, x₂> £ < y₁, y₂> Û x₁ £ y₁ & x₂ £ y₂ ;

A = {<0, 1>, <1, 0>}

Множество мажорант А

R

 

 

<0, 1> -

<1, 1> = supA

 

Множество минорант А

infA = <0, 0> | R

<1, 0>

 

Рис. 1

Доказательства теорем

УТВ ОЧП-5 Принцип индукции Пусть < X, £ > - вполне упорядоченное м. A:X® Pr -параметрическое высказывание ½1) X'1 - наименьший элемент в X Þ A(1) истинно;

2) (1¹yÎX & A(x) истинно для "x < y) Þ A(y) истинно. Тогда A(x) истинно для "xÎX.

До-во. От противного. Пусть X_л ={xÎX | A(x) ложно}¹Æ =(X вполне упорядочено)Þ $ y – наименьший элемент в X_л; A(y) ложно =(1))Þ y¹1 =(определение наименьшего элемента)Þ "x < y¹1 A(x) истинно =(2))Þ A(y) истинно. Полученное противоречие доказывает теорему ¨

 

Задачи для самостоятельной работы

1. Пусть < X, £ > - ЧУМ, AÍX, BÍX. Доказать утверждение.

Варианты

1. Единственность наибольшего элемента в А.

2. Единственность наименьшего элемента в А.

3. Единственность supA.

4. Единственность infA.

5. Наибольший элемент в А является supA, но не наоборот.

6. Наименьший элемент в А является infA, но не наоборот.

7. Наибольший элемент в А является maxA, но не наоборот.

8. Наименьший элемент в А является minA, но не наоборот.

9. Если $ supA и $ supB и AÍB Þ supA £ supB.

10. Если $ infA и $ infB и AÍB Þ infA ³ infB.

 

Образец решения (5 задача).

b – наибольший элемент А =(?)Þ b = supA.

Д-во. b – наибольший элемент А Ü(определение наибольшего элемента А)Þ
b = мажоранта А & bÎA =(определение мажоранты А: a£m "aÎA)Þ b = мажоранта А & b£m " m – мажоранты А Ü(определение наименьшего элемента)Þ b = мажоранта А, наименьшая в множестве всех мажорант А Ü(определение supA)Þ b = supA ª

Контрпример. < R, £ >, A = (0,1). SupA = 1, наибольшего элемента А нет. Следовательно, supA не является наибольшим элементом.

 

 

2. Решите "свой" вариант теста (не забудьте указать вариант, например, ТЕСТ ОЧП - 1). Тестовое задание (ТЗ) с номером № студента (mod12) представьте с решением, на остальные ТЗ пришлите только ответы.

 

Варианты

1. ТЕСТ ОЧП-1

№	А	В	Дополнительная информация
	Мажоранта A	Наибольший элемент A	Понятия, <X, £ >, AÍ X
	Супремум A, supA	Наименьшая мажорантa A во множестве всех мажорант	Понятия, <X, £ >, AÍ X
	Инфимум A, infA	Миноранта AÎ A	Понятия, <X, £ >, AÍ X
	Ограниченное сверху подмножество	ПодмножествоA, для которого существует мажоранта	Понятия, <X, £ >, AÍ X
	Цепь	Подмножество A, у которого нет строгой мажоранты: не$ xÎX½a < x "aÎA	Понятия, <X, £ >, AÍ X
	Наибольший э. {{2}, {2,3,4}}	sup{{1}, {2,3,4}}	Множества, Ã(N)
	x - наибольший э. в А	x = supA	Параметрические высказывания, <X,£>, AÍX
	a £ x "aÎA & xÎA	x = supA	Параметрические высказывания, <X,£>, AÍX
	x - наименьший э. в А	x £ a "aÎA & xÎA	Параметрические высказывания, <X,£>, AÍX
	Х можно вполне упорядочить	В Х $ сквозная цепь	Пар-е выс-я, <X,£> - ЧУМ
	Миноранта А, наибольшая во множестве всех минорант	minA	Понятия, X,YÎ ObS
	Мажоранта А, наименьшая во м. всех мажорант А	maxA	Понятия, X,YÎ ObS

 

 

2. ТЕСТ ОЧП-2

№	А	В	Дополнительная информация
	Мажоранта AÎ A	ЭлементxÎX ½ a £ x "aÎA	Понятия, <X, £ >, AÍ X
	Наименьший элемент A	Миноранта AÎ A	Понятия, <X, £ >, AÍ X
	Наименьший элемент A	Инфимум A, infA	Понятия, <X, £ >, AÍ X
	Элемент м. А	ЭлементminA Î A½ aÎA & a £ minA Þ a=minA	Понятия, <X, £ >, AÍ X
	ПодмножествоA, для которого существует мажоранта	Cквозное подмножество	Понятия, <X, £ >, AÍ X
	Элемент S(X, Ã(Y))	Многозначное отображение	Понятия, X,YÎ ObS
	{min{{1}, {2,3}}}	{max{{1}, {2,3}}}	Множества, Ã(N)
	a £ x "aÎA & xÎA	x £ z "z - мажоранта А	Параметрические высказывания, <X,£>, AÍX
	x = supA	x £ z "z - мажоранта А	Параметрические высказывания, <X,£>, AÍX
	x1 £ x2 & x2 £ x1	x1, x2 - наименьшие э. в А	Параметрические высказывания, <X,£>, AÍX
	F:X®Ã(Y) | Fx¹Æ "xÎX	$ f:X®Y | fxÎFx "xÎX	Пар-е выс-я, <X,£> - ЧУМ
	supA	maxA	Понятия, X,YÎ ObS

 

3. ТЕСТ ОЧП-3

№	А	В	Дополнительная информация
	Миноранта AÎ A	Миноранта A	Понятия, <X, £ >, AÍ X
	Наибольшая минорантa Aво множестве всех минорант	ЭлементxÎX ½ x £ a " aÎA	Понятия, <X, £ >, AÍ X
	Наименьший элемент A	Минимальный элемент A, minA	Понятия, <X, £ >, AÍ X
	ОтображениеF:X®Ã(Y)	Элемент S(X,Y)	Понятия, X,YÎ ObS
	Отображениеf: X ® Y½ xÎX Þ fx Î Fx	Функциональное отношение в XÈY	Понятия, X,YÎ ObS
	sup{Æ, {2}, {3,4}}	sup{Æ, {2}, {3}, {4}}	Множества, Ã(N)
	inf{{2,3}, {1,2,3}, {3,4}}	sup{{2,5}, {1,2,5}}	Множества, Ã(N)
	{{2}, Æ, {2,3}} - цепь	{{2}, Æ, {2,3}} - сквозное множество	Параметрические высказывания, Ã({1,2,3})
	x = infA	x - наименьший э. в А	Параметрические высказывания, <X,£>, AÍX
	x = minA	x - наименьший э. в А	Параметрические высказывания, <X,£>, AÍX
	supA единственен	infA единственен	Параметрические высказывания, <X,£>, AÍX
	infA	minA	Понятия, X,YÎ ObS

 

4. ТЕСТ ОЧП-4

№	А	В	Дополнительная информация
	Наименьшая мажорантa A во множестве всех мажорант	Наименьший элемент A	Понятия, <X, £ >, AÍ X
	Элемент maxA Î A½ aÎA & a³maxAÞa=maxA	Наибольший элемент A	Понятия, <X, £ >, AÍ X
	ПодмножествоA, для которого существует миноранта	Элемент системы всех множеств	Понятия, <X, £ >, AÍ X
	ЧУМ А	Подмножество A, в котором любые два элемента сравнимы	Понятия, <X, £ >, AÍ X
	Oднозначная ветвь м. о. F	Отображениеf: X ® Y½ xÎX Þ fx Î Fx	Понятия, X,YÎ ObS
	Наибольшая миноранта м. {{1}, {2}, {1,2}}	Наименьший э. м. {{1}, {1,3,5}}	Множества, Ã(N)
	x = maxA	x - наибольший э. в А	Параметрические высказывания, <X,£>, AÍX
	x1, x2 - наибольшие э. в А	x2 £ x1 & x1 £ x2	Параметрические высказывания, <X,£>, AÍX
	С - сквозная цепь в <X,£>	$yÎX | x£y " xÎC	Пар-е выс-я, <X,£> - ЧУМ, в котором " цепь ограничена сверху
	" цепь в Х ограничена сверху	В Х $ максимальный э. maxX	Пар-е выс-я, <X,£> - ЧУМ
	$ сквозная цепь в Х	$yÎX | xÎX & x ³ y Þ x = y	Пар-е выс-я, <X,£> - ЧУМ
	Э. yÎA | aÎA & a £ y Þ a = y	infA	Понятия, X,YÎ ObS

ã Калмыков А.А. 2003. m_ochp.doc