Propiedad hereditaria

Propiedad de los objetos heredada por todos sus subobjetos

En matemáticas, una propiedad hereditaria es una propiedad de un objeto que es heredada por todos sus subobjetos, donde el significado del subobjeto depende del contexto. Estas propiedades se consideran particularmente en topología y teoría de grafos , pero también en teoría de conjuntos .

En topología

En topología , se dice que una propiedad topológica es hereditaria si, siempre que un espacio topológico tiene esa propiedad, también la tiene cada subespacio del mismo. Si esto último es cierto solo para subespacios cerrados , entonces la propiedad se llama débilmente hereditaria o hereditaria cerrada .

Por ejemplo, la segunda contabilidad y la metrisabilidad son propiedades hereditarias. La secuencialidad y la compacidad de Hausdorff son débilmente hereditarias, pero no hereditarias. ^[1] La conectividad no es débilmente hereditaria.

Si P es una propiedad de un espacio topológico X y cada subespacio también tiene la propiedad P , entonces se dice que X es "hereditariamente P ".

En combinatoria y teoría de grafos

Las propiedades hereditarias aparecen en la combinatoria y la teoría de grafos, aunque se las conoce con distintos nombres. Por ejemplo, en el contexto de los patrones de permutación , las propiedades hereditarias suelen denominarse clases de permutación .

En teoría de grafos

En teoría de grafos , una propiedad hereditaria generalmente significa una propiedad de un grafo que también se cumple para (es "heredada" por) sus subgrafos inducidos . ^[2] Equivalentemente, una propiedad hereditaria se conserva mediante la eliminación de vértices. Una clase de grafo se llama hereditaria si está cerrada bajo subgrafos inducidos. Ejemplos de clases de grafos hereditarios son grafos independientes (grafos sin aristas), que es un caso especial (con c = 1) de ser c -coloreable para algún número c , ser bosques , planos , completos , multipartitos completos , etc. ${\displaystyle {\mathcal {G}}}$

En ocasiones, el término "hereditario" se ha definido con referencia a los menores de grafos ; en ese caso, se lo puede llamar propiedad hereditaria menor . El teorema de Robertson-Seymour implica que una propiedad hereditaria menor puede caracterizarse en términos de un conjunto finito de menores prohibidos .

El término "hereditario" también se ha utilizado para propiedades de grafos que están cerradas con respecto a la toma de subgrafos. ^[3] En tal caso, las propiedades que están cerradas con respecto a la toma de subgrafos inducidos se denominan inducidas-hereditarias . El lenguaje de las propiedades hereditarias y las propiedades inducidas-hereditarias proporciona una herramienta poderosa para el estudio de las propiedades estructurales de varios tipos de coloraciones generalizadas . El resultado más importante de esta área es el teorema de factorización única. ^[4]

Propiedad monótona

No existe consenso sobre el significado de " propiedad monótona " en la teoría de grafos. Algunos ejemplos de definiciones son:

• Conservado mediante la eliminación de los bordes. ^[5]
• Se conserva mediante la eliminación de aristas y vértices (es decir, la propiedad debería cumplirse para todos los subgrafos). ^[2]
• Se conserva mediante la adición de aristas y vértices (es decir, la propiedad debería cumplirse para todos los supergrafos). ^[6]
• Conservado por la adición de aristas. ^[7] (Este significado se utiliza en el enunciado de la conjetura de Aanderaa–Karp–Rosenberg ).

La propiedad complementaria de una propiedad que se conserva al eliminar aristas se conserva bajo la adición de aristas. Por lo tanto, algunos autores evitan esta ambigüedad diciendo que una propiedad A es monótona si A o A ^C (el complemento de A) es monótona. ^[8] Algunos autores optan por resolver esto utilizando el término monótona creciente para las propiedades que se conservan bajo la adición de algún objeto, y monótona decreciente para las que se conservan bajo la eliminación del mismo objeto.

En la teoría matroide

En un matroide , cada subconjunto de un conjunto independiente es a su vez independiente. Esta es una propiedad hereditaria de los conjuntos.

