Relations

Question 1

What is an ordered n-tuple?

Answer 1

The ordered collection that has a₁ as its first element, a₂ as its second element, and aₙ as its last element

Question 2

What are ordered pairs?

Answer 2

2-tuples

Question 3

How do you find the cartesian product of A x B x C?

Answer 3

List all the possible combinations where the first element is from set A, the second is from set B, and the 3rd element is from set C. The whole answer is in {} and each tuple is in ().

Question 4

What is the binary relation R from set A to set B?

Answer 4

R ⊆ A×B

Question 5

What does aRb denote?

Answer 5

(a,b)∈R

Question 6

What does a ̸Rb denote?

Answer 6

(a,b)∉R

Question 7

What does it mean if (a,b) belongs to R?

Answer 7

a is related to b by R

Question 8

Let A = {0,1,2} and B = {a,b}. What is a relation from A to B?

Answer 8

{(0,a), (0,b), (1,a), (2,b)}

Question 9

Let R1 = {(1,1), (2,2), (3,3)} and R2 = {(1,1), (1,2), (1,3), (1,4)}. What is R1-R2?

Answer 9

{(2,2), (3,3)}

Question 10

Let R1 = {(1,1), (2,2), (3,3)} and R2 = {(1,1), (1,2), (1,3), (1,4)}. What is R2-R1?

Answer 10

{(1,2), (1,3), (1,4)}

Question 11

Let R1 = {(1,1), (2,2), (3,3)} and R2 = {(1,1), (1,2), (1,3), (1,4)}. What is R1∩R2?

Answer 11

{(1,1)}

Question 12

Let R1 = {(1,1), (2,2), (3,3)} and R2 = {(1,1), (1,2), (1,3), (1,4)}. What is R1 ∪ R2?

Answer 12

{(1,1), (1,2), (1,3), (1,4), (2,2), (3,3)}

Question 13

How do you define the composition of R1 and R2 where R2 ⊆ B×C and R1⊆ A×B?

Answer 13

R2 ◦ R1 ⊆ A×C = {(a, c) | ∃b ∈ B. (a,b) ∈ R1 ∧(b,c) ∈ R2}

Question 14

What does it mean if a relation is reflexive?

Answer 14

A relation R on set A is reflexive iff (a,a) ∈ R for every element a ∈ A

Question 15

What is the notation for a reflexive relation?

Answer 15

∀x. (x ∈ A→(x,x) ∈ R)

Question 16

What does it mean if a relation is symmetric?

Answer 16

A relation R on set A is symmetric iff (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A

Question 17

What is the notation for a symmetric relation?

Answer 17

∀x.∀y. ((x,y) ∈ R→(y,x) ∈ R)

Question 18

What does it mean if a relation is antisymmetric?

Answer 18

If (a,b) ∈ R and (b,a) ∈ R, then a=b

Question 19

What is the notation for an antisymmetric relation?

Answer 19

∀x, y. ((x,y) ∈ R ∧ (y,x) ∈ R→x=y)

Question 20

What does it mean if a relation is transitive?

Answer 20

If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R for all a,b,c ∈ A

Question 21

What is the notation for a transitive relation?

Answer 21

∀x, y, z. ((x,y) ∈ R ∧ (y,z) ∈ R→(x,z) ∈ R)

Question 22

What does it mean if you need to find the closure of a relation R?

Answer 22

Find all the ordered pairs that need to be added to the relation in order to satisfy the required property (reflexive, symmetric, or transitive)

Question 23

What is an equivalence relation?

Answer 23

A relation on set A is called an equivalence relation if it is reflexive, symmetric, and transitive

Question 24

What does a∼b denote?

Answer 24

a and b are equivalent

Question 25

What is an equivalence class?

Answer 25

Let R be an equivalence relation on set A. The set of all elements that are related to an element a of A is called the equivalence class of a.

Question 26

How do you denote the equivalence class of a with respect to R?

Answer 26

[a] little R={s |(a,s)∈R}

Question 27

What is a representative of the equivalence class [a] little R?

Answer 27

If b ∈ [a] little R (if b is included in the equivalence class of a)

Question 28

What is ["ab"] little R? (equivalence classes)

Answer 28

{...,“ab”,“ba”,“ac”,...}

Question 29

What is a partition of a set S?

Answer 29

A collection of disjoint nonempty subsets of S that have S as their union.

Question 30

What is a partial ordering (or partial order)?

Answer 30

A relation R on set S is called a partial ordering if it is reflexive, antisymmetric, and transitive

Question 31

What is a Hasse diagram?

Answer 31

A visual representation of a partial ordering that leaves out edges that must be present because of the reflexive and transitive properties

Question 32

Can you have loops from one element back to the same element again in a Hasse diagram?

Answer 32

No, all loops (a,a) must be removed