Лемма Диксона - Википедия - Dicksons lemma

В математика, Лемма Диксона заявляет, что каждый набор ${ displaystyle n}$-наборы натуральные числа имеет конечное количество минимальные элементы. Этот простой факт из комбинаторика был приписан американскому алгебраисту Л. Э. Диксон, кто использовал его, чтобы доказать результат в теория чисел о идеальные числа.^[1] Однако лемма наверняка была известна ранее, например, Пол Гордан в своем исследовании теория инвариантов.^[2]

Пример

Бесконечно много минимальных пар действительных чисел Икс,у (черная гипербола), но только пять минимальных пар натуральных чисел (красные) имеют ху ≥ 9.

Позволять ${ displaystyle K}$ - фиксированное число, и пусть ${ Displaystyle S = {(х, у) середина ху geq К }}$ - множество пар чисел, произведение которых не меньше ${ displaystyle K}$. Когда определяется положительным действительные числа, ${ displaystyle S}$ имеет бесконечно много минимальных элементов вида ${ Displaystyle (х, К / х)}$, по одному на каждое положительное число ${ displaystyle x}$; этот набор точек образует одну из ветвей гипербола. Пары на этой гиперболе минимальны, потому что это невозможно для другой пары, принадлежащей ${ displaystyle S}$ быть меньше или равно ${ Displaystyle (х, К / х)}$ в обеих его координатах. Однако лемма Диксона касается только наборов натуральных чисел, а над натуральными числами существует лишь конечное число минимальных пар. Каждая минимальная пара ${ Displaystyle (х, у)}$ натуральных чисел имеет ${ Displaystyle х leq K}$ и ${ displaystyle y leq K}$, если Икс были больше, чем K тогда (Икс −1,у) также будет принадлежать S, что противоречит минимальности (Икс,у), и симметрично, если у были больше, чем K тогда (Икс,у −1) также будет принадлежатьS. Следовательно, над натуральными числами ${ displaystyle S}$ имеет самое большее ${ displaystyle K ^ {2}}$ минимальные элементы, конечное число.^{[примечание 1]}

Официальное заявление

Позволять ${ Displaystyle mathbb {N}}$ - набор неотрицательных целых чисел (натуральные числа ), позволять п - любая фиксированная константа, и пусть ${ displaystyle mathbb {N} ^ {n}}$ быть набором ${ displaystyle n}$-наборы натуральных чисел. Этим кортежам можно присвоить точечно частичный заказ, то заказ продукта, в котором ${ displaystyle (a_ {1}, a_ {2}, dots, a_ {n}) leq (b_ {1}, b_ {2}, dots b_ {n})}$ тогда и только тогда, когда для каждого ${ displaystyle i}$, ${ displaystyle a_ {i} leq b_ {i}}$. Набор кортежей, которые больше или равны некоторому определенному кортежу. ${ Displaystyle (а_ {1}, а_ {2}, точки, а_ {п})}$ формирует положительный ортодоксальный с его вершиной в данном кортеже.

В этих обозначениях лемму Диксона можно сформулировать в нескольких эквивалентных формах:

• В каждом подмножестве ${ Displaystyle S neq emptyset}$ из ${ displaystyle mathbb {N} ^ {n}}$, существует хотя бы один, но не более конечного числа элементов, которые минимальные элементы из ${ displaystyle S}$ для поточечного частичного порядка.^[3]
• Для каждой бесконечной последовательности ${ Displaystyle (х_ {я}) _ {я в mathbb {N}}}$ из ${ displaystyle n}$-наборы натуральных чисел, существует два индекса ${ displaystyle i$ такой, что ${ displaystyle x_ {i} leq x_ {j}}$ относительно поточечного порядка.^[4]
• Частично упорядоченный набор ${ Displaystyle ( mathbb {N} ^ {n}, leq)}$ не содержит бесконечного антицепи ни бесконечные (строго) убывающие последовательности из ${ displaystyle n}$- пары.^[4]
• Частично упорядоченный набор ${ Displaystyle ( mathbb {N} ^ {n}, leq)}$ это ну частичный порядок.^[5]
• Каждое подмножество ${ displaystyle S}$ из ${ displaystyle mathbb {N} ^ {n}}$ могут быть покрыты конечным множеством положительных ортантов, все вершины которых принадлежат ${ displaystyle S}$.

Обобщения и приложения

Диксон использовал свою лемму, чтобы доказать, что для любого данного числа ${ displaystyle n}$, может существовать лишь конечное число странный идеальные числа которые имеют самое большее ${ displaystyle n}$ главные факторы.^[1] Однако остается открытым вопрос, существуют ли вообще какие-либо нечетные совершенные числа.

В делимость отношения между п-гладкие числа, натуральные числа, все простые множители которых принадлежат конечный набор п, придает этим числам структуру частично упорядоченного множества, изоморфного ${ Displaystyle ( mathbb {N} ^ {| P |}, leq)}$. Таким образом, для любого набора S из п-гладких чисел существует конечное подмножество S так что каждый элемент S делится на одно из чисел этого подмножества. Этот факт использовался, например, чтобы показать, что существует алгоритм для классификации выигрышных и проигрышных ходов из начальной позиции в игре Серебряная чеканка, хотя сам алгоритм остается неизвестным.^[6]

Кортежи ${ Displaystyle (а_ {1}, а_ {2}, точки, а_ {п})}$ в ${ displaystyle mathbb {N} ^ {n}}$ однозначно соответствуют мономы ${ displaystyle x_ {1} ^ {a_ {1}} x_ {2} ^ {a_ {2}} dots x_ {n} ^ {a_ {n}}}$ над набором ${ displaystyle n}$ переменные ${ displaystyle x_ {1}, x_ {2}, dots x_ {n}}$. При таком соответствии лемму Диксона можно рассматривать как частный случай Базисная теорема Гильберта заявляя, что каждый многочлен идеальный имеет конечный базис идеалов, порожденных одночленами. В самом деле, Пол Гордан использовал эту переформулировку леммы Диксона в 1899 году как часть доказательства теоремы Гильберта о базисе.^[2]

Смотрите также

• Лемма Гордана

Примечания

Рекомендации