~~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:

- What is
`S2 ∩ S4`

? - Which of
`S1`

through`S4`

are members of`S4`

? - Which of
`S1`

through`S4`

are subsets of`S4`

?

- What is
For each of the following, true or false?

- If
`Α ⊆ Β`

and`Β ⊆ Γ`

then`Α ⊆ Γ`

. - If
`Α ⊆ Β`

and`Β ⊆ Α`

then`Α = Β`

. - If
`a ∈ Α`

and`Α ⊆ Β`

then`a ∈ Β`

. `a ∈ Α`

iff`{a} ⊆ Α`

.`a ∈ Α`

and`b ∈ Α`

iff`{a,b} ⊆ Α`

.

- If
Let

`Α = {"a","b","c"}`

,`Γ = {"c","d"}`

, and`Δ = {"d","e","f"}`

. Then:- List 𝟚
^{Α}(the powerset of`Α`

, also sometimes written`℘{Α)`

) - What is
`Α – Γ`

? - What is
`Α ∩ Γ`

? - What is
`Α ∪ Γ`

? - What is
`∅ ∪ Γ`

? - What is
`Α ∪ (Γ ∩ Δ)`

? - What is
`Α ∩ (Γ ∩ Δ)`

?

- List 𝟚
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) = x`

`f(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.