(Co)homology of propositional logic

333 Views Asked by At

Sorry if this is a rather vague question, but it seemed like something that might be interesting.

Let $P$ be a family of propositions, and let $\mathcal L(P)$ be the set of all compound propositions over $P$. Now let $K$ be the set of all finite consistent subsets of $\mathcal L(P)$.

Now note that $K$ is non-empty, and hereditary in the sense that if $A\in K$ and $B\subset A$, then $B\in K$. In other words, $K$ is an abstract simplicial complex.

Can we say anything interesting about the simplicial (co)homology of $K$?

Note: My guess is that the answer is 'no', because we set $\mathcal L(P)$ up in a fairly arbitrary way (we could, for example, take $\vee$ and $\wedge$ to be our basic connectives rather than $\Rightarrow$ and $\perp$). But perhaps this 'arbitrariness' only leads to changes that are invariant under homotopy, in some sense.

Has anyone done any work on this, and is there anything interesting that can be said?

Edit: I've just realized that there are many other questions I could have asked about (co)homology of combinatorial simplicial complexes before asking this one, but let's stick with this for now.

1

There are 1 best solutions below

1
On BEST ANSWER

This is a good example of a situation where (co)homology is the wrong tool to use.

On the one hand, there "ought" to be lots of nontrivial elements of each cohomology group. For example, given any sequence of formulas $p_1, . . . , p_k$, let $\psi=\neg(p_1\wedge . . . \wedge p_k)$; then $$A=\{p_1, . . . , p_k, \psi\}$$ is inconsistent, but as long as no $p_i$ is a consequence of $\{p_j: j\not=i\}$, every proper subset of $A$ is consistent. So at first glance it seems like $A$ ought to correspond to a nontrivial element of the appropriate homology group.

The problem is that there might be something that "fills in" $A$ by other means. Let's consider the simplest possible case: $$A=\{p, q, \neg(p\wedge q)\}$$ (where $p, q$ are distinct propositional atoms). But now let $$A_1\{p, q, \top\}=, \quad A_2=\{p, \neg(p\wedge q), \top\}, \quad A_3=\{q, \neg(p\wedge q), \top\}.$$ Each $A_i$ is consistent, so their union is a subset of the simplicial complex we're looking at, and its boundary is exactly $A$.

To visualize this: consider a tetrahedron with its bottom face removed. The boundary of the bottom ex-face "looks like" a representative of a nontrivial element of cohomology, until we "look up" and see the rest of the complex, which "fills it in." And now I'm going to link to something about persistent homology on general principle.

More generally, we can "fill in" any cycle in the complex you describe. So its homology (and cohomology) is trivial. (In fact, a good exercise is to show that it's contractible!)

This is not to say that the hypergraph you've described, and related hypergraphs, are uninteresting; rather, that (co)homology is too coarse a tool to usefully study it. Indeed, see http://math.uchicago.edu/~mem/mm-char-seq-revised.pdf for some deep results on an analogous hypergraph in the context of first-order logic!