S2 Flashcards
(10 cards)
χA∪C (x) + χB∪C (x) = χA∪B∪C(x).
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).
χA∩C(x) + χA∪C(x) = 2 · χA(x).
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).
χA×B(x,y) = χA(x)χB(y)
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)

A×(B∩C) = (A×B) ∩ (A×C).
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).
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.
True.
Suppose x1,x2 ∈ X are such that (g◦f)(x1) = (g◦f)(x2).
This means, by definition, that g(f(x1)) = g(f(x2)).
Since g is injective, we must have f(x1) = f(x2).
Since f is also injective, x1 = x2.
This proves that the composition g ◦ f is injective.
For any real numbers x1,···xn,

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.
If n is odd, then n divides Σk.

True.
We know (or can prove by induction).
If n is odd, then 1/2(n + 1) is an integer and hence the sum on the left is an integer multiple 2 of n.

Consider the relation ∼ on ℤ where a∼b if and only if a−b is a power of 2. Then ∼ is an equivalence relation.
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 = 21) and 9 ∼ 5 (as 9 − 5 = 22), but 11 ∼/∼ 5, since 11 − 5 = 6 is not a power of 2.
Consider the relation ∼ on ℤ where a ∼ b if and only if a−b is divisible by 3. Then ∼ is an equivalence relation.
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.
Let A and B be finite sets with card(A) = card(B). Then there exists a bijection between A and B.
True.
Suppose n := card(A) = card(B).
Then we may write out the elements of A = {a1,…,an} and B = {b1,…,bn}, since each set has n elements, there are no repeats in either set.
We define f : A → B by f(ai) := bi for 1 ≤ i ≤ n.
We claim this is a bijection. Given an element b∈B, we know that b=bi for some 1 ≤ i ≤ n, but then f(ai) = bi = b.
This shows that f is surjective. Suppose that x1, x2 ∈ A are such that f(x1) = f(x2).
Thenx1 =ai,x2 =aj for some 1 ≤ i, j ≤ n. This means that bi = f(ai) = f(x1) = f(x2) = f(aj) = bj. But since we have listed the elements of B without repeating any elements, we must have i = j and hence x1 = ai = aj = x2. This shows that f is injective and hence a bijection.