Una familia de matroides puede tener una propiedad hereditaria. Por ejemplo, una familia cerrada en cuanto a la adopción de matroides menores puede ser denominada "hereditaria".

En la resolución de problemas

En la planificación y resolución de problemas , o más formalmente en los juegos unipersonales, el espacio de búsqueda se considera un gráfico dirigido con estados como nodos y transiciones como aristas. Los estados pueden tener propiedades, y una propiedad de este tipo, P, es hereditaria si para cada estado S que tiene P, cada estado al que se puede llegar desde S también tiene P.

El subconjunto de todos los estados que tienen P más el subconjunto de todos los estados que tienen ~P forman una partición del conjunto de estados llamada partición hereditaria. Esta noción se puede extender trivialmente a particiones más discriminantes mediante en lugar de propiedades, considerando aspectos de los estados y sus dominios. Si los estados tienen un aspecto A , con d _i ⊂ D una partición del dominio D de A , entonces los subconjuntos de estados para los cuales A ∈ d _i forman una partición hereditaria del conjunto total de estados si y solo si ∀ i , desde cualquier estado donde A ∈ d _i solo se pueden alcanzar otros estados donde A ∈ d _{i .}

Si el estado actual y el estado objetivo están en elementos diferentes de una partición hereditaria, no hay camino desde el estado actual al estado objetivo: el problema no tiene solución.

¿Se puede cubrir un tablero de damas con fichas de dominó, cada una de las cuales cubre exactamente dos casillas adyacentes? Sí. ¿Qué pasa si eliminamos la casilla superior izquierda y la casilla inferior derecha? Entonces ya no es posible cubrirlo, porque la diferencia entre el número de casillas blancas descubiertas y el número de casillas negras descubiertas es 2, y al añadir una ficha de dominó (que cubre una casilla blanca y una negra) ese número se mantiene en 2. Para un cubrimiento total, el número es 0, por lo que no se puede alcanzar un cubrimiento total desde la posición inicial.

Esta noción fue introducida por primera vez por Laurent Siklóssy y Roach. ^[9]

En la teoría de modelos

En la teoría de modelos y el álgebra universal , se dice que una clase K de estructuras de una firma dada tiene la propiedad hereditaria si cada subestructura de una estructura en K está nuevamente en K. Una variante de esta definición se utiliza en conexión con el teorema de Fraïssé : Una clase K de estructuras finitamente generadas tiene la propiedad hereditaria si cada subestructura finitamente generada está nuevamente en K. Véase edad .

En la teoría de conjuntos

En la teoría de conjuntos se encuentran a menudo definiciones recursivas que utilizan el adjetivo "hereditario" .

Se dice que un conjunto es hereditario (o puro ) si todos sus elementos son conjuntos hereditarios. Es vacuamente cierto que el conjunto vacío es un conjunto hereditario y, por lo tanto, el conjunto que contiene solo el conjunto vacío es un conjunto hereditario y, recursivamente , también lo es , por ejemplo. En las formulaciones de la teoría de conjuntos que pretenden ser interpretadas en el universo de von Neumann o expresar el contenido de la teoría de conjuntos de Zermelo-Fraenkel , todos los conjuntos son hereditarios, porque el único tipo de objeto que es siquiera candidato a ser un elemento de un conjunto es otro conjunto. Por lo tanto, la noción de conjunto hereditario es interesante solo en un contexto en el que puede haber urelementos . ${\displaystyle \{\varnothing \}}$ ${\displaystyle \varnothing }$ ${\displaystyle \{\varnothing ,\{\varnothing \}\}}$

Un par de nociones se definen de forma análoga:

• Un conjunto finito hereditario se define como un conjunto finito que consta de cero o más conjuntos finitos hereditarios. De manera equivalente, un conjunto es finito hereditario si y solo si su clausura transitiva es finita.
• Un conjunto contable hereditariamente es un conjunto contable de conjuntos contables hereditariamente. Suponiendo el axioma de elección contable , entonces un conjunto es contable hereditariamente si y solo si su clausura transitiva es contable.

