Structure and cardinality of the set of dependence systems on a given set

Abstract

A dependence system on a set $S$ is defined by an operator $f$, a function on the power set of $S$ which is extensive ($A$ is included in $f(A)$) and monotone (if $A$ is included in $B$, then $f(A)$ is included in $f(B)$). In this paper, the structure of the set $F(S)$ of all dependence systems on a given set $S$ is studied. The partially ordered set of operators ($f<g$ if for every set $A$, $f(A)$ is included in $g(A)$) is a bounded, complete, completely distributive, atomic, and dual atomic lattice with an involution. It is shown that every operator is a join of transitive operators (usually called closure operators, operators which are idempotent $ff=f$). The study of the class of transitive operators that join-generate all operators makes it possible to express $F(n)$ (the cardinality of the set $F(S)$ of all operators on a set $S$ with $n$ elements) by the Dedekind number $D(n)$. The formula has interesting consequences for dependence system theory.