Учебник мануалов ВГУ по дискретке

Теория множеств		11
1)	последовательности непустых множеств Χ 1, Χ 2 ,..., Χ n ,..., такой, что
Χ 1	Χ 2 ... и Ι Χ n = ;
	n Ν

2)последовательности множеств, отличных от универсального множества

Λ , такой, что Χ 1 Χ 2 ... и Υ	Χ n = Λ ;
n	Ν

3) семейства множеств такого, что пересечение любого конечного числа множеств из этого семейства непусто, а пересечение всех множеств пусто.

	§ 2. Прямое произведение множеств.
		Бинарные отношения
Произведением (или			декартовым произведением) Χ	1 Χ	2 двух
непустых множеств Χ 1		и Χ 2	будем называть множество упорядоченных
пар (x1 , x2 ) , где	x1	Χ 1 ,	x2 Χ 2 . Это понятие выросло	из	понятия

декартовой системы координат. Данное понятие можно обобщить и						на
случай n множеств. Если Χ 1 , Χ 2 ,..., Χ n - n непустых множеств, то						их
произведение	состоит		из	всевозможных	упорядоченных наборов
(x1 , x2 ,..., xn ) ,	xk Χ	k , k = 1,..., n		элементов этих множеств. Если множества
Χ 1 = Χ 2 = ... =	Χ n =	Χ ,	то их	произведение	Χ 1 , Χ 2 ,..., Χ n обозначается

Χn . Так, символом R n обозначается множество упорядоченных векторов n

вещественных чисел.

Любое подмножество из произведения Χ Υ называется бинарным отношением. Если Χ = Υ , то бинарное отношение называется бинарным отношением на множестве Χ . Бинарные отношения обозначаются буквами φ , ρ , f ,... Если пара (x, y) принадлежит бинарному отношению ρ , то пишут

(x, y) ρ или x ρ y .

Для задания бинарного отношения ρ используют те же методы, что и

для произвольных множеств, кроме того, бинарное отношение, заданное на конечном множестве Χ , можно задать в виде графа, а бинарное отношение на множестве R можно задать в виде декартовой диаграммы. Под графом бинарного отношения мы понимаем схему, в которой элементы множества

Χ изображаются точками на плоскости, элементы x, y	Χ	, такие, что пара
(x, y) ρ соединяются стрелкой, направленной от x	к	y , пары (x, x) ρ

изображаются петлей вокруг точки x . Под декартовой диаграммой понимают изображение пар (x, y) ρ в декартовой прямоугольной системе

координат.

Областью определения бинарного отношения ρ называется множество

Dρ = { x Χ : y (x, y) ρ} .

Областью значений бинарного отношения ρ называется множество

Rρ = { y Υ : x (x, y) ρ} .

Теория множеств		12
Бинарное отношение ρ на множестве Χ				называется		рефлексивным,
если для любого x	Χ	пара (x, x) ρ . Если		Χ	- конечное множество, то
рефлексивность бинарного отношения ρ			означает, что на графе данного
бинарного отношения вокруг каждой точки x из Χ					есть петля. Если Χ			= R ,
то рефлексивность	бинарного отношения		ρ	с	точки зрения		декартовой
диаграммы означает,		что в число изображенных точек войдут все точки
прямой y(x) = x .
Бинарное отношение		ρ на множестве Χ	называется симметричным, если
для любых x, y Χ	из принадлежности пары (x, y) отношению						ρ следует
принадлежность этому отношению также пары ( y, x) . Если						Χ	- конечное
множество, то симметричность бинарного отношения ρ означает,								что на

графе данного бинарного отношения все присутствующие стрелки двусторонние. Если Χ = R , то симметричность бинарного отношения ρ с

точки зрения декартовой диаграммы означает, что изображенное множество

симметрично относительно прямой y(x) =				x .
Бинарное	отношение	ρ	на		множестве	Χ	называется
антисимметричным, если для любых x, y				Χ	из принадлежности пар (x, y)			и
( y, x) отношению	ρ следует	x =	y . Если		Χ - конечное множество,			то

антисимметричность бинарного отношения ρ означает, что на графе данного бинарного отношения все присутствующие стрелки односторонние.

	Бинарное отношение	ρ на множестве Χ		называется транзитивным,
