# 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

$x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in A$

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

## Canonical systems

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

### Maximal one

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

In most cases, there are smaller systems of Horn clauses that still characterize $\mathcal{A}$. 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 $(x,S)$ for which $S$ is not contained in any other $S'$ for which $(x,S')$. In other words, $S$ can be assumed to be a minimal transversal of $\mathcal{A}_x$.

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

### Using free sets

A set $S$ is free if for every $y\in S$ there is $A\in\mathcal{A}_y$ with $A\cap S = \{y\}$. (At least this is the terminology used in the dual case of intersection-closed families, where it seems to be motivated by the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses $(x,S)$ with $S$ free and $x$ such that $A\cap S=\emptyset$ implies $x\not\in A$.

## 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.