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 contained in any [math]\displaystyle{ \mathcal{A} }[/math]-member; 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].

Using minimal transversals

<ref>Template:Cite paper</ref>

Literature

For intersection-closed families, there are plenty of papers in certain areas of artificial intelligence research, including data analysis and formal concept analysis.