Tag: negation

On Tarski’s Calculus of Systems (2)

Bas van FraassenLeave a comment

The relation between negation and infinity loomed large in the Intuitionist critique of mathematics.  But when we come to Intuitionistic logic, it turns out to be all about the conditional.  Negation comes in just by means of a definition:  ~A =def A β†’ f.  

It is in the logic’s realizations that the intimate relation between negation and infinity comes to the fore.  Recall from the previous post that the lattice of theories of any distributive logic is a complete Heyting lattice with zero element Cn(πœ™), and

T β†’ T’ is the weakest (largest) theory X such that T βˆ© X βŠ† T’; 

T β†’ T’ = βŠ•{T’’: T βˆ© T’’ βŠ†  T’)

The pseudo-complement Β¬T of T, if it exist, must be the weakest element X which is contrary to T, that is, it is such that T βˆ© X βŠ† Cn(πœ™).  So we instantiate the above:  Β¬ T is the weakest element X such that  T βˆ© X βŠ†  Cn(πœ™)), hence:

Β¬ T  = T β†’ Cn(πœ™).  Equivalently, Β¬ T = βŠ•{T’: T βˆ© T’ βŠ†  Cn(πœ™)}. 

So much, so general.  How does it happen that the Laws of Excluded Middle and of Double Negation fail in Intuitionistic logic, and their corresponding principles fail in the calculus of systems?

To continue, let L be classical propositional logic, with & and ~ as primitive connectives and let S be the set of all sentences.  Thus S = Cn(S) is the unit (top) of the lattice. For brevity, if A is a sentence I will write  β€œCn(A)” for “Cn({A})”.

Note: Contrariety, the condition T βˆ© T’ βŠ†  Cn(πœ™), is different from mutually inconsistency.  With p, q atomic sentences, Cn(πœ™) is contrary to but consistent with Cn(p), Cn(p) and Cn(~p) are both mutually inconsistent and contrary. But Cn(p & q) and Cn(~p & q) are mutually inconsistent, their join is S, but not contrary for their intersection contains non-theorem q.  Contrariety is this:

Theorem 1.  T βˆ© T’ βŠ†  Cn(πœ™) iff for every non-theorem A in T there is a consistent extension of T’ that includes ~A.

To prove this we can appeal to the general features of theories in classical logic:

  • any consistent theory is part of a maximal consistent theory 
  • every theory is the intersection of all its maximal consistent extensions
  • for all sentences A, if T is a maximal consistent theory then T contains either A or ~A 
  • if T does not imply A then T has a maximal consistent extension that includes ~A 

Proof.  

  •  Let A be any L-non-theorem in T.   Suppose that T’ has no consistent extension that includes ~A.  Then A is in all the maximal consistent extensions of T’, hence in T’, hence in T βˆ© T’,  which is thererfore not included in Cn(πœ™).
  •  Suppose that for every L-non-theorem A in T, T’ has a consistent extension which includes ~A.  Then if A is an L-non-theorem in T, A is not in T’, and hence not in T βˆ© T’.  If A is an L-non-theorem that is not in T then it is also not in T βˆ© T’.  Therefore T βˆ© T’ contains only L-theorems, and is Cn(πœ™).

Lemma 1. Cn(~A) βŠ† Β¬Cn(A)

If E is in Cn(A) there is a sentence B such that E is equivalent to A v B.  For each such sentence Cn(~A) has a consistent extension that includes ~(A v B).

  • If ~A entails B then it too entails A v B, so then A v ~A entails A v B, hence A v B is an L-theorem.
  • If ~A does not entail B then Cn(~A) has a maximal consistent extension that includes ~B, which includes ~A & ~B.

So by Theorem 1, Cn(A) ∩ Cn(~A) βŠ† Cn(πœ™). Hence Cn(~A) βŠ† CnA) β†’ Cn(πœ™) = Β¬Cn(A).

Theorem 2.  If T is finitely axiomatizable then T Θ Β¬T = S

Because of the classical conjunction rules, if T is finitely axiomatizable then there is a sentence A such that T = Cn(A).  By the lemma, Cn(A) Θ  Cn(~A) βŠ† Cn(A) Θ  Β¬Cn(A).  But Cn(A) Θ  Cn(~A) = Cn(Cn(A) βˆͺ  Cn(~A)) = S.

It follows then that violations of Excluded Middle can only be by theories that are not finitely axiomatizable.

To pursue this we need to improve on the above lemma.

Lemma 2.   T βˆ© T’ βŠ†  Cn(πœ™) iff for every non-theorem A in T there is a maximal consistent extension of T’ that includes ~A.

This follows at once from Theorem 1.

Lemma 3.  If T βˆ© T’ βŠ†  Cn(πœ™) then T’ βŠ† βˆ© Cn({~A: A is in T})

Suppose T βˆ© T’ βŠ†  Cn(πœ™) and that A is an L-non-theorem of T.  Let KT’(A) be the set of all consistent extensions of T’ that include ~A.  So βˆ©KT’(A) βŠ† Cn(~A). Let MT’ be the set of all maximal consistent extensions of T.  Then for each L-non-theorem A of T:

            T’ = ∩MT’ βŠ† βˆ©KT’(A) βŠ† Cn(~A). 

Since T’ has a consistent extension that includes ~A for each L-non-theorem in T it follows that T’ βŠ† βˆ©{Cn(~A): A is an L-non-theorem in T}.  From this the lemma follows because if A is an L-theorem then Cn({~A}) = S, which has no effect on the intersection.

Theorem 3.    Β¬T = ∩({Cn{~A}: A in T}).

First, it is clear that for every L-non-theorem A in T, βˆ©({Cn{~A}: A in T}) has a consistent extension that includes ~A.  Therefore ∩({Cn{~A}: A in T})  βŠ†  Β¬T by theorem 1 and definition.  

Secondly,  T βˆ© Β¬T βŠ†  Cn(πœ™), so by Lemma 3, Β¬T βŠ† βˆ© Cn({~A: A is in T})

Corollaries:  Cn({~A}) = Β¬Cn(A), Β¬Cn(πœ™) = S, Β¬S = Cn(πœ™)

This theorem gives us a way to identify the pseudo-complement of theories that are not finitely axiomatizable.

Example. Let AT be the infinite list of atomic sentences p1, …, pm , … and T = Cn(AT).  Let ATfin be the set of finite conjunctions of atomic sentences. Every member of T is equivalent to a finite conjunction C of atomic sentences disjoined with some other sentence A (e.g. p v q).  

So Β¬T = ∩ Cn({~(C v A): C in ATfin})

As an example, consider the L-non-theorem (p1 & ~p2). Could it belong to Β¬T?  It does not belong either to Cn(~p1) or to Cn(~p2). Nor does it belong to Cn(~q) for any q in ATfin other than  p1 or p2.

We can generalize this reasoning to cover any L-non-theorem.  Since L is classical propositional logic, we can think in terms of truth-table rows or their generalization: 

a finite state-description is a consistent conjunction p*1 & …& p*m of  atomic sentences each of which either has or does not have an appended negation sign. 

In classical propositional logic,  A is an L-non-theorem if and only if there is a finite state-description B such that Bβ”œL~A.  For any such B, since B is finite and AT is infinite, there is an atomic sentence q which does not appear in B.  But then B is not in Cn(~q), hence not in Β¬T.  Therefore there is no derivation of ~A in Β¬T.  Hence Β¬T = Cn(πœ™).

This gives us a counterexample to both Excluded Middle and Double Negation, with T = Cn(AT):

            T βŠ• Β¬T = T and T β‰  S

            Β¬ Β¬T = Β¬ Cn(πœ™) = S and S β‰  T

The following analogy strikes me as apt.  Remember that Β¬T  is also the join of its contraries.  There are uncountably many infinite state descriptions, all inconsistent with each other.  So we can look to continua for analogies. In a geometric space, the join of a family of subspaces is the least subspace that contains all.  Suppose P is a plane, its subspaces are the straight lines through the origin.  Take away one such straight line:  the join of the remaining ones is still the entire plane.

Probability statements (2) Compounds

Bas van FraassenLeave a comment

There is never any difficulty in adding truth-functional connectives to a set of statements, but doing so doesn’t give us any new insight into their character or structure. The better approach is to ask: are there, in this very class of statements itself, already ones that count as conjunctions, disjunctions, and the like? (What is the ‘internal’ logic of this sort of discourse?)

