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.
Let S1 be a set, and let:
S2 = {S1}
S3 = {{S1}}
S4 = {S1, {S1}}
Questions:
S2 ∩ S4?S1 through S4 are members of S4?S1 through S4 are subsets of S4?For each of the following, true or false?
Α ⊆ Β and Β ⊆ Γ then Α ⊆ Γ.Α ⊆ Β and Β ⊆ Α then Α = Β.a ∈ Α and Α ⊆ Β then a ∈ Β.a ∈ Α iff {a} ⊆ Α.a ∈ Α and b ∈ Α iff {a,b} ⊆ Α.Let Α = {"a","b","c"}, Γ = {"c","d"}, and Δ = {"d","e","f"}. Then:
Α, also sometimes written ℘{Α))Α – Γ?Α ∩ Γ?Α ∪ Γ?∅ ∪ Γ?Α ∪ (Γ ∩ Δ)?Α ∩ (Γ ∩ Δ)?List all elements of {0,1,2}².
List all elements of {0,1}³.
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:
Α ∪ (Α ∩ Β) = Α
Α ∩ (Α ∪ Β) = Α
Α ⊆ Β iff Α ∪ Β ⊆ Β
Α ⊆ Β iff Α ⊆ Α ∩ Β
Α – (Α – Β) = Α ∩ Β
(Α – Β) ∩ Β = ∅
Α – (Β ∪ Γ) = (A – Β) ∩ (A – Γ)
Α – (Β ∩ Γ) = (A – Β) ∪ (A – Γ)
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?)
f(x,y) = (y,x)f(x,y) = xf(x) = y₀, for some fixed y₀ ∈ ΨIs + an operation on the set of odd natural numbers? Justify your answer.
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.
(a) How many different partitions of the set {1,2,3} are there? (b) How many different permutation functions are there on that set?
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 Α ⊖ Β = (Α – Β) ∪ (Β – Α).
(b) Prove that Α ⊖ Β ⊆ Β iff Α ⊆ Β.
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?
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.
If f: Δ → Γ and ΙΔ and ΙΓ are identity functions on Δ and Γ respectively, (a) what is f ∘ ΙΔ? (b) What is ΙΓ ∘ f?
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.