Con base en lo anterior, se deduce que en ZFC se puede definir una noción más general para cualquier predicado . Se dice que un conjunto x tiene hereditariamente la propiedad si x mismo y todos los miembros de su clausura transitiva satisfacen , es decir . De manera equivalente, x satisface hereditariamente si y solo si es un miembro de un subconjunto transitivo de ^{[10] [11]} Por lo tanto, se dice que una propiedad (de un conjunto) es hereditaria si es heredada por cada subconjunto. Por ejemplo, estar bien ordenado es una propiedad hereditaria, y por lo tanto es finito. ^[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)\}.}$

Si instanciamos en el esquema anterior con " x tiene cardinalidad menor que κ", obtenemos la noción más general de un conjunto que es hereditariamente de cardinalidad menor que κ, usualmente denotada por ^[13] o . Recuperamos las dos nociones simples que introdujimos anteriormente como ser el conjunto de conjuntos hereditariamente finitos y ser el conjunto de conjuntos hereditariamente contables. ^[14] ( es el primer ordinal incontable .) ${\displaystyle \Phi (x)}$ ${\displaystyle H_{\kappa }}$ ${\displaystyle H(\kappa )}$ ${\displaystyle H(\omega )}$ ${\displaystyle H(\omega _{1})}$ ${\displaystyle \omega _{1}}$

Referencias

1. Goreham, Anthony (2016). "Convergencia secuencial en espacios topológicos". arXiv : math/0412558 .
2. Alon, Noga ; Shapira, Asaf (2008). "Cada propiedad de un grafo monótono es comprobable" (PDF) . SIAM Journal on Computing . 38 (2): 505–522. CiteSeerX 10.1.1.108.2303 . doi :10.1137/050633445. 
3. Borowiecki, Mieczysław; Broere, Izak; Frick, Marietjie; Mihok, Peter; Semanišin, Gabriel (1997), "Un estudio de las propiedades hereditarias de los gráficos", Discussiones Mathematicae Graph Theory , 17 (1): 5–50, doi :10.7151/dmgt.1037, MR  1633268
4. Farrugia, Alastair (2005). "Factorizaciones y caracterizaciones de propiedades hereditarias inducidas y compositivas". Revista de teoría de grafos . 49 (1): 11–27. doi : 10.1002/jgt.20062 . S2CID  12689856.
5. King, R (1990). "Un límite inferior para el reconocimiento de propiedades de dígrafos". Combinatorica . 10 : 53–59. doi :10.1007/bf02122695. S2CID  31532357.
6. Achlioptas, D.; Friedgut, E. (1999). "Un umbral preciso para la colorabilidad k". Random Structures & Algorithms . 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). Representaciones gráficas eficientes . Librería AMS. pág. 9. ISBN 0-8218-2815-0.
8. Goel, Ashish; Sanatan Rai; Bhaskar Krishnamachari (2003). "Las propiedades monótonas de los gráficos geométricos aleatorios tienen umbrales agudos". Anales de probabilidad aplicada . 15 (4): 2535–2552. arXiv : math/0310232 . doi :10.1214/105051605000000575. S2CID  685451.
9. Siklossy, L.; Roach, J. (1973). "Probar que lo imposible es imposible es posible: refutaciones basadas en particiones hereditarias". Actas de la 3.ª conferencia conjunta internacional sobre inteligencia artificial (IJCAI'73) . Morgan Kaufmann. págs. 383–7.
10. Levy, Azriel (2002). Teoría básica de conjuntos . Dover. pp. 82. ISBN. 978-0-486-42079-0.
11. Forster, Thomas (2003). Lógica, inducción y conjuntos . Cambridge University Press. pp. 197. ISBN. 978-0-521-53361-4.
12. Roitman, Judith (1990). Introducción a la teoría de conjuntos moderna . Wiley. pp. 10. ISBN 978-0-471-63519-2.
13. Levy 2002, pág. 137
14. Kunen, Kenneth (2014) [1980]. Teoría de conjuntos: Introducción a las pruebas de independencia. Estudios de lógica y fundamentos de las matemáticas. Vol. 102. Elsevier. pág. 131. ISBN 978-0-08-057058-7.