Phil 455: Homework 1

We’ll settle the due date later; it will be sometime during the third week of classes. Due by the end of the day on Wed, Jan 24.

We’ll do some or all of problems 1–8 in class.

Note that when a problem asks you to “explain/justify” something, that is not asking for an answer as rigorous as when you are asked to “show/prove” something. And as we’ve discussed in class, when you are asked to prove something, we don’t expect it to be in a strict formal proof calculus, unless/until that’s what we specifically request. The kinds of proofs we’ll be doing on the board (with the steps made explicit enough), or that you’d submit for homework in a math class, are usually adequate.

Sample answers in purple.

  1. Let S1 be a set, and let:

    S2 = {S1}
    S3 = {{S1}}
    S4 = {S1, {S1}}

    Questions:

    1. What is S2 ∩ S4? S2, that is {S1}
    2. Which of S1 through S4 are members of S4? S1, S2
    3. Which of S1 through S4 are subsets of S4? S2, S3, S4. One of you noticed that S1 would also be a subset if S1 happened to be the empty set. Nice!

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

    1. If Α ⊆ Β and Β ⊆ Γ then Α ⊆ Γ. true
    2. If Α ⊆ Β and Β ⊆ Α then Α = Β. true
    3. If a ∈ Α and Α ⊆ Β then a ∈ Β. true
    4. a ∈ Α iff {a} ⊆ Α. true
    5. a ∈ Α and b ∈ Α iff {a,b} ⊆ Α. true

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

    Some students get confused between (i) the empty set, written as ∅ or {}; and (ii) the set containing the empty set, written as {∅} or {{}}. The first of these is a subset of Α, and so a member of 𝟚Α; the second is not.

    Spelling it out in more detail: The first is a set with no members; that is why it is a subset of A (and of every other set): because all of its members (all zero of them) are also members of A. Since it is a subset of A, this set ∅ should be a member of 𝟚A. (The powerset of A is defined to be the set whose members are all and only the subsets of A.)

    The second set {∅} is a set with one member, namely the first set. The second set will be a subset of A iff its one member is also a member of A. But the empty set ∅ is not a member of A; hence the set {∅} which contains the empty set is not a subset of A. Hence that set {∅} should not be a member of 𝟚A.

    1. List 𝟚Α (the powerset of Α, also sometimes written ℘{Α)) ∅, {"a"}, {"b"}, {"c"}, {"a","b"}, {"a","c"}, {"b","c"}, {"a","b","c"}
    2. What is Α – Γ? {"a","b"}
    3. What is Α ∩ Γ? {"c"}
    4. What is Α ∪ Γ? {"a","b","c","d"}
    5. What is ∅ ∪ Γ? Γ, that is, {"c","d"}
    6. What is Α ∪ (Γ ∩ Δ)? {"a","b","c","d"}
    7. What is Α ∩ (Γ ∩ Δ)? ∅

  4. List all elements of {0,1,2}².

    (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2). Note that these elements are all ordered pairs, not sets. (Unless you equate ordered pairs with some complex set-construction.)

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

    (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). Note that these elements are all ordered triples, not sets. (Unless you equate ordered triples with some complex set-construction.)

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

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

    Prove the following:

    In several of the proofs below, we make use of the two results just established.

    1. Α ∪ (Α ∩ Β) = Α

      Proof of ⊆: Suppose a ∈ Α ∪ (Α ∩ Β). Then by def of ∪, either (i) a ∈ Α or (ii) a ∈ Α ∩ Β. By def of ∩, (ii) implies that a ∈ Α. So in either case (i) or (ii), a ∈ Α. So by def of ⊆, Α ∪ (Α ∩ Β) ⊆ Α.

      Proof of ⊇ was given above (with Γ being Α ∩ Β).

    2. Α ∩ (Α ∪ Β) = Α

      Proof of ⊆ was given above (with Δ being Α ∪ Β).

      Proof of ⊇: Suppose (i) a ∈ Α. We already saw that Α ⊆ Α ∪ Γ for any Γ; let it here be Β. It follows from (i) and def of ⊆ that (ii) a ∈ Α ∪ Β. From (i) and (ii) and def of ∩ it follows that a ∈ Α ∩ (Α ∪ Β). So by def of ⊆, Α ⊆ Α ∩ (Α ∪ Β).

    3. Α ⊆ Β iff Α ∪ Β ⊆ Β

      Proof of →: Suppose a ∈ Α ∪ Β. Then by def of ∪, either (i) a ∈ Α or (ii) a ∈ Β. In case (i), the assumption that Α ⊆ Β and def of ⊆ give us that a ∈ Β. So in both cases a ∈ Β. So by def of ⊆, Α ∪ Β ⊆ Β.

      Proof of ←: Suppose a ∈ Α. We already saw that Α ⊆ Α ∪ Γ for any Γ; let it here be Β. It follows that a ∈ Α ∪ Β. The assumption that Α ∪ Β ⊆ Β and def of ⊆ give us that a ∈ Β. So by def of ⊆, Α ⊆ Β.

    4. Α ⊆ Β iff Α ⊆ Α ∩ Β

      Proof of →: Suppose (i) a ∈ Α. The assumption that Α ⊆ Β and def of ⊆ give us that (ii) a ∈ Β. (i) and (ii) and def of ∩ give us that a ∈ Α ∩ Β. So by def of ⊆, Α ⊆ Α ∩ Β.

      Proof of ←: Suppose a ∈ Α. The assumption that Α ⊆ Α ∩ Β and def of ⊆ give us that a ∈ Α ∩ Β. So by def of ∩, a ∈ Β. So by def of ⊆, Α ⊆ Β.

    5. Α – (Α – Β) = Α ∩ Β

      Proof of ⊆: Suppose a ∈ Α – (Α – Β). Then by def of –, (i) a ∈ Α and (ii) a ∉ Α – Β. Suppose (iii) a ∉ Β. Then by (i) and (iii) and def of –, a ∈ Α – Β, contradicting (ii). So (iii) must be false; that is, (iv) a ∈ Β. From (i) and (iv) and def of ∩, a ∈ Α ∩ Β. So by def of ⊆, Α – (Α – Β) ⊆ Α ∩ Β.

      Proof of ⊇: Suppose a ∈ Α ∩ Β. Then by def of ∩, (i) a ∈ Α and (ii) a ∈ Β. By (ii) and def of –, we have (iii) a ∉ Α – Β. By (i) and (iii) and def of –, we have a ∈ Α – (Α – Β). So by def of ⊆, Α ∩ Β ⊆ Α – (Α – Β).

    6. (Α – Β) ∩ Β = ∅

      Proof of ⊆: Suppose a ∈ (Α – Β) ∩ Β; then by def of ∩, a ∈ Α – Β and a ∈ Β. But if a ∈ Α – Β, then by def of – it’s not ∈ Β. So there is no such a. So every element of (Α – Β) ∩ Β (all none of them) are elements of ∅.

      Proof of ⊇: ∅ is a subset of every set, by def of ∅ and ⊆.

    7. Α – (Β ∪ Γ) = (A – Β) ∩ (A – Γ)

      Proof of ⊆: Suppose a ∈ Α – (Β ∪ Γ); then by def of – and ∪, a ∈ Α but ∉ either of Β or Γ. Thus it’s the case that a is ∈ Α but ∉ Β, which means a ∈ Α – Β. Similarly, a is ∈ Α but ∉ Γ, which means a ∈ Α – Γ. So by the def of ∩, a ∈ (A – Β) ∩ (A – Γ).

      Proof of ⊇: Suppose a ∈ (A – Β) ∩ (A – Γ); then by def of ∩, a ∈ Α – Β and a ∈ Α – Γ. By def of –, the first means that a ∈ Α but ∉ Β, and the second means that a ∈ Α but ∉ Γ. So a ∈ Α but ∉ either of Β or Γ. By def of – and ∪, this means a ∈ Α – (Β ∪ Γ).

    8. Α – (Β ∩ Γ) = (A – Β) ∪ (A – Γ)

      Proof of ⊆: Suppose a ∈ Α – (Β ∩ Γ); then by def of – and ∩, a ∈ Α but either ∉ Β or ∉ Γ. Thus it’s eithr the case that a is ∈ Α but ∉ Β, which means a ∈ Α – Β. Or it’s the case that a is ∈ Α but ∉ Γ, which means a ∈ Α – Γ. So by the def of ∪, a ∈ (A – Β) ∪ (A – Γ).

      Proof of ⊇: Suppose a ∈ (A – Β) ∪ (A – Γ); then by def of ∪, a ∈ Α – Β or a ∈ Α – Γ. By def of –, the first means that a ∈ Α but ∉ Β, and the second means that a ∈ Α but ∉ Γ. So a ∈ Α but either a ∉ Β or a ∉ Γ. Thus it cannot be the case that a ∈ both of Β and Γ; by def of ∩ that means a ∉ Β ∩ Γ. Since we said a ∈ Α, by def of – this means a ∈ Α – (Β ∩ Γ).

  7. Consider the functions described below, understood as applying for all x ∈ Χ and y ∈ Ψ. Is the function injective? (If “it depends,” what does it depend on?)

    1. f(x,y) = (y,x) injective. Why? Suppose f(a,b) = f(c,d) = (y,x). By definition of f, y = b = d, and x = a = c. So (a,b) = (c,d). There cannot be distinct pairs that f maps both of to (y,x).
    2. f(x,y) = x if Ψ has more than one element, not injective
    3. f(x) = y₀, for some fixed y₀ ∈ Ψ if Χ has more than one element, not injective

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

    No, 1 + 3 = 4, and 4 is not an odd natural number. But operations have to have the same codomain as their domain(s) of arguments.

  9. Prove that Α ⨯ (Β ∩ Γ) = (Α ⨯ Β) ∩ (Α ⨯ Γ).

    To prove that two sets are equal, first we prove that the left-hand set ⊆ the right-hand one, then we prove the converse (which I’ll describe as the left-hand set being ⊇ the right-hand one).

    Here is a proof of the ⊆ direction: Suppose e ∈ Α ⨯ (Β ∩ Γ). Then by def of ⨯, e = (a,d) where (i) a ∈ Α and (ii) d ∈ Β ∩ Γ. From (ii) and def of ∩, it follows that (iii) d ∈ Β and (iv) d ∈ Γ. From (i) and (iii) and def of ⨯, it follows that (v) (a,d) ∈ Α ⨯ Β. From (i) and (iv) and def of ⨯, it follows that (vi) (a,d) ∈ Α ⨯ Γ. From (v) and (vi) and def of ∩, it follows that (a,d) ∈ (Α ⨯ Β) ∩ (Α ⨯ Γ). So by def of ⊆, Α ⨯ (Β ∩ Γ) ⊆ (Α ⨯ Β) ∩ (Α ⨯ Γ).

    You supply a proof of the other direction.

    Proof of ⊇: Suppose e ∈ (Α ⨯ Β) ∩ (Α ⨯ Γ). From def of ∩, (i) e ∈ Α ⨯ Β, and (ii) e ∈ Α ⨯ Γ. From def of ⨯, it follows that e = (a,d) where (iii) a ∈ Α and (iv) d ∈ Β and (v) d ∈ Γ. From (iv) and (v) and def of ∩, it follows that (vi) d ∈ Β ∩ Γ. From (iii) and (vi) and def of ⨯, it follows that (a,d) ∈ Α ⨯ (Β ∩ Γ). So by def of ⊇, Α ⨯ (Β ∩ Γ) ⊇ (Α ⨯ Β) ∩ (Α ⨯ Γ).

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

    Five partitions: one into three cells, three ways of dividing into two cells, and one into a single cell.

    1. {{1},{2},{3}}
    2. {{1,2},{3}}
    3. {{1},{2,3}}
    4. {{1,3},{2}}
    5. {{1,2,3}}

    Six permutation functions.

    1. 123 –> 123, using this as shorthand for the function that maps 1 into 1, 2 into 2, 3 into 3. Writing it out more verbosely, this is the function whose graph is {(1,1),(2,2),(3,3)}.
    2. 123 –> 132
    3. 123 –> 213
    4. 123 –> 312
    5. 123 –> 231
    6. 123 –> 321

  11. Understand the symmetric difference of sets Α and Β to be the set (Α ∪ Β) – (Α ∩ Β). I’ve seen this operation expressed using each of the following notations: ∆ ⊖ ⊕ and +. For the purposes of this question, let’s express symmetric difference using ⊖.

    (a) Prove that Α ⊖ Β = (Α – Β) ∪ (Β – Α).

    Proof of ⊆: Suppose a ∈ (Α ∪ Β) – (Α ∩ Β). By def of –, (i) a ∈ Α ∪ Β and (ii) a ∉ Α ∩ Β. From (i) it follows that a ∈ Α or a ∈ Β, but (ii) says a can’t be an element of both Α and Β. So either (iii) a ∈ Α and a ∉ Β, or (iv) a ∉ Α and a ∈ Β. In case (iii) it would be the case by def of – that a ∈ Α – Β, and hence ∈ (Α – Β) ∪ Γ for any Γ. In case (iv) it would be the case by def of – that a ∈ Β – Α, and hence ∈ Δ ∪ (Β – Α) for any Δ. Letting Γ be Β – Α and Δ be Α – Β, in both cases we have a ∈ (Α – Β) ∪ (Β – Α). So by def of ⊆, (Α ∪ Β) – (Α ∩ Β) ⊆ (Α – Β) ∪ (Β – Α).

    Proof of ⊇: Suppose a ∈ (Α – Β) ∪ (Β – Α). By def of ∪, it follows that (i) a ∈ Α – Β or (ii) a ∈ Β – Α. In case (i) by def of –, a ∈ Α and a ∉ Β. In case (ii) by def of –, a ∈ Β and a ∉ Α. In each case by def of ∪, a ∈ Α ∪ Β, and in each case by def of ∩, a ∉ Α ∩ Β. So by def of –, in each case a ∈ (Α ∪ Β) – (Α ∩ Β). So by def of ⊆, (Α – Β) ∪ (Β – Α) ⊆ (Α ∪ Β) – (Α ∩ Β).

    (b) Prove that Α ⊖ Β ⊆ Β iff Α ⊆ Β.

    Proof of →: Suppose a ∈ Α. Suppose (i) a ∉ Β. Then by def of –, a ∈ Α – Β. Then a ∈ (Α – Β) ∪ Γ for any Γ. Thus by the result of (9a), a ∈ Α ⊖ Β. The assumption that Α ⊖ Β ⊆ Β gives us that a ∈ Β, contradicting (i). So (i) must be false; that is, a ∈ Β. So by def of ⊆, Α ⊆ Β.

    Proof of ←: Suppose a ∈ Α ⊖ Β. Then by the result of (9a), either (i) a ∈ Α – Β or (ii) a ∈ Β – Α. In case (i) by def of –, a ∈ Α and a ∉ Β. In case (ii) by def of –, a ∈ Β and a ∉ Α. The assumption that Α ⊆ Β tells us that case (i) cannot hold. Thus we’re in case (ii) where a ∈ Β. So by def of ⊆, Α ⊖ Β ⊆ Β.

  12. Let Β be a set and consider its powerset 𝟚Β. Is ∪ an operation on 𝟚Β? 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 𝟚Β are idempotent?

    All three are operations, because the results are always subsets of Β, that is, elements of 𝟚Β. Only ∪ and ∩ are idempotent. For Α ⊆ Β, Α – Α will = Α only in the special case where Α = ∅.

  13. Again let Β be a set, but now consider the set Ψ of permutations on Β. 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.

    Recall that a permutation on Β is a bijective function from Β → Β.

    Yes, it’s an operation, because any composition of permutations f, g on Β will also be a function from Β → Β. It will also be injective, because if the composition mapped two arguments to the same result, it would have to be because f did or g did (or both); but f and g are permutations so they’re injective. The composition will also be surjective, because if it failed to map to some element of Β, it would have to be because f did or g did (or both); but f and g are permutations so they’re surjective. So the composition is also an injective, surjective function (i.e. a bijection) from Β → Β. In other words, it’s also a permutation and will be a member of Ψ by definition. So composition on elements of of Ψ is an operation.

    If Β has enough elements, then composition won’t be commutative. Here’s an example where Β is {1,2,3}. Using the same shorthand as in the answer to 10(b), let f be the permutation 123 –> 132; and g be the permutation 123 –> 312. Then (g ∘ f)(2) = 2 but (f ∘ g)(2) = 1.

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

    The first is f. The second is also f.

  15. 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.

    1. the first is ΙΔ, from the previous question
    2. the second is ΙΓ, from the previous question