Relations

Question 1

What is the cartesian product of A={1,2,3} and B={4,5,6}

Answer 1

AxB = {(a,b)|a in A, b in B}
AxB={(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)}

Question 2

What are the different ways to find R^n? (a path of length n in R from a to g)

Answer 2

1. Draw digraph D_R Find all paths of length n
2. Use matrix multiplication to compute M_{R^n} = M_R * M_R … M_R (repeat matrix n times)

Question 3

for a function f: A -> B
if dom(f) = A, then the function is…

Answer 3

defined everywhere / total

Question 4

For a function f: A -> B if ran(f) = B then the function is…

Answer 4

surjective or onto

Question 5

For a function f: A -> B if for x_1 not equal to x_2 it holds that f(x_1) not equal to f(x_2), then the function is…

Answer 5

Injective or one-to-one

Question 6

If f is total, surjective, and injective then it is called

Answer 6

Bijective (f can also be called a bijection)

Question 7

A relation R on A is reflexive if

Answer 7

for all a there exist (a, a) in R

Question 8

A relation R on A is symmetric if

Answer 8

for all a,g there exist (a,g) in A and (g, a) in R

Question 9

A relation R on A is antisymmetric if

Answer 9

for all a,g there exist (a,g) in A and (g, a) in R but a = g

Question 10

if a matrix representation contains a diagonal of all 1s this means

Answer 10

The relation is reflexive

Question 11

if a matrix represetation is symmetric ((M_R)^T = M_R) this means

Answer 11

A representation is symmetric

Question 12

if for all a,g,c in A there exist (a,g) in R and (g,c) in R there exist (a,c) in R. This means that the relation is

Answer 12

Transitive

Question 13

A relation R on A is an equivalence relation if

Answer 13

it is reflexive, symmetric, and transitive

Question 14

what is a partition

Answer 14

a collection of subsets p1,p2,p3,…,pk
such that
for all i in [k], pi is not equal to Ø
for all i,j in [k], i not equal to j, the the intersection of pi and pj = Ø

Question 15

let A = {1,2,3,4,5,6,7}
p1 = {1,4,7}
p2 = {2,5}
p3 = {3,6}
p4 = {2,3,5,7}
Does this collection of subsets have any partitions?

Answer 15

{p1,p2,p3} is the only partition