Lesson test: Equivalence relations

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Equivalence relations

1.[3p]
Which of these relations on $ℤ$ are equivalence relations?

Select all that apply

$a \sim b$ when $a \equiv b (mod 7)$

Correct

$a \sim b$ when $a^{2} = b^{2}$

Correct

$a \sim b$ when $a + b$ is even

Correct

$a \sim b$ when $a ∣ b$

The answer is: $a \sim b$ when $a \equiv b (mod 7)$ , $a \sim b$ when $a^{2} = b^{2}$ , $a \sim b$ when $a + b$ is even

$a \sim b$ when $| a - b | \leq 1$

The answer is: $a \sim b$ when $a \equiv b (mod 7)$ , $a \sim b$ when $a^{2} = b^{2}$ , $a \sim b$ when $a + b$ is even

$a \sim b$ when $a b > 0$

The answer is: $a \sim b$ when $a \equiv b (mod 7)$ , $a \sim b$ when $a^{2} = b^{2}$ , $a \sim b$ when $a + b$ is even

2.[2p]
Match each relation on $ℝ$ to the property it lacks.

$x \leq y$
$| x - y | \leq 1$
$x y > 0$
$x - y \in ℤ$

reflexive
symmetric
transitive
none, it is an equivalence relation

Show the answer

$x \leq y$ : symmetric $| x - y | \leq 1$ : transitive $x y > 0$ : reflexive $x - y \in ℤ$ : none, it is an equivalence relation

3.[2p]
What is wrong with the argument "if $a \sim b$ then $b \sim a$ by symmetry, so $a \sim a$ by transitivity, hence every symmetric and transitive relation is reflexive"?

It assumes some $b$ with $a \sim b$ exists, and for some $a$ there may be none

Correct

Transitivity cannot be applied to $a \sim b$ and $b \sim a$ together

The answer is: It assumes some $b$ with $a \sim b$ exists, and for some $a$ there may be none

Symmetry only applies when $a \neq b$

The answer is: It assumes some $b$ with $a \sim b$ exists, and for some $a$ there may be none

Nothing: every symmetric and transitive relation is reflexive

The answer is: It assumes some $b$ with $a \sim b$ exists, and for some $a$ there may be none

4.[1p]
How many relations are there on a set with $3$ elements?

CorrectNot quite: 512

5.[2p]
How many equivalence relations are there on the set ${1, 2, 3, 4}$ ?

CorrectNot quite: 15

6.[1p]
Which set is the congruence class $[2]$ modulo $3$ ?

${\dots, - 4, - 1, 2, 5, 8, \dots}$

Correct

${\dots, - 2, 2, 6, 10, \dots}$

The answer is: ${\dots, - 4, - 1, 2, 5, 8, \dots}$

${\dots, - 5, - 2, 1, 4, 7, \dots}$

The answer is: ${\dots, - 4, - 1, 2, 5, 8, \dots}$

${\dots, - 6, - 3, 0, 3, 6, \dots}$

The answer is: ${\dots, - 4, - 1, 2, 5, 8, \dots}$

7.[2p]
Put the lines of the proof that the relation $(a, b) \sim (c, d)$ when $a d = b c$ , on pairs with nonzero second coordinate, is transitive in order.

Let $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$ , so $a d = b c$ and $c f = d e$ .
Multiplying the first equation by $f$ gives $a d f = b c f$ .
Substituting $c f = d e$ gives $a d f = b d e$ .
Since $d \neq 0$ , $a f = b e$ , that is, $(a, b) \sim (e, f)$ .
So $d (a f - b e) = 0$ .

Show the answer

a, b, c, d, e

8.[2p]
In building $ℚ$ from pairs $(a, b)$ with $(a, b) \sim (c, d)$ when $a d = b c$ , why must the pair $(0, 0)$ be excluded?

It would be related to every pair, and transitivity would fail

Correct

It would make the relation fail to be reflexive

The answer is: It would be related to every pair, and transitivity would fail

It would make the relation fail to be symmetric

The answer is: It would be related to every pair, and transitivity would fail

It would give $ℚ$ a second zero, but the relation would still be an equivalence

The answer is: It would be related to every pair, and transitivity would fail

9.[3p]
Which of these rules are well defined?

Select all that apply

$[a] + [b] = [a + b]$ on congruence classes modulo $n$

Correct

$[(a, b)] \mapsto [(a^{2}, b^{2})]$ on $ℚ$

Correct

The congruence class of $a$ modulo $6$ sent to the class of $a$ modulo $3$

Correct

$[(a, b)] \mapsto a$ from $ℚ$ to $ℤ$

The answer is: $[a] + [b] = [a + b]$ on congruence classes modulo $n$ , $[(a, b)] \mapsto [(a^{2}, b^{2})]$ on $ℚ$ , The congruence class of $a$ modulo $6$ sent to the class of $a$ modulo $3$

$[(a, b)] \oplus [(c, d)] = [(a + c, b + d)]$ on $ℚ$

The answer is: $[a] + [b] = [a + b]$ on congruence classes modulo $n$ , $[(a, b)] \mapsto [(a^{2}, b^{2})]$ on $ℚ$ , The congruence class of $a$ modulo $6$ sent to the class of $a$ modulo $3$

