A set T of ordered pairs (a, b), where a, b are integers 0, is defined recursively as follows.?

Question

Rule-1: (0, 0), and (1, 1) are in T
Rule-2: If (a, b) is in T, then so is (a+2, b).
Rule-3: If (a, b) is in T then so is (a, b+2).

(i) List the first 10 elements/pairs (a, b) of set T in increasing order. Use a+b as value of a pair (a, b) for ordering purpose. Break ties arbitrary. Start with (0, 0).


(ii) The set T can be defined non-inductively using several other ways. Give one such definition that does not use induction or recursion but uses set comprehension. In other words, T = { (a, b) | some property P is satisfied by a, b}. State property P.

Answer 1

(i)
0,0
0,2
1,1
2,0
0,4
1,3
2,2
3,1
4,0
0,6

(ii) T = { (a, b) | a,b nonnegative integers, and a+b is even}.
Incidentally, this is not too hard to prove if you are handy with induction. You can prove that for all nonnegative integers n, that T contains all (a,b) such that a,b nonnegative integers, and a+b = 2n.

Answer 2

Part i -- This is just blindly applying the rules that you are given at the beginning:

#1: (0, 0) -- rule 1
#2: (1, 1) -- rule 1
#3: (2, 0) -- from 1 by rule 2
#4: (0, 2) -- from 1 by rule 3
#5: (3, 1) -- from 2 by rule 2
#6: (1, 3) -- from 2 by rule 3
#7: (4, 0) -- from 3 by rule 2
#8: (2, 2) -- from 3 by rule 3
#9: (0, 4) -- from 4 by rule 3
#10: (5, 1): -- from 5 by rule 2

ii -- here we need to characterize the set T. One possible way of doing it is:

T={(a, b) ∈ (ℕ∪{0})×(ℕ∪{0}): (a+b)/2 ∈ ℕ∪{0}}

Proof: Let S = {(a, b) ∈ (ℕ∪{0})×(ℕ∪{0}): (a+b)/2 ∈ ℕ∪{0}}. Clearly (0, 0) and (1, 1) are in S, since 0+0=0 and 1+1=2, both of which are even. Suppose (a, b) is in S. Then a and b are nonnegative integers, and a+b is even. This implies that a+2 is a nonnegative integer and (a+2)+b is even, and also that b+2 is a nonnegative integer and a+(b+2) is even, so (a+2, b) and (a, b+2) are both elements of S. So S satisfies the recursive definition, and since T is the smallest set satisfying that definition, we have that T⊆S. To prove the converse, we suppose (a, b)∈S. Then a+b is even, so either a and b are both even or a and b are both odd. If a and b are both even, then (a, 0) can be obtained from (0, 0) by applying rule 2 a/2 times, and then (a, b) can be obtained from (a, 0) by applying rule 3 b/2 times, so (a, b)∈T. Conversely, if a and b are both odd, then a-1 and b-1 are both even, so (a, 1) = (1+(a-1), 1) can be obtained from (1, 1) by applying rule 2 (a-1)/2 times, and then (a, b) = (a, 1+(b-1)) can be obtained from (a, 1) by applying rule 3 (b-1)/2 times, so (a, b)∈T. In either case, (a, b)∈S ⇒ (a, b)∈T, so S⊆T. Having already proved T⊆S, it follows that S=T. Q.E.D.