О числе линейно упорядочиваемых бинарных отношений на конечном множестве

Размещено на http://www.allbest.ru/

О числе линейно упорядочиваемых бинарных отношений на конечном множестве

Титов Георгий Николаевич

Титов Николай Георгиевич

Лысенко Александра Васильевна

Аннотации

Понятие частично упорядоченного множества является фундаментальным для современной теоретико-множественной математики. Проблема линейного упорядочивания множеств с заданными на них бинарными отношениями широко известна. Всякий частичный порядок на конечном множестве линейно упорядочиваем, но не всякое бинарное отношение на этом множестве является линейно упорядочиваемым. До сих пор не известна формула для подсчета числа частичных порядков на данном конечном множестве. Оказывается, формула для подсчета бинарных линейно упорядочиваемых отношений на конечном множестве существует. Выводу этой формулы и посвящена настоящая статья. В ходе доказательства, существенную роль играет факт из работы Г.Н. Титова [9] о том, что бинарное отношение на конечном множестве линейно упорядоченно тогда и только тогда, когда любой диагональный блок матрицы, полученной из матрицы бинарного отношения в результате обнуления элементов главной диагонали, содержит хотя бы одну нулевую строку (под диагональным блоком матрицы мы понимаем всякую матрицу, составленную из элементов, стоящих на пересечении строк и столбцов данной матрицы с одинаковыми номерами). Основным результатом статьи является теорема, позволяющая по формуле найти число линейно упорядочиваемых бинарных отношений на множестве из n элементов. Также получена рекуррентная формула для числа линейно упорядочиваемых (иррефлексивных) бинарных отношений на конечном множестве из n элементов, которая приводится в лемме

Ключевые слова: БИНАРНОЕ ОТНОШЕНИЕ, ЧАСТИЧНЫЙ ПОРЯДОК, МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ, ИРРЕФЛЕКСИВНОЕ БИНАРНОЕ ОТНОШЕНИЕ, ЛИНЕЙНОЕ УПОРЯДОЧИВАНИЕ

Physical-Mathematical sciences

THE NUMBER OF LINEARLY ORDERABLE BINARY RELATIONS ON A FINITE SET

Titov Georgy Nikolaevich

Cand. Phys.-Math. Sci., associate Professor

RSCI SPIN-code: 8910-6262

Titov Nikolay Georgievich

lecturer

RSCI SPIN-code: 7871-1889

Lysenko Aleksandra Vasil'evna

Student

Kuban State University, Krasnodar, Russia

Partially ordered set is a basic concept of modern set-theoretic mathematics. The problem of linear set ordering with given binary relations is well-known. Every partial order over a finite set can be linearly ordered, but not every binary relation over this set can be linearly ordered as well. Up to now, there is no known formula for calculating the number of partial orders over a given finite set. It appears that there is a formula for calculating linearly ordered binary relations over a finite set. This article is concerned with derivation of this formula. The fact from work of G.N. Titov [9] that a binary relation over a finite set is linearly ordered if and only if any diagonal block, derived from the binary relation matrix as a result of setting main diagonal elements to zero, contains at least one zero row (diagonal block of matrix means any matrix composed of elements at the crossings of rows and columns of a given matrix with the same numbers), plays a key role in process of corroboration. The main conclusion of the article is a theorem that allows to find the number of linearly ordered binary relations over a set of n elements using the formula. A recurrence formula for the number of linearly ordered (irreflexive) binary relations over a finite set of n elements, provided in the lemma, was derived as well

Keywords: BINARY RELATION, PARTIAL ORDER, MATRIX OF THE BINARY RELATION, IRREFLEXIVE BINARY RELATION, LINEAR ORDERING

В статье используются стандартные понятия теории бинарных отношений и теории групп [1-4]. Известна проблема линейного упорядочивания множеств (Linear Ordering Problem) [6], в связи с которой в научной литературе, например, [5-9] изучаются те или иные её аспекты. Основным результатом статьи является следующая

Теорема. Число линейно упорядочиваемых бинарных отношений на множестве из n элементов при ? равно числу

(1)

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

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