The congruence class of $a$ modulo $3$ sent to the class of $a$ modulo $6$

The answer is: $[a] + [b] = [a + b]$ on congruence classes modulo $n$ , $[(a, b)] \mapsto [(a^{2}, b^{2})]$ on $ℚ$ , The congruence class of $a$ modulo $6$ sent to the class of $a$ modulo $3$

10.[2p]
On $ℤ$ , let $a \sim b$ when $a^{2} \equiv b^{2} (mod 7)$ . How many equivalence classes does $\sim$ have?

CorrectNot quite: 4

11.[2p]
How many ordered pairs does the equivalence relation on ${1, 2, 3, 4, 5, 6}$ with classes ${1, 2, 3}$ , ${4, 5}$ and ${6}$ contain?

CorrectNot quite: 14

12.[1p]
The union of two equivalence relations on the same set is always an equivalence relation.

True

The answer is: False

False

Correct

13.[2p]
Given a partition of $A$ , the relation " $a$ and $b$ lie in the same block" is an equivalence relation. Which property of a partition does the proof of transitivity use?

Every element lies in at most one block

Correct

Every block is non-empty

The answer is: Every element lies in at most one block

There are finitely many blocks

The answer is: Every element lies in at most one block

The blocks can be listed in order

The answer is: Every element lies in at most one block

14.[2p]
For $f : A \to B$ , the kernel relates $a$ to $a'$ when $f (a) = f (a')$ . What are its equivalence classes?

The non-empty fibres $f^{- 1} (b)$ , for $b$ in the range of $f$

Correct

The one-element subsets of $A$

The answer is: The non-empty fibres $f^{- 1} (b)$ , for $b$ in the range of $f$

The images $f ({a})$ , for $a \in A$

The answer is: The non-empty fibres $f^{- 1} (b)$ , for $b$ in the range of $f$

All the fibres $f^{- 1} (b)$ , for $b \in B$ , including empty ones

The answer is: The non-empty fibres $f^{- 1} (b)$ , for $b$ in the range of $f$

1.[3p] Which of these relations on ℤ are equivalence relations?

2.[2p] Match each relation on ℝ to the property it lacks.

3.[2p] What is wrong with the argument "if a∼b then b∼a by symmetry, so a∼a by transitivity, hence every symmetric and transitive relation is reflexive"?

4.[1p] How many relations are there on a set with 3 elements?

5.[2p] How many equivalence relations are there on the set {1,2,3,4}?

6.[1p] Which set is the congruence class [2] modulo 3?

7.[2p] Put the lines of the proof that the relation (a,b)∼(c,d) when ad=bc, on pairs with nonzero second coordinate, is transitive in order.

8.[2p] In building ℚ from pairs (a,b) with (a,b)∼(c,d) when ad=bc, why must the pair (0,0) be excluded?

9.[3p] Which of these rules are well defined?

10.[2p] On ℤ, let a∼b when a2≡b2(mod7). How many equivalence classes does ∼ have?

11.[2p] How many ordered pairs does the equivalence relation on {1,2,3,4,5,6} with classes {1,2,3}, {4,5} and {6} contain?

12.[1p] The union of two equivalence relations on the same set is always an equivalence relation.

13.[2p] Given a partition of A, the relation "a and b lie in the same block" is an equivalence relation. Which property of a partition does the proof of transitivity use?

14.[2p] For f:A→B, the kernel relates a to a′ when f(a)=f(a′). What are its equivalence classes?

1.[3p]
Which of these relations on $ℤ$ are equivalence relations?

2.[2p]
Match each relation on $ℝ$ to the property it lacks.

3.[2p]
What is wrong with the argument "if $a \sim b$ then $b \sim a$ by symmetry, so $a \sim a$ by transitivity, hence every symmetric and transitive relation is reflexive"?

4.[1p]
How many relations are there on a set with $3$ elements?

5.[2p]
How many equivalence relations are there on the set ${1, 2, 3, 4}$ ?

6.[1p]
Which set is the congruence class $[2]$ modulo $3$ ?

7.[2p]
Put the lines of the proof that the relation $(a, b) \sim (c, d)$ when $a d = b c$ , on pairs with nonzero second coordinate, is transitive in order.

8.[2p]
In building $ℚ$ from pairs $(a, b)$ with $(a, b) \sim (c, d)$ when $a d = b c$ , why must the pair $(0, 0)$ be excluded?

9.[3p]
Which of these rules are well defined?

10.[2p]
On $ℤ$ , let $a \sim b$ when $a^{2} \equiv b^{2} (mod 7)$ . How many equivalence classes does $\sim$ have?

11.[2p]
How many ordered pairs does the equivalence relation on ${1, 2, 3, 4, 5, 6}$ with classes ${1, 2, 3}$ , ${4, 5}$ and ${6}$ contain?

12.[1p]
The union of two equivalence relations on the same set is always an equivalence relation.

13.[2p]
Given a partition of $A$ , the relation " $a$ and $b$ lie in the same block" is an equivalence relation. Which property of a partition does the proof of transitivity use?

14.[2p]
For $f : A \to B$ , the kernel relates $a$ to $a'$ when $f (a) = f (a')$ . What are its equivalence classes?