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

Let

`S1`

be a set, and let:S2 = {S1}

S3 = {{S1}}

S4 = {S1, {S1}}Questions:

- What is
`S2 ∩ S4`

?`S2`

, that is`{S1}`

- Which of
`S1`

through`S4`

are members of`S4`

?`S1`

,`S2`

- 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!

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

- If
`Α ⊆ Β`

and`Β ⊆ Γ`

then`Α ⊆ Γ`

. true - If
`Α ⊆ Β`

and`Β ⊆ Α`

then`Α = Β`

. true - If
`a ∈ Α`

and`Α ⊆ Β`

then`a ∈ Β`

. true `a ∈ Α`

iff`{a} ⊆ Α`

. true`a ∈ Α`

and`b ∈ Α`

iff`{a,b} ⊆ Α`

. true

- If
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}.- List 𝟚
^{Α}(the powerset of`Α`

, also sometimes written`℘{Α)`

)`∅`

,`{"a"}`

,`{"b"}`

,`{"c"}`

,`{"a","b"}`

,`{"a","c"}`

,`{"b","c"}`

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

- What is
`Α – Γ`

?`{"a","b"}`

- What is
`Α ∩ Γ`

?`{"c"}`

- What is
`Α ∪ Γ`

?`{"a","b","c","d"}`

- What is
`∅ ∪ Γ`

?`Γ`

, that is,`{"c","d"}`

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

?`{"a","b","c","d"}`

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

?`∅`

- List 𝟚
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.)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.)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.

`Α ∪ (Α ∩ Β) = Α`

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`Α ∩ Β`

).`Α ∩ (Α ∪ Β) = Α`

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`⊆`

,`Α ⊆ Α ∩ (Α ∪ Β)`

.`Α ⊆ Β`

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`⊆`

,`Α ⊆ Β`

.`Α ⊆ Β`

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`⊆`

,`Α ⊆ Β`

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

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`⊆`

,`Α ∩ Β ⊆ Α – (Α – Β)`

.`(Α – Β) ∩ Β = ∅`

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`⊆`

.`Α – (Β ∪ Γ) = (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 ∈ Α – (Β ∪ Γ)`

.`Α – (Β ∩ Γ) = (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 ∈ Α – (Β ∩ Γ)`

.

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)`

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)`

.`f(x,y) = x`

if`Ψ`

has more than one element, not injective`f(x) = y₀`

, for some fixed`y₀ ∈ Ψ`

if`Χ`

has more than one element, not injective

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.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`⊇`

,`Α ⨯ (Β ∩ Γ) ⊇ (Α ⨯ Β) ∩ (Α ⨯ Γ)`

.(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},{2},{3}}`

`{{1,2},{3}}`

`{{1},{2,3}}`

`{{1,3},{2}}`

`{{1,2,3}}`

Six permutation functions.

- 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)}`

. - 123 –> 132
- 123 –> 213
- 123 –> 312
- 123 –> 231
- 123 –> 321

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`⊆`

,`Α ⊖ Β ⊆ Β`

.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`Α = ∅`

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

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

.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.- the first is Ι
_{Δ}, from the previous question - the second is Ι
_{Γ}, from the previous question

- the first is Ι