Foundations of Computer Science: Honors
Homework 2A
Problem 1 For each of the following statements about sets determine whether it is always true (also provide an example), or only sometimes true (also provide an example and counterexample). Please provide an explanation.
1. A ∈ P(A)
2. A ⊆ P(A)
3. (|A|≤|B|) =⇒ (A ⊆ B)
4. (A ⊆ B) =⇒ (|A|≤|B|)
Problem 2 Find the smallest two finite sets A and B for each of the following four conditions Note: The smallest sets may not be unique.
1. A ∈ B,A ⊆ B, and P(A) ⊆ B
2. (N∩A) ∈ A,B ⊂ A, and P(B) ⊆ A
3. A ⊆ (P(P(B))−P(A))
4. A ⊇ (P(P(B))−P(A))
Problem 3 Prove or disprove (by providing a counterexample) each of the following properties of binary relations: Let S(A) be the symmetric closure of set A. Let T(A) be the transitive closure of set A. For every binary relation R,
1. T(S(R)) ⊆ S(T(R))
2. S(T(R)) ⊆ T(S(R))
Problem 4 How many reflexive binary relations are there on S x S? How many symmetric relations? Explain. Bonus: How many equivalence relations are there on S x S? Explain.
