Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математике наследственное свойство - это свойство объекта, которое наследуется всеми его подобъектами, причем значение подобъекта зависит от контекста. Эти свойства особенно рассматриваются в топологии и теории графов , а также в теории множеств .

В топологии [ править ]

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

Например, вторая счетность и метризуемость являются наследственными свойствами. Последовательность и хаусдорфова компактность слабо наследственные, но не наследственные. [1] Связность не является наследственной слабо.

Если P является свойством топологического пространства X и каждое подпространство также обладает свойством P , то X называется «наследственно P ».

В комбинаторике и теории графов [ править ]

Понятие наследственных свойств встречается во всей комбинаторике и теории графов, хотя они известны под разными именами. Например, в контексте шаблонов перестановок наследственные свойства обычно называют классами перестановок .

В теории графов , A наследственное свойство является свойство из графа , который также имеет место для (это «унаследовал» от) его индуцированных подграфов . [2] С другой стороны, наследственность сохраняется за счет удаления вершин. Класс графов называется наследственным, если он замкнут относительно индуцированных подграфов. Примерами классов наследственных графов являются независимые графы (графы без ребер), которые являются частным случаем (с c = 1) c- раскрашиваемости для некоторого числа c , будучи лесами , планарными , полными ,полная многосторонняя и т. д.

В некоторых случаях термин «наследственный» был определен со ссылкой на миноры графа , но это более правильно назвать второстепенным наследственным свойством. Из теоремы Робертсона – Сеймура следует, что мино-наследственное свойство можно охарактеризовать в терминах конечного набора запрещенных миноров .

Термин «наследственный» также использовался для свойств графа, замкнутых относительно взятия подграфов. [3] В таком случае свойства, замкнутые относительно взятия индуцированных подграфов, называются индуцированно-наследственными . Язык наследственных свойств и индуцированно-наследственных свойств предоставляет мощный инструмент для изучения структурных свойств различных типов обобщенных раскрасок . Наиболее важным результатом в этой области является теорема единственной факторизации. [4]

Монотонное свойство [ править ]

Нет единого мнения о значении « монотонного свойства » в теории графов. Примеры определений:

  • Сохраняется удалением краев. [5]
  • Сохраняется удалением ребер и вершин (т. Е. Свойство должно выполняться для всех подграфов). [2]
  • Сохраняется добавлением ребер и вершин (т. Е. Свойство должно выполняться для всех суперграфов). [6]
  • Сохранилось добавлением краев. [7] (Этот смысл используется в формулировке гипотезы Андераа – Карпа – Розенберга .)

Дополнительное свойство свойства, которое сохраняется при удалении ребер, сохраняется при добавлении ребер. Следовательно, некоторые авторы избегают этой двусмысленности, говоря, что свойство A монотонно, если A или A C (дополнение к A) монотонно. [8] Некоторые авторы решают эту проблему, используя термин « монотонное увеличение» для свойств, сохраняемых при добавлении некоторого объекта, и « монотонное уменьшение» для свойств, сохраняемых при удалении того же объекта.

В решении проблем [ править ]

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

Подмножество всех состояний, имеющие P плюс подмножество всех состояний, имеющих \ P образует разбиение множества состояний называется наследственный разделом . Это понятие может быть тривиально распространено на более различающие разделы, вместо свойств, с учетом аспектов состояний и их областей. Если состояния имеют аспект A , где d i ⊂ D является разбиением области D элемента A , то подмножества состояний, для которых A ∈ d i, образуют наследственное разбиение полного набора состояний тогда и только тогда, когда ∀ i , из любого состояния, гдеA ∈ D I только другие состояния , где A ∈ д я может быть достигнута.

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

Можно ли покрыть доску для шашек плиткой домино, каждая из которых покрывает ровно два соседних поля? Да. Что, если мы удалим верхнее левое и нижнее правое поля? Тогда никакое покрытие больше не возможно, потому что разница между количеством непокрытых белых полей и количеством непокрытых черных полей равна 2, а добавление плитки домино (которая покрывает одно белое и одно черное поле) сохраняет это число равным 2. Для a общее покрытие число равно 0, поэтому полное покрытие не может быть достигнуто с начальной позиции.

Это понятие впервые было введено Лораном Шиклоши и Роучем. [9]

В теории моделей [ править ]

