Mindestmenge

Mindestmenge, literally “minimal set” in German, is a term used in mathematics and related disciplines to denote a subset S of a given universe U that satisfies a specified property P and is minimal with respect to inclusion: no proper subset of S also satisfies P.

Formal definition: Let U be a set and P a predicate that assigns true or false to subsets of U. A subset S ⊆ U is a Mindestmenge with respect to P if P(S) is true and for every proper subset T ⊂ S, P(T) is false. In other words, S cannot be made smaller without losing the property P.

Distinction from minimum: A Mindestmenge is not the same as a minimum set. A minimum set is a Mindestmenge of smallest possible size among all subsets satisfying P. There may be several Mindestmengen (all minimal with respect to inclusion) of different sizes, or in some contexts no single minimum by cardinality exists at all. For example, in the power set of a finite universe ordered by inclusion with P(S) = “S ≠ ∅,” the minimal sets are all singletons, but there is no single minimum element under inclusion.

Examples: In a graph, a minimal vertex cover is a cover that cannot be reduced by removing a vertex, though there may be other vertex covers of smaller size elsewhere. Alternatively, with P(S) = “S contains at least one fixed element a,” the set {a} is both minimal and minimum.

Existence and computation: Minimal sets need not be unique; their existence depends on the predicate P and the underlying universe. Finding all minimal sets or a smallest one is a common problem in combinatorics, logic, and computer science.

See also: minimality, minimum, posets, subset, vertex cover, hitting set.