Horn clause formulation

The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form

[math]\displaystyle{ x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in\mathcal{A} }[/math]

To keep the notation concise, we use the shorthand notation [math]\displaystyle{ (x,S) }[/math] for such a Horn clause. The following page provides various details of this formulation. Throughout, [math]\displaystyle{ \mathcal{A}\subseteq 2^X }[/math] is union-closed with [math]\displaystyle{ \emptyset\in\mathcal{A} }[/math].

Canonical systems

There are at least three canonical systems of Horn clauses that describe a given union-closed family.

Maximal one

Considering all [math]\displaystyle{ (x,S) }[/math] that are satisfied by [math]\displaystyle{ \mathcal{A} }[/math] characterizes [math]\displaystyle{ \mathcal{A} }[/math]. To see this, we need to show that every set not in [math]\displaystyle{ \mathcal{A} }[/math] violates some [math]\displaystyle{ (x,S) }[/math]. Indeed for [math]\displaystyle{ A\not\in\mathcal{A} }[/math], take some [math]\displaystyle{ x\in A }[/math] that is not an element of any [math]\displaystyle{ \mathcal{A} }[/math]-member contained in [math]\displaystyle{ A }[/math]; this is possible due to the union-closure assumption. Then put [math]\displaystyle{ S:=X\setminus A }[/math].

In most cases, there are smaller systems of Horn clauses that still characterize [math]\displaystyle{ \mathcal{A} }[/math]. The following is taken from this paper, which investigates the dual notions for intersection-closed families.

Using minimal transversals

It is sufficient to consider those [math]\displaystyle{ (x,S) }[/math] for which [math]\displaystyle{ S }[/math] is not contained in any other [math]\displaystyle{ S' }[/math] for which [math]\displaystyle{ (x,S') }[/math]. In other words, [math]\displaystyle{ S }[/math] can be assumed to be a minimal transversal of [math]\displaystyle{ \mathcal{A}_x }[/math].

Various reformulations of this can be found in the paper above.

Using free sets

A set [math]\displaystyle{ S }[/math] is free if for every [math]\displaystyle{ y\in S }[/math] there is [math]\displaystyle{ A\in\mathcal{A}_y }[/math] with [math]\displaystyle{ A\cap S = \{y\} }[/math]. (This terminology seems motivated by the dual notion for intersection-closed families, applied to the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses [math]\displaystyle{ (x,S) }[/math] with [math]\displaystyle{ S }[/math] free and [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ A\cap S=\emptyset }[/math] implies [math]\displaystyle{ x\not\in A }[/math].

Literature

For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is a survey.