356 Let A \ B be the difference between bunch A and bunch B . The operator \ has precedence level 4, and is defined by the axiom
x:A\B = x:A ∧ ¬x:B
For each of the following fixed-point equations, what does recursive construction yield? Does it satisfy the fixed-point equation?
(a) Q =
§ Q0 = Q1 = Q2 = Q3 = Q4 = Q5 =
nat \ (Q+3)
null
nat\(null+3) = nat\null = nat
nat \ (nat+3) = 0, 1, 2
nat \ ((0, 1, 2)+3) = nat \ (3, 4, 5) = 0, 1, 2, nat+6
nat \ ((0, 1, 2, nat+6)+3) = nat \ (3, 4, 5, nat+9) = 0, 1, 2, 6, 7, 8 nat \ ((0, 1, 2, 6, 7, 8)+3) = nat \ (3, 4, 5, 9, 10, 11)
= 0, 1, 2, 6, 7, 8, nat+12
Time for a guess. It looks like there are two patterns: the even index pattern and the odd index pattern. So I guess
Q2×n = 6×(0,..n) + (0,..3)
Q2×n+1 = 6×(0,..n) + (0,..3), (6×n,..∞) From the even case, I propose
Q∞ = 6×nat + (0,..3)
and now I have to check whether it satisfies the equation. Starting with the right side,
nat \ (Q∞+3)
= nat \ (6×nat + (0,..3) + 3)
= nat \ (6×nat + (3,..6)) here is an informal expansion
= nat \ ((0, 6, 12, 18, 24, …) + (3,..6))
= nat \ (3, 4, 5, 9, 10, 11, 15, 16, 17, 21, 22, 23, 27, 28, 29, …)
= 0, 1, 2, 6, 7, 8, 12, 13, 14, 18, 19, 20, 24, 25, 26, …
= (0, 6, 12, 18, 24, …) + (0,..3)
= 6×nat + (0,..3)
= Q∞
So it does satisfy the equation. From the odd case, we can’t make a proposal because we can’t simplify ∞,..∞ .
(b) D = 0, (D+1) \ (D–1) § D0 = null
D1 = 0, (D0 +1) \ (D0–1) = 0, (null +1) \ (null–1) = 0, null \ null
=0
D2 = 0, (D1 +1) \ (D1–1) = 0, (0+1) \ (0–1)
= 0, 1\ –1
= 0, 1
D3 = 0, (D2 +1) \ (D2–1)
= 0, ((0, 1)+1) \ ((0, 1)–1) = 0, (1, 2)\(–1, 0)
= 0, 1, 2
D4 = 0, (D3 +1) \ (D3–1)
= 0, ((0, 1, 2)+1) \ ((0, 1, 2)–1) = 0, (1, 2, 3)\(–1, 0, 1)
= 0, 2, 3
and an informal addition
D5 = 0, (D4 +1) \ (D4–1)
= 0, ((0, 2, 3)+1) \ ((0, 2, 3)–1)
= 0, (1, 3, 4)\(–1, 1, 2)
= 0, 3, 4
D6 = 0, (D5 +1) \ (D5–1)
= 0, ((0, 3, 4)+1) \ ((0, 3, 4)–1)
= 0, (1, 4, 5)\(–1, 2, 3)
= 0, 1, 4, 5
D7 = 0, (D6 +1) \ (D6–1)
= 0, ((0, 1, 4, 5)+1) \ ((0, 1, 4, 5)–1)
= 0, (1, 2, 5, 6)\(–1, 0, 3, 4)
= 0, 1, 2, 5, 6
D8 = 0, (D7 +1) \ (D7–1)
= 0, ((0, 1, 2, 5, 6)+1) \ ((0, 1, 2, 5, 6)–1)
= 0, (1, 2, 3, 6, 7)\(–1, 0, 1, 4, 5)
= 0, 2, 3, 6, 7
It’s still hard to see the patterns, so maybe we have to go a bit farther. Then we see D4×n+1 = 0, 4×(0,..n) + (3, 4)
D4×n+2 = 0, 1, 4×(0,..n) + (4, 5)
D4×n+3 = 0, 1, 2, 4×(0,..n) + (5, 6)
D4×n+4 = 0, 2, 3, 4×(0,..n) + (6, 7)
We have a choice of four possible answers for equation. Recursive construction fails.
(c) E = nat\(E+1)
D∞ , but none of them satisfies the
§ E0 = E1 = E2 = E3 = E4 = E5 =
E2×n = E2×n+1 =
null
nat
0
0, nat+2 0, 2
0, 2, nat+4 2×(0,..n) 2×(0,..n), nat+2×n
From the even E∞ = 2×nat
case, we propose
which satisfies the equation. From the odd case, we propose E∞ = 2×nat, ∞
which does not satisfy the equation.
(d) F § F0 F1 F2 F3 F4 F5
=
0, (nat \ F)+1
= null
= nat
= 0
= 0, nat+2
= 0, 2
= 0, 2, nat+4
= 2×(0,..n)
F2×n F2×n+1 =
From the even F∞ = 2×nat
2×(0,..n), nat+2×n case, we propose
which satisfies the fixed-point equation. From the odd case, we propose
F∞ = 2×nat, ∞
which does not satisfy the fixed-point equation.