флеров

Системы общих представителей

Идея замены множеств их представителями оказалась плодотворной и получила последующее развитие. Системы представителей выделяются с учетом условий задач или целей теоретических обобщений. Например, задачи о разбиении множеств привели к понятию систем общих (одновременных) представителей.

Пусть даны два различных разбиения одного и того же множества S на n непересекающихся непустых подмножеств:

S = A₁  A₂  ...  A_n = B₁ ...  B_n ;

A_i  A_j = , ij, i,j [n];

B_i  B_j = , ij, i,j [n].

Если существует подмножество O  S, состоящее из n различных элементов x₁ ,..., x_n , которые являются одновременными представителями множеств A_i и B_j то оно называется системой общих представителей (с.о.п.).

Теорема 1.22. Два разбиения множества S, S = A₁  A₂  ...  A_n и S =B₁ ...  B_n тогда и только тогда имеют с.о.п., когда любые m из множеств B_i содержатся не менее, чем в m из множеств A_j , m n.

Доказательство. Необходимость, как и в случае c.р.п., очевидна. Достаточность доказывается простым сведением к теореме о с.р.п..

Рассмотрим A₁, ... , A_n  S.

Для каждого B_i , i =1,2, ... , m определим множество S_i, состоящее из A_j ( j = 1, ... , m ) с такими индексами j , что A_jB_i не пусто.

S_i = {A_j| A_jB_i  }.

Получим M(S) = {S₁ , S₂ ,..., S_n}.

Для M(S) существует с.р.п. .

Выбор различных представителей для каждого B_i дает свое A_j , причем пересечение между ними не пусто. В этом пересечении можно выбрать хотя бы один элемент, общий для A_j и B_i , т.е. общего представителя.

Содержание