4
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – liwoxa Jul 25 '19 at 9:57

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.