consequence operator
1 Definition
Let $L$ be a set. A consequence operator on $L$ is a mapping^{1}^{1}Here, β$\mathrm{\pi \x9d\x92\xab}$β denotes the power set^{} and $\mathrm{\beta \x84\pm}$ denotes the finite power set. $C:\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$ which satisfies the following three properties:

1.
For all $X\beta \x8a\x86L$, it happens that $X\beta \x8a\x86C\beta \x81\u2019(X)$.

2.
$C\beta \x88\x98C=C$

3.
For all $X,Y\beta \x8a\x86L$, if $X\beta \x8a\x86Y$, then $C\beta \x81\u2019(X)\beta \x8a\x86C\beta \x81\u2019(Y)$
If, in addition^{}, the following condition is satisfied, then a consequence operator $C$ is known as finitary . (Synonyms are βfinite consequence operatorβ and βalgebraic consequence operatorβ.)

β’
For all $X\beta \x88\x88L$, it happens that $C\beta \x81\u2019(X)=\underset{Y\beta \x88\x88\mathrm{\beta \x84\pm}\beta \x81\u2019(X)}{\beta \x8b\x83}C\beta \x81\u2019(Y)$.
It is worth noting that, if the above condition is satisfied, then the third condition of last paragraph becomes superfluous β as shown in http://planetmath.org/node/ 8678an attachment, it automatically follows from conitions 1 and 2 of last paragraph and the condition stated above.
A consequence operator $C$ such that $C\beta \x81\u2019(\mathrm{\beta \x88\x85})=\mathrm{\beta \x88\x85}$ is called axiomless. A consequence operator $C$ such that $C\beta \x81\u2019(\mathrm{\beta \x88\x85})\beta \x89\mathrm{\beta \x88\x85}$ is called axiomatic.
2 Motivation
Alfred Tarksi introduced consequence operators as a way of discussing the notion of conclusions^{} following from premises in a general fashion. Suppose that the set $L$ consists of statements in some language^{}. Then, given a set of statements $X$, let $C\beta \x81\u2019(X)$ be the set of all statements which can be inferred form statements of $X$.
The defining properties of βconsequence operatorβ given above then express some fundamental facts about the process of inferring conclusions from premises: Any statement can be concluded from itself. If a statement $s$ follows from a set of premises $X$ and $Y$ is a superset^{} of $X$, then $s$ also follows from $Y$. If one augments a set of premises by conclusions derived from those premises, then one can only draw conclusions from the larger set which could have been drawn from the original set of premises. Note that these conditions hold for a large class of logics, not just classical logic of Aristotle, Boole, and Frege. However, they do not hold for all logics β in particular, there are the socalled nonmonotonic logics in which it is not always the case that, if $X\beta \x8a\x82Y$, then $C\beta \x81\u2019(X)\beta \x8a\x86C\beta \x81\u2019(Y)$.
In terms of this usage in logic, it is easy to understand the origin of the terms βaxiomaticβ and βaxiomlessβ. An axiom in a logical theory is a statement which is assumed true without having to prove it from any other statement. Hence, an axiom is a consequence of the empty set^{}, so we call consequence operators which allow one to deduce conclusions from an empty set of premises axiomatic.
The distinction of finitary consequence operators has to do with whether one is permitted to draw a conclusion from an infinite set^{} of premises which could not be drawn from any finite subset thereof. As for why one might want to do this, consider the following example. Suppose $X$ consists of the following statements:

β’
$1={1}^{2}$

β’
$2={1}^{2}+{1}^{2}$

β’
$3={1}^{2}+{1}^{2}+{1}^{2}$

β’
$4={2}^{2}$

β’
$5={2}^{2}+{1}^{2}$

β’
$6={2}^{2}+{1}^{2}+{1}^{2}$

β’
$7={2}^{2}+{1}^{2}+{1}^{2}+{1}^{2}$

β’
$8={2}^{2}+{2}^{2}$

β’
$9={3}^{2}$

β’
$10={3}^{2}+{1}^{2}$

β’
$11={3}^{2}+{1}^{2}+{1}^{2}$

β’
$12={2}^{2}+{2}^{2}+{2}^{2}$

β’
$13={3}^{2}+{2}^{2}$

β’
$14={3}^{2}+{2}^{2}+{1}^{2}$

β’
$\mathrm{\beta \x8b\u2015}$
From $X$ one would like to be able to draw the conclusion βAny positive integer can be expressed as the sum of at most four squares.β. This conclusion, however, cannot be inferred from any proper subset^{} of $X$, in particular, from any finite subset of $X$. To make this conclusion would require a consequence operator which is not finitary.
3 Examples

