Hereditary property
Encyclopedia
In mathematics
, a hereditary property is a property of an object, that inherits to all its subobjects, where the term subobject depends on the context. These properties are particularly considered in topology
and graph theory
.
, a topological property
is said to be hereditary if whenever a space has that property, then so does every subspace
of it. If the latter is true only for closed subspaces
, then the property is called weakly hereditary.
For example, second countability and metrisability are hereditary properties. Sequentiality
and Hausdorff compactness
are weakly hereditary, but not hereditary. Connectivity
is not weakly hereditary.
, a hereditary property is a property
of a graph
which also holds for (is "inherited" by) its induced subgraphs. Alternately, a hereditary property is preserved by the removal of vertices.
In some cases, the term "hereditary" has been defined with reference to graph minors, but this is more properly called a minor-hereditary property. The Robertson–Seymour theorem
implies that a minor-hereditary property may be characterized in terms of a finite set of forbidden minors.
There is no consensus for the meaning of "monotone property" in graph theory. Examples of definitions are:
The complementary property of a property that is preserved by the removal of edges is preserved under the addition of edges. Hence some authors avoid this ambiguity by saying a property A is monotone if A or AC (the complement of A) is monotone. Some authors choose to resolve this by using the term increasing monotone for properties preserved under the addition of some object, and decreasing monotone for those preserved under the removal of the same object.
and universal algebra
, a class K of structures
of a given signature
is said to have the hereditary property if every substructure
of a structure in K is again in K. A variant of this definition is used in connection with Fraïssé's theorem: A class K of finitely generated structures has the hereditary property if every finitely generated substructure is again in K. See age
.
, every subset of an independent set is again independent. This is also sometimes called the hereditary property.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a hereditary property is a property of an object, that inherits to all its subobjects, where the term subobject depends on the context. These properties are particularly considered in topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
and graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
.
In topology
In topologyTopology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, a topological property
Topological property
In topology and related areas of mathematics a topological property or topological invariant is a property of a topological space which is invariant under homeomorphisms. That is, a property of spaces is a topological property if whenever a space X possesses that property every space homeomorphic...
is said to be hereditary if whenever a space has that property, then so does every subspace
Subspace topology
In topology and related areas of mathematics, a subspace of a topological space X is a subset S of X which is equipped with a natural topology induced from that of X called the subspace topology .- Definition :Given a topological space and a subset S of X, the...
of it. If the latter is true only for closed subspaces
Closed set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points...
, then the property is called weakly hereditary.
For example, second countability and metrisability are hereditary properties. Sequentiality
Sequential space
In topology and related fields of mathematics, a sequential space is a topological space that satisfies a very weak axiom of countability. Sequential spaces are the most general class of spaces for which sequences suffice to determine the topology....
and Hausdorff compactness
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
are weakly hereditary, but not hereditary. Connectivity
Connected space
In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint nonempty open subsets. Connectedness is one of the principal topological properties that is used to distinguish topological spaces...
is not weakly hereditary.
In graph theory
In graph theoryGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a hereditary property is a property
Graph property
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.-Definitions:...
of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
which also holds for (is "inherited" by) its induced subgraphs. Alternately, a hereditary property is preserved by the removal of vertices.
In some cases, the term "hereditary" has been defined with reference to graph minors, but this is more properly called a minor-hereditary property. The Robertson–Seymour theorem
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
implies that a minor-hereditary property may be characterized in terms of a finite set of forbidden minors.
Monotone property
There is no consensus for the meaning of "monotone property" in graph theory. Examples of definitions are:
- Preserved by the removal of edges.
- Preserved by the removal of edges and vertices (i.e., the property should hold for all subgraphs).
- Preserved by the addition of edges and vertices (i.e., the property should hold for all supergraphs).
- Preserved by the addition of edges. (This meaning is used in the statement of the Aanderaa–Karp–Rosenberg conjecture.)
The complementary property of a property that is preserved by the removal of edges is preserved under the addition of edges. Hence some authors avoid this ambiguity by saying a property A is monotone if A or AC (the complement of A) is monotone. Some authors choose to resolve this by using the term increasing monotone for properties preserved under the addition of some object, and decreasing monotone for those preserved under the removal of the same object.
In model theory
In model theoryModel theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
and universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
, a class K of structures
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
of a given signature
Signature (logic)
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes.Signatures play the same...
is said to have the hereditary property if every substructure
Substructure
In mathematical logic, an substructure or subalgebra is a structure whose domain is a subset of that of a bigger structure, and whose functions and relations are the traces of the functions and relations of the bigger structure...
of a structure in K is again in K. A variant of this definition is used in connection with Fraïssé's theorem: A class K of finitely generated structures has the hereditary property if every finitely generated substructure is again in K. See age
Age (model theory)
In model theory, the age of a structure A is the class of all finitely generated structures which are embeddable in A . This concept is central in the construction of a Fraïssé limit....
.
In matroid theory
In a matroidMatroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
, every subset of an independent set is again independent. This is also sometimes called the hereditary property.