CmSc 365 Theory of Computation
Homework 02
1. Modified Problem 1.3.6, p.19. Let R Í A x A be a binary relation as defined below. In which cases R is a partial order? A total order? Prove your answers
a. A = the positive integers; (a,b) Î R iff b is divisible by a
b. A = N; (a,b) Î R iff b = a or b = a+1
c. A is the set of all English words; (a,b) Î R iff a is the same as b or occurs more frequently than b in our textbook.
a. A = the positive integers; (a,b) Î R iff b is divisible by a
Week partial order: reflexive, anti-symmetrical, transitive
a. reflexivity:
Let a is any positive integer. a is divisible by a (property of positive integers) therefore (a,a) Î R
b. anti-symmetrical
Let (a,b) Î R and a¹ b
a is divisible by b, therefore b is not divisible by a,
therefore (b,a) Ï R
c. transitive
Let (a,b) Î R and (b,c) Î R. a is divisible by b, and b is divisible by c. Therefore a is divisible by c (property of positive integers)
Therefore (a,c) Î R
Therefore R is partial order.
It is not a total order, because there are elements of A that are not in the relation R, e.g. (3,7) and (7,3) are not in R
b. A = N; (a,b) Î R iff b = a or b = a+1
Not a partial order because it is not transitive.
Let (a,b) Î R and (b,c) Î R, and let b = a+1, and c = b+1
Consider (a,c): c = b + 1 = a + 2, therefore (a,c) Ï R
c. A is the set of all English words; (a,b) Î R iff a is the same as b or occurs more frequently than b in our textbook.
Partial order
Reflexive: (a,a) Î R by the definition of R
Anti-symmetric:
Let (a,b) Î R, and a b. Therefore a occurs more frequently than b, therefore b does not occur more frequently than a, therefore (b,a) is not in the relation.
Transitivity:
Let (a,b) Î R and (b,c) Î R
A occurs more frequently than b, and b occurs more frequently than c, therefore a occurs more frequently than c, therefore (a,c) Î R
Not a total order, because different words that occur with same frequency cannot be ordered.
2. Problem 1.3.7 p.20. Let R1 and R2 be any two partial orders on the same set A. Show that R1 Ç R2 is a partial order
Antisymmetry:
Assume that R1 Ç R2 is not antisymmetrical. This means that there is a pair (a,b) Î R1 Ç R2 such that (b,a) Î R1 Ç R2
From the definition of intersection (a,b) Î R1 and (b,a) Î R1
Contradiction with the given fact that R1 is a partial order
Transitivity:
Assume that R1 Ç R2 is not transitive. This means that that there are two pairs
(a,b) Î R1 Ç R2 and (b,c) Î R1 Ç R2 such that (a,c) Ï R1 Ç R2
Since R1 is transitive and (a,b) Î R1 and (b,c) Î R1, (a,c) has to be in R1
Since R2 is transitive and (a,b) Î R2 and (b,c) Î R2, (a,c) has to be in R2
Therefore (a,c) has to be in R1 Ç R2.
3. Problem 1.3.9, p.20. Under what circumstances does a directed graph represent a function?
Let V be the set of nodes in the graph. The graph represents a relation GÍ V x V . For the relation to be a function, each node needs to have one and only one image under the relation. This is possible when each node has only one outgoing edge.
4. Prove that the set of all finite strings of 0 and 1 is countable.
Let S be the set of all finite binary strings. Consider the sets S1, S2, …, Sn, …
where Sk is the set containing only strings of length k.
{S1, S2, …, Sn, ..} is a partition of S, and each Sk is a finite set. Therefore we can first order the elements of S1, then the elements of S2, etc. We will show how we can order each of the sets Sk.
Each binary string of length k corresponds to a number and hence there is a mapping between the natural numbers and the elements of the set Sk. The elements of Sk can be ordered corresponding to the numbers they represent.
5. Prove that the set of all points in 3D space with integer coordinates is countable.
The task is to prove that N x N x N is countable. We know that N x N is infinitely countable and its elements can be ordered by using the dovetailing method.
Let A = N x N. Then N x N x N = A x N. The set A x N is countable because its elements can be ordered by using the dovetailing method
6. Prove that the powerset of an infinite countable set is not countable.
The powerset of an infinite countable set will contain finite and infinite sets. We can represent each set by an infinite binary string. This is possible because subsets of a countable set are also countable.
Assume that we can order these strings somehow. Consider the string that contains the first element of the first string inverted, the second element of the second string inverted etc. This string represents a subset, however it is not among the ordered strings. Therefore the strings cannot be ordered.
7. Suppose that A and B are sets. Consider 2 A È B and 2 A È 2 B . Under what circumstances are they equal? If they are not equal, is one necessarily a subset of the other and if so, which one? Prove your answers.
Let A = B. In this case 2 A È B = 2 A È A = 2 A
2 A È 2 B = 2 A È 2 A = 2 A
Thus if A = B, 2 A È B = 2 A È 2 B
Let A ¹ B.
Case a) A Í B.
We will prove that 2 A È B = 2 A È 2 B
Since A Í B we have A È B = B
Therefore 2 A È B = 2 B (1)
We need to show that 2 A Í 2 B
Let S Î 2 A . This means that S Í A
Since A Í B we have that S Í B. Therefore S Î 2 B
Therefore 2 A Í 2 B
Therefore 2 A È 2 B = 2 B (2)
From (1) and (2) it follows that
2 A È B = 2 A È 2 B
Case b) B Í A . The proof is carried out in a similar way
Case c) A – B ¹ Æ and B – A ¹ Æ
We will prove that 2 A È B ¹ 2 A È 2 B
Let S1 = A – B and S2 = B – A
Let s1 Î S1 and s2 Î S2
Consider the set {s1, s2}
s1 Î S1 Í A, therefore s1 Î A
s2 Î S2 Í B, therefore s2 Î B
Therefore {s1, s2} Í A È B, therefore {s1, s2}Î 2 A È B (3)
s2 Ï A, therefore {s1, s2} Ë A, therefore {s1, s2}Ï 2 A
s1 Ï B, therefore {s1, s2} Ë B, therefore {s1, s2}Ï 2 B
Therefore {s1, s2} Ï 2 A È 2 B (4)
From (3) and (4) it follows that 2 A È B ¹ 2 A È 2 B
We will show that necessarily 2 A È 2 B Í 2 A È B
Let Q Î 2 A È 2 B
Case c1. Q Í A Í A È B
Therefore Q Î 2 A È B
Case c2. Q Í B Í A È B
Therefore Q Î 2 A È B
Therefore 2 A È 2 B Í 2 A È B
To summarize: 2 A È B = 2 A È 2 B whenever A = B or A Í B or B Í A
In all other cases necessarily 2 A È 2 B Í 2 A È B
4