The Connectives

0. Preliminaries

Chapter 0 Preliminaries Skip or skim this chapter, returning for background explanations as necessary.§0.1 CONNECTIONS AND COMBINATIONS 0.11 Relational Connections and Posets Given n non-empty sets S1, . . . , Sn and a relation R ⊆ S1 × · · · × Sn, we call the structure (R, S1, . . . , Sn) an n-ary relational connection. When si ∈ Si (for i = 1, . . . , n) we often write Rs1 . . . sn for s1, . . . , sn ∈ R, using the familiar ‘infix’ notation s1Rs2 for the case of n = 2. We will be especially concerned in what follows with this case – the case of binary relational connections – and will then write “S” (for “source”) and “T” (for “target”) for S1 and S2. A binary relational connection will be said to have the cross-over property (or to satisfy the cross-over condition) just in case for all s1, s2 ∈ S, and all t1, t2 ∈ T: (*) (s1Rt1 & s2Rt2) ⇒ (s1Rt2 or s2Rt1) The label “cross-over”, for this condition, is explained pictorially. Elements of S appear on the left, and those of T on the right. An arrow going from one of the former to one of the latter indicates that the object represented at the tail of the arrow bears the relation R to that represented at the head of the arrow: s1   (( R R R R R R R R R R R R R R R R //  t1 s2   66 l l l l l l l l l l l l l l l l //  t2 Figure 0.11a: The Cross-Over Condition Read the diagram as follows: if objects are related as by the solid arrows, then they must be related as by at least one of the broken arrows. Thus, given the horizontally connected (ordered) pairs as belonging to R, we must have at least one of the crossing-over diagonal pairs also in R. Our main interest in this condition arises through Theorem 0.14.2 below, which will be appealed to more 1 2 CHAPTER 0. PRELIMINARIES than once in later chapters (beginning with the proof of 1.14.6, p. 69). In the meantime, we include several familiarization exercises. Exercise 0.11.1 Check that if a binary connection (R, S, T) has the cross-over property then so does the complementary connection (R, S, T) where R = (S × T)  R, and so also does the converse connection (R−1 , T, S) where R−1 = { t, s | s, t ∈ R}. Exercise 0.11.2 Given R ⊆ S × T, put R(s) = {t ∈ T | sRt}. Show that (R, S, T) has the cross-over property iff for all s1, s2 ∈ S: R(s1) ⊆ R(s2) or R(s2) ⊆ R(s1). Exercise 0.11.3 (i) For S any set containing more than one element, show that the relational connection (∈, S, ℘(S)) does not have the cross-over property. (Here ℘(S) is the power set of S, i.e., the set of all subsets of S.) (ii) Where N is the set of natural numbers and  is the usual less-thanor -equal-to relation, show that the relational connection (, N, N) has the cross-over property. Inspired by 0.11.3(i), we say that (R, S, T) is extensional on the left if for all s1, s2 ∈ S, R(s1) = R(s2) implies s1 = s2, and that it is extensional on the right if for all t1, t2 ∈ T, R−1 (t1) = R−1 (t2) implies t1 = t2. The ‘Axiom of Extensionality’ in set theory says that such connections as that exercise mentions are extensional on the right. (They are also extensional on the left.) Part (ii) of 0.11.3, on the other hand, serves as a reminder that we do not exclude the possibility, for an n-ary relational connection (R, S1, . . . , Sn), that the various Si are equal, in which case we call the relational connection homogeneous . A more common convention is to consider in place of (R, S1, . . . , Sn) the structure (S, R), where S = S1 = · · · = Sn. Such a pair is a special case of the notion of a relational structure in which there is only one relation involved. (In general one allows (S, R1, . . . , Rm) where the Ri are relations – not necessarily of the same arity – on the set S. Here the arity of a relation Ri is that n such that Ri is n-ary. We speak similarly, below, of the arity of a function or operation .) Various conditions on binary relational connections which make sense in the homogeneous case...