Перед формулировкой леммы с целью строгости изложения результатов введем некоторые обозначения и некоторые известные понятия. Полагаем, что ? - множество натуральных чисел; - число элементов (мощность) множества ; ?n = {} при ?; ?n ?n - бинарное отношение на множестве ?n; Bn - множество бинарных отношений на ?n; Mn - множество матриц размеров , состоящих из нулей и единиц; - матрица бинарного отношения на ?n, то есть матрица, полученная по правилу: при и при для всех ?n; Bn - частичный порядок на ?n, если для всех ?n (рефлексивность), из следует для всех ?n (транзитивность), из следует для всех ?n (антисимметричность); частичный порядок на ?n называют линейным порядком на ?n, если для всех ?n имеем или ; Bn - иррефлексивное отношение, если при всех ?n; если Bn и , где - линейный порядок на ?n, то называем линейно упорядочиваемым бинарным отношением на ?n; число линейно упорядочиваемых отношений на ?n обозначаем через , а число линейно упорядочиваемых иррефлексивных бинарных отношений на ?n обозначаем через . Очевидно, что . Другие обозначения будем описывать по тексту. множество математика бинарный

Замечаем, что абстрагируясь от природы элементов множества при , где ?, можно считать, что ?n. В связи с этим доказательство теоремы сводится к доказательству равенства числа (1) числу линейно упорядочиваемых отношений на ?n.

Лемма. При ? имеем

(2)

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

Перед доказательством леммы приведем ещё ряд обозначений, связанных с подстановками, а также сформулируем простейшие известные утверждения из [1-2, 4, 6], которые понадобятся нам в дальнейшем.

Sn - симметрическая группа подстановок n-ой степени, то есть группа биекций ?n на ?n; если Sn и Bn, то - бинарное отношение на ?n, определенное по правилу: тогда и только тогда, когда , то есть для любых ?n; пары <?n,> и <?n, >, где Bn, называют изоморфными, если существует подстановка Sn такая, что тогда и только тогда, когда для всех ?n (при этом сама подстановка называется изоморфизмом <?n,> на <?n, >); при Sn и Mn через обозначаем матрицу, для которой при всех ?n; в заключении, через Ln обозначим множество матриц линейно упорядочиваемых иррефлексивных бинарных отношений на ?n, а через Ln, где ?n и - различные элементы из ?n, - множество матриц из Ln, у которых строки с номерами являются нулевыми.

Теперь приведем ряд известных или легко получаемых непосредственно из определений утверждений 1-9, некоторые из которых в тексте будем использовать по умолчанию:

1. Отображение Bn >Mn, определенное по правилу: для всех Bn, является биекцией, в частности,

|Bn| = |Mn | = ;

2. Bn - иррефлексивное бинарное отношение на ?n тогда и только тогда, когда все элементы на главной диагонали матрицы равны нулю;

3. При ?n имеем LnLn(it);

4. Sn действует на множестве Mn по правилу: для всех Sn и Mn;

5. Sn действует на множестве Bn по правилу: для всех Sn и Bn;

6. Для всех Sn и Bn имеем ;

7. Sn - изоморфизм <?n,> на <?n, > тогда и только тогда, когда ;

8. Для всех Bn и Sn имеем и , а также тогда и только тогда, когда ;

9. При изоморфизме пар <?n,> на <?n, >, где Bn, выполнимость для отношения одного из условий: рефлексивность, иррефлексивность, транзитивность, антисимметричность или условие линейного порядка автоматически влечет выполнимость соответствующего условия для отношения . Другими словами, если для некоторой подстановки Sn имеем или , то указанные условия для и для будут выполняться или не выполняться одновременно.

Теперь докажем предложения 1-8, которые понадобятся нам в ходе доказательства леммы и теоремы.

Предложение 1.

Пусть - бинарное отношение на ?n (?) и ? матрица, полученная из матрицы в результате обнуления элементов, стоящих на главной диагонали. Тогда линейно упорядочиваемо в том и только в том случае, когда любой диагональный блок матрицы (то есть матрица, стоящая на пересечении строк и столбцов матрицы с одинаковыми номерами) содержит хотя бы одну нулевою строку.

Доказательство. В теореме из источника [8] доказано, что отношение Bn вложимо в некоторый частичный порядок тогда и только тогда, когда каждый диагональный блок матрицы имеет нулевую строку. Заметим, что всякий частичный порядок на ?n содержится в некотором линейном порядке на ?n, например, это следует из теоремы 4 в главе 2.4 источника [2]. Это замечание и доказывает истинность предложения 1.

Предложение 2.

Ln(i)| при ?.

Доказательство. Согласно предложению 1 матрица любого линейно упорядочиваемого иррефлексивного бинарного отношения в силу равенства должна содержать нулевую строку. Поэтому для некоторого ?n имеем Ln(i). Из этого следует, что

Ln Ln(i).

Откуда в виду

|Ln|

получаем требуемое равенство, которое и доказывает предложение 2.

Предложение 3.

Пусть ?n, ?n и - различные числа из ?n. Тогда |Ln | = |Ln |.

Доказательство. Пусть J = ?n \. Если , то есть ?n, то множества Ln и Ln просто совпадают и доказывать нечего. Пусть и . Рассмотрим подстановку

.

Пусть Ln , то есть для некоторого линейно упорядочиваемого иррефлексивного бинарного отношения на ?n имеем . Тогда

, а значит

для любых ?n. Откуда следует, что для любых ?n имеем . Пусть ?k, тогда s-ая строка матрицы A является нулевой, поэтому для любых ?n имеем

.

Но это означает, что все элементы -ой строки матрицы будут равны нулю, то есть в силу произвольности выбора ?k у матрицы все строки с номерами являются нулевыми. С другой стороны по утверждению 9 - тоже линейно упорядочиваемое иррефлекствное отношение на ?n, а значит, получаем, что Ln .

Итак, мы показали, что для любой матрицы Ln найдется матрица , лежащая в Ln . Аналогично рассуждая, можно показать, что для любой матрицы B из Ln найдется матрица , лежащая в Ln . Но тогда между элементами множеств Ln и Ln установлено взаимно однозначное соответствие. Откуда следует, что |Ln | = |Ln |. Предложение 3 доказано.

Предложение 4.

Пусть Ln+1, где ?. Тогда после вычеркивания в A первой строки и первого столбца получим матрицу B такую, что Ln.

Доказательство. Пусть Bn так, что . Иррефлексивность отношения следует из того, что на главное диагонали матрицы B как и ввиду Ln+1 на главное диагонали матрицы A, будут стоять нули. Согласно предложению 1 каждый диагональный блок матрицы A имеет нулевую строку, а значит, каждый диагональный блок матрицы B тоже имеет нулевую строку. Но тогда по тому же предложению 1 получаем, что - линейно упорядочиваемое отношение на ?n. В силу отмеченной иррефлексивности отношения получаем, что матрица лежит в Ln. Это и доказывает предложение 4.

Предложение 5.

Пусть Mn+1, где ?, и B - матрица, полученная из A в результате вычеркивания первой строки и первого столбца. Тогда, если первая строка матрицы A является нулевой и Ln, то Ln+1.

Доказательство. Пусть Bn и Bn+1 так, что и . По условию Ln, в частности, - иррефлексивно, а значит, все элементы на главной диагонали B равны нулю. Так как первая строка матрицы A является нулевой, то все элементы из A, стоящие на главной диагонали, тоже равны нулю. Откуда следует, что отношение является иррефлексивным. Далее, в силу Ln, отношение линейно упорядочиваемо, и поэтому согласно предложению 1 каждый диагональный блок матрицы B содержит нулевую строку. Но тогда каждый диагональный блок матрицы A тоже должен содержать нулевую строку, так как, если первая строка диагонального блока из A является ненулевой, то этот блок будет диагональным блоком из B. Откуда согласно предложению 1 следует, что - линейно упорядочиваемое, как показано выше, иррефлексивное бинарное отношение на ?n+1, а значит лежит в ?n+1. Предложение 5 доказано.

Предложение 6.

|Ln+1(1)| = ,

где ?.

Доказательство. Пусть Ln+1(1). Согласно предложению 4 имеем Ln, где B - матрица, полученная из A в результате вычеркивания первой строки и первого столбца. Таким образом, каждой матрице A из Ln+1(1) соответствует единственная, полученная указанным способом, матрица Ln. С другой стороны, для всякой матрицы Ln, согласно предложению 5, любая матрица Mn+1 с нулевой первой строкой, из которой B получатся в результате вычеркивания первой строки и первого столбца, обязательно лежит в Ln+1(1). Но таких матриц A для фиксированной матрицы Ln можно построить ровно штук (число способ расстановки чисел 0 и 1 на места в матрице A). Таким образом, общее число матриц в Ln+1(1) оказывается равным |Ln|, то есть |Ln+1(1)| = , что и доказывает предложение 6.

Предложение 7.

|Ln+1|= ,

где ? и ?n.

Доказательство. При (в частности, при ) предложение 7 следует из предложения 6. Пусть далее . После вычеркивания в матрице из Ln+1 первой строки и первого столбца согласно предложению 4 получаем матрицу из Ln, у которой первые строк являются нулевыми, а значит, матрицу из Ln. С другой стороны, если к любой матрице из Ln мы припишем сверху нулевую строку и слева столбец, у которого первые компонент являются нулями, а остальные компонент произвольными (0 или 1), то согласно предложению 5 получим матрицу из Ln+1. Причем у этой матрицы из Ln+1 первые k строк будут нулевыми, а значит она будет принадлежать Ln+1. Таким образом число матриц в Ln+1 равно произведению числа на число матриц в Ln+1, то есть |Ln+1|= |Ln|.

Теперь, проводя индукцию по n, по предположению индукции имеем

|Ln| = ,

где ? и ?n-1 (учли, что ). Откуда следует, что

|Ln+1|=|Ln|=, а значит |Ln+1|=

и предложение 7 доказано.

Предложение 8.

,

где ?.

Доказательство. Если на главной диагонали матрицы из Ln, соответствующей линейно упорядочиваемому бинарному отношению на ?n, расставить произвольным образом нули и единицы, то мы получим матрицу бинарного отношения, принадлежащего тому же линейному порядку на ?n, что и . С другой стороны, если у матрицы произвольного линейно упорядочиваемого бинарного отношения на ?n обнулить все элементы главной диагонали, то мы получим матрицу линейно упорядочиваемого иррефлексивного бинарного отношения на ?n, то есть получим матрицу из Ln. Таким образом, число линейно упорядочиваемых бинарных отношений на ?n равно произведению числа на число матриц в Ln. Последнее и означает справедливость предложения 8.

Теперь мы можем переходить к доказательству леммы и теоремы.

Доказательство леммы. При равенство (2) примет вид , что очевидно истинно. Поэтому далее полагаем, что . Согласно предложению 2 имеем:

Ll (i)|.

Применяя метод включений и исключений [2, §5.5], получаем

Ll |).

Учитывая утверждение 3, имеем Ll=Ll, а также, учитывая предложения 3, имеем |Ll|=|Ll|. Откуда получаем

Ll| =|Ll|=|Ll()|.

Поэтому приходим к равенствам

|Ll(= = |Ll ()| +|Ll ()|.

Далее, ясно, что при множество Ll состоит только из одной (нулевой) матрицы, то есть |Ll | = 1. С другой стороны, при согласно предложению 7 получаем |Ll | = . Откуда приходим к формуле

.

В заключение, производим замену в последней формуле t на (учитываем, что при ) и получаем формулу (2), что окончательно доказывает лемму.

Доказательство теоремы. Число (1) из формулировки теоремы обозначим через . Нам надо доказать истинность равенства для всех ?. Согласно предложению 8 . Полагая , приходим к равенству . Другими словами, нам нужно доказать для всех ? истинность равенства

. (3)

Докажем истинность равенства (3), то есть равенства , методом математической индукции по . При слева , а справа имеем и , , то есть , а значит . Теперь предположим истинность равенства (3), то есть равенства для всех при некотором ?. Докажем истинность равенства , что и завершит доказательство теоремы.

Согласно лемме по формуле (2) при , получаем

Но по предположению индукции при истинным является равенство , получаемое из формулы (3) при (напоминаем, что - число, стоящее в правой части равенства (3)). Поэтому после легких преобразований приходим к равенству

. (4)

С другой стороны, ввиду обозначения через числа в правой части равенства (3), занеся числовой множитель под знак суммы, получим:

. (5)

Для полного доказательства теоремы нам осталось установить равенство правых частей в (4) и в (5).

Сначала опередим число слагаемых в правой части равенства (4). Кроме одного слагаемого ещё имеется количество слагаемых, равное числу

.

Здесь учли, что число слагаемых под знаком суммы вида

равно числу подмножеств множества ?t-1, то есть равно числу (при полагаем ?t-1 ). Таким образом, в правой части равенства (4) содержится слагаемых.

Теперь определим число слагаемых в правой части равенства (5). Оно по аналогии с расчетом выше равно числу подмножеств множества ?k, то есть тоже равно числу .

Установим взаимно однозначное соответствие между слагаемыми в правых частях формул (4) и (5), при котором соответствующие слагаемые будут равны, что окончательно завершит наше доказательство.

Рассмотрим слагаемое в правой части формулы (5) при . Тогда и это единственное слагаемое при примет вид

,

то есть совпадает с первым слагаемым в правой части формулы (4).

Теперь рассмотрим произвольное слагаемое в правой части формулы (5) при фиксированном ?k+1, с условием и фиксированными целыми числами , для которых . Оно имеет вид:

. (6)

Далее, рассмотрим слагаемое в правой части формулы (4) под знаками двух сумм, для которого и , где (для удобства в записи этого слагаемого вместо букв пишем буквы соответственно). Тогда это слагаемое при указанных значениях и () примет вид:

.

В результате получили слагаемое вида (6), то есть и при для каждого слагаемого в правой части формулы (5) нам удалось указать, соответствующее только ему слагаемое из правой части формулы (4), которое ему равно. Теорема доказана.

Литература

1. Белоусов А.И., Ткачёв С.Б. Дискретная математика. М.: МГТУ им. Н.Э. Баумана, 2001, 744 с.

2. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976, 398 с.

3. Горчаков Ю.М. Теория групп. Тверь: ТГУ, 1998, 112 с.

4. Каргополов М. И, Мерзляков Ю.И. Основы теории групп. - 3-е изд., перераб. и доп.- М.: Наука, 1982. - 288 с.

5. Кислицын С.С. Конечные частично упорядоченные множества и соответствующие им множества перестановок / Математические заметки, т. 4, №5, 1968, с. 511-518.

6. Новиков О.И., Титов Н.Г., Титов Г.Н. О нумерациях конечных частично упорядоченных множеств / Научный журнал КубГАУ, №118(04), 2016 года, IDA [article ID]: 1181604006.

7. Roy T. Search and learning for the linear ordering problem with an application to machine translation / PhD thesis, Johns Hopkins University, 2009.

8. Титов Г.Н. О некоторых критериях триангулируемости матрицы / Вестник Армавирской государственной педагогической академии. Естественные и технические науки, №5, 2011, с. 89-92.

9. Титов Г.Н. Критерий принадлежности бинарного отношения отношению частичного порядка / Известия Кубанского государственного университета. Естественные науки, В. 1, 2012, с. 2-6.

References

1. Belousov A. I., Tkachjov S. B. Diskretnaja matematika. M.: MGTU im. N. Je. Baumana, 2001, 744 s.

2. Birkgof G., Barti T. Sovremennaja prikladnaja algebra. M.: Mir, 1976, 398 s.

3. Gorchakov Ju. M. Teorija grupp. Tver': TGU, 1998, 112 s.

4. Kargopolov M. I, Merzljakov Ju. I. Osnovy teorii grupp. - 3-e izd., pererab. i dop.- M.: Nauka, 1982. - 288 s.

5. Kislicyn S. S. Konechnye chastichno uporjadochennye mnozhestva i sootvetstvujushhie im mnozhestva perestanovok / Matematicheskie zametki, t. 4, №5, 1968, s. 511-518.

6. Novikov O. I., Titov N.G., Titov G.N. O numeracijah konechnyh chastichno uporjadochennyh mnozhestv / Nauchnyj zhurnal KubGAU, №118(04), 2016 go-da, IDA [article ID]: 1181604006.

7. Roy T. Search and learning for the linear ordering problem with an application to machine translation / PhD thesis, Johns Hopkins University, 2009.

8. Titov G. N. O nekotoryh kriterijah trianguliruemosti matricy / Vestnik Armavirskoj gosudarstvennoj pedagogicheskoj akademii. Estestvennye i tehnicheskie nauki, №5, 2011, s. 89-92.

9. Titov G. N. Kriterij prinadlezhnosti binarnogo otnoshenija otnosheniju chastichnogo porjadka / Izvestija Kubanskogo gosudarstvennogo universiteta. Estestvennye nauki, V. 1, 2012, s. 2-6.

Размещено на Allbest.ru

...