Let $S$ be a set of sentences from first order logic that is closed under logical consequence. Letting $C$ denote the logical closure operator, we have $S=C(S)$.

Suppose that there is a set $A$ of sentences from first order logic such that $A$ is finite and $C(A)=S$.

Is there a way to determine $A$ from $S$?

In other words, is there an algorithm for determining which elements of $S$ are also elements of $A$?


If you had a specific $A$ that led to $S$, then no, you cannot recover $A$ from $S$, even if you knew that $A$ is finite ($S$, of course, will be infinite, because there are infinitely many tautologies that will all be in $S$).

For example, if you had $P \land Q \in S$, you don't know whether you had $P \land Q \in A$, or both $P \in A$ and $Q \in A$, or maybe all three, or maybe both $P$ and $P \land Q$, or maybe both $Q$ and $P \land Q$, or maybe just $Q \land P$, or ...

Something you could do, is to find a kind of 'minimal' set whose closure is $S$. See prime implicants for one way to think about that. However, the techniques discussed there are for propositional logic, and for first-order logic things will get a lot more complicated ... indeed, you may well run into the problem of the undecidability of first-order logic when trying to find such a 'minimal' set.

Finally, as I said, $S$ will be of infinite size, so there are some serious practical considerations to deal with here as well!

| cite | improve this answer | |
  • $\begingroup$ Thanks for the answer! I see that it won't be possible to recover the unique set A. But will it be possible to recover from S a set of sentences A' such that A' is logically equivalent to A? That is, from S can we find A' such that A' is logically equivalent to any A where C(A) = S? $\endgroup$ – Aaron Thieme Jul 11 '17 at 18:00
  • $\begingroup$ @AaronThieme Logical equivalence is typically defined as between two sentences, not two sets of sentences ... Of course, one intuitive way to define logical equivalence between two sets of sentences is to say: $A$ is equivalent to $A'$ if and only if the $Conj(A)$ is equivalent to $Conj(A')$, where $Conj(A)$ is the conjunction of all sentences in $A$. But now note that for any set $A$: $Conj(A)=Conj(C(A))$, since whenever some statement $\psi$ can be inferred from statement $\varphi$, then $\varphi$ is logically equivalent to $\varphi \land \psi$. $\endgroup$ – Bram28 Jul 11 '17 at 18:09
  • $\begingroup$ @AaronThieme In other words, if you are looking for an $A'$ such that $A'$ is equivalent to $A$ for which $C(A)=S$ (I assume you present me with such an $A$), then I will simply say: sure! Just pick $A'=S$, for whichever $A$ you present to me, the fact that $C(A)=S$ makes $A$ logically equivalent to $C(A)=S$ in the sense just defined, and hence $A'=S$ is logically equivalent to $A$. $\endgroup$ – Bram28 Jul 11 '17 at 18:11
  • $\begingroup$ I'm interested, however, in finding a finite set $A'$---though I didn't state this in my comment to be fair. So the finite restriction should rule out the easy response that takes $A'=S$. Also, a side note: doesn't $Conj(C(A))$ require an infinitary logic? $\endgroup$ – Aaron Thieme Jul 11 '17 at 21:36
  • $\begingroup$ @AaronThieme OK, but even saying it is finite still leaves open many possibilities I mentioned in my original Answer. And yes, you would need infinitary logic to create a conjunction with infinitely many conjuncts. So, if you want to avoid that, you can also define the equivalence of two sets of statements $A$ and $A'$ as: $A$ and $A'$ are equivalent if and only if every statement in $A$ is implied by $A'$, and vice versa. But yet again, that leaves all of the possibilities mentioned in my post, e.g. $\{P, Q \}$, $\{P \land Q \}$, $\{ Q \land P \}$, $\{ P, P \land Q\}$, etc. are all equivalent $\endgroup$ – Bram28 Jul 11 '17 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.