midterm 2

Question 1

def of relation

Answer 1

Let A and B be sets. R is a relation from A to B if R is a subset of A x B

Question 2

identity relation

Answer 2

Ia = {(a,a): a∈A

Question 3

domain of the relation R from A to B

Answer 3

Dom(R) = {x∈A: ∃y∈B st xRy}

Question 4

range of the relation R

Answer 4

Rng(R) = {y∈B: ∃x∈A st xRy}

Question 5

inverse relation

Answer 5

{(y,x): (x,y)∈R}

Question 6

The composite of two relations R and S

Answer 6

Let R be a relation from A to B and S be a relation from B to C
S o R = {(a,c): ∃b∈B st (a,b)∈R and (b,c)∈S}

Question 7

(S o R)^-1

Answer 7

R^-1 o S^-1

Question 8

reflexive

Answer 8

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

Question 9

irreflexive

Answer 9

∀x∈A, (x,x)∉R

Question 10

transitive

Answer 10

if (x,y), (y,z)∈R, then (x,z)∈R

Question 11

symmetric

Answer 11

if (x,y)∈R, then (y,x)∈R

Question 12

antisymmetric

Answer 12

if (x,y),(y,x)∈R, then x=y

Question 13

comparability property

Answer 13

either (x,y)∈R or (y,x)∈R

Question 14

equivalence relation

Answer 14

R is reflexive, symmetric, and transitive

Question 15

partial order

Answer 15

R is reflexive, antisymmetric, and transitive

Question 16

strict partial order

Answer 16

R is irreflexive, antisymmetric, and transitive

Question 17

A function from A to B is a relation f from A to B such that…

Answer 17

i) dom(f) =A
ii) if (x,y),(y,z)∈f, then y=z

Question 18

image of y = f(x)

Answer 18

y is the image of f at x

Question 19

pre-image of y = f(x)

Answer 19

x is a pre-image of y

Question 20

two functions are equal iff

Answer 20

i) Dom(f) = Dom(g)
ii) ∀x∈Dom(f), f(x)=g(x)

Question 21

the composite of functions f and g

Answer 21

g o f = {∃y∈B st (x,y)∈f and (y,z)∈g}

Question 22

a function f from A to B is onto or surjective if

Answer 22

∀b∈B ∃a∈A st f(a) = b

Question 23

a function is 1-1 or injective if

Answer 23

if f(x)=f(y), then x=y