THE LOGIC NOTES

Consequence relation Glossary

Definition

Let R be a binary relation relating sets of objects to individual objects. Then we say R is a consequence relation iff it satisfies three conditions:

  • Reflexivity: for all objects a, R({a},a).

  • Monotonicity: for all sets X and Y and all objects a, if X ⊆ Y and R(X,a) then R(Y,a).

  • Extended transitivity: for all sets X and Y and all objects a and b, if R(Y,a) and R(X∪{a}, b) then R(X∪Y, b).

Comments

Extended transitivity, known as "cut" in the literature of proof theory, is sometimes given in a slightly stronger form: for all sets X and Y and all objects a, if R(Y,a) and R(X,b) for every b in Y, then R(X, a). For finite sets of premises. these two formulations are equivalent.

There is a more general notion of consequence appropriate to logic with multiple conclusions. See the sequent calculus link below for details.

Examples

  1. Let R(X,A) mean X ⊢ A. That is, it holds iff there is a derivation of A from X by means of some notion of "immediate consequence". Then R is a consequence relation.
  2. Let R(X,A) mean X ⊨ A. That is, it holds iff all interpretations (if any) which satisfy all formulae in X also satisfy A. Then R is a consequence relation.

    3. These are the intended cases, but many other relations are also "consequence relations" in the sense that they happen to satisfy the conditions. For example:

  3. In set theory, let R(X,a) hold iff a is a member of X. Then R is a consequence relation.
  4. In arithmetic, let R(X,a) hold iff either there is no lower bound on the set of numbers X or else inf(X) ≤ a. Then R is a consequence relation.
  5. Let X be a set of intersections in the downtown area of a city, and let i be an intersection. Let R(X,i) hold iff i is "downtown-reachable" from X. That is, it holds iff there is a point in X from which the one-way system allows you to get to i without exiting the downtown area. Then downtown-reachability is a consequence relation.

Links