S2 Flashcards

(10 cards)

1
Q

χA∪C (x) + χB∪C (x) = χA∪B∪C(x).

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

χA×B(x,y) = χA(x)χB(y)

A

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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

For any real numbers x1,···xn,

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

If n is odd, then n divides Σk.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly