Chapter 7: Relations

Question 1

What is a relation?

Answer 1

A connection between two sets. a relation R from s -> T is a subset of S x T

Question 2

Give examples of relations

Answer 2

Two column table in a relational database- binary relation
database set of n-ary relations
The graph of a function
A function with exactly one t with (s, t) in R

Question 3

Give the identity relation on s

Answer 3

{(s, s) in S x S | s in S}

Question 4

Give the relational composite

Answer 4

R’ = {(s,s’’) in S x S’’ | exists s’ in S. (s,s’) in R and (s’,s’’) in R’}

Question 5

What operations can be performed on relations

Answer 5

Union: R U S = {(a,b) in A x B | (a,b) in R or S}
Intersection: R and S = {(a,b) in A x B | (a,b) in R and S}
Complement: Rc = {(a,b) in A x B | (a,b) not in R}
Opposite/inverse Rop = {(a,b) in A x B | (b,a) in R}

Question 6

Define a partial function

Answer 6

for every s in S there is at most one t in T with

s mapped to t

Question 7

What is the domain of definition of a partial function?

Answer 7

{s in S | fs is defined}.

There is a unique total function g: dom f to T for which all s in dom f are defined as gs = fs

Question 8

Give the composite of two partial functions

Answer 8

(g . f) s = g(fs) if fs and g(fs) are defined

Question 9

What is a binary relation

Answer 9

A relation from a set to itself: S -> S

Question 10

What is a directed graph?

Answer 10

A directed graph on a set is given by a binary relation on S. elements of S are nodes and the pairs in the relation the edges

Question 11

What is reflexivity? What is the reflexive closure?

Answer 11

A binary relation is reflexive if for all s in S, sRs.

The reflexive closure of a relation A is:
R U Identity_a

Question 12

What is symmetry? What is the symmetric closure?

Answer 12

A binary relation is symmetric if for all s, s’ in S sRs’ and s’Rs

The symmetric closure is R U Rop

Question 13

What is anti symmetry?

Answer 13

if aRb and bRa then a=b

Question 14

What is transitivity? What is the transitive closure?

Answer 14

A binary relation is transitive if for s, s’, s’’ in S
sRs’ and s’Rs’’ implies sRs’’

If there is a path from s to s’ then there is an edge from s to s’

Question 15

What is an equivalence relation?

Answer 15

A binary relation that is reflexive, symmetric and transitive

Question 16

Describe Mod as an equivalence relation

Answer 16

Mod 3 gives us 3 equivalence classes {0,1,2}
We can calculate with these classes by adding or multiplying.
Hence for every number n we may calculate with equivalence classes modulo n

Question 17

How do we find the multiplicative inverse? i.e m^-1 (mod n)

Answer 17

Find a number such that m x l = 1 (mod n)
i.e. m x l = i x n + 1
Do this using Euclid’s Algorithm

Question 18

How do we calculate a^b (mod n)?

Answer 18

alg 1: calculate a^b then calculate remainder when dividing by n
alg 2: keep multiplying by base and calculating the remainder when dividing by n at each step
alg 3: bring down the number of multiplications is brought down using the squaring operation

Question 19

What is a partial order?

Answer 19

A partial order on a set S is a binary relation which is reflexive, anti symmetric and transitive.
A set together with a partially order is a poset

Question 20

What is the quotient of S with respect to ~?

Answer 20

The set of equivalence classes of set S with respect to relation ~, written S\~

Question 21

What is a Hasse Diagram?

Answer 21

We draw partial orders as an undirected graph that is oriented on the page. An element is <= another if it sits lower on the page. We don’t draw transitive connections

Question 22

What is a total order?

Answer 22

A partial order <= with the property that for all s, s’ in S
s <= s’ or s] <= s

Question 23

Define maximal/minimal of a poset (P, <=)

Answer 23

maximal if for all p’ if p <= p’ then p = p’

minimal if for all p’ if p’ <= p then p’ = p

Question 24

Define greatest and least of a poset (P, <=)

Answer 24

Greatest if for all p’ p’ <= p

Least if for all p’ p <= p’

Question 25

Define Upper and lower bound of a set S of poset (P, <=)

Answer 25

Upper bound if for all p’ in S, p’ <= p

Lower bound if for all p’ in S, p <= p’

Question 26

Define p as Least upper and Greatest lower bound of a subset S of the poset (P, <=)

Answer 26

Least Upper Bound (supremum) if an upperbound for S and if p’ is an upperbound for S then p <= p’

Greatest lower bound (infimum) if a lower bound and if p’ is a lower bound for s then p’ <= p