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

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

В топологии

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

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

Если п является свойством топологического пространства Икс и каждое подпространство также обладает свойством п, тогда Икс считается "по наследству п".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. * Горхэм, Энтони "Последовательная сходимость в топологических пространствах.
2. Алон, Нога; Шапира, Асаф (2008). «Каждое свойство монотонного графа можно проверить» (PDF). SIAM Журнал по вычислениям. 38 (2): 505–522. CiteSeerX  10.1.1.108.2303. Дои:10.1137/050633445.
3. Боровецкий, Мечислав; Броэр, Изак; Фрик, Мариетджи; Михок, Питер; Семанишин, Габриэль (1997), "Обзор наследственных свойств графов", Обсуждения Математическая теория графов, 17 (1): 5–50, Дои:10.7151 / dmgt.1037, МИСТЕР  1633268
4. Фарруджа, Аластер (2005). «Факторизации и характеристики индуцированно-наследственных и композитных свойств». Журнал теории графов. 49 (1): 11–27. Дои:10.1002 / jgt.20062.
5. Кинг, Р. (1990). «Нижняя граница распознавания свойств орграфа». Комбинаторика. 10: 53–59. Дои: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. Дои:10.1214/105051605000000575. S2CID  685451.
9. «Доказать невозможное невозможно».
10. Азриэль Леви (2002), Теория основных множеств, п. 82
11. Томас Форстер (2003), Логика, индукция и множества, п. 197
12. Джудит Ройтман (1990), Введение в современную теорию множеств, п. 10
13. Леви (2002), стр. 137
14. Кеннет Кунен (1983), Теория множеств, п. 131