# Different definitions of consequence relations' cut property

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').

• I don't understand the vote to close - this seems a perfectly reasonable question. – Noah Schweber Jul 24 '19 at 19:32

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.

• I guess with (C) you could still define a theory as a set that is equal to $\mathcal{D}(\Gamma)$ for some set $\Gamma$. I assume your point was that (C') is better behaved in that $\mathcal{D}$ is necessarily a closure operation. – liwoxa Jul 25 '19 at 9:57