1.
To begin, there are two trivial consequence operators defined on any set. One is the identity operator $I:\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$ defined as $I\beta \x81\u2019(X)=X$. The other is the constant operator $U:\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$ defined as $U\beta \x81\u2019(X)=L$. It is perfectly straightforward to check that these two operators satisfy the defining properties of consequence operator and, furthermore, that they are both finitary consequence operators and that $I$ is axiomless whilst $U$ is axiomatic. Trivial though they may be, these operators play an important role as exrtremal elements in the lattice^{} of all consequence operators over a given set.

2.
Next, we consider some less trivial consequence operators which can be defined over an arbitrary set. Let $X$ and $Y$ be any two subsets of $L$. Then we may define operators ${C}_{\beta \x88\copyright}\beta \x81\u2019(X,Y):\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$ and ${C}_{\beta \x88\u037a}\beta \x81\u2019(X,Y):\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$ as follows:
${C}_{\beta \x88\copyright}\beta \x81\u2019(X,Y)\beta \x81\u2019(Z)$ $=$ $\{\begin{array}{cc}X\beta \x88\u037aZ\hfill & Y\beta \x88\copyright Z\beta \x89\mathrm{\beta \x88\x85}\hfill \\ Z\hfill & Y\beta \x88\copyright Z=\mathrm{\beta \x88\x85}\hfill \end{array}$ ${C}_{\beta \x88\u037a}\beta \x81\u2019(X,Y)\beta \x81\u2019(Z)$ $=$ $\{\begin{array}{cc}X\beta \x88\u037aZ\hfill & Y\beta \x88\u037aZ=Z\hfill \\ Z\hfill & Y\beta \x88\u037aZ\beta \x89Z\hfill \end{array}$ It is shown that these are indeed consequence operators in an attachment to this entry.

3.
A much larger class of consequence operators may be defined as follows. Let $K$ be a subset of $\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$ which includes $L$. Then, as shown in an http://planetmath.org/node/8671attachment, the map $C:\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$, defined as
$$C\beta \x81\u2019(X)=\beta \x88\copyright \{Y\beta \x88\x88K\beta \x88\pounds X\beta \x8a\x86Y\},$$ is a consequence operator. As we shall see, all consequence operators can be obtained by this construction. In particular, the examples discussed above can be obtained as follows: To obtain $I$, set $K=\mathrm{\pi \x9d\x90\x8f}\beta \x81\u2019(L)$; to obtain $U$, set $K=\{L\}$; to obtain ${C}_{\beta \x88\copyright}\beta \x81\u2019(X,Y)$, set
$$K=\{Z\beta \x8a\x86L\beta \x88\pounds Y\beta \x88\copyright Z=\mathrm{\beta \x88\x85}\}\beta \x88\u037a\{X\beta \x88\u037aZ\beta \x88\pounds Z\beta \x8a\x86L\beta \x88\S Y\beta \x88\copyright Z\beta \x89\mathrm{\beta \x88\x85}\};$$ to obtain ${C}_{\beta \x88\u037a}\beta \x81\u2019(X,Y)$, set
$$K=\{Z\beta \x8a\x86L\beta \x88\pounds Y\beta \x88\u037aZ\beta \x89\mathrm{\beta \x88\x85}\}\beta \x88\u037a\{X\beta \x88\u037aZ\beta \x88\pounds Z\beta \x8a\x86L\beta \x88\S Y\beta \x88\u037aZ=\mathrm{\beta \x88\x85}\}.$$ 
4.
Turning to more specific examples, we have the example which inspired the definintion in the first place. Let $L$ be a set of logical expressions constructed from some set of sentence^{} letters and predicate^{} letters and the usual connectives^{} and quantifiers^{}. Given a subset $X\beta \x8a\x86L$, let $C\beta \x81\u2019(X)$ be the set of all expressions $\mathrm{{\rm O}\x88}$ for which there exists a finite set^{} of expressions ${\mathrm{{\rm O}\x95}}_{1},\mathrm{\beta \x80\xa6},{\mathrm{{\rm O}\x95}}_{n}$ such that $\mathrm{\beta \x8c\x9c}\beta \x81\u2019{\mathrm{{\rm O}\x95}}_{1}\beta \x88\S \mathrm{\beta \x8b\u2015}\beta \x88\S {\mathrm{{\rm O}\x95}}_{n}\beta \x87\x92\mathrm{{\rm O}\x88}\beta \x81\u2019\mathrm{\beta \x8c\x9d}$ is a tautology^{}. Note that this is a finitary consequence operator β it does not enable one to make the sort of deductions^{} from infinite sets of premises described above.

5.
This notion of consequence operator also applies to areas of mathematics other than logic. For instance, suppose that $L$ is a vector space^{}. Then the operator which assigns to a subset of $L$ the vector subspace which it spans is a consequence operator. This particular consequence operator is finitary because if a vector $v$ belongs to the span of a set $X$, then $v$ can be expressed as a linear combination^{} of a finite number of elements of $X$.

6.
The closure operator^{} in topology^{} is a consequence operator. It is worth pointing out that not every consequence operator can be expressed as the closure operator for some topology because the closure operator satisfies some extra conditions beyond those which define consequence operators. Typically, the closure operator is not finitary because infinite subsets of topological spaces may have limit points^{}.
4 Alternative Definition and Generalization
A consequence operator can be characterized by its fixed points^{}. Given a consequence operator $C:\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)\beta \x86\x92\mathrm{\pi \x9d\x92\xab}\beta \x81\u2019(L)$, set $K=\{X\beta \x8a\x86L\beta \x88\pounds C\beta \x81\u2019(X)=X\}$. By the second defining property of consequence operator, we have $K=\{C\beta \x81\u2019(X)\beta \x88\pounds X\beta \x88\x88L\}$. One can show that
$$C\beta \x81\u2019(X)=\beta \x88\copyright \{Y\beta \x88\x88K\beta \x88\pounds X\beta \x8a\x86Y\}.$$ 
Conversely, suppose that $K$ is a subset of $L$ with the following minimum property:

β’
For every $X\beta \x88\x88L$, there exists a $Y\beta \x88\x88K$ such that $X\beta \x8a\x86Y$ and if, for any $Z\beta \x88\x88K$, if $X\beta \x8a\x86Z$, then $Y\beta \x8a\x86Z$.
Then the operator $C$ defined as
$$C\beta \x81\u2019(X)=\beta \x88\copyright \{Y\beta \x88\x88K\beta \x88\pounds X\beta \x8a\x86Y\}$$ 
is a consequence operator with $K$ as its set of fixed points.
One may also define consequence operators in the more general context of a partially ordered set^{} which may not be the power set of any set. Suppose that $\beta \x9f\xa8S,\beta \x89\u20ac\beta \x9f\copyright $ is a partially ordered set. Then we may define a consequence operator on this ordered set to be a map $C:S\beta \x86\x92S$ which satisfies the following three properties:

1.
For all $X\beta \x88\x88S$, it happens that $X\beta \x89\u20acC\beta \x81\u2019(X)$.

2.
$C\beta \x88\x98C=C$

3.
For all $X,Y\beta \x88\x88S$, if $X\beta \x89\u20acY$, then $C\beta \x81\u2019(X)\beta \x89\u20acC\beta \x81\u2019(Y)$
Such more general consequence operators arise frequently when we restrict attention to distinguished subsets of a set. As an example, we may consider the following situation. Let $S$ be the set of linear subspaces of a Banach space, ordered by inclusion. Then the operator $C:S\beta \x86\x92S$ which assigns to each subspace^{} its Cauchy completion is a consequence operator.
As an example which does not arise this way, let $S=\mathrm{\beta \x84\x9d}$ with the usual order. Then the ceiling function $\beta \x8c\x88\beta \x8b\x85\beta \x8c\x89:\mathrm{\beta \x84\x9d}\beta \x86\x92\mathrm{\beta \x84\x9d}$ is a consequence operator.
For another example, let $S$ be the set of all fields with a countable^{} number of elements. This set may be ordered as follows: $E\beta \x89\u20acF$ if and only if there exists a nontrivial morphism of $E$ into $F$. Then the operator which sends each field to its algebraic closure is a consequence operator.
Title  consequence operator 
Canonical name  ConsequenceOperator 
Date of creation  20130322 16:28:48 
Last modified on  20130322 16:28:48 
Owner  rspuzio (6075) 
Last modified by  rspuzio (6075) 
Numerical id  40 
Author  rspuzio (6075) 
Entry type  Definition 
Classification  msc 03G25 
Classification  msc 03G10 
Classification  msc 03B22 
Synonym  closure operator 
Defines  finitary consequence operator 
Defines  finite consequence operator 
Defines  algebraic consequence operator 
Defines  axiomatic consequence operator 
Defines  axiomless consequence operator 