Different definitions of consequence relations' cut property

Question

Let $\bf L$ be a set, e.g. the set of all formulas in a particular language. A consequence relation on $\bf L$ is a relation $\vdash_{\bf L}$ between $\mathcal{P}({\bf L})$ (the powerset of $\bf L$) and $\bf L$ that satisfies Reflexivity (R), Monotonicity (M), and Cut (C), where (from now on let $\vdash$ denote $\vdash_{\bf L}$):

R) $T \cup \{A\} \vdash A$.

M) If $T \vdash A$, then $T \cup S \vdash A$.

C) If $T \vdash A$, and $T \cup \{A\} \vdash B$, then $T \vdash B$.

However, I came across this alternative definition for Cut (C'):

C') If $S \vdash B$, and $T \vdash C$ for all $C \in S$, then $T \vdash B$.

Given (R), note that (C') entails (C) (by taking $S$ to be $T \cup \{A\}$).

This begs the question of whether using (C') is equivalent to using (C). More precisely:

Do (R), (M), and (C) together entail (C')?

Note that the answer is yes in case $S$ is assumed to be finite, since (C) can be applied once for every $C \in S$. In particular, consider Finitariness (F):

F) If $T \vdash A$, then a finite $T' \subseteq T$ exists such that $T' \vdash A$.

(F), (R), (M), and (C) together entail (C').

Another broad special case in which this holds is when the relation is semantically defined. That is, consider Semanticity (S):

S) There exists a set $\bf M$ (of "models") and a relation $\models$ between $\bf M$ and $\bf X$ such that $T \vdash A$ iff for every $v \in \bf M$, if $v \models D$ for every $D \in T$, then $v \models A$.

(S), (R), (M), and (C) together entail (C').

Every consequence relation I know (from logic) satisfies either (F) or (S). Other relations I considered did not differentiate between (C) and (C').

Answer 1

No, $C'$ is not so deducible. That said, all the counterexamples I know are very silly. The basic idea is to have a deduction relation which behaves fundamentally differently on infinite theories than on finite theories.

For simplicity, consider the following "toy" language L: sentences are just ordinals. (Or if you prefer, countable ordinals.) Our deduction relation will then be:

$\Gamma\vdash\alpha$ iff for some finite $n$ we have $\sup(\Gamma)+n>\alpha$.

So, for example, $\{17, \omega\}\vdash \omega+12$ (we have $\sup(\Gamma)=\omega$; now take $n=13$). It's easy to check that this satisfies (R), (M), and (C): (R) follows since the supremum of a set is at least as big as each of its elements, (M) follows since the supremum is monotonic (making a set bigger only increases it), and (C) follows since "finite + finite = finite."

Now consider the following:

• From the set of finite ordinals we can deduce $\omega$. (In symbols, "$\omega\vdash\omega$," but that's perhaps a bit confusing at first glance: it looks like "$\{\omega\}\vdash\omega$" - which is trivially true - but it isn't.)

• For each $n\in\omega$ we have $\{1\}\vdash n$.

• But $\{1\}\not\vdash\omega+1$.

---

Incidentally, I'd argue that (C') is the ideal cut principle. It basically says (in conjunction with (R) and (M)) that the deductive closure operation $$\mathcal{D}:\Gamma\mapsto\{\varphi:\Gamma\vdash\varphi\}$$ is well-behaved. Specifically, (C') is equivalent (over (R)+(M)) to the statement that $\mathcal{D}$ is idempotent: $\mathcal{D}(\mathcal{D}(\Gamma))=\mathcal{D}(\Gamma)$.

This lets us define the notion of a theory with respect to the consequence relation, namely a set $\Gamma$ satisfying $\mathcal{D}(\Gamma)=\Gamma$. By contrast, these might not even exist with merely (C)! (E.g. in the example in my answer, for any set $\Gamma$ of ordinals we have $\sup(\Gamma)+1\in\mathcal{D}(\Gamma)\setminus\Gamma$.)

Finally, it's also worth point out that there is a way to take a consequence relation $\vdash$ satisfying only (R,M,C) and create a new one satisfying (R,M,C'). Specifically, we define $\vdash'$, a consequence relation on the same class of sentences, by setting $$\Gamma\vdash'\varphi\quad\iff\quad\varphi\mbox{ is in every $\vdash$-closed superset of $\Gamma$}.$$ It's easy to check that $\vdash'$ satisfies (R,M,C') and extends $\vdash$ - moreover, it's the smallest such relation, and in particular if $\vdash$ satisfies (C') then $\vdash$ and $\vdash'$ are the same thing. Sets of sentences which aren't contained in any $\vdash$-closed set of sentences - e.g. in my example above, all of them - are now trivial with respect to $\vdash'$ (the right generalization of inconsistent in the setting of classical logic): if $\Gamma$ is such a set, then we get $\Gamma\vdash'\varphi$ for every $\varphi$ by vacuity.