Phil 455: Homework 2 (on Sets and Functions)

Since this homework was posted late, it won’t be due until the end of the day (11:59 pm) on Friday.

1. Let T1 be a set, and let:

   T2 = {T1}

   T3 = {{T1}}

   T4 = {T1, {T1}}

   Questions:

   1. What is T2 ∩ T4?
   2. Which of T1 through T4 are members of T4?
   100. Which of T1 through T4 are subsets of T4?

2. For each of the following, true or false?

   1. If a ∈ A and A ⊆ B then a ∈ B.
   2. If A ⊆ B and B ⊆ Γ then A ⊆ Γ.
   100. a ∈ A iff {a} ⊆ A.
   101. a ∈ A and b ∈ A iff {a,b} ⊆ A.
   5. If A ⊆ B and B ⊆ A then A = B.

3. Let A = {"a","b","c"}, Γ = {"c","d"}, and Δ = {"d","e","f"}. Then:

   1. List 𝟚^A (the powerset of A).
   2. What is A ∪ Γ?
   100. What is Γ ∪ ∅?
   101. What is A ∩ Γ?
   5. What is A – Γ?
   6. What is A ∪ (Γ ∩ Δ)?
   7. What is A ∩ (Γ ∩ Δ)?

4. Is it always true that (A ∩ B) ∪ C = A ∩ (B ∪ C)? Justify your answer.

5. List all elements of {0,1}³.

6. (a) How many different partitions of the set {1,2,3} are there? (b) How many different permutation functions are there on that set?

7. Here is an example proof that A ⊆ A ∪ B. Suppose that a ∈ A. Then it is either the case that a ∈ A or a ∈ B. Thus by the definition of ∪, a ∈ A ∪ B. Since this holds for any a ∈ A, then by the definition of ⊆, A ⊆ A ∪ B.

   Here is an example proof that A ∩ B ⊆ A. Suppose that a ∈ A ∩ B. Then by the definition of ∩, a ∈ A (and also a ∈ B, but we don’t need that). Since this holds for any a ∈ A ∩ B, then by the definition of ⊆, A ∩ B ⊆ A.

   Prove the following:

   1. A ∪ (A ∩ B) = A
   2. A ∩ (A ∪ B) = A
   100. A ⊆ B iff A ∪ B ⊆ B
   101. A ⊆ B iff A ⊆ A ∩ B
   5. A – (A – B) = A ∩ B
   6. (A – B) ∩ B = ∅

8. Prove that A × (B ∩ Γ) = (A × B) ∩ (A × Γ).

9. Understand the symmetric difference of sets A and B to be the set (A ∪ B) – (A ∩ B). I’ve seen this operation expressed using each of the following notations: ∆ ⊝ ⊕ and + (+ is also sometimes used instead to express “disjoint union”). For the purposes of this question, let’s express symmetric difference using ⊕. (a) Prove that A ⊕ B = (A – B) ∪ (B – A). (b) Prove that A ⊕ B ⊆ B iff A ⊆ B.

10. Which of the following mathematical symbols express unary functions? Which express binary functions? Which don’t express functions at all?

    1. +
    2. <
    100. ∪
    101. ⊆
    5. sin

11. Consider the functions described below, where x ∈ Χ and y ∈ Ψ. Is the function injective? (If “it depends,” what does it depend on?)

    1. f(x,y) = x
    2. f(x,y) = (y,x)
    100. f(x) = (x,y₀), for some fixed y₀ ∈ Ψ

12. Let A be a finite set, and f be a function from A into A. (a) Explain why f’s being injective implies it is also surjective. (b) Explain why f’s being surjective implies it is also injective.

13. Is + an operation on the set of odd natural numbers? Justify your answer.

14. Let B be a set and consider its powerset 𝟚^B. Is ∪ an operation on 𝟚^B? What about ∩? What about –? A binary operator is called idempotent when applying it to (b,b) always gives b as a result. Which if any of those operators on 𝟚^B are idempotent?

15. Again let B be a set, but now consider the set Ψ of permutations on B. Consider the operator ∘ that takes two functions as arguments and delivers their composition as a result. Is ∘ an operation on Ψ? Is it commutative? Justify your answers.

16. When we’re talking about the composition of more than two functions, sometimes we’ll leave off the parentheses. Should h ∘ g ∘ f be understood as h ∘ (g ∘ f) or as (h ∘ g) ∘ f? Justify your answer.

17. If f: Δ → Γ and id_Δ and id_Γ are identity functions on Δ and Γ respectively, (a) what is f ∘ id_Δ? (b) What is id_Γ ∘ f?

18. If f: Δ → Γ is a bijection, (a) what is f⁻¹ ∘ f? (b) What is f ∘ f⁻¹? It should be clear what the domain and codomain of your answers are.