Minimal set definition

Question

I'm very confused about minimal sets, particularly with graphs. According to Wolfram Mathworld, a minimal set is "a member set that is not a proper subset of another member set is called a minimal set." However I'm confused because doesn't that mean that it can contain proper subsets? And in that case, how can a minimum set also be minimal? For example, Wolfram also says here that every minimum vertex cover is minimal. But some minimum vertex cover is a subset of the vertex set, which is also a vertex cover, so how does the original definition of minimal set make sense here?

I'm confused on the meaning of minimal in general, because I thought that minimal means it cannot get any smaller, or that it has no proper subsets. But Wolfram's definition makes it seem like it can't get any bigger.

Examples to explain this would be very helpful.

Answer 1

You are right to be confused. "Proper subset" should read "proper superset" for Minimal Set, Minimal Dominating Set, Minimal Vertex Cover, and Minimal Edge Cover definitions, possible in other places as well.

If you look for example here, or even here and here the definition is consistently correct (proper superset).

In addition, Wolfram's definition of Maximal Set seems to be incorrect as well. For example the set $\{a\}$ is obviously not maximal in the collection of two sets $\{a\},\{a,b,c\}$. However, $\{a\}$ cannot be expanded to $\{a,b,c\}$ through the addition of any element.

Moral: Just because it's on Wolfram website, it does not mean it is correct. You should contact Wolfram guys to fix it.

Answer 2

"Minimality" (or dually, "maximality") is usually spoken of with respect to certain properties. For instance, in topology: a set $A$ has closure $\mathrm{cl}({A})$ which can be defined to be the smallest closed set containing $A$. Sometimes we even write this formally as an intersection:

$$\mathrm{cl}({A}) = \bigcap \left\{ \text{sets } F \, \middle| \, A \subseteq F \text{ and } F \text{ is closed} \right\}$$

Notice: "smallest" references minimality, and "closed set containing $A$" references the property of concern. (And of course we can also speak to how we "order" sets, set inclusion $\subseteq$.)

---

$\mathrm{cl}({A})$ (to continue the topology example) may, and often will, contain proper subsets $B$. However, in doing so, one of the following ends up being true:

• $B$ ends up somehow not being a proper subset after all (and often equal to $\mathrm{cl}({A})$) - a convenient angle for proofs
• $B$ is not closed
• $B$ does not contain $A$

This gives another way to look at things: if $H$ is another set satisfying $\mathrm{cl}({A})$'s properties (smallest closed set containing $A$), then $H \subseteq \mathrm{cl}({A}) \subseteq H \implies H = \mathrm{cl}({A})$, giving a sort of uniqueness as well. If $H$ were somehow smaller than $\mathrm{cl}({A})$ or contained in it, then it cannot be a proper subset, only equal at best.

---

Without speaking of such a property that the minimality is concerned about, yeah, minimality is pointless as a notion to discuss since the only "minimal" set with no properties of concern would be the empty set.

In fact, let us look back at MathWorld:

Given a collection of sets, a member set that is not a proper subset of another member set is called a minimal set.

The bolded bit is what you overlooked. The collection of sets (call it $\cal S$) in this case is (typically) that defined by a given property, i.e. we may say

$$\mathcal{S} = \{ \text{sets } B \mid B \text{ has property } P \}$$

In the case of our closure example, $P$ is the property of containing $A$ and being closed. In that light, we may also want to note that while some set $B \in \mathcal{S}$ may be true, subsets of $B$ might not be in $\mathcal{S}$.

Answer 3

The term "minimal" is defined only with respect to some ordering. It refers to a member for which there is no smaller member, where "smaller" is defined in terms of that order. Given the set $\{2,3,4,5,6,7,8,9\}$, $2$ is the sole minimal number given the ordinary order. However, if we use the order of "can divide", then $2$, $3$, $5$, and $7$ are all minimal numbers, because no other member of the set can divide them. The usual ordering of sets is that $A<B$ if $B$ contains $A$, and given this ordering, a minimal set would be a set that contains no other set.

I suppose you could define an ordering that goes the other way around, in which case a minimal set would be a set that isn't contained in any other set. In that case, a minimum set would be a set that contains all other sets. But that's a confusing usage, and would be at odds with the ordering they use for vertex coverings (There are cases where it's not obvious which direction should be "smaller". For instance, a smaller set of equations generally means a larger set of solutions.) I do think that it's more likely that the person who wrote this page miswrote the definition rather than is using a nonstandard ordering. I find it odd that not only Wolfram is giving this definition of "minimal set", but apparently doesn't give a definition of the term "minimal" in general. It