S2

Question 1

χ_A∪C (x) + χ_B∪C (x) = χ_A∪B∪C(x).

Answer 1

False.

Since C is non-empty, we may take x ∈ C.

Then x ∈ A∪C, B∪C, A∪ B ∪ C and so:

χ_A∪C(x) + χ_B∪C(x) = 1 + 1 ≠ 1 = χ_A∪B∪C(x).

Question 2

χ_A∩C(x) + χ_A∪C(x) = 2 · χ_A(x).

Answer 2

False.

Let A := {3}, C := {5}.

Then A ∩ C = ∅, A ∪ C = {3, 5} and so:

χ_A∩C(5) + χ_A∪C(5) = 0 + 1 ≠ 0 = 2 · χ_A(5).

Question 3

χ_A×B(x,y) = χ_A(x)_χB(y)

Answer 3

True.

We need to check four cases: ​

• x ∈ A and y ∈ B, so (x,y) ∈ A×B ⇒ χ_A×B(x,y) = 1 = 1·1 = χ_A(x)χ_B(y)
• x ∉ A and y∈ B, so(x,y) ∉ A×B ⇒ χ_A×B(x,y) = 0 = 0·1 = χ_A(x)χ_B(y)
• x ∈ A and y∉ B, so(x,y) ∉ A×B ⇒ χ_A×B(x,y) = 0 = 1·0 = χ_A(x)χ_B(y)
• x ∉ A and y ∉ B, so(x,y) ∉ A×B ⇒ χ_A×B(x,y) = 0 = 0·0 = χ_A(x)χ_B(y)

Question 4

A×(B∩C) = (A×B) ∩ (A×C).

Answer 4

True.

Suppose (x,y) ∈ A × (B∩C), then x ∈ A and y ∈ B∩C.

In particular y ∈ B and y ∈ C, so (x,y) ∈ A×B and (x,y) ∈ A×C.

Hence (x,y) ∈ (A×B) ∩ (A×C).

Conversely, if (x,y) ∈ (A×B) ∩ (A×C), then (x,y) ∈ A × B, so x ∈ A and y ∈ B. Also, (x,y) ∈ A×C, so x ∈ A and y ∈ C.

Since y ∈ B and y ∈ C, we have y ∈ B ∩ C.

Hence (x,y) ∈ A×(B∩C).

Question 5

Let X, Y and Z be any sets and let f : X → Y and g : Y → Z be two functions.

If f and g are injective, then g ◦ f is injective.

Answer 5

True.

Suppose x₁,x₂ ∈ X are such that (g◦f)(x₁) = (g◦f)(x₂).

This means, by definition, that g(f(x₁)) = g(f(x₂)).

Since g is injective, we must have f(x₁) = f(x₂).

Since f is also injective, x₁ = x₂.

This proves that the composition g ◦ f is injective.

Question 6

For any real numbers x₁,···x_n,

Answer 6

True.

For each fixed value of i, we may divide the set {1,…,n} into

{j : j < i} ∪ {i} ∪ {j : j > n} and hence divide the sum into three parts.

See answer sheet 2 for more detailed answer.

Question 7

If n is odd, then n divides Σk.

Answer 7

True.

We know (or can prove by induction).

If n is odd, then ^₁/₂(n + 1) is an integer and hence the sum on the left is an integer multiple 2 of n.

Question 8

Consider the relation ∼ on ℤ where a∼b if and only if a−b is a power of 2. Then ∼ is an equivalence relation.

Answer 8

False.

The relation is not reflexive since 0 is not a power of 2.

Furthermore, it is not transitive, since 11 ∼ 9 (as 11 − 9 = 2¹) and 9 ∼ 5 (as 9 − 5 = 2²), but 11 ∼/∼ 5, since 11 − 5 = 6 is not a power of 2.

Question 9

Consider the relation ∼ on ℤ where a ∼ b if and only if a−b is divisible by 3. Then ∼ is an equivalence relation.

Answer 9

True.

It is reflexive: if a ∈ ℤ, then a−a = 0 is divisible by 3.

It is symmetric: if a ∼ b, then a−b is divisible by 3, and so b−a is also divisible by 3, so b ∼ a.

It is transitive: if a ∼ b and b ∼ c, then a−b and b−c are divisible by 3, then so is their sum a−b+b−c = a−c, but this means that a ∼ c.

Question 10

Let A and B be finite sets with card(A) = card(B). Then there exists a bijection between A and B.

Answer 10

True.

Suppose n := card(A) = card(B).

Then we may write out the elements of A = {a₁,…,a_n} and B = {b₁,…,b_n}, since each set has n elements, there are no repeats in either set.

We define f : A → B by f(a_i) := b_i for 1 ≤ i ≤ n.

We claim this is a bijection. Given an element b∈B, we know that b=b_i for some 1 ≤ i ≤ n, but then f(a_i) = b_i = b.

This shows that f is surjective. Suppose that x₁, x₂ ∈ A are such that f(x₁) = f(x₂).

Thenx₁ =a_i,x₂ =a_j for some 1 ≤ i, j ≤ n. This means that b_i = f(a_i) = f(x₁) = f(x₂) = f(a_j) = b_j. But since we have listed the elements of B without repeating any elements, we must have i = j and hence x₁ = a_i = a_j = x₂. This shows that f is injective and hence a bijection.