# In what sense is logical entailment a set-theoretic relation?

In set theory a relation is a subset of a Cartesian product. I suppose that in logics this product is the Cartesian square of the powerset of all propositions(?).

Semantic/model-theoretic entailment between two sets holds (is "true"?) when there is no interpretation that makes elements left of the double turnstile $$\vDash$$ all true and elements on the right all false.

Syntactic/proof-theoretic entailment $$\vdash$$ holds if you can derive the RHS from the LHS.

In what formal sense are these set theoretic relations, and is this at all important?

• Okay, propositions do form a set (as long as you do not add too many constant symbols to the language, for example), and so "entails" is indeed a relation in the way you describe. -- However, we'd use the term (binary) relation rather for a WFF with two free variables. So for example $x= y$ or $x\in y$ or $\forall z\colon z\in x\to z\in y$ would be relations of this form (in the language of FOL with $=$ and $\in$, as used in set theory), but are not relations in the Cartesian product sense, simply because we'd need the Cartesian product of proper classes to express this. Commented Dec 3, 2020 at 10:31
• Hi @HagenvonEitzen Thanks. When you say "we'd use the term (binary) relation rather for a WFF with two free variables" is this a conventional use somewhere? Does this contradict the answer below? I am afraid I don't understand what proper classes are :(.
– JRC
Commented Dec 3, 2020 at 16:00

Under the most common definition of entailment, it is a relation between a (possibly empty or singleton) set of premise propositions and a single conclusion proposition, i.e. a subset of $$\wp{(\text{PROP})} \times \text{PROP}$$ with $$\langle \Gamma, \phi \rangle \in R \text{ iff } \Gamma \vDash \phi$$.
If one permits, rather than a single proposition, a set of conclusions which are read as disjoined (entailment holding if at least one of the conclusions is true), one gets $$R \subseteq \wp{(\text{PROP})} \times \wp{(\text{PROP})}$$ wiht $$\langle \Gamma, \Delta \rangle \in R \text{ iff } \Gamma \vDash \Delta$$ by the definition you cited.

While the relation holds between sets of propositions, a set-theoretic definition can be given via the propositions' models: By definition, entailment holds (not: "is true") iff all interpretations which are models of all premises are also models of at least one conclusion. This means that the set of models of the premises is a subset of the set of models of the conclusions. The models of the premises are those interpretations which are models of all of the premises; this is the intersection between the models of the premises. The models of the conclusions are those interpretations which are models of at least one of the conclusions; this is the union between the models of the conclusions. Thus, we have:

$$\psi_1, \ldots, \psi_m \vDash \phi_1, \ldots, \phi_n\\ \text{ iff } \bigcap_{i=1}^{m} \{\mathcal{M}: [\![\psi_i]\!]^\mathcal{M} = 1\} \subseteq \bigcup_{j=1}^{n} \{\mathcal{M}: [\![\phi_j]\!]^\mathcal{M} = 1\}$$

In order to make the limit cases behave as desired, one needs to define that the set of models for an empty set of premises (empty intersection of models) is the set of all structures, and the models for an empty set of conclusions (empty union of models) is the empty set.

For the variant with a singular conclusion, it is the same without disjunction of truth/union of models on the right-hand side:

$$\psi_1, \ldots, \psi_m \vDash \phi\\ \text{ iff } \bigcap_{i=1}^{m} \{\mathcal{M}: [\![\psi_i]\!]^\mathcal{M} = 1\} \subseteq \{\mathcal{M}: [\![\phi]\!]^\mathcal{M} = 1\}$$

As for whether this is relevant: It does not really add new information because it is pretty much a direct consequence or even just a paraphrase of the definition, but perhaps it helps to better understand some of the properties of the entailment relation (contradictory premises entail arbitrary conclusions because the empty set is a subset of every set; an argument with no premises is valid iff the conclusion is a tautology because the conclusion's models then must be the set of all structures; entailment is reflexive and transitive but not symmetric because so is the subsethood relation, etc.)

A similar idea of accounting for relations between propositions via their models is also useful in the field of cognition, to model an agent's beliefs and changes in those beliefs through the addition of new information, though this is usually done with the related concept of possible worlds rather than structures.

• Thanks for your thoughtful and helpful response. I am still wondering about syntactic entailment, in case you have any ideas.
– JRC
Commented Dec 15, 2020 at 11:43
• Syntactic entailment is defined as the existence of a derivation; this doesn't give rise to a set-theoretic treatment. But provided that the proof system is sound and complete, $\Gamma \vdash \Delta \Longleftrightarrow \Gamma \vDash \Delta$, the model-theoretic condition follows indirectly through the equivalence to semantic entailment. Commented Dec 15, 2020 at 13:13