Boolean Paradoxes and Revision Periods

Ming Hsiung

Boolean Paradoxes and Revision Periods

Abstract. According to the revision theory of truth, the paradoxical sentences have certain revision periods in their valuations with respect to the stages of revision sequences. We find that the revision periods play a key role in characterizing the degrees of paradoxicality for Boolean paradoxes. We prove that a Boolean paradox is paradoxical in a digraph, iff this digraph contains a closed walk whose height is not any revision period of this paradox. And for any finitely many (but non-zero) numbers greater than 1, if any of them is not divisible by any other, we can construct a Boolean paradox whose primary revision periods are just these numbers. Consequently, the degrees of Boolean paradoxes form an unbounded dense lattice. The area of Boolean paradoxes is proved to be rich in mathematical structures and properties. Keywords: Degree of Paradoxicality, Digraph, Boolean Paradox, Revision Period, Revision Sequence.

1.

Introduction

The revision sequence, introduced by Gupta ([4]) and Herzberger ([7]) independently, is a basic notion of the revision theory of truth. This notion is a very useful tool in studying the truth predicate and the related paradoxes. In particular, we can obtain a quantitative description of the paradoxical sentences: the paradoxical sentences have certain revision periods in their valuations with respect to the stages of revision sequences, provided the revision sequences have a fixed rule at limit stages. As Herzberger ([6], 485, 492) said, the paradoxical sentences are evaluated stage by stage in revision sequences, and what they eventually obtain is ‘not fixed truth values but rather cyclic patterns of valuations. These will be their primary semantic characteristics.’ The revision periods we just mentioned turn out to be significant invariants in the study of the paradoxes. In the present work, we will study a kind of paradox, which includes no sentence involving quantification over the truth predicate, and so are named ‘Boolean paradoxes’. Our main question is the degrees of paradoxicality for Boolean paradoxes, and we show that the area of Boolean paradoxes is rich in mathematical structures and

Presented by Name of Editor; Received XXX

Studia Logica (0) 0: 1–35

c Springer ⃝

0

2

Ming Hsiung

properties. The method of our study is graph-theoretical. In particular, we will characterize a paradox by the digraphs in which the set of sentences we call ‘a paradox’ is paradoxical. As we will see, once we give a generalization of the notion of revision sequence, we can articulate in what sense a set of sentences is paradoxical in a digraph. We will prove that the digraph conditions that we use to characterize Boolean paradoxes are closely related to the revision periods of these paradoxes. Before making it clear how the digraphs play their roles in characterizing paradoxes, we first give two basic concepts from the revision theory of truth: revision sequences and revision periods. As usual, we study paradoxes in the language obtained from the firstorder language L of Peano arithmetic by adding a unary predicate letter T . Let it be L + . Unless otherwise noted, a sentence always means a sentence of L + . A base model of L + is a pair ⟨N, X⟩, where N = ⟨ N,′ , +, ·, 0 ⟩ is the standard model for Peano arithmetic, and X ⊆ N is the extension of T . For a sentence A, define ⟨N, X⟩ |= A as usual. For brevity, we will use X |= A rather than ⟨N, X⟩ |= A, and say ‘A is true for X’ when X |= A holds. To avoid clumsy notation, we also use ⌜A⌝ to denote both the G¨odel number of A and the corresponding numeral of L , as it is easy to distinguish between the( number and the numeral from the context. For instance, T ⌜A⌝ denotes ) T ⌜A⌝ . For any n ≥ 0, define T n ⌜A⌝ inductively as follows: T 0 ⌜A⌝ = A and T n+1 ⌜A⌝ = T ⌜T n ⌜A⌝⌝ for n ≥ 0. For formulas A and B, we use the equivalence A ≡ B to denote that the universal closure of the biconditional A ↔ B is true for all X ⊆ N. By the G¨odel diagonal lemma, for any positive number n, we can construct a sentence λn1 in L + such that λn1 ≡ ¬T n ⌜λn1 ⌝.1 When computing the truth value of λn1 , we find it is more convenient to decrease the iteration times of T down to 1 in the equivalence. For 1 ≤ i < n, let λni+1 = T ⌜λni ⌝. We will consider the set {λni | 1 ≤ i ≤ n} rather than the single sentence λn1 . Let λn = {λni | 1 ≤ i ≤ n}, and this set is the so-called ‘n-cycle liar’.2 Note that λ11 is the Liar sentence, and the 2-cycle liar is also called the ‘Jourdain card paradox’. All of the cycle liars are the simplest examples among Boolean paradoxes which we will define in the beginning of Section 2. As far as Boolean paradoxes are concerned, we only need consider the 1 The sentences we consider in this paper, especially those in a Boolean system (Definition 2.2), can always be constructed by the G¨ odel diagonal lemma. Since the construction is routine, the details are omitted. See ([1], 53-54) for an elegant exposition of the G¨ odel diagonal lemma. 2 More general α-liars were defined for all ordinals α by Herzberger ([7], 74-5) and Yablo ([14], 340). In the next section, we will give the ω-liar.

Boolean Paradoxes and Revision Periods

3

revision sequences of length ω. Definition 1.1 ([4], 10; [7], 68). For a subset X of N, let X r be the set {⌜A⌝ | X |= A, A ∈ L + }. Define Xk inductively for all k ≥ 0 as follows: X0 = X, and for all k ≥ 0, Xk+1 = Xkr . X = ⟨Xk | k ≥ 0⟩ is the revision sequence starting from X. For the revision sequence X = ⟨Xk | k ≥ 0⟩, we also use Xk (A) = T instead of Xk |= A (and Xk (A) = F instead of Xk ̸|= A). When Xk (A) = T, we can say A is true at stage k of X . In the revision theory of truth, a set of sentences is defined to be paradoxical, if it does not have a stable truth value in any revision sequences ([4], 49; [7], 70). An equivalent but more straightforward definition is as follows. Definition 1.2. Let ∆ be a set of sentences. ∆ is said to be paradoxical, if no X ⊆ N satisfies the condition: 3 X ∩ ⌜∆⌝ = X r ∩ ⌜∆⌝.

(1)

That is, there is no X such that for any A ∈ ∆, X |= T ⌜A⌝, iff X |= A. As is pointed out by Herzberger, the revision sequence can be seen as ‘a process of progressive semantic evaluation’, in which every sentence eventually falls into some ‘cyclic pattern of valuations’. The period is used to designate the length of such a cyclic pattern ([7], 81; [6], 492). But unlike the periods Herzberger gave, the periods we define below are never infinite, since we only consider revision sequences of length ω. Definition 1.3 ([7], 75). Let ∆ be a set of sentences, and let X = ⟨Xk | k ≥ 0⟩ be a revision sequence. A number m ≥ 1 is a (revision) period of ∆ on X , if there exists a number N ≥ 0 such that Xk+m (A) = Xk (A) for all k ≥ N and for all A ∈ ∆. m is a period of ∆, if m is a period of ∆ on some X . Note that if ∆ has a period 1, ∆ cannot be paradoxical, since there exists a revision sequence such that the truth values of sentences in ∆ eventually become fixed (or ‘stable’ in terms of the revision theory) in this revision sequence. Thus, if a paradox has a period, it must be greater than 1. It is clear that if m is a period of a paradox, so is any positive multiple of m. Among all the periods of a paradox, we will focus specifically on those that are not a multiple of any other period. 3

As usual, when a set of sentences is paradoxical, we will say it is a paradox.

4

Ming Hsiung

Definition 1.4. A period p of ∆ is said to be primary, if m ∤ p (i.e., p is not divisible by m) for any period m of ∆ with m ̸= p. Define the periodicity set of ∆ to be the set of all primary periods of ∆. For example, for any n = 2i (2j + 1), the n-cycle liar λn has a unique primary period 2i+1 . Since we will give a procedure for computing the primary period for a more complex example in Section 3, the details of the computing procedure for the n-cycle liar are omitted. We now give a generalization of revision sequences. After doing that, we can specify immediately in what sense a set of sentences is paradoxical in a digraph. Hereafter, we always use K to denote the digraph ⟨W, R⟩ unless otherwise noted. See the end of this section for the definitions of digraphs and related notions. Definition 1.5 ([8], 243-244). Let ∆ be a set of sentences. t: W → P(N) is a revision mapping for ∆ in K, if for all u, v ∈ W satisfying u R v, t(v) ∩ ⌜∆⌝ = t(u)r ∩ ⌜∆⌝

(2)

Revision mappings are a generalization of revision sequences. Actually, when ∆ is the set of all sentences, W is the set of natural numbers and R is the successor relation between natural numbers, a revision mapping t for ∆ in K is a revision sequence starting from the set t(0). Also note (2) is equivalent to for all A ∈ ∆, t(v) |= T ⌜A⌝ ⇐⇒ t(u) |= A. And so a revision mapping is the same as a ‘truth-predicate realization of T ’ which is defined in [8]. But the philosophical motivation is different when the mapping t is introduced as the truth-predicate realization of T . For more relevant discussions, the reader may refer to ([8], 244-248). Definition 1.6 ([8], 248, 254). Let ∆, Γ be two sets of sentences. (a) ∆ is paradoxical in K, if there is no revision mapping for ∆ in K. In that case, K is said to be a characterization digraph of ∆. (b) Define ∆ ≤P Γ, if for any digraph K, whenever ∆ is paradoxical in K, Γ is also paradoxical in K. Define ∆ ≡P Γ, if ∆ ≤P Γ and Γ ≤P ∆. Define ∆ x ¬T ⌜ν (y) ˙ ⌝.6

(7)

Yablo’s paradox cannot be a generalized Boolean paradox, much less a Boolean paradox. For this, only note the following known fact: any finite parts of Yablo’s paradox are non-paradoxical ([5], 198). Note if we replace the universal quantifier by iterated quantifiers in equivalence (7), we then can get more complex variants of Yablo’s paradox. For instance, the following equivalence gives the so-called ‘∀∃-unwinding’ variant of Yablo’s paradox: ν ′ (x) ≡ ∀y > x ∃z > y ¬T ⌜ν ′ (z) ˙ ⌝. More generally, for the quantifiers Q1 , . . . , Qn , we have the Q1 . . . Qn unwinding variants of Yablo’s paradox in the apparent sense.7 Among all the Q1 . . . Qn -unwinding variants of Yablo’s paradox, only four kinds are not logically equivalent to each other: the ∀n -unwinding, ∃n -unwinding, ∀∃-unwinding, and ∃∀-unwinding variants.8 But from the periodical point of view, all the unwinding variants of Yablo’s paradox are 6

Again, ν(x) can be obtained by the G¨ odel diagonal lemma. Note the dot notation in (7) allows the scope of the quantifier ∀y covers the formula ν (y), even though ν (y) hides behind a closed term. 7 The ∀∃-unwinding variant and its dual—the ∃∀-unwinding variant—were first given in [16] and [2]. More general variants were given in [12]. 8 See Theorem 3.3.2 in [3].

10

Ming Hsiung

the same: they all have a unique primary period 2. For this, note that the sentences in any ∀n -unwinding variant have the uniform truth value from the second stage of the revision sequence, no matter what the revision sequence starts from. And so we have only one periodic pattern of valuations for the ∀n -unwinding variant as follows: ⟨F, F, F, . . .⟩ (i.e. all sentences in the ∀n -unwinding variant are false), ⟨T, T, T, . . .⟩, ⟨F, F, F, . . .⟩, and so on. The same is true for other three kinds of unwinding variants of Yablo’s paradox. Next, we give a paradoxical example without any periods. By the G¨odel diagonal lemma, we can find a sentence µ such that µ ≡ ¬∀xT S x˙ ⌜µ⌝

(8)

It can be easily seen that the sentence µ is paradoxical. This paradox is introduced by McGee, and will be called McGee’s paradox ([11], 400). As we do for the n-cycle liar, we can decrease the T -iteration times of µ in the right side of equivalence (8). Let µ0 = µ, and for any k ≥ 0, let µk+1 = T ⌜µk ⌝. Then equivalence (8) can be replaced by the system of the following equivalences:  µ0 ≡ ¬∀xT ⌜µx˙ ⌝    µ1 ≡ T ⌜µ0 ⌝ (9) µ2 ≡ T ⌜µ1 ⌝    ... ... Thus, the set {µn | n ∈ N} (subject to equivalences (9)) is an equivalent formulation of McGee’s paradox. Now in equivalence (9), if we put µω to be ∀xT ⌜µx˙ ⌝, and recast µ0 as ¬T ⌜µω ⌝, we get the dual of McGee’s paradox:  ′ µ0 ≡ ¬T ⌜µ′ω ⌝      µ′1 ≡ T ⌜µ′0 ⌝ µ′2 ≡ T ⌜µ′1 ⌝ (10)   . . . . . .    ′ µω ≡ ∀x T ⌜µ′x˙ ⌝ The set {µ′ω , µ′n | n ∈ N} is the ω-liar we have mentioned in Footnote 2. We now come to determine the primary periods of McGee’s paradox. Let X = ⟨Xk | k ≥ 0⟩ be a revision sequence. For k ≥ 0, define an infinite sequence of T’s and F’s, say sk , as follows: sk = ⟨Xk (µi ) | i ≥ 0⟩. We will say that sk is a valuation of McGee’s paradox at stage k of X . Let N (sk ) be the number of the occurrences of T before the first occurrence of F in

Boolean Paradoxes and Revision Periods

11

s, or −1 if there is no occurrence of F in sk . Now it can be easily verified that for all k ≥ 0, N (sk+1 ) = N (sk ) + 1. That means any valuation of McGee’s paradox cannot be repeated twice at the stages of X . Therefore, no number can be the period of McGee’s paradox. Similarly, we can show the ω-liar does not have any period either. Actually, all transfinite α-liars have no periods. This is not surprising. Informally, the reason why all these paradoxes have no (finite) period is that the revision sequences we consider here have only the length ω, and they are too short for these paradoxes to show their periodic patterns of valuations. McGee’s paradox and the ω-liar can not be Boolean paradoxes, since all Boolean paradoxes, as we will prove below, have at least one primary period. We now return to Boolean paradoxes. Consider the following finitary variants of McGee’s paradox. By the G¨odel diagonal lemma again, for any n ∈ N, it is not hard to find sentences µni (0 ≤ i ≤ n) such that  n µ ≡ ¬T ⌜µn0 ⌝ ∨ . . . ∨ ¬T ⌜µnn ⌝    0n µ1 ≡ T ⌜µn0 ⌝ ... ...    n µn ≡ T ⌜µnn−1 ⌝

(11)

The set {µni | 0 ≤ i ≤ n} is clearly a Boolean paradox, which will be denoted by µn . Note the Liar, i.e., µ0 , appears again. It can be easily verified that for all n ≥ 0, µn has a unique period n + 2. In the end of this section, we show an important feature of Boolean paradoxes: they always have finitely many (and non-zero) primary periods. Lemma 2.5. Let ∆ = {δ1 , . . . , δn } be a Boolean system as given by equivalences (6) and let X = ⟨Xk | k ≥ 0⟩ be a revision sequence. Then for all 1 ≤ i ≤ n, Xk+1 (δi ) = fi (Xk (δ1 ), . . . , Xk (δn )). Proof. First, note that Xk |= A, iff Xk+1 |= T ⌜A⌝. Then we can get Xk |= fi (δ1 , . . . , δn ) ⇐⇒ Xk+1 |= fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝). By equivalence (6) for δi , we have Xk+1 |= δi ⇐⇒ Xk+1 |= fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝). And so Xk+1 |= δi is equivalent to Xk |= fi (δ1 , . . . , δn ). That is, Xk+1 (δi ) =

12

Ming Hsiung

Xk (fi (δ1 , . . . , δn )). On the other hand, it can be easily seen that Xk (fi (δ1 , . . . , δn )) = fi (Xk (δ1 ), . . . , Xk (δn )).9 Consequently, we get Xk+1 (δi ) = fi (Xk (δ1 ), . . . , Xk (δn )). We give the notion of valuation sequences, which are more convenient than revision sequences when we compute the periods of Boolean paradoxes. Definition 2.6. Let ∆ = {δ1 , . . . , δn } and let X = ⟨Xk | k ≥ 0⟩. For all k ≥ 0, set sk = ⟨ Xk (δ1 ), . . . , Xk (δn )⟩. (12) sk is called the valuation of ∆ at stage k of X . s = ⟨sk | k ≥ 0⟩ is called the valuation sequence of ∆ on X . A positive number m is called a period of s, if there exists a number N ≥ 0 such that sk+m = sk for all k ≥ N . Lemma 2.7. Let ∆, X and s be given as above. Then a positive number m is a period of ∆ on X , iff m is a period of s. Theorem 2.8. All Boolean paradoxes have only finitely many but non-zero primary periods. Proof. Fix a Boolean system ∆ = {δ1 , . . . , δn }. Let X = ⟨Xk | k ≥ 0⟩ be a revision sequence and let s = ⟨sk | k ≥ 0⟩ be the valuation sequence of ∆ on X . First, note that there are only 2n possible valuations of ∆ (at some stage of X ). And so among all the valuations of ∆ before stage 2n of X , at least one must be repeated after stage 2n of X . That is to say, there exist numbers N (≤ 2n ) and m such that sN = sN +m . Then by Lemma 2.5, we can see that for all k ≥ N , sk = sk+m . Hence, m is a period of s. By Lemma 2.7, m is a period of ∆. Now the least one of all periods of ∆ is a primary period of ∆. Next, we show: Claim 2.9. among all the periods of ∆ on X , there are at most one that can be a primary period of ∆. Proof of Claim 2.9: Let m1 be the least one among all the periods of ∆ on X . Clearly, if there is indeed a period of ∆ on X that is primary, m1 must be a primary period of ∆. Now suppose m2 is a period of ∆ on X and it is 9 The occurrence of fi in the left side of this equation is a Boolean combination, while the occurrence in the right side is the corresponding truth function. We will see similar abuse of notations. This abuse of notations does not raise any confusion, since we can always determine whether fi denotes a formula or a function from the context.

Boolean Paradoxes and Revision Periods

13

also a primary period of ∆. It suffices to prove m1 = m2 . Assume m2 ̸= m1 for contradiction. Then m2 = q · m1 + r for some q ≥ 0 and 0 < r < m1 . By our assumption, there exist numbers Ni such that sNi = sNi +mi for i = 1, 2. Then, sN1 +N2 = sN1 +N2 +q·m1 and sN1 +N2 = sN1 +N2 +m2 . Let N = N1 + N2 + q · m1 . It follows that sN = sN +r . That means r is a period of ∆ on X . But r < m1 , a contradiction. Claim 2.9 is proved. Finally, we define a binary relation ∼∆ on subsets of N as follows: X ∼∆ Y iff for all 1 ≤ i ≤ n, X(δi ) = Y (δi ). Obviously, ∼∆ is an equivalence relation and there are only finitely many (actually, at most 2n ) equivalence classes of ∼∆ . Let X and Y be the revision sequence starting from X and Y respectively. Then by Lemma 2.7, we can easily see that whenever X ∼∆ Y , the periods of ∆ on X are the same as those on Y. Further, by Claim 2.9, only one of the periods of ∆ on X can be a primary period of ∆. Thus, there is also at most one primary period of ∆ corresponding to an equivalence class of ∼∆ . Hence, ∆ has only finitely many primary periods. In the above, we have proved that all Boolean systems have finitely many and non-zero primary periods. In particular, this is certainly true for Boolean paradoxes. Note that those non-paradoxical Boolean systems take 1 as their unique primary period.

3.

Construction of Boolean Paradoxes

In the previous section, we have given the primary periods of many typical paradoxes. We find that these paradoxes, Boolean or not, either have a unique primary period, or have none at all. As far as I know, all the known paradoxes in the field of truth theory, without exception, have a unique primary period if they have at least one. It naturally raises a question: is there any paradox of more than one primary periods? In this section, we will give a positive answer to this question. Actually, for each finite non-empty set of numbers greater than 1, if none of its elements is divisible by any other, we can find a Boolean paradoxes whose primary periods are just the numbers of that set. This actually is a converse of Theorem 2.8. To some extent, we can construct a Boolean paradox that satisfies any reasonable requirement about revision periods. Before our construction, we first take Wen’s paradox as an example to show how to effectively determine the primary periods of a Boolean paradox. This will gives us some heuristics for the construction of a Boolean paradox. Recall Wen’s paradox is the set ∆ = {δ1 , δ2 , δ3 }, defined by system (3) of equivalences. Let X be the revision sequence starting from X. We will use the corresponding valuation sequence to make our computation of periods

14

Ming Hsiung

easier. Let s = ⟨sk | k ≥ 0⟩, wherein sk = ⟨Xk (δ1 ), Xk (δ2 ), Xk (δ3 )⟩. By Lemma 2.5, for any stage k of X , we have   Xk+1 (δ1 ) = Xk (δ2 ) ∧ ¬Xk (δ3 ) X (δ2 ) = ¬Xk (δ1 ) ∨ Xk (δ3 ) (13)  k+1 Xk+1 (δ3 ) = Xk (δ1 ) ∧ Xk (δ2 ) That means, even without knowing what each Xk is, we can still determine sk+1 from sk . For instance, let s0 = FTF (i.e., ⟨F, T, F⟩), which by the way is the valuation of ∆ at stage 0 of X starting from X0 = ∅. But the information about X0 is not necessary to determine the periods of ∆. Actually, by applying equations (13), we can compute sk iteratively: s1 = TTF, s2 = TFT, s3 = FTF and so on. We notice s3 = s0 , and thus see immediately 3 is a period of ∆ on X (see Table 1). Of course, 3 is a primary period of ∆ because 3 is a prime number. δ1 δ2 δ3

0 F T F

1 T T F

2 T F T

3 F T F

... ... ... ...

Table 1: A valuation sequence of Wen’s paradox

By the proof of Theorem 2.8, to find a different primary period (if any) of ∆ from 3, we can only consider a revision sequence starting from a set that is not ∼∆ -equivalent to the above X. That means we only need to consider a valuation sequence whose starting valuation is not FTF any longer. Actually, we can only consider a valuation sequence whose starting point is not any valuation of ∆ that has appeared up to now. For instance, we can start from s0 = TTT and then get a second valuation sequence of ∆: s1 = FTT, s2 = FTF, and so on. After doing that, we then start from a new s0 that never appears in the previous computation, and so get a third valuation sequence of ∆. Repeat this procedure until there is no new valuation of ∆ that we can use as the starting point of the valuation sequence of ∆. And this procedure halts necessarily, since there are at most 23 valuations for Wen’s paradox. There are still three different valuation sequences we can get besides the one we show in Table 1. The three valuation sequences are shown in Table 2. We can see that all the three valuation sequences eventually fall into the cyclic pattern that we have seen in the valuation sequence starting from s0 = FTF. As a result, we can conclude that Wen’s paradox has a unique primary period 3.

15

Boolean Paradoxes and Revision Periods

δ1 δ2 δ3

0 T T T

1 F T T

2 F T F

... ... ... ...

0 T F F

1 F F F

2 F T F

... ... ... ...

0 F F T

1 F T F

... ... ... ...

Table 2: Other valuation sequences of Wen’s paradox

PROOF of Theorem 1.8: The proof is an effective construction procedure. Suppose P = {m1 , . . . , mp } where p is a positive number. Note that mk ≥ 2 for 1 ≤ k ≤ p. Our target is to construct a Boolean paradox ∆ whose periodicity set is just P . The construction procedure is given as follows, and at the same time a typical example is used to show how this procedure works. Step 1. We determine the number of sentences in ∆. For this, choose the least number n such that the sum of all numbers in P is not greater than 2n . Let ∆ = {δ1 , . . . , δn }. As we will see in Step 2, such a choice of n is enough to provide us at least p different valuation sequences whose primary periods are respectively the numbers of P . To take an example, we come to construct a Boolean paradox such that its periodicity set is P = {2, 3}. Clearly, 3 is the smallest number n such that 2 + 3 ≤ 2n . And so the paradox we are constructing consists of three sentences, that is, ∆ = {δ1 , δ2 , δ3 }. What we need to do is to determine the equivalences that define these three sentences. A preliminary procedure before doing that is to give certain valuation sequences for the target set ∆. This will be articulated in Step 2. Step 2. For all 1 ≤ k ≤ p, we will give a valuation sequence sk of a period mk . Additionally, we will also make these valuation sequences satisfy a further condition: (∗) each possible valuation (of the target ∆) must occur in one and only one of these valuation sequences. Let Θ denote the set of all the possible valuations of ∆. The size of Θ is 2n . Now by our choice of n, we can represent 2n = N1 + . . . + Np , such that Nk ≥ mk holds for all 1 ≤ k ≤ p. It means that we can divide Θ into p subsets of the sizes N1 , . . . , and Np respectively. We use T1 , . . . , and Tp to denote these sets. Now for every 1 ≤ k ≤ p, we list without repetition all the elements of Tk⟩ in some ordering (for instance, the lexicographic ordering): ⟨ tk0 , . . . , tkNk −1 . for all 1 ≤ k ≤ p, we set up a valuation sequence of ∆, say sk = ⟨ k Now ⟩ s0 , sk1 , . . . , as follows: for 0 ≤ j < Nk , define skj = tkj ; and when j ≥ Nk ,

16

Ming Hsiung

then j = Nk + q · mk + r for some (unique) q ≥ 0 and 0 ≤ r < mk , and define skj = tkNk −mk +r . Intuitively, we can list some terms of sk as follows tk0 , . . . , tkNk −mk , tkNk −mk +1 , . . . , tkNk −1 , tkNk −mk , tkNk −mk +1 , . . . , tkNk −1 , . . . It can be seen that sk begins a periodic pattern from stage Nk − mk , and the period is just mk . Back to the above example. Here, 23 is represented to be 3 + 5. Correspondingly, we have s1 as follows: TTT, TTF, TFT, TTF, TFT, etc.. s1 is shown in the left side of double vertical line of Table 3, Another valuation sequence, say s2 , is shown in the right side. Clearly, 2 is a period of s1 , and 3 is a period of s2 .

δ1 δ2 δ3

0 T T T

1 T T F

2 T F T

3 T T F

... ... ... ...

0 T F F

1 F T T

2 F T F

3 F F T

4 F F F

5 F T F

... ... ... ...

Table 3: Two valuation sequences of respectively periods 2 and 3

Step 3. For 1 ≤ i ≤ n, an n-ary Boolean function fi can be induced from the valuation sequences s1 , . . . , sp as follows: ( ) fi skj (δ1 ) , . . . , skj (δn ) = skj+1 (δi ) , (14) where 1 ≤ k ≤ p, and 0 ≤ j < Ni . By condition (∗) in Step 2, each element of Θ occurs once and only once in those skj (1 ≤ k ≤ p, 0 ≤ j < Ni ). Thus, fi is a well-defined Boolean function. For the present example, Table 4 shows the Boolean functions f1 , f2 and f3 that are induced from the valuation sequences shown in Table 3. It is routine to find a Boolean formula which corresponds to the Boolean function fi . We can even construct such a formula in the disjunctive normal form (or in conjunctive normal form). Now suppose we have found a Boolean formula corresponding to fi , and suppose its arguments are just the sentence letters δ1 , . . . , δn . Let us denote this formula by fi (δ1 , . . . , δn ). As before, let fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝) be the result of substituting simultaneously T ⌜δ1 ⌝, . . . , T ⌜δn ⌝ for δ1 , . . . , δn in fi (δ1 , . . . , δn ). Let ∆ be the set {δi | 1 ≤ i ≤ n}, where the sentence δi is defined by the following equivalence δi ≡ fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝).

(15)

17

Boolean Paradoxes and Revision Periods

δ1 T T T T F F F F

δ2 T T F F T T F F

δ3 T F T F T F T F

f1 (δ1 , δ2 , δ3 ) T T T F F F F F

f2 (δ1 , δ2 , δ3 ) T F T T T F F T

f3 (δ1 , δ2 , δ3 ) F T F T F T F F

Table 4: Three Boolean functions induced from valuation sequences in Table 3

We will show ∆ is the target paradox. For this, we prove that the periodicity set of ∆ is exactly P . For 1 ≤ k ≤ p, define X0k to be a subset of N as follows: { } X0k = ⌜δi ⌝ | sk0 (δi ) = T, 1 ≤ i ≤ n . ⟨ ⟩ Let X k be the revision sequence starting from X0k , i.e., X k = X0k , X1k , . . . . Claim 3.1. For all j ∈ N and for all 1 ≤ i ≤ n, Xjk (δi ) = skj+1 (δi ) .

(16)

Proof of Claim 3.1: Prove (16) by induction on j. First, by definition of X0k , X0k (T ⌜δi ⌝) = sk0 (δi ) .

(17)

Thus, X0k (δi ) = X0k (fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝)) ( ) k k = fi X0 (T ⌜δ1 ⌝) , . . . , X0 (T ⌜δn ⌝) ( ) = fi sk0 (δ1 ) , . . . , sk0 (δn ) = sk1 (δi ) The first equation holds because of the definitional equivalence, the second holds because fi is a Boolean function, the third holds because of equation (17) and the last is due to equation (14).

18

Ming Hsiung

Second, for j ≥ 0, we have

) ( k Xj+1 (δi ) = fi Xjk (δ1 ) , . . . , Xjk (δn ) ( ) = fi skj+1 (δ1 ) , . . . , skj+1 (δn ) = skj+2 (δi )

The first equation holds by Lemma 2.5, the second holds by the induction hypothesis, and the third again is due to equation (14). As a result, we obtain equation (16). We proceed with the proof of Theorem 1.8. By claim 3.1, for 1 ≤ k ≤ p, k X has the same periods as sk . Thus, mk is a period of ∆ on X k . By the assumption about P , mk is a primary period of ∆. Hence, {mk | 1 ≤ k ≤ p} is a subset of the periodicity set of ∆. What is more, every element of Θ occurs once in skj (1 ≤ k ≤ p, 0 ≤ j < Ni ), and so for any X ⊆ N, there must be some 1 ≤ k ≤ p and some 0 ≤ j < Ni , such that X ∼∆ Xjk . Therefore, mk is a period of ∆ on the revision sequence starting from X. From the proof of Theorem 2.8, we know mk is a unique primary period of ∆, which comes from the revision sequence starting from X. Thus, all primary periods of ∆ are in the set {mk | 1 ≤ k ≤ p}. Consequently, we conclude that the periodicity set of ∆ is exactly P . We return to the above example. We have given three Boolean functions in Table 4. Then for the Boolean function f1 , we can get a Boolean formula in a disjunctive normal form as follows: f1 (δ1 , δ2 , δ3 ) ⇐⇒ (δ1 ∧ δ2 ∧ δ3 ) ∨ (δ1 ∧ δ2 ∧ ¬δ3 ) ∨(δ1 ∧ ¬δ2 ∧ δ3 ). It can be equivalently simplified to be f1 (δ1 , δ2 , δ3 ) ⇐⇒ (δ1 ∧ δ2 ) ∨ (δ1 ∧ ¬δ2 ∧ δ3 ). Similarly, we can get f2 (δ1 , δ2 , δ3 ) ⇐⇒ (δ1 ∧ δ3 ) ∨ (¬δ2 ∧ ¬δ3 ) ∨ (¬δ1 ∧ δ2 ∧ δ3 ), f3 (δ1 , δ2 , δ3 ) ⇐⇒ (δ1 ∧ ¬δ3 ) ∨ (¬δ1 ∧ δ2 ∧ ¬δ3 ). Therefore, a paradox of periodicity set {2, 3} is the Boolean system {δ1 , δ2 , δ3 }, defined by the following equivalences:  δ1 ≡ (T ⌜δ1 ⌝ ∧ T ⌜δ2 ⌝) ∨ (T ⌜δ1 ⌝ ∧ ¬T ⌜δ2 ⌝ ∧ T ⌜δ3 ⌝)    δ2 ≡ (T ⌜δ1 ⌝ ∧ T ⌜δ3 ⌝) ∨ (¬T ⌜δ2 ⌝ ∧ ¬T ⌜δ3 ⌝) (18) ∨(¬T ⌜δ1 ⌝ ∧ T ⌜δ2 ⌝ ∧ T ⌜δ3 ⌝)    δ3 ≡ (T ⌜δ1 ⌝ ∧ ¬T ⌜δ3 ⌝) ∨ (¬T ⌜δ1 ⌝ ∧ T ⌜δ2 ⌝ ∧ ¬T ⌜δ3 ⌝)

Boolean Paradoxes and Revision Periods

19

It is worth noting that in Step 2, we may have different choices for the valuation sequences sk at two places: first, the number 2n may have a different decomposition: 2n = N1′ + . . . + Np′ satisfying Nk′ ≥ mk for all 1 ≤ k ≤ p; second, the elements of Tk may be listed by a different ordering. Thus, by choosing different valuation sequences, we can construct a different paradox of the periodicity set {2, 3}. At the same time, it has to be noticed that we need to construct at least three sentences to obtain a Boolean paradox of periodicity set {2, 3}. In fact, if a Boolean paradox consists of a single sentence, it clearly only has a unique primary period 2. And if it consists of two sentences, it also has a unique primary period (2, 3, or 4 exclusively). Thus, it is necessary to provide at least three sentences for our purpose. But it is possible to decrease the numbers of occurrences of T ⌜δi ⌝ in the right sides of equivalences (18). For this, I leave the following question: Problem 3.2. Is there a Boolean paradox {δ1 , δ2 , δ3 } of the periodicity set {2, 3} which is not directly self-referential in the following sense: for any 1 ≤ i ≤ 3, there is no occurrence of T ⌜δi ⌝ in the right side of definitional equivalence of δi ? For any Boolean paradox, is there a Boolean paradox which has the same primary periods as the known one, but is not directly self-referential in the similar sense we just explain for the Boolean paradox of the periodicity set {2, 3}?

4.

Characterization of Boolean Paradoxes

This section is devoted to prove Theorem 1.7. We first introduce the notion of height. Definition 4.1. Define a mapping h on the set of walks of K as follows: for any world u ∈ W , hK (u) = 0; and for any walk ξ = u0 u1 . . . ul ul+1 (l ≥ 0), { hK (u0 u1 . . . ul ) + 1, if ul R ul+1 ; hK (ξ) = hK (u0 u1 . . . ul ) − 1, otherwise. hK (ξ) is called the height of ξ in K. The subscript K will be suppressed if no confusion arises. The notion of height is actually the dual of the notion of depth, and the latter is introduced in literature ([10], 26). We here prefer height because it is more convenient. The following lemma has a corresponding result involving the notion of depth. Since its proof is similar to that of the corresponding result in ([10], 27), we here omit the proof of Lemma 4.2. Let us call ξ =

20

Ming Hsiung

u0 u1 . . . ul is a piecewise one-way walk, if for any 0 ≤ k < l, either uk R uk+1 or uk+1 R uk , but not both. Lemma 4.2. (a) Let ξ be a walk in a digraph, then h(ξ − ) ≡ −h(ξ)(mod 2). In particular, if ξ is a piecewise one-way walk, then h(ξ − ) = −h(ξ). (b) For any positive number m, m divides the height of each cycle of K, iff it also divides the height of each closed walk of K. This also holds for any connected component of K. We will prove Theorem 1.7 by proving the following three implications: (c) ⇒ (b), (b) ⇒ (a), and (a) ⇒ (c). The proof of ‘(c) ⇒ (b)’ is purely graphtheoretical. PROOF of ‘(c) ⇒ (b)’ of Theorem 1.7: Suppose for each closed walk in K, its height is a period of ∆. Let K′ be a connected component of K, and suppose ξ0 , ξ1 , . . . , ξk are k arbitrarily fixed cycles in K′ . Note hK′ (ξi ) = hK (ξi ). We will use the notation h(ξi ) instead. Claim 4.3. For k ≥ 0, there exists a primary period m of ∆, such that for all 0 ≤ i ≤ k, m divides the height of ξi . Proof of Claim 4.3: We prove this claim by mathematical induction on k. The case k = 0 is immediate by our supposition. Next, we consider the case k + 1. Let c0 be the greatest common divisor of h(ξ0 ), h(ξ1 ), . . . , and h(ξk ). Let c1 be the greatest common divisor of c0 and h(ξk+1 ). Note c1 is also the greatest common divisor of h(ξ0 ), . . . , h(ξk ) and h(ξk+1 ). The inductive hypothesis says that c0 is divisible by some primary period of ∆, and we must show that c1 is divisible by some primary period of ∆ too. We consider two cases. Case 1: all walks in K′ are piecewise one-way. By B´e∑ zout’s lemma, there exist integers xi (0 ≤ i ≤ k) and yj (j = 0, 1) such that 0≤i≤k h(ξi )xi = c0 and c0 y0 + h(ξk+1 )y1 = c1 . And so we can get ∑ h(ξi )xi y0 + h(ξk+1 )y1 = c1 (19) 0≤i≤k

We now come to find a closed walk in K′ whose height is c1 . We notice K′ is connected, and so for all 0 ≤ i < k, we can find a walk, namely ζi , which connects ξi with ξi+1 . What is more, the walks ζi can be chosen such that for 0 ≤ i < k, the ‘tail’ of ζi is the ‘head’ of ζi+1 .10 10

More specifically, we first fix arbitrarily ζ0 , and then starting from the tail of ζ0 , we can reach a point in ξ1 and so we get ζ1 . Iterating this process, we can find ζ2 , and then ζ3 , and so on.

21

Boolean Paradoxes and Revision Periods

For any 0 ≤ i ≤ k, define ξi∗

=

{

ξi , if xi y0 ≥ 0; ξi− , otherwise.

∗ ∗ ∗ Similarly, define ξk+1 such that if y1 ≥ 0, ξk+1 = ξk+1 ; otherwise, ξk+1 = − ξk+1 . Let

ξ 0 = ξ0∗ ⌢ ξ0∗ ⌢ . . .⌢ ξ0∗ ⌢ ζ0 ⌢ ξ1∗ ⌢ ξ1∗ ⌢ . . .⌢ ξ1∗ ⌢ ζ1 ⌢ . . .⌢ ξk∗ ⌢ ξk∗ ⌢ . . .⌢ ξk∗ | {z } | {z } | {z } ξ

1

=

|x0 y0 | times |x1 y0 | times ⌢ ⌢ ∗ ∗ ∗ ⌢ −⌢ − ⌢ ξk+1 . . .⌢ ξk+1 ζk ζk−1 . . .⌢ ζ0− ζk ⌢ ξk+1

|

{z

|y1 | times

|xk y0 | times

}

By our choice of ζi (0 ≤ i ≤ k), we can see both ξ 0 and ξ 1 are walks in ⌢ K′ . Let ξ ⋆ = ξ 0 ξ 1 . Clearly, ξ ⋆ is a closed walk in K′ . And we also have ∑ ∑ ∑ h (ξ ⋆ ) = h(ξi )xi y0 + h(ξk+1 )y1 + h(ζi ) + h(ζi− ), (20) 0≤i≤k

0≤i≤k

0≤i≤k

By (a) of Lemma 4.2, the last two terms of (20) are opposite numbers. Thus, the height of ξ ⋆ is just equal to c1 . By our supposition, c1 must be is divisible by some primary period of ∆. Case 2: some walks in K′ are not piecewise one-way. WLOG, suppose ζ0 is not piecewise one-way. Let ζ0 = w0 w1 . . . wb . Then we can find the first a ≤ b such that wa R wa+1 and wa+1 R wa . Let ζ0′ = wa wa+1 wa . Since ζ0′ is a closed walk of height 2, 2 must a period of ∆ and it is also a primary period of ∆. Let the periodicity set of ∆ be {mi | 0 ≤ i ≤ p}. WLOG, suppose m0 = 2, and then any other period of ∆ is an odd number. We now prove that 2 divides h(ξ0 ). Assume that 2 does not divide h(ξ0 ), then 2 and h(ξ0 ) are relatively prime. But 2 and m1 m2 . . . mp are also relatively prime, since m1 , . . . , mp are all odd. Therefore, 2 and h(ξ0 )m1 m2 . . . mp are relatively prime. By B´ezout’s lemma for arithmetic, there exists two natural numbers x and y such that 2x = h(ξ0 )m1 m2 . . . mp + 1. (21) Thus, we get 2x + h(ξ0 )m1 m2 . . . mp = 2h(ξ0 )m1 m2 . . . mp + 1. Let ξ ′ = w0 . . . wa . Let ξ ′′ = ξ0⌢ ξ0⌢ . . .⌢ ξ0 ⌢ ξ ′ | {z } m1 m2 ...mp times

⌢ ′⌢ ′⌢ − ζ0 ζ0 . . .⌢ ζ0′ ⌢ ξ ′

|

{z

x times

}

(22)

22

Ming Hsiung

Again, ξ ′′ is a closed walk in K′ , and its height is ( ) ( ) − 2x + h ξ ′ + h (ξ0 ) m1 m2 . . . mp + h ξ ′ . By our choice of a, ξ ′ is piecewise one-way. And so by (a) of Lemma 4.2 again, the height of ξ ′′ is equal to 2x + h(ξ0 )m1 m2 . . . mp . By equation (22), the height of ξ ′′ is not divisible by any mi (0 ≤ i ≤ p), and therefore a contradiction. Notice that like ξ0 , any other ξi is also connected with the walk of height 2 that is an evidence of the supposition of case 2. And so for all any other ξi besides ξ0 , we can similarly prove that 2 divides h(ξi ). It follows that h(ξ0 ), h(ξ1 ), . . . , h(ξk+1 ) have a common divisor 2. In this case, m0 divides c1 . Up to now, the proof of Claim 4.3 is finished. At last, we pin down the desired primary period that divides the heights of all the cycles in K′ . If there are only finitely many cycles in K′ , the proof is finished by Claim 4.3. Otherwise, we enumerate all the cycles in K′ : ξ0 , ξ1 , . . . . For all k ≥ 0, define σ(k) to be the greatest common divisor of h(ξ0 ), h(ξ1 ), . . . , and h(ξk ). σ is a monotonically decreasing mapping. By Claim 4.3, σ(k) ≥ 2 for all k ≥ 0. Therefore, σ must have a fixed point. Then on one hand, this fixed point is the greatest common divisor of h(ξ0 ), h(ξ1 ), . . . , and h(ξN ) for a sufficiently large N , and so by Claim 4.3, it is divisible by some primary period of ∆. On the other hand, it is clear that this fixed point divides the height of ξk for every k ≥ 0. To sum up, we find a primary period of ∆ which divides the heights of the cycles in K. Note that in the above proof, we do not use any special feature of cycles in condition (b) of Theorem 1.7. Actually, by (b) of Lemma 4.2, if we replace ‘cycle’ by ‘closed walk’ in condition (b), we get an equivalent condition. Next, we prove ‘(b) ⇒ (a)’ of Theorem 1.7. We first introduce two notions.11 Definition 4.4 ([10], 28). Let ∆ be a set of sentences and let m be a natural number. ∆ has a characteristic m of truth in K, if whenever t : W → P(N) is a revision mapping for ∆ in K, equation (2) holds for all points u and v in W such that there is a finite walk ξ from u to v satisfying h(ξ) ≡ 1(mod m). Definition 4.5 ([10], 28). Let K, K′ (⟨W ′ , R′ ⟩) be digraphs and m be a natural number. f : W → W ′ is an m-winding mapping from K to K′ (write 11

The characteristic of truth we define here is with respect to a digraph, which is a slight refinement of the original definition in ([10], 28). Note also the reformulation of these two definitions involves the concept of height rather than the concept of depth.

Boolean Paradoxes and Revision Periods

23

f : K ⪯m K′ ), if for any points u and v with uRv in K, there exists a walk ξ ′ from f (u) to f (v) in K′ such that h(ξ ′ ) ≡ 1(mod m). In case such an f exists, we write K ⪯m K′ . Lemma 4.6. Suppose K ⪯m K′ and ∆ has a characteristic m of truth in K′ . Then ∆ is paradoxical in K implies ∆ is so in K′ . Proof. Suppose f : K ⪯m K′ and suppose t′ is a revision mapping for ∆ in K′ . Define a mapping t such that t(u) = t′ (f (u)). We verify t is a revision mapping for ∆ in K. Fix arbitrarily two points u, v ∈ W with uRv, then there exists a walk ξ from f (u) to f (v) in K′ such that h(ξ) ≡ 1(mod m). Since ∆ has a characteristic m of truth in K′ , we know that for all A ∈ ∆, t′ (f (v)) |= T ⌜A⌝ iff t′ (f (u)) |= A. By definition of t, we get for all A ∈ ∆, t(v) |= T ⌜A⌝ iff t(u) |= A. Our idea for proving ‘(b) ⇒ (a)’ of Theorem 1.7 is as follows. Suppose m is a (primary) period of ∆ in condition (b) of the theorem, then we find a special digraph Nm such that ∆ has a characteristic m of truth in Nm and ∆ is non-paradoxical in Nm . If K satisfies condition (b), we can prove K ⪯m Nm . By Lemma 4.6, ∆ is non-paradoxical in K. Note that throughout this proof, we do not use the the ‘primary’ feature of period m. Actually, it can be easily seen that condition (b) is equivalent to the condition obtained by replacing ‘primary period’ by ‘period’ in condition (b). From now on, unless otherwise noted, suppose ∆ = {δ1 , . . . , δn } is a Boolean system as given by equivalences (6). We now introduce an auxiliary concept. Definition 4.7. An assignment of ∆ in K is a mapping χ from the product set ∆ × W to the set {T, F} of truth values. χ is said to be admissible for ∆, if for all 1 ≤ i ≤ n and for all u, v ∈ W with u R v, χ(δi , v) = fi (χ(δ1 , u), . . . , χ(δn , u)) .

(23)

Informally, χ(δi , v) is to a revision mapping as Xk (δi ) is to a revision sequence. The following lemma provides a basic relation between admissible assignments and revision mappings. Lemma 4.8. For any digraph K, ∆ has a revision mapping in K, iff it has an admissible assignment in K. Proof. By Definition 1.5 and equivalences (6), t is a revision mapping of ∆ in K, iff for all 1 ≤ i ≤ n and for all u, v ∈ W with u R v, t(v) |= T ⌜δi ⌝ ⇐⇒ t(u) |= fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝) .

(24)

24

Ming Hsiung

If t is a revision mapping of ∆ in K, an assignment of ∆ can be induced as follows: for all 1 ≤ i ≤ n, { T, if δi ∈ t(u); χ(δi , u) = F, otherwise. The left side of (24) is clearly equivalent to χ(δi , v) = T. Using a similar method as used in the proof of Lemma 2.5, we can prove that the right side of (24) is equivalent to χ (fi (δ1 , . . . , δn ) , u) = T. Then (24) is equivalent to χ(δi , v) = χ (fi (δ1 , . . . , δn ) , u) . But χ (fi (δ1 , . . . , δn ) , u) = fi (χ (δj , u) , . . . , χ (δj , u)), and so we get (23). Conversely, suppose χ is an admissible assignment of ∆ in K, and a mapping t : W → P(N) can be induced from χ as follows: t(u) = {⌜δi ⌝ | χ(δi , u) = T} . Note in the above proof, each step is reversible. Hence, we can conclude that t satisfies (24). Now we give a special digraph. First, for m ≥ 1, define a binary operation +m on Z2 as follows: for all numbers i and j, i +m j is equal to the unique number k such that 1 ≤ k ≤ m and i + j ≡ k(mod m). Then, for any positive number m, define the digraph Nm = ⟨Nm , Pm ⟩ as follows: Nm = {i ∈ N | 1 ≤ i ≤ m}, and Pm is a binary relation on Nm such that i Pm j, iff j = i +m 1. Lemma 4.9. If m is a period of ∆, ∆ has a characteristic m of truth in Nm . Proof. Only note that for any points i and j in Nm , i Pm j, iff there is a walk ξ from i to j in Nm such that h(ξ) ≡ 1(mod m). Lemma 4.10. ∆ has an admissible assignment in Nm , iff m is a period of ∆. Proof. First, for sufficiency, suppose m is a period of ∆, then there are X (⟨Xk | k ≥ 0⟩) and N ∈ N such that for all k ≥ N , Xk+m (δi ) = Xk (δi ) (1 ≤ i ≤ n). Define an assignment χ as follows: for all 1 ≤ i ≤ n and 1 ≤ k ≤ m, χ(δi , k) = XN +k (δi ). By Lemma 2.5, XN +(k+1) (δi ) = fi (XN +k (δ1 ), . . . , XN +k (δn )) .

Boolean Paradoxes and Revision Periods

25

Then it is not hard to get χ(δi , k +m 1) = fi (χ (δ1 , k) , . . . , χ (δn , k)) .

(25)

Hence, χ is an admissible assignment of ∆ in Nm . Conversely, suppose χ satisfies equation (25). Define X0 = {⌜δi ⌝ | χ(δi , m) = T, 1 ≤ i ≤ n} . Again, as we do in the proof of Lemma 2.5, we can verify: X0 |= fi (T ⌜δ1 ⌝, . . . , T ⌜δn ⌝) ⇐⇒ fi (χ(δ1 , m), . . . , χ(δn , m)) = T. It follows that X0 (δi ) = fi (χ(δ1 , m), . . . , χ(δn , m)). Thus, by equation (25), we get X0 (δi ) = χ(δi , 1). Let ⟨Xk | k ≥ 0⟩ be the revision sequence starting from the set X0 . We claim that for all k ≥ 0, Xk (δi ) = χ(δi , k +m 1). Prove this claim by mathematical induction on k. We have verified the case of k = 0 above. Next, we consider χ(δi , (k + 1) +m 1). It is equal to χ(δi , (k +m 1) +m 1). And by (25), induction hypothesis and Lemma 2.5, we have χ(δi , (k +m 1) +m 1) = fi (χ (δ1 , k +m 1) , . . . , χ (δn , k +m 1)) , = fi (Xk (δ1 ), . . . , Xk (δn )) , = Xk+1 (δi ).

The claim is proved. By the above claim, we can see that for all k ≥ 0, Xk+m (δi ) = Xk (δi ). Hence, m is a period of ∆. Lemma 4.11. Let m be a positive number and K be a connected digraph. If for each closed walk of a digraph K, its height is divisible by m, then K ⪯ m Nm . Proof. When m = 1, Nm is the minimal reflexive digraph, and so K ⪯m Nm always holds for any K. Thus, we can suppose m > 1. Fix a point u0 in W . By connectedness, for any u ∈ W , there exists a walk ξ from u0 to u. Let du be the number such that 1 ≤ du ≤ m and d(ξ) ≡ du (mod m). Claim 4.12. For all walk ξ ′ from u0 to u, d(ξ ′ ) ≡ du (mod m).

26

Ming Hsiung

Proof of Claim 4.12: Assume not, then there exists ξ ′ from u0 to u, such that d(ξ ′ ) ≡ d′u (mod m) with 1 ≤ d′u ≤ m and d′u ̸= du . Now consider the walk obtained by concatenating ξ ′ with the inverse of ξ, i.e. ξ ′⌢ ξ − . We consider the following two cases. Case 1: m = 2. By (a) of Lemma 4.2, we know d (ξ ′⌢ ξ − ) ≡ d′u − du (mod 2), and so d (ξ ′⌢ ξ − ) ̸≡ 0(mod 2). Therefore, ξ ′⌢ ξ − is a closed walk whose height is not divisible by 2. A contradiction! Case 2: m > 2. In this case, any walk of K is piecewise one-way. Then by (b) of Lemma 4.2, we know d (ξ ′⌢ ξ − ) = d′u − du , and so d (ξ ′⌢ ξ − ) ̸≡ 0(mod m). Therefore, ξ ′⌢ ξ − is a closed walk whose height is not divisible by m. A contradiction again! We finish the proof of the claim. Thus, by Claim 4.12, we can define a mapping f : W → Nm such that for all point u ∈ W , f (u) is the (unique) number du such that 1 ≤ du ≤ m and d(ξ) ≡ du (mod m). It is the mapping f that witnesses K ⪯m Nm . PROOF of ‘(b) ⇒ (a)’ of Theorem 1.7: Suppose m is a (primary) period of ∆, satisfying condition (b). Since ∆ is non-paradoxical in K, iff it is so in all connected components of K, we can suppose K is connected. The height of any cycle of K is divisible by m, and so by (b) of Lemma 4.2, the height of any closed walk of K is also divisible by m. By Lemma 4.11, we know K ⪯m Nm . But m is a period of ∆, and so by Lemma 4.9, ∆ has a characteristic m of truth in Nm . By Lemma 4.8 and 4.10, ∆ is not paradoxical in Nm . Finally, by Lemma 4.6, we obtain that ∆ is not paradoxical in K. Now, we come to prove ‘(a) ⇒ (c)’ of Theorem 1.7. We first introduce a special kind of cyclic assignments. Recall that the notion of periods comes from Herzberger’s idea of the ‘cyclic patterns of valuations’. We now give an abstraction of Herzberger’s cyclic pattern of valuations. Definition 4.13. Let X = ⟨Xk | k ≥ 0⟩. ⟨m, N ⟩ is said to be a cyclic pattern of ∆ on X , if m ≥ 1 and Xk (A) = Xk+m (A) holds for k ≥ N , A ∈ ∆. Definition 4.14. Let χ be an assignment of ∆ in K. χ is m-cyclic, if there exists a revision sequence X = ⟨Xk | k ≥ 0⟩ and a number N such that ⟨m, N ⟩ is a cyclic pattern of ∆ on X and for every u ∈ W , there exists k ≥ N such that for all A ∈ ∆, χ(A, u) = Xk (A). Intuitively, when some sentences fall into the ‘cyclic pattern of valuations’, the truth values of these sentences can be taken as the values of a cyclic assignment of these sentences at some point. In Figure 1, we give two

27

Boolean Paradoxes and Revision Periods

FTF FTT

FTF TTF

FTF

TFT

TFT

TTF

FTF

TFT

Figure 1: non-cyclic and cyclic assignments assignments of Wen’s paradox in a digraph. Here, as we do in Section 3, we use a triple of truth values near a point to denote the truth values of δ1 , δ2 and δ3 in Wen’s paradox. For instance, FTF at the top point denotes δ1 is false, δ2 is true and δ3 is false at this point. The two assignments are both admissible for Wen’s paradox in this digraph. The one on the right side is 3-cyclic, but the left side is not, since the truth-value sequence FTT does not belong to the cyclic pattern of valuations: FTF, TTF, TFT, FTF, . . . . The following is a refinement of Lemma 4.10. The proof is similar and the details are omitted. Lemma 4.15. ∆ has an m-cyclic admissible assignment in Nl iff m is a period of ∆ and l is divisible by m. The following lemma is a key to proving ‘(a) ⇒ (c)’ of Theorem 1.7. Lemma 4.16. If ∆ has an m-cyclic admissible assignment in K, then for each closed walk in K, its height is divisible by m. To prove this lemma, we introduce the following notions. Definition 4.17. Let ξ = u0 u1 . . . ul be a walk in K. For some 0 ≤ a < l, ua is a upset point of ξ if ua R ua+1 fails. For m > 1, add m − 2 new points, say v1 , v2 , . . . , vm−2 , into W . And we stipulate v0 = ua and vm−1 = ua+1 . Extend R to be R ∪ {⟨vi , vi+1 ⟩ | 0 ≤ i < m − 1}. Let the extended relation be R[ua , m] and let the extended digraph be K[ua , m]. Then u0 . . . ua v1 . . . vm−2 ua+1 . . . un is a walk in K[ua , m]. Let it be ξ[ua , m] (see Figure 2 for an example). Lemma 4.18. Let K, ξ, K[ua , m], and ξ[ua , m] be as above. (a) h (ξ[ua , m]) ≡ h(ξ)(mod m). (b) If χ is an m-cyclic admissible assignment of ∆ in K, then χ can be extended to an m-cyclic admissible assignment of ∆ in K[ua , m].

28

Ming Hsiung

ua

ua

ua+1

ua+1 ξ[ua , 4]

ξ

Figure 2: Upset points Proof. For (a), we only need to note that h (ξ[ua , m]) = h(ξ) + m. To prove (b), suppose χ is an m-cyclic admissible assignment of ∆ in K. Then by definition, there exists a revision sequence X = ⟨Xk | k ≥ 0⟩ and a number N such that ⟨m, N ⟩ is a cyclic pattern of ∆ on X and for every u ∈ W , there exists k ≥ N such that for all 1 ≤ i ≤ n, χ(δi , u) = Xk (δi ). In particular, for ua , fix k1 such that for all 1 ≤ i ≤ n, χ(δi , ua ) = Xk1 (δi ); and for ua+1 , fix k0 such that for all 1 ≤ i ≤ n, χ(δi , ua+1 ) = Xk0 (δi ). Claim 4.19. For all 1 ≤ i ≤ n, Xk1 (δi ) = Xk0 +1 (δi ). Proof of Claim 4.19: Note that ua+1 R ua , then by Definition 4.7, for all 1 ≤ i ≤ n, Xk1 (δi ) = fi (Xk0 (δ1 ), . . . , Xk0 (δn )) . On the other hand, by Lemma 2.5, for all 1 ≤ i ≤ n, Xk0 +1 (δi ) = fi (Xk0 (δ1 ), . . . , Xk0 (δn )) . Thus, we get Xk1 (δi ) = Xk0 +1 (δi ). Now define an assignment χ′ of ∆ in K[ua , m] as follows: for all 1 ≤ i ≤ n, χ′ (δi , u) = χ(δi , u) when u ∈ W , and χ′ (δi , vk ) = Xk1 +k (δi ) when 1 ≤ k ≤ m − 2. χ′ is clearly m-cyclic, and we only need to prove that χ′ is admissible for ∆ in K[ua , m]. Note that by our stipulation, v0 = ua and vm−1 = ua+1 . Then for all 0 ≤ k < m2 , by Lemma 2.5 again, we have ( ) χ′ (δi , vk+1 ) = fi χ′ (δ1 , vk ) , . . . , χ′ (δn , vk ) . Additionally, by construction, χ′ (δi , vm−2 ) = Xk1 +m−2 (δi ). But m is a period of ∆ on X, and so by Claim 4.19, χ′ (δi , vm−2 ) = Xk0 +m−1 (δi ) = Xk0 −1 (δi ). It follows immediately that ( ) χ′ (δi , vm−1 ) = fi χ′ (δ1 , vm−2 ) , . . . , χ′ (δn , vm−2 ) .

Boolean Paradoxes and Revision Periods

29

Consequently, we can conclude that χ′ is an m-cyclic admissible assignment of ∆ in K[ua , m]. PROOF of Lemma 4.16: Suppose ξ is a closed walk in K. Define ξ ′ to be ξ[u, m], where u is the first upset point of ξ (if there is no upset point in ξ, just define ξ ′ = ξ). Define ξ (k) inductively as follows: ξ (0) = ξ ( )′ and ξ (k+1) = ξ (k) . Define K(k) with its binary relation R(k) as we do in Definition 4.17. Since there are only finitely many upset points in ξ, there must exist a number k0 such that ξ (k0 ) no longer contains upset points. That means, ξ (k0 ) can be represented as a closed walk u0 u1 . . . ul (u0 = ul ) in K(k0 ) such that for all 0 ≤ i < l, ui R(k0 ) ui+1 . Suppose ∆ has an m-cyclic admissible assignment in K. Then by repeatedly applying Lemma 4.18, we can get that ∆ has an m-cyclic admissible assignment in K(k0 ) . Now the digraph K(k0 ) restricted to ξ (k0 ) is isomorphic to Nl . And so by applying Lemma 4.15 (to this) restricted we can see l ( (kdigraph, ) (k ) ) 0 0 must be divisible by m. Besides, l = h ξ , and h ξ ≡ h(ξ)(mod m). Hence, h(ξ) is also divisible by m. Lemma 4.20. Let K be a connected digraph. If ∆ has an admissible assignment in K, then it has an m-cyclic admissible assignment of ∆ in K for some period m of ∆. Proof. Suppose χ is an admissible assignment of ∆ in K. Define an assignment χ′ as follows: for all 1 ≤ i ≤ n and u ∈ W , χ′ (δi , u) = fi (χ(δ1 , u), . . . , χ(δn , u)). For k ≥ 0, define χk inductively as follows: for all 1 ≤ i ≤ n and u ∈ W , χ0 (δi , u) = χ(δi , u); and χk+1 (δi , u) = (χk )′ (δi , u). As we define cyclic patterns for revision sequences (see Definition 4.13), we give the notion of cyclic patterns for admissible assignments. Let ⟨m, N ⟩ be a cyclic pattern of ∆ on χ at point u, if m ≥ 1 and for all k ≥ N and for all 1 ≤ i ≤ n, χk (δi , u) = χk+m (δi , u). In that case, we also say that m is a period of ∆ on χ at point u and N is a stabilization number of ∆ on χ at point u.12 We prove that ∆ has the same periods on χ at all points of K. For this, it suffices to prove that ∆ has the same periods on χ at every two adjacent points u and v, since K is connected. Without loss of generality, suppose u R v. Thus, χ(δi , v) = fi (χ(δ1 , u), . . . , χ(δn , u)) . 12

The stabilization numbers come from Herzberger’s stabilization ordinals. See ([7], 71).

30

Ming Hsiung

Then it can be easily seen that for all k ≥ 0, χk (δi , v) = χk+1 (δi , u). It follows immediately that ∆ has the same periods on χ at u and v. Let m be a (unique) smallest period of ∆ on χ at some (any) point. Then clearly, m is also a period of ∆. For every u ∈ W , let Nu be a corresponding stabilization number of ∆ on χ at point u. Since Nu is bounded from above by 2n , we can find a number N such that N is a stabilization number of ∆ on χ at point u. Now consider the assignment χ∗ defined by χ∗ (δi , u) = χN (δi , u). χ∗ is clearly an m-cyclic admissible assignment of ∆ in K. PROOF of ‘(a) ⇒ (c)’ of Theorem 1.7: Without loss of generality, assume K is connected. Suppose ∆ is non-paradoxical in K, then by Lemma 4.8, ∆ has an admissible assignment in K. It follows from Lemma 4.20 that for some period m of ∆, ∆ has an m-cyclic admissible assignment in K. Finally, by Lemma 4.16, for any closed walk in K, its height is divisible by m, and thus is a period of ∆.

5.

Degrees of Boolean Paradoxes

We prove Theorem 1.9 in this section. Before doing that, we give some useful corollaries of Theorem 1.7. First, by condition (b) of Theorem 1.7, we have the following characterization theorem for those Boolean paradoxes of a unique primary period: Theorem 5.1. If ∆ is a Boolean paradox of a unique primary period m, then ∆ is paradoxical in K iff there is at least a cycle of K, whose height is indivisible by m. We come to see some applications of the above result. For any positive number n = 2i (2j + 1), since the n-cycle liar λn has a unique primary period 2i+1 , its characterization digraphs are those containing a cycle whose height is indivisible by 2i+1 . For any positive number n, since the paradox µn (see System (11) of equivalences) has a unique primary period n + 2, its characterization digraphs are those containing a cycle whose height is indivisible by n + 2. It is worth pointing out that condition (c) in Theorem 1.7 can not be weakened to be ‘For each cycle in K, its height is a period of ∆.’ Actually, this may be false for those ∆ with more than one primary period. For example, consider the paradox that we construct as an example in the proof of Theorem 1.8. It has two primary periods: 2 and 3. It is paradoxical in the digraph obtained by gluing a copy of N2 with a copy of N3 at a common

Boolean Paradoxes and Revision Periods

31

point, because this digraph contains a closed walk whose height is 5. But this digraph contains only two cycles: one’s height is 2 and the other’s is 3. We also must notice that in condition (b) of Theorem 1.7, the primary period of ∆ depends on the connected component of K: different connected components of K may correspond to different primary periods of ∆, and it is possible that none of primary periods of ∆ divides the heights of the cycles in all connected components of K. To see this point, we still consider the paradox of the periodicity set {2, 3}. It is not paradoxical in the digraph which has only two disjoint parts: one part is a copy of N2 and the other part is a copy of N3 . However, neither 2 nor 3 divides the heights of all cycles in this digraph. Definition 5.2 ([10], 35). A cycle in a digraph is improper , if its height is zero; otherwise it is proper . A set of sentences is said to have circularity dependence, if it is not paradoxical in any digraph unless this digraph contains some proper cycle. A set of sentences is said to have digraph compactness, if whenever it is paradoxical in a digraph, it must be paradoxical in some finite sub-digraph of this digraph. The following result is immediate from Theorem 1.7: Theorem 5.3. Each Boolean paradox has both the circularity dependence and digraph compactness. To compare the degrees of paradoxicality for Boolean paradoxes, we introduce the following notion: Definition 5.4. Define the period set of ∆ to be the set of all periods of ∆, which is denoted by P(∆). It had been proved in [10] that for any positive numbers n1 = 2i1 (2j1 +1) and n2 = 2i2 (2j2 + 1), λn1 ≤P λn2 iff i1 ≤ i2 . This result is equivalent to λn1 ≤P λn2 iff P(λn2 ) ⊆ P(λn1 ). A more general result is as follows. Its proof is also immediate from Theorem 1.7. Theorem 5.5. Let ∆, Γ be two Boolean paradoxes. Γ ≤P ∆ iff P(∆) ⊆ P(Γ). We now can prove Theorem 1.9. Let us say m is a proper multiple of n if m = nk for some number k > 1. We use [m, n] to denote the least common multiple of m and n. PROOF of Theorem 1.9: Suppose ∆1 and ∆2 are two Boolean paradoxes. Let C1 and C2 be their periodicity sets. First, we seek the greatest lower bound of the degrees of ∆1 and ∆2 . Let C ∧ be the union of C1 and C2 minus

32

Ming Hsiung

those numbers which are a proper multiple of some number of C1 ∪ C2 . C ∧ is non-empty since the smallest number of C1 ∪ C2 must belong to C ∧ . Furthermore, every number of C ∧ is not divisible by any other number of C ∧ . And so by Theorem 1.8, we can construct a Boolean paradox, say ∆∧ , the periodicity set of which is just C ∧ . It can be easily verified that P (∆∧ ) = P(∆1 ) ∪ P(∆2 ). Thus, by Theorem 5.5, the degree of ∆∧ is the greatest lower bound of those of ∆1 and ∆2 (among all the degrees of Boolean paradoxes). Second, we determine the least upper bound of degrees of ∆1 and ∆2 . Let C3 = {[i, j] | i ∈ C1 , j ∈ C2 }. Let C ∨ be C3 minus those numbers which are a proper multiple of some number of C3 . Again, C ∨ ̸= ∅ and every number of C ∨ is not divisible by any other number of C ∨ . And so by Theorem 1.8, we can find a Boolean paradox, say ∆∨ , whose periodicity set is just C ∨ . Claim 5.6. P (∆∨ ) = P(∆1 ) ∩ P(∆2 ). Proof of Claim 5.6: To prove the claim, suppose m ∈ P (∆∨ ), then m = pk for some p ∈ C3 and some positive integer k. But p is a multiple of a number of C1 , and so p belongs to P(∆1 ). Similarly, p belongs to P(∆2 ). And thus p (and so pk) belongs to the intersection of P(∆1 ) and P(∆2 ). Conversely, suppose that m belongs to the intersection of P(∆1 ) and P(∆2 ). Then m = p1 k1 = p2 k2 for some pi ∈ Ci (i = 1, 2) and for some positive integers k1 and k2 . It follows that m = pk for some common multiple p of p1 and p2 and for some positive integer k. By definition of C ∨ , p must be either an element of C ∨ , or a number that is a proper multiple of some number of C ∨ . In any case, pk is a multiple of some number of C ∨ . Hence, pk belongs to P (∆∨ ). To sum up, we can conclude that P (∆∨ ) is equal to the intersection of P(∆1 ) and P(∆2 ). Now, by Theorem 5.5 together with Claim 5.6, the degree of ∆∨ is the least upper bound of those of ∆1 and ∆2 (among all the degrees of Boolean paradoxes). Next, suppose ∆1