En matemáticas, una propiedad hereditaria es una propiedad de un objeto que es heredada por todos sus subobjetos, donde el significado de 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 , 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 sólo para subespacios cerrados , entonces la propiedad se llama débilmente hereditaria o hereditaria cerrada .
Por ejemplo, la segunda contabilización y la metrización 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 ".
Las propiedades hereditarias ocurren en la combinatoria y la teoría de grafos, aunque se las conoce con diversos 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 , una propiedad hereditaria generalmente significa una propiedad de un grafo que también se cumple (es "heredada" por) sus subgrafos inducidos . [2] De manera equivalente, una propiedad hereditaria se preserva mediante la eliminación de los vértices. Una clase de gráfico se llama hereditaria si está cerrada bajo subgrafos inducidos. Ejemplos de clases de gráficos hereditarios son gráficos independientes (gráficos 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.
En ocasiones el término "hereditario" ha sido definido con referencia a grafos menores ; entonces se le 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 las propiedades de los gráficos que son 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 hereditarias inducidas . El lenguaje de las propiedades hereditarias y de las propiedades hereditarias inducidas proporciona una poderosa herramienta 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]
No existe consenso sobre el significado de " propiedad monótona " en la teoría de grafos. Ejemplos de definiciones son:
La propiedad complementaria de una propiedad que se conserva mediante la eliminación de aristas se conserva al agregar 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ótono creciente para las propiedades conservadas tras la adición de algún objeto, y monótono decreciente para aquellas conservadas tras la eliminación del mismo objeto.
En una matroide , cada subconjunto de un conjunto independiente vuelve a ser independiente. Ésta es una propiedad hereditaria de los conjuntos.
Una familia de matroides puede tener una propiedad hereditaria. Por ejemplo, una familia cerrada que acepta menores matroides puede denominarse "hereditaria".
En la planificación y resolución de problemas , o más formalmente en juegos de una sola persona, el espacio de búsqueda se ve como un gráfico dirigido con estados como nodos y transiciones como aristas. Los estados pueden tener propiedades, y dicha propiedad P es hereditaria si por 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 puede extenderse trivialmente a particiones más discriminantes, 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 sólo si ∀ i , de cualquier estado donde A ∈ d i sólo otros estados donde se puede alcanzar A ∈ d i .
Si el estado actual y el estado objetivo se encuentran en diferentes elementos 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 campos adyacentes? Sí. ¿Qué pasa si eliminamos el campo superior izquierdo y el inferior derecho? Entonces ya no es posible cubrir, porque la diferencia entre el número de campos blancos descubiertos y el número de campos negros descubiertos es 2, y al agregar una ficha de dominó (que cubre un campo blanco y uno negro) ese número se mantiene en 2. Para un El número de cobertura total es 0, por lo que no se puede alcanzar una cobertura total desde la posición inicial.
Esta noción fue introducida por primera vez por Laurent Siklóssy y Roach. [9]
En teoría de modelos y á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. Se utiliza una variante de esta definición en relació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. Ver edad .
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 vagamente cierto que el conjunto vacío es un conjunto hereditario y, por tanto, el conjunto que contiene sólo 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 elemento de un el conjunto es otro conjunto. Por lo tanto, la noción de conjunto hereditario sólo es interesante en un contexto en el que puede haber elementos .
De manera análoga se definen un par de nociones:
De lo anterior se desprende 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 el propio x y todos los miembros de su clausura transitiva satisfacen , es decir . De manera equivalente, x satisface hereditariamente si es miembro de un subconjunto transitivo de [10] [11]. Por 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 tanto, ser finito. [12]
Si instanciamos en el esquema anterior con " x tiene cardinalidad menor que κ", obtenemos la noción más general de un conjunto que tiene hereditariamente cardinalidad menor que κ, generalmente denotada por [13] o . Recuperamos las dos nociones simples que presentamos anteriormente: el conjunto de conjuntos hereditariamente finitos y el conjunto de conjuntos hereditariamente contables. [14] ( es el primer ordinal incontable ).
