Наследственная собственность

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

В топологии

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

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

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

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

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

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

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

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

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

Монотонное свойство

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

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

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

В теории матроидов

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

Семья матроидов может иметь наследственную собственность. Например, семью, закрытую по приему несовершеннолетних матроидов, можно назвать «наследственной».

В решении проблем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Горэм, Энтони (2016). «Последовательная сходимость в топологических пространствах». arXiv : math/0412558 .
^ Jump up to: ^а ^б Алон, Нога ; Шапира, Асаф (2008). «Каждое свойство монотонного графа можно проверить» (PDF) . SIAM Journal по вычислительной технике . 38 (2): 505–522. CiteSeerX 10.1.1.108.2303 . дои : 10.1137/050633445 .
^ Боровецкий, Мечислав; Броэр, Исаак; Фрик, Мариетджи; Михок, Питер; наследственных свойств графов», Обсуждения Mathematicae Graph Theory , 17 (1):5–50, doi : 10.7151/dmgt.1037 , MR1633268 Семанишин, Габриэль (1997), « Обзор
^ Фарруджа, Аластер (2005). «Факторизации и характеристики индуцированно-наследственных и композиционных свойств» . Журнал теории графов . 49 (1): 11–27. дои : 10.1002/jgt.20062 . S2CID 12689856 .
^ Кинг, Р. (1990). «Нижняя граница распознавания свойств орграфа». Комбинаторика . 10 : 53–59. дои : 10.1007/bf02122695 . S2CID 31532357 .
^ Ахлиоптас, Д.; Фридгут, Э. (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 .
^ Спинрад, Дж. (2003). Эффективное представление графов . Книжный магазин АМС. п. 9. ISBN 0-8218-2815-0 .
^ Гоэль, Ашиш; Санатан Рай; Бхаскар Кришнамачари (2003). «Монотонные свойства случайных геометрических графов имеют резкие пороги». Анналы прикладной теории вероятности . 15 (4): 2535–2552. arXiv : математика/0310232 . дои : 10.1214/105051605000000575 . S2CID 685451 .
^ Сиклосси, Л.; Роуч, Дж. (1973). «Доказать невозможное невозможно: опровержения, основанные на наследственных разделах» . Материалы 3-й международной совместной конференции по искусственному интеллекту (IJCAI'73) . Морган Кауфманн. стр. 383–7.
^ Леви, Азриэль (2002). Базовая теория множеств . Дувр. стр. 82 . ISBN 978-0-486-42079-0 .
^ Форстер, Томас (2003). Логика, индукция и множества . Издательство Кембриджского университета. стр. 197 . ISBN 978-0-521-53361-4 .
^ Ройтман, Джудит (1990). Введение в современную теорию множеств . Уайли. стр. 10 . ISBN 978-0-471-63519-2 .
^ Леви 2002 , с. 137
^ Кунен, Кеннет (2014) [1980]. Теория множеств. Введение в доказательства независимости . Исследования по логике и основам математики. Том. 102. Эльзевир. п. 131. ИСБН 978-0-08-057058-7 .

[1] Горэм, Энтони (2016). «Последовательная сходимость в топологических пространствах». arXiv : math/0412558 .

[AS-2] Jump up to: ^а ^б Алон, Нога ; Шапира, Асаф (2008). «Каждое свойство монотонного графа можно проверить» (PDF) . SIAM Journal по вычислительной технике . 38 (2): 505–522. CiteSeerX 10.1.1.108.2303 . дои : 10.1137/050633445 .

[Survey-3] Боровецкий, Мечислав; Броэр, Исаак; Фрик, Мариетджи; Михок, Питер; наследственных свойств графов», Обсуждения Mathematicae Graph Theory , 17 (1):5–50, doi : 10.7151/dmgt.1037 , MR1633268 Семанишин, Габриэль (1997), « Обзор

[UFT-4] Фарруджа, Аластер (2005). «Факторизации и характеристики индуцированно-наследственных и композиционных свойств» . Журнал теории графов . 49 (1): 11–27. дои : 10.1002/jgt.20062 . S2CID 12689856 .

[5] Кинг, Р. (1990). «Нижняя граница распознавания свойств орграфа». Комбинаторика . 10 : 53–59. дои : 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] Спинрад, Дж. (2003). Эффективное представление графов . Книжный магазин АМС. п. 9. ISBN 0-8218-2815-0 .

[8] Гоэль, Ашиш; Санатан Рай; Бхаскар Кришнамачари (2003). «Монотонные свойства случайных геометрических графов имеют резкие пороги». Анналы прикладной теории вероятности . 15 (4): 2535–2552. arXiv : математика/0310232 . дои : 10.1214/105051605000000575 . S2CID 685451 .

[9] Сиклосси, Л.; Роуч, Дж. (1973). «Доказать невозможное невозможно: опровержения, основанные на наследственных разделах» . Материалы 3-й международной совместной конференции по искусственному интеллекту (IJCAI'73) . Морган Кауфманн. стр. 383–7.

[10] Леви, Азриэль (2002). Базовая теория множеств . Дувр. стр. 82 . ISBN 978-0-486-42079-0 .

[11] Форстер, Томас (2003). Логика, индукция и множества . Издательство Кембриджского университета. стр. 197 . ISBN 978-0-521-53361-4 .

[12] Ройтман, Джудит (1990). Введение в современную теорию множеств . Уайли. стр. 10 . ISBN 978-0-471-63519-2 .

[13] Леви 2002 , с. 137

[14] Кунен, Кеннет (2014) [1980]. Теория множеств. Введение в доказательства независимости . Исследования по логике и основам математики. Том. 102. Эльзевир. п. 131. ИСБН 978-0-08-057058-7 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]