Scott & Tarski consequence (basic info)

Scott consequence relations (a.k.a. multiple-conclusion consequence relations), as oppossed to Tarski consequence operations (that have single formulas as consequences) take the consequence relation to bear one set of formulas to another. What follows is a brief explanation of the relation between these two types of consequence relations.

Let A, B, C, ... stand for sentences, a, b, c, ... for finite sets of sentences, and u, v, w, ... for arbitrary sets of sentences. Relative to a language, the complement of a set u will be denoted by u'.

A Scott sequent is of the form:
a⇒b
which can be read: if all sentences in a hold (=are true/are accepted/whatnot), so does at least one sentence from b [in short: a secures b]. For typographical reasons, this will also sometimes be written as "a>b".

A set of Scott sequents is a Scott consequence relation if it satisfies (for any A, a, b, c, d):
  • reflexivity: A⇒ A
  • Monotonicity: If a⇒b, a⊆c, b⊆d, then c⊆d.
  • Cut: If a⇒b, A and a,A⇒b, then a⇒b.
The intuitive justification for reflexivity is pretty obvious: every sentence entails itself. To get a better grip of the monotonicity requirement, observe that it is composed, in a sense, of two claims: (i) increasing of the premise set preserves consequence, (ii) increasing of the conclusion set preserves consequence.

Condition (i) captures the idea that if something follows if all the premises in a set are true, then the truth of some other sentences doesn't have any impact on this fact. (Nota bene, there are certain contexts where we might not want monotonicity to hold, say, for conditionals. For instance, even if it is true that if it's sunny, we'll go for a walk today, it's probably false that if it's sunny and I get hit by a car, we'll go for a walk today. Let's not worry about these things). Condition (ii), on the other hand, expresses the requirement that if the truth of all sentenes in the premise set makes at least one sentence in the conclusion set true, then the truth of all sentences in the premise set makes at least one sentence in any superset of the conclusion set true.

The Cut condition expresses the assumption that if [i] the truth of all sentences in a true entails the truth of either A, or one of the sentences in b, and [ii] the truth of all the sentences in a together with the truth of A entails the truth of at least one sentence in b, then [iii] the truth of all the sentences in a entails the truth of at least one sentence in b (i.e. entails that at least one sentence in b is true; it doesn't have to entail any specific sentence in b). For indeed, assume the [i] and [ii], and suppose that all the sentences in a are true. By [i] either A is true, or at least one sentence in b is true. In the latter case, we're done. In the former case, all the sentences in a are true, and A is true. Then, by [ii], at least one sentence in b is true.

The consequence operation is extended to infinite sets of sentences by requiring:
Compactness u⇒v iff a⇒b for some finite a⊆u, b⊆v.
The first neat thing to observe about Scott consequence operation in comparison to Tarski consequence operation is that dual notions can be easily defined. For instance, for any Scott consequence, a dual consquence operation can be defined:
a⇒db iff b⇒a
It turns out, this dual operation is also a Scott consequence (convince yourself!). In general, amy notion definable for Scott consequence operations has a dual notion.

Observe:
Fact 1. Any set of Scott sequents is contained in a least Scott consequence relation.
A set of sentences u is called a Scott theory of a consequence relation iff it is not the case that:
u⇒u'
The basic idea is that a theory is a set of sentences closed under consequence relation: that is, a set that doesn't make any sentence that doesn't already belong to it true. This is captured by the following fact:
Fact 2. A set of sentences u is a theory iff for any a, b:
if a⇒b and a⊆u, then u∩b is non-empty.
The basic reason why this holds is that if b has no common elements with u, this means that b is a subset of u', the complement of u. This means that if a secures b, then (by monotonicity) a also secures u'. But we also assume that a is a subset of u. Thus, by applying monotonicity again, we reach the conclusion that u secures u', which means that u is not a theory, which contradicts the assumption.


A few more words about the relation between Tarski and Scott consequence are due. Recall, that a Tarski consequence is characterized by a set of sequents a>A, where A is a sentence, satisfying reflexivity (A>A), monotonicity (if a>A and b is a superset of a, then b>A), and cut (if a>A and a, A>B, then a>B). The operation is extended to infinite sets of sentences by requiring compactness. A Tarski theory > generates a provability operator Cn: Cn(u)={A| u>A}. A Tarski theory is a set u such that u=Cn(u).

Now, even though intersections of Tarski theories (wrt. a Tarski consequence operation) are Tarski theories, this doesn't hold for Scott consequence operations. Not every intersection of a Scott theory is a Scott theory.

Off the top of my head, here's an example of two Scott theories whose intersection is not a Scott theory (although, I'm sloppy, so don't trust me and double-check if this is correct).
  • Language L: say we have only three sentences P, Q, R, no connectives.
  • Consequence operation: Start with extending the language with conjunction, disjunction, and material implication thus obtaining language L'. Then, for any two sets of sentences of L, a and b, a>b iff in L', the conjunction of the members of a tautologically entails (we're using classical propositional logic) the disjunction of the elements of b, on the assumption that R -> (P or Q). [convince yourself this actually is a Scott consequence operation]
  • Theories: {P, R} and {Q, R}.
First, observe that {P,R} is a theory. The complement of {P,R} is {Q}, and it is not the case that P&R tautologically entails Q, even on the assumption that R -> (P or Q).

Second, {Q,R} is also a theory: the complement of this set is {P}, and Q&R does not (even on our assumption) entail P.

Third, their intersection is {R}. But this actually isn't a theory, because, by assumption, R>{P,Q}.


There's a restricted version of the claim, though.

Say a set of theories is downward directed if for any two theories in that set, there is a theory in that set which is included in both theories. We have the following:
Fact 3. The intersection of a downward directed set of Scott theories is always a Scott theory.
Also, one can prove the existence of inclusion minimal theories containing some set of sentences and inclusion maximal theories disjoint from a set of sentences. Also:
Fact 4. For any Scott consequence >, the restriction of > to sequents whose second members are singletons is a Tarski relation. It's called a Tarski subrelation of >. For any >, the set of theories of the Tarski subrelation of > is the intersection of all theories of > plus the trivial theory.

So, why exactly does a difference shows up when we talk about intersections of Scott theories not being in general intersections? Well maybe this helps to understand why this happens:

Say a Scott consequence is singular iff for any a, b, if a>b, then a>B for some B in b.
Fact 5. Any intersection of theories of a singular Scott consequence is also a theory of that singular Scott consequence relation.
So, the difference arises basically because a finite set of sentences may be Sott-secured by another set, without any particular member of this set being secured.

Another fun fact. Every set of sets of sentences S determines a Scott consequence >S, defined by:
aSb iff for any u∈S, if a⊆u, then u∩b is non-empty.
Fact 6. Any set in S is a theory of the consequence operation generated by S.

Finally, the representation theorem for Scott consquences says something like this: take a Scott consequence >. Take the set of all theories of >, call it Con. Take the consequence relation generated according to the above instructions from Con. It turns out, this consequence relation will be the same as the original >. This means, Scott consequence relations are uniquely determined by their theories.



Comments