если для любых x, y, z Χ		из принадлежности пар (x, y)			и ( y, z) отношению
ρ следует принадлежность этому отношению также пары (x, z) .
	Обратным отношением для ρ называется отношение
		ρ − 1 = {(x, y) :( y, x) ρ} .
	Композицией отношений ρ1 и ρ 2		называется отношение
	ρ 2 ο ρ1 = {(x, y) : z		( x, z) ρ1 ,( z, y) ρ 2 } .
	Для любых бинарных отношений выполняются следующие свойства:
	1. (ρ − 1)− 1 = ρ ;
	2. (ρ 2 ο ρ1) − 1 = ρ1− 1 ο ρ 2− 1.
	Задача 1. Перечислите элементы множеств Α			× Β ,	Β × Α :
1)	Α = {1,2} , Β ={ 3,4},5	;

2)Α = , Β = {1,2,3,4} .

Решение. По определению	{(a,b) : a Α , b Β } .
Α × Β =

13

Теория множеств

Порядок построения данного множества будет следующий: вначале перечислим все пары, первый элемент которых равен первому элементу множества Α , а второй элемент берется из множества Β в том порядке, в котором они записаны в множестве Β , затем аналогично берем второй

элемент из Α				и составляем пары со всеми элементами из Β																			и т.д.
	Аналогичен и метод построения множества
									Β Α =					{(b, a) : b Β , a Α } .
				(1,3),(1,4) (, 1,5) ,											(3,1),( 3,2)					,
	1) Α	Β	=									,		Β Α
					(2,3),( 2,4) (,										=		(4,1),( 4,2) , .
									2,5)						(5,1),( 5,2)
3)	Α	Β	=	Β	Α	= ,
									поскольку множество										Α	пусто и мы не можем
составить ни одной пары.
Задача 2. Пусть Α						= {3,4}			. Перечислите элементы множеств Α 4 .
Решение. По определению																							Α } =
				Α 4 =		{(a	, a	2	, a	3	, a	4	) : a Α		, a	2	Α , a	3		Α , a	4
						1								1
							(3,3,3,3),( 3,3,3,4) (,								3,3,4,3) (, 3,3,4,)4 ,
							(3,4,3,3),( 3,4,3,4) (,								3,4,4,3) (, 3,4,4,)4 ,
						=	(4,3,3,3),( 4,3,3,4) (,													.
															4,3,4,3) (, 4,3,4,)4 ,
							(4,4,3,3),( 4,4,3,4) (,								4,4,4,3) (, 4,4,4,)4

Задача 3. Пусть на плоскости задана декартова система координат. Изобразите на плоскости следующее множество:

Μ= [a,b] [ c, d] ,

где a,b, c, d R	a < b, c <	d .			Μ = [a,b] [ c, d]
Решение.	При построении прямого произведения
каждой точке x	из отрезка	[a,b]	ставятся пары	(x, y), y	[c, d] , поэтому в

результате получим множество

y

c

a	M	b	x

d

14

Теория множеств

Задача 4. Докажите следующее равенство:

(Α ∩ Β ) ( Κ ∩ Μ ) = ( Α Κ) ∩ ( Β Μ ) .

Решение. Равенство двух множеств мы докажем с помощью двух включений, объединив их одной записью. Заметим, что элементами

множеств в данном случае являются упорядоченные пары точек. Итак, пусть

(x, y) (

Α ∩ Β

) (

Κ ∩ Μ )

x ( Α ∩ Β)

, y ( Κ ∩ Μ)

x Α , x Β , y Κ , y Μ x Α , y Κ , x Β , y Μ

(x, y) Α Κ ,( x, y) Β Μ ( x, y) ( Α Κ) ∩( Β Μ) .

Задача 5.

Докажите, что для любых непустых множеств Α

, Β , Κ из

равенства (Α

Β ) ( Β

Α )

=

Κ Κ следует, что Α =

Β = Κ .

Решение. Для доказательства данного утверждения установим два

равенства Α

= Κ

и Β

=

Κ .

Для произвольных x

Α

и y

Β

(x, y) Α Β ( x, y) Κ Κ x Κ , y Κ Α Κ , Β Κ .

С другой стороны,

для произвольного x Κ

(x, x) Κ Κ (

x, x)

Α

Β

или

(x, x)

Β Α

x Α

и x Β Κ Α и Κ Β .

Таким образом, Α =

Β

=

Κ .

Задача

6.

На

множестве

Α

= {5,6,7,8,9,10,11,12,13,14,15}

задано

бинарное отношение

ρ =

{(x, y) : x делится на y} . Нарисуйте граф данного

бинарного отношения.

. Точки

Решение. Расположим

на

плоскости точки

множества Α

x, y Α

, для которых пара (x, y)

ρ ,

соединим стрелкой, направленной от

x к y . Пары (x, x) ρ

изобразим петлей вокруг точки x . Результатом такого

построения будет граф

5

6

7

8

9

10

11

12

13

14

Теория множеств	15

Задача 7. Для следующего бинарного отношения, определенного на множестве R , найдите область определения, область значений и нарисуйте

декартову диаграмму	ρ = {(x, y) : x2 = y}.
Решение. В соответствии с определением
Dρ =	{ x R : y	(x, y) ρ} = R .

Rρ = { y Υ : x (x, y) ρ} = R+ 0 .

Декартова диаграмма для данного бинарного отношения имеет вид

y

x

Задача 8. Для каждого из следующих бинарных отношений выясните, какими свойствами (рефлексивность, симметричность, антисимметричность,

транзитивность) оно обладает и какими не обладает.							{1,2,3} ;
1)	ρ =	{(1,2), (2,1),(	1,1) (, 1,3) (, 3,)2(, 3),3} на множестве Χ =
2)	ρ =	{(x, y) : x −	y Ζ } на множестве	Χ	=	R ;
3)	ρ =	{(x, y) : 2x =	3y} на множестве Χ	=	Ζ	;
4)	ρ =	{(x, y) : x	y} на множестве Χ	= Ρ	(Ζ	) .