Conjunction

A simple example is (P(A) > x & P(A) < y), which can also be written as: P(A) Ξ΅ (x, y). But that is the special case, of two statements about the probability of a single proposition. What about such combinations when different propositions are involved?

Theorem: If C is a family of convex sets (finite, countable or uncountable), then the intersection of the members of C is a convex set.

Proof: That the intersection ∩C is convex is trivially so if the intersection is empty, or has just one member. If ∩C has more than one member, consider any two p, p’ of its members: these belong to each member of C, and hence any of their convex combinations are also members of each member of C. Hence all the convex combinations belonging to all members of C, and hence of ∩C, are in ∩C.

This Theorem shows that it is fine to introduce the usual sort of conjunction in to the language, for then the set of measures that satisfy both of two elementary statements will also be convex. So if Q and R are elementary statements then (Q & R) is the statement such that |Q&R| = |Q| ∩ |R|, and this is again an elementary statement.

Disjunction

The same ease is not to be found for disjunction. The union of two convex sets is not in general convex. Anyway, we already know that disjunction does not behave like a truth-function when it comes to probability. In fact, it does not make sense to ask whether p satisfies (P(A) = r or P(A) = s) , as opposed to asking whether it satisfies either (P(A) = r) or satisfies (P(A) = s). At most we can ask whether p satisfies what the two ‘have in common’.

Can we find an operation on elementary statements that has the main characteristics we require of disjunction, in general?

Requirement. The general concept of disjunction of two statements, Q, R, in any kind of language, requires that it must be the logically strongest statement that is implied by both Q and R, and thus itself implies all that is implied by both Q and R.

In the first post I defined entailment for elementary statements. What we should look at therefore is this situation. Suppose that S is a statement S

Q entails S and R entails S

What is the relation that |S|bears to |Q| and |R|?

Theorem. If Q, R, S are elementary statements, Q entails S, and R entails S, then all convex combinations of members p of |Q| and p’ of |R| belong to |S|.

For note that if Q and R entail S then both |Q| and |R| are part of |S|. Therefore, iff is in |Q| and p’ is in |R| then both belong to |S|. Since |S| is convex it will also contain all the convex combinations of p and p’.

The smallest set that fits the Requirement above is therefore the convex hull of the union |Q| ⋃ |R|, that is the set of all convex combinations of members of those two sets. That is the smallest convex set which contains both. Since that is more than just the union, it does not correspond to a truth-functional disjunction. So let’s introduce a special symbol:

Definition. The join of convex sets X and Y is (X βŠ• Y) = {ap +(1-a)p’: a Ξ΅ [0,1], p in X, p’ in Y}.

That is precisely the convex hull of X ⋃Y. Following upon this we can introduce a statement connective of ‘disjunction’ to the language, which will combine elementary statements into other elementary statements. Without expecting any confusion from this, I will use βŠ• equally for the statement connective and for the operation on convex sets:

| Q βŠ• R| = |Q| βŠ• |R|.

Negation

Really, there is no negation. In a specific case we can make up the negation, but it will typically not be an elementary statement. For example what would be the negation of P(A) = 0.5?

Its contraries are P(A) < 0.5 and P(A) > 0.5. Each of these is an elementary statement. But there is no truth-functional ‘or’ that would combine them into the contradictory of P(A) = 0.5, at least not one that would produce an elementary statement.

The sort of disjunction we do have produces something, but not the contradictory of P(A) = 0.5. In fact,

(P(A) < 0.5) βŠ• (P(A) > 0.5)

is satisfied by the 50/50 convex combination p” of p and p’ which assign 0.25 and 0.75 to A respectively, and p”(A) is 0.5. So we have arrived at a tautology, this disjunction has the same semantic value as |P(A) Ξ΅ [0,1]|.

The underlying reason is of course that there is no largest convex subset of [0,1] disjoint from [0.5]. The two convex sets disjoint from [0.5] are [0.0.5) and (0.5,1] which are as large as can be, so there is no largest.

New Question: are there other forms of that elementary statements can have? What about other sorts of probability talk, such as about odds or conditional probabilities?

That will be the topic of the next post.