Наследственное имущество

Свойство объектов, наследуемое всеми их подобъектами

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

В топологии

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

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

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

В комбинаторике и теории графов

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

В теории графов

В теории графов наследственное свойство обычно означает свойство графа , которое также выполняется для ("наследуется" им) его индуцированных подграфов . ^[2] Эквивалентно, наследственное свойство сохраняется при удалении вершин. Класс графа называется наследственным, если он замкнут относительно индуцированных подграфов. Примерами наследственных классов графов являются независимые графы (графы без ребер), которые являются частным случаем (при c = 1) того, что является c -раскрашиваемым для некоторого числа c , является лесом , планарным , полным , полным многодольным и т. д. ${\displaystyle {\mathcal {G}}}$

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

Термин «наследственный» также использовался для свойств графа, которые замкнуты относительно взятия подграфов. ^[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 ∈ d _{i .}

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

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

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

В теории моделей

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

В теории множеств

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

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

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

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

На основании вышесказанного следует, что в ZFC можно определить более общее понятие для любого предиката . Говорят, что множество x наследственно обладает свойством , если само x и все члены его транзитивного замыкания удовлетворяют , т. е . . Эквивалентно, x наследственно удовлетворяет , если и только если оно является членом транзитивного подмножества ^{[10] [11]} Таким образом, свойство (множества) называется наследственным, если оно наследуется каждым подмножеством. Например, быть хорошо упорядоченным является наследственным свойством, и поэтому оно быть конечным. ^[12] ${\displaystyle \Phi (x)}$ ${\displaystyle \Phi (x)}$ ${\displaystyle \Phi (y)}$ ${\displaystyle x\cup \mathop {\rm {tc}} (x)\subseteq \{y:\Phi (y)\}}$ ${\displaystyle \Phi (x)}$ ${\displaystyle \{y:\Phi (y)\}.}$

Если мы реализуем в приведенной выше схеме схему с « x имеет мощность меньше κ», мы получим более общее понятие множества, являющегося наследственно имеющим мощность меньше κ, обычно обозначаемое как ^[13] или . Мы возвращаемся к двум простым понятиям, которые мы ввели выше, как множество наследственно конечных множеств и множество наследственно счетных множеств. ^[14] ( — первый несчетный ординал .) ${\displaystyle \Phi (x)}$ ${\displaystyle H_{\kappa }}$ ${\displaystyle H(\kappa )}$ ${\displaystyle H(\omega )}$ ${\displaystyle H(\omega _{1})}$ ${\displaystyle \omega _{1}}$

Ссылки

1. Горхэм, Энтони (2016). «Последовательная сходимость в топологических пространствах». arXiv : math/0412558 .
2. Alon, Noga ; Shapira, Asaf (2008). "Каждое свойство монотонного графа проверяемо" (PDF) . SIAM Journal on Computing . 38 (2): 505–522. CiteSeerX 10.1.1.108.2303 . doi :10.1137/050633445. 
3. Боровецкий, Мечислав; Броэр, Изак; Фрик, Мариетджи; Михок, Питер; Семанишин, Габриэль (1997), «Обзор наследственных свойств графов», Discountes Mathematicae Graph Theory , 17 (1): 5–50, doi : 10.7151/dmgt.1037, MR  1633268
4. Фарругия, Аластер (2005). «Факторизации и характеристики индуцированно-наследственных и композитных свойств». Журнал теории графов . 49 (1): 11–27. doi : 10.1002/jgt.20062 . S2CID  12689856.
5. Кинг, Р. (1990). «Нижняя граница для распознавания свойств диграфа». Combinatorica . 10 : 53–59. doi :10.1007/bf02122695. S2CID  31532357.
6. Ахлиоптас, Д.; Фридгут, Э. (1999). «Резкий порог для k-раскрашиваемости». Случайные структуры и алгоритмы . 14 (1): 63–70. CiteSeerX 10.1.1.127.4597 . doi :10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7. 
7. Spinrad, J. (2003). Эффективные графовые представления . AMS Bookstore. стр. 9. ISBN 0-8218-2815-0.
8. Гоэль, Ашиш; Санатан Рай; Бхаскар Кришнамачари (2003). «Монотонные свойства случайных геометрических графов имеют острые пороги». Annals of Applied Probability . 15 (4): 2535–2552. arXiv : math/0310232 . doi :10.1214/105051605000000575. S2CID  685451.
9. Siklossy, L.; Roach, J. (1973). «Доказательство того, что невозможное невозможно, возможно: опровержения, основанные на наследственных разбиениях». Труды 3-й международной совместной конференции по искусственному интеллекту (IJCAI'73) . Morgan Kaufmann. стр. 383–7.
10. Леви, Азриэль (2002). Базовая теория множеств . Довер. С. 82. ISBN 978-0-486-42079-0.
11. Форстер, Томас (2003). Логика, индукция и множества . Cambridge University Press. С. 197. ISBN 978-0-521-53361-4.
12. Ройтман, Джудит (1990). Введение в современную теорию множеств . Wiley. С. 10. ISBN 978-0-471-63519-2.
13. Леви 2002, стр. 137
14. Кунен, Кеннет (2014) [1980]. Теория множеств. Введение в доказательства независимости. Исследования по логике и основаниям математики. Т. 102. Elsevier. С. 131. ISBN 978-0-08-057058-7.