ВЫБОРА ТЕОРЕМЫ

ВЫБОРА ТЕОРЕМЫ

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

1) Пусть - некоторое семейство подмножеств данного множества .

Набор различных элементов множества Тназ. системой различных представителей (с. р. п.) семейства S, если элемент наз. представителем множества . Напр., если и Sсостоит из то есть с. р. п. для- S, где элемент 5 представляет множество , элемент 2 - множество и т. д. Если же Sсоставить из множеств то для Sне существует с. р. п., так как вместе содержат только три элемента.

Теорема о системе различных представителей. Семейство тогда и только тогда имеет с. р. п., когда объединение каждых kмножеств из Sсодержит по крайней мере kразличных элементов, k=1, 2, ..., п.

Эта теорема доказана Ф. Холлом [3] (см. также [1], [2]). С ее помощью доказывается теорема о системе общих представителей, также относящаяся к В. т. Пусть


суть два разбиения множества Т, в к-рых ни одно из составляющих не пусто. Множество наз. системой общих представителей (с. о. п.) разбиений (1) и (2), если Rявляется с. р. п. как для семейства так и для семейства Напр., если и



Теорема о системе общих представителей. Разбиения (1) и (2) имеют с. о. п. тогда и только тогда, когда объединение каждых kмножеств из семейства Асодержит не более kмножеств из семейства (см. [1], [2]).

2) Пусть задана прямоугольная матрица. Линией в матрице наз. как строку, так и столбец этой матрицы.

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

Эта теорема сформулирована и доказана Д. Кёнигом ([4], с. 240; см. также [1], [2]). Она эквивалентна теореме Холла о с. р. п. Используется, напр., при доказательстве того, что нек-рые матрицы являются линейными комбинациями перестановочных матриц (перестановочная матрица - такая прямоугольная матрица Рразмера , состоящая из нулей и единиц, что , где Р' - транспонированная матрица Р, а I - единичная матрица порядка т; напр., перестановочная квадратная матрица порядка mсостоит из mединиц, расположенных так, что никакие две из них не лежат на одной линии). Иными словами, если дана матрица Аразмера , , элементами к-рой являются неотрицательные действительные числа, причем сумма элементов каждой строки в Аравна т' , а сумма элементов каждого столбца равна п', то где каждое Pi есть перестановочная матрица, а коэффициенты с i - неотрицательные действительные числа (ем. [1], [2]). В частности, если квадратная матрица Апорядка п, состоящая из нулей и единиц, такова, что суммы элементов по любой строке или любому столбцу равны целому положительному числу k, то


где все - перестановочные матрицы порядка п.3) Пусть Т - конечное множество и - множество всех его подмножеств, содержащих точно г элементов. Пусть


- произвольное упорядоченное разбиение Р r (Т).(на lсоставляющих А 1 , А 2 , . . ., Al ). Пусть q1,q2,...,ql - такие целые числа, что


Если существует такое подмножество, содержащее qi элементов множества Т, что все его подмножества, содержащие точно rэлементов, содержатся именно в Ai , то оно наз. (qi, А i )-подмножеством множества Т.

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

Эта теорема доказана Ф. Рамсеем ([5]; см. также [1], [2]). Примером приложения теоремы Рамсея служит следующий результат (см. [6], [1], [2]): для любого заданного целого числа существует такое целое число

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

Лит.: [1] Холл М., Комбинаторный анализ, пер. с англ., М., 1963; [2] Райзер Г. Д ж., Комбинаторная математика, пер. с англ., М., 1966; [3] Hall Ph., "J. London Math. Soc.", 1935, v. 10, p. 26-30; [4] Konig D., Theorie der Endlichen und Unendiichen Graphen, Leipzig, 1936; [5] Ramsеу F. P., "Proc. London Math. Soc.", (2), 1930, v. 30, p. 264-286; [6] Erdos P., Szekeres G., "Compositio Mathematica", 1935, v. 2, № 3, p. 463-70. M. П. Минеев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "ВЫБОРА ТЕОРЕМЫ" в других словарях:

  • Утверждения, эквивалентные аксиоме выбора — В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений: Аксиома выбора Теорема Цермело Принцип максимума Хаусдорфа Лемма Куратовского Цорна Эквивалентность этих предложений следует понимать в… …   Википедия

  • БОЛЬЦАНО - ВЕЙЕРШТРАССА ПРИНЦИП ВЫБОРА — метод доказательства, часто применяемый в математич. анализе и основанный на последовательном делении отрезка пополам и выборе из двух получившихся отрезков отрезка, обладающего нек рым свойством. Этот метод может быть применен, если свойство… …   Математическая энциклопедия

  • Простые теоремы в алгебре множеств — Курсы элементарной дискретной математики иногда оставляют у студентов ошибочное представление о том, что основой теории множеств является алгебра объединения, пересечения и дополнения множеств. Для того, чтобы получить представление о некоторых… …   Википедия

  • КЁНИГА ТЕОРЕМА — если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к рые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин линия… …   Математическая энциклопедия

  • РАЗЛИЧНЫХ ПРЕДСТАВИТЕЛЕЙ СИСТЕМА — для заданного семейства подмножеств множества S множество при любом взаимно однозначном отображении , обладающем свойством: для любого (здесь I произволь вое множество индексов). Другое название Р. п. с. R трансверсаль семейства F.… …   Математическая энциклопедия

  • ЦЕРМЕЛО АКСИОМА — выбора аксиома для произвольного (не обязательно дизъюнктного) семейства множеств. Эту аксиому Э. Цермело сформулировал в 1904 в виде следующего утверждения, названного им принципом выбора [1]: для любого семейства множества . можно выбрать из… …   Математическая энциклопедия

  • Теорема Гаусса —     Классическая электродинамика …   Википедия

  • ГЁДЕЛЬ — (Gödel) Курт (1906 1978) математик и логик, член Национальной Академии наук США и Американского философского общества, автор фундаментального открытия ограниченности аксиоматического метода и основополагающих работ в таких направлениях… …   История Философии: Энциклопедия

  • ГЁДЕЛЬ Курт (1906 - 1978) — математик и логик, член Национальной Академии наук США и Американского философского общества, автор фундаментального открытия ограниченности аксиоматического метода и основополагающих работ в таких направлениях математической логики, как теория… …   История Философии: Энциклопедия

  • ГЁДЕЛЬ — (Godel) Курт (1906 1978) австр. логик и математик. Участвовал в работе Венского кружка. В 1933 1939 приват доцент Венского ун та, в 1940 эмигрировал в США, с 1953 проф. Ин та высших исследований в Принстоне. Г. принадлежат ряд важнейших… …   Философская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»