В теории моделей и универсальной алгебре , класс K из структур данной подписи , как говорят, имеет наследственную собственность , если каждая подструктура структуры в K снова в K . Вариант этого определения используется в связи с теоремой FRAISSE в : класс K конечно порожденных структур имеет наследственную собственность , если каждая конечно порожденная подструктура снова в K . Смотрите возраст .

В теории матроидов [ править ]

В матроиде каждое подмножество независимого набора снова является независимым. Это также иногда называют наследственным свойством.

В теории множеств [ править ]

Рекурсивные определения с использованием прилагательного «наследственный» часто встречаются в теории множеств .

Множество называется наследственным (или чистый ) , если все ее элементы являются наследственные множества. Это бессодержательно правда , что пустое множество является наследственным множество, и , таким образом, набор , содержащий только пустое множество является наследственным множество, и рекурсивно так , к примеру. В формулировках теории множеств, которые предназначены для интерпретации во вселенной фон Неймана или для выражения содержания теории множеств Цермело – Френкеля., все наборы являются наследственными, потому что единственный вид объекта, который даже является кандидатом на роль элемента набора, - это другой набор. Таким образом, понятие наследственной совокупности интересно только в контексте, в котором могут существовать уэлементы .

Аналогично определяется пара понятий:

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

Из вышесказанного следует, что в ZFC можно определить более общее понятие для любого предиката . Говорят, что множество x наследственно обладает свойством, если ему удовлетворяет сам x и все элементы его транзитивного замыкания , т . Е. Эквивалентно, x наследственно удовлетворяет тогда и только тогда, когда он является членом транзитивного подмножества [10] [11]. Таким образом, свойство (набора) называется наследственным, если оно наследуется каждым подмножеством. Например, упорядоченность - это наследственное свойство, а значит, конечность. [12]

Если мы создадим экземпляр в приведенной выше схеме с « x имеет мощность меньше, чем κ», мы получим более общее понятие набора, наследственно имеющего мощность меньше, чем κ, обычно обозначаемую [13] или . Мы восстанавливаем два простых понятия, которые мы ввели выше, как множество наследственно конечных множеств и множество наследственно счетных множеств. [14] ( это первое несчетное порядковое .)

Ссылки [ править ]

  1. ^ * Горхэм, Энтони, " Последовательная сходимость в топологических пространствах"
  2. ^ а б Алон, Нога ; Шапира, Асаф (2008). «Каждое свойство монотонного графа можно проверить» (PDF) . SIAM Journal on Computing . 38 (2): 505–522. CiteSeerX  10.1.1.108.2303 . DOI : 10.1137 / 050633445 .
  3. ^ Боровецкий, Мечислав; Броэр, Изак; Фрик, Мариетджи; Михок, Питер; Семанишин, Габриэль (1997), "Обзор наследственных свойств графов", Discussiones Mathematicae Graph Theory , 17 (1): 5–50, doi : 10.7151 / dmgt.1037 , MR 1633268 
  4. ^ Farrugia, Аластер (2005). «Факторизации и характеристики индуцированно-наследственных и композиционных свойств». Журнал теории графов . 49 (1): 11–27. DOI : 10.1002 / jgt.20062 .
  5. Перейти ↑ King, R (1990). «Нижняя граница распознавания свойств орграфа». Combinatorica . 10 : 53–59. DOI : 10.1007 / bf02122695 . S2CID 31532357 . 
  6. ^ http://www.cs.ucsc.edu/~optas/papers/k-col-threshold.pdf
  7. ^ Спинрад, Дж. (2003), Эффективные графические представления , Книжный магазин AMS, ISBN 0-8218-2815-0 , стр. 9. 
  8. ^ Ашиш Гоэль; Санатан Рай; Бхаскар Кришнамачари (2003). «Монотонные свойства случайных геометрических графов имеют резкие пороги». Анналы прикладной теории вероятностей . 15 (4): 2535–2552. arXiv : math.PR/0310232 . DOI : 10.1214 / 105051605000000575 . S2CID 685451 . 
  9. ^ «Доказать невозможное невозможно» .
  10. ^ Азриэль Леви (2002), Основная теория множеств , стр. 82
  11. ^ Томас Форстер (2003), Логика, индукция и множества , стр. 197
  12. ^ Джудит Ройтман (1990), Введение в современную теорию множеств , стр. 10
  13. ^ Леви (2002), стр. 137
  14. ↑ Кеннет Кунен (1983), Теория множеств , стр. 131