Решение.
1)	Данное отношение не является рефлексивным, поскольку для точки
2 Χ	пара		(2,2) ρ ; не является симметричным, поскольку, например, пара
(1,3) ρ ,		а пара (3,1) ρ ; не является антисимметричным, поскольку,
например,		пары (1,2) и (2,1) принадлежат ρ ,				но 1 ≠ 2 ;	не	является
транзитивным, поскольку, например (3,2) ρ ,( 2,1)						ρ , а (3,1) ρ .
2)	Данное отношение является рефлексивным, поскольку для любой
точки	x	R	разность x −	x =	0 Ζ , т.е. (x, x) R ;	является симметричным,
поскольку			принадлежность		любой пары (x, y)	отношению	ρ	означает
x − y = k		Ζ	, но тогда	y −	x = − k Ζ , т.е. пара	( y, x) ρ ;	не	является

Теория множеств

16

антисиммеричным, поскольку, например,

пары (1.2,3.2)

ρ и (3.2,1.2)

ρ ,

но

3.2 ≠ 1.2 ;

является

транзитивным,

поскольку для

любых x, y, z

R

принадлежность пар (x, y)

и ( y, z)

отношению ρ

означает

x −

y =

k

Ζ

и

y − z = n Ζ

, но тогда x −

z =

k +

n

Ζ , т.е. (x, z)

ρ .

3)

Данное отношение не является рефлексивным, поскольку из всех пар

(x, x), x Ζ

только пара

(0,0)

ρ , ведь для всех остальных

x Ζ

не

выполнено

равенство

2x = 3x ;

не является

симметричным,

поскольку,

например,

пара (3,2) ρ

( 2 3 =

3 2 ), а пара (

2,3) ρ ( 2 2 ≠

3 3); является

антисимметричным, поскольку для любых

пар

(x, y)

ρ ,( y, x)

ρ

одновременно

выполняются

равенства

2x =

3y и

2 y = 3x ,

т.е.

9x =

4x

и

4 y =

9 y , но это может быть только в том случае, если x =

y =

0 ; не является

транзитивным,

поскольку,

например,

пара

(9,6) ρ

( 2 9 =

3 6 ),

пара

(6,4) ρ ( 2 6 =

3 4 ), но пара (9,4)

ρ ( 2 9 ≠

3 4 ).

4)

Данное

отношение

не

является

рефлексивным, поскольку

для

Ρ (Ζ ) пересечение

∩

= ,

т.е.

(

,

)

ρ ;

является симметричным,

поскольку

принадлежность

любой пары

(x, y)

отношению ρ

означает

x ∩

y ≠ ,

но

тогда

y ∩

x ≠

, т.е.

пара

( y, x)

ρ ;

не

является

транзитивным,

поскольку,

например,

пара

({1,2} {,

2},3 )

ρ

({1,2}

∩ { 2},3 {=}

2 ≠

)

и пара ({2,3} {, 3,6},7 )

ρ

({2,3} ∩ { 3,6},7 {=}

3

≠

),

но

пара ({1,2} {, 3,6},7 )

ρ , так как {1,2} ∩ { 3,6},7

=

.

Задача 9. Пусть на множестве R заданы следующие бинарные

отношения:

{(x, y) : x = y 2} ; ρ 2 = {(x, y) : x + y ≤ 2} ; ρ 3 = {(x, y) : x + y Ζ }

ρ1 =

Найдите обратные к данным бинарным отношениям и всевозможные

композиции этих бинарных отношений.
		Решение. Вначале выпишем обратные отношения:
ρ − 1	=	{(x, y) :( y, x)	ρ }	= ({	x, )y : y = x2 };
1		{(x, y) :( y, x)	1	= ({	x, )y : y + x ≤ 2} =
ρ − 1	=		ρ }			ρ	2		;
2		{(x, y) :( y, x)	2	= ({	x, )y : y + x Ζ } =
ρ − 1	=		ρ }			ρ		3		.
3			3

В качестве примера рассмотрим некоторые композиции рассматриваемых бинарных отношений:

ρ1 ο ρ 2 = {(x, y) : z ( x, z) ρ 2 ,(	z, y) ρ1} =
= {(x, y) : z x + z ≤ 2, z = y 2} =	{(x, y) : x + y 2 ≤ 2} ;
ρ 2 ο ρ1 = {(x, y) : z ( x, z) ρ1,( z, y) ρ 2} =
= {(x, y) : z x = z 2 , z + y ≤ 2} =				x +	y ≤ 2
		0,					=
	(x, y) : x ≥				+ y ≤
			− x			2
= {(x, y) : x ≥ 0, − x + y ≤ 2} ;

Теория множеств

17

ρ 2 ο ρ 3 = {(x, y) : z

( x, z) ρ 3 ,( z, y) ρ 2} =

=

{(x, y) : z x + z Ζ , z + y ≤ 2} =

= {(x, y) : z x + z = k Ζ , z + y ≤ 2} = ({ x, )y : k Ζ

k − x + y ≤ 2} = R × R

ρ 3 ο ρ 2 = {(x, y) : z ( x, z) ρ 2 ,( z, y) ρ 3} =

=

{(x, y) : z x + z ≤ 2, z + y Ζ } = R × R .

Остальные композиции постройте самостоятельно.

Задача 10. Пусть Χ

- произвольное множество,

обозначим символом

ΙΧ

отношение на множестве Χ

вида

ΙΧ

= {(x, y) : x = y} = ({ x,)x : x Χ } .

Докажите,

что

для

любого бинарного отношения ρ

между

элементами

множеств Α

и Β

выполняются равенства:

Решение.

ΙΒ

ο ρ = ρ ,

ρ οΙΑ = ρ .

} =

Ι

ο ρ = {(x, y) Α × Β : z Β ( x, z) ρ ,( z, y) Ι

=

Β

{(x, y) Α × Β : z Β ( x, z) ρ , z = y} = ({ x, )y

Β Α × Β (: x,)y ρ} = ρ;

ρ οΙΑ = {(x, y) Α × Β : z Α ( x, z) ΙΑ ,( z, y) ρ} =

= {(x, y) Α × Β : z Α

x = z,( z, y) ρ} = ({ x, )y Α × Β (: x,)y ρ} = ρ.

Задача 11. Пусть ϕ

,φ, χ бинарные

отношения,

определенные

на

множестве Χ

. Докажите следующие утверждения:

1)

если ϕ ,φ

- симметричные (антисимметричные) отношения, то (ϕ

∩ φ) − 1

- симметричное (антисимметричное) отношение;

2)

(ϕ \ φ) ο χ

( ϕ ο χ )

\( φ ο χ) .

Решение.

(ϕ

φ) − 1

1.

Пусть

ϕ ,φ

-

симметричные

отношения,

докажем,

что

∩

-

симметричное отношение. Пусть

( y, x) ϕ

(x, y) ( ϕ ∩ φ) − 1 ( y, x) ϕ ∩ φ

( y, x)

φ

(x, y) ϕ

симметричность ϕ ,φ

(x,

y) ϕ ∩

φ

(

y, x) ( ϕ

∩

φ) − 1;

(x, y) φ

Пусть

ϕ ,φ

-

антисимметричные отношения,

докажем,

что

(ϕ

∩

φ) − 1

-

антисимметричное отношение. Пусть

(x, y) ( ϕ ∩ φ)

− 1

( y, x)

ϕ ∩

φ

(x, y),( y, x)

ϕ

(x, y)

ϕ ∩ φ

(x, y),( y, x)

φ

− 1

( y, x) ( ϕ ∩ φ)

антисимметричность ϕ ,φ

x =

y .

2.

Докажем требуемое включение. Пусть

(x, y) ( ϕ ο χ )

\(

φ ο χ)

(

x, )y ϕ ο χ ,

(

x,)y φ ο χ

Теория множеств

18

z

(x, z) χ

(

)

χ

y) ϕ

x, z

(x, z) χ

(z,

(z, y) ϕ

z

(

)

χ

z

z

(z, y) ϕ \ φ

x, z

(z, y) φ

y)

φ

(z,

(x, y) ( ϕ \ φ) οχ

Задачи для самостоятельного решения

1.

Пусть Χ

= { , }

. Перечислите все элементы множеств Χ

3 , Χ

4 .

2.

Найдите геометрическую интерпретацию множества

Α

× Β ,

где Α

-

множество точек отрезка

[0,1] , а

Β

- множество точек квадрата с вершинами

в точках

(0,0),(

0,1)

,(

1,0) (, 1),1 .

3.

Доказать,

что

(Α

Β

) ( Κ Μ )

(

Α

Κ) ( Β

Μ )

.

При

каких

Α

, Β

, Κ , Μ включение можно заменить равенством.

4.

Доказать, что для произвольных множеств Α , Β , Κ :

1)

(Α

Β

)

Κ =

( Α Κ)

(

Β Κ)

;

2)

(Α \ Β

) × Κ =

(

Α × Κ) \(

Β × Κ)

;

3)

Α (Β \ Κ ) = ( Α Β ) \(

Α Κ) .

5.

Пусть

Α

≠

, Β

≠

и

(

Α Β

) ( Β

Α

)

= Κ Μ .

Доказать, что в этом

случае Α

=

Β

=

Κ

=

Μ .

6.

Перечислите все элементы бинарного отношения ρ и нарисуйте его граф:

1)

ρ = {(x, y) : x <

y} на множестве Χ

= {1,2,3,4,5} ;

2)

ρ =

{(x, y) : y =

x +

1}

на множестве Χ

=

{1,2,3,4,5,6,7,8,9,10} .

7.

Для каждого из следующих бинарных отношений, определенных на

множестве R ,

найдите область определения, область значений и нарисуйте

декартову диаграмму:

1)

ρ =

{(x, y)

: x ≤ y} ;

2)

ρ =

{(x, y) : x = y} ;

3)

ρ =

{(x, y) : x2 + 4 y 2 ≤ 1} ;

4)

ρ =

{(x, y) : x2 = y 2} ;

5)

ρ =

{(x, y) : y =

log2 x}

;

6)

ρ =

{(x, y) : y =

sin x} .

8.

Даны

бинарные

отношения

ρ

между

элементами множеств

Α и

Β ,

найдите область определения и область значений для данных бинарных

отношений:

1) Α = {1,2,3,4,5} , Β = {{}1{ , }1{,2 ,} {2},5 , 3} , ρ = ({ x, )y Α × Β : x y} ;

Теория множеств					19
2)	Α = Ζ × Ζ , Β = Q,	ρ	=		((a,b), c)	Α × Β : c =	a		;
							b
3)	Α = Ζ , Β = Q, ρ =	{(x, y) Α × Β : x y = 1} ;
4)	Α = Ζ , Β = Q, ρ =	{(x, y) Α × Β : b = 2a }.

9. Для каждого из следующих бинарных отношений выясните, какими

свойствами (рефлексивность, симметричность, антисимметричность,
транзитивность) оно обладает и какими не обладает:
1)	ρ =	{(x, y) R × R : x2 = y 2} ;
2)	ρ =	{(x, y) R × R : x2 + y 2 = 1} ;
3)	ρ =	{(x, y) R × R : x y >						1} ;
4)	ρ =	{(x, y) R × R : y =					x} ;
5)	ρ =	{(x, y) R × R : x + x2 = y + y 2} ;
6)	ρ = {(x, y) Ζ × Ζ : x ≤ y + 1} ;
7)	ρ =	{(x, y) Ζ		× Ζ : 3 делится на x + y}						;
8)	ρ = {(x, y) Ρ (Ζ ) × Ρ (Ζ ) : x								y} ;
9)	ρ = {(x, y) Ρ (Ζ ) × Ρ (Ζ ) : x ∩ y = } .
10. Пусть
ρ1 =	{(x, y) R × R : x = y 2 };							ρ 2 = {(x, y) R × R : x + y ≤ 5} ;
ρ 3 =	{(x, y) R × R : x3 = y} ;							ρ 4 =	{(x, y)	R × R : y = sin x} .
Найдите всевозможные композиции ρ i ο ρ k										i, k = 1,2,3,4.
11. Покажите, что равенство								ϕ οφ = φ οϕ		верно не для любых бинарных
отношений.
12. Докажите,			что	для	любого				бинарного отношения ρ выполняются
условия:		Dρ − 1 =	Rρ	и Rρ − 1	= Dρ .
13. Пусть		ϕ ,φ, χ - бинарные отношения, определенные на некотором
множестве. Докажите следующие утверждения:
1) (ϕ \ φ) − 1 = ϕ − 1 \ φ − 1;
2)	(ϕ ∩ φ) οχ ( ϕ ο χ ) ∩ ( φ ο χ) ;
3)	(ϕ οφ) − 1 = φ − 1 οϕ − 1 ;
4)	(ϕ φ) − 1 = ϕ − 1 φ − 1;
5)	(ϕ φ) ο χ = ( ϕ ο χ ) ( φ ο χ) .

14. Приведите примеры бинарных отношений:

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

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

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

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

Теория множеств		20
15. Докажите,	что если	ρ - транзитивное и симметричное бинарное
отношение на множестве Α		, область определения которого совпадает с	Α ,
то ρ рефлексивно.
	§ 3. Специальные бинарные отношения
Рефлексивное, симметричное и транзитивное отношение ρ			на
множестве Χ	называется	отношением эквивалентности на множестве Χ .

Для отношения эквивалентности вместо записи (x, y) ρ часто используют

запись x ≈ y (читается : x эквивалентен y )

Классом эквивалентности, порожденным элементом x , называется

подмножество множества Χ ,	состоящее из тех		элементов	y	Χ ,	для
которых (x, y) ρ . Класс эквивалентности, порожденный				элементом		x ,
обозначается через [x] :		: (x, y) ρ} .
[x] = { y Χ
Разбиением множества	Χ	называется	совокупность		попарно
непересекающихся подмножеств Χ		таких, что каждый элемент множества

Χпринадлежит одному и только одному из этих подмножеств. Всякое

разбиение множества Χ определяет на Χ	отношение эквивалентности ρ :
(x, y) ρ тогда и только тогда, когда	x и y принадлежат одному

подмножеству разбиения. С другой стороны, всякое отношение

эквивалентности ρ определяет разбиение	множества Χ	на классы
эквивалентности относительно этого отношения.
Совокупность классов эквивалентности	элементов множества Χ по
отношению эквивалентности ρ называется фактор-множеством множества

Χ по отношению ρ и обозначается Χ

/ ρ .

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

называется

отношением частичного

порядка

на

множестве Χ

и

вместо

записи

(x, y) ρ

для данного отношения часто используют запись

x ≤ y .

Отношение частичного порядка

на множестве Χ

, для которого любые два

элемента сравнимы, т.е. для любых

x, y Χ

выполнено либо

x ≤ y ,

либо

y ≤ x ,

называется

отношением

линейного

порядка.

Множество

Χ

с

заданным на нем частичным (линейным)

порядком называется частично

(линейно) упорядоченным.

Пусть

Χ -

непустое конечное множество,

на котором задано отношение

частичного

порядка. Запишем

x < y , если

x ≤ y и

x ≠ y . Говорят,

что

элемент y покрывает элемент x , если x < y и не существует такого элемента

u , что x < u < y . Для x < y можно записать x = x1 < x2 < ... < xn = y , где xi+ 1 покрывает xi .

Частично упорядоченные множества можно изображать с помощью так называемых диаграмм Хассе. На диаграмме Хассе элементы частично