Chapter 7: Relations Flashcards
What is a relation?
A connection between two sets. a relation R from s -> T is a subset of S x T
Give examples of relations
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
Give the identity relation on s
{(s, s) in S x S | s in S}
Give the relational composite
R’ = {(s,s’’) in S x S’’ | exists s’ in S. (s,s’) in R and (s’,s’’) in R’}
What operations can be performed on relations
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}
Define a partial function
for every s in S there is at most one t in T with
s mapped to t
What is the domain of definition of a partial function?
{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
Give the composite of two partial functions
(g . f) s = g(fs) if fs and g(fs) are defined
What is a binary relation
A relation from a set to itself: S -> S
What is a directed graph?
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
What is reflexivity? What is the reflexive closure?
A binary relation is reflexive if for all s in S, sRs.
The reflexive closure of a relation A is:
R U Identity_a
What is symmetry? What is the symmetric closure?
A binary relation is symmetric if for all s, s’ in S sRs’ and s’Rs
The symmetric closure is R U Rop
What is anti symmetry?
if aRb and bRa then a=b
What is transitivity? What is the transitive closure?
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’
What is an equivalence relation?
A binary relation that is reflexive, symmetric and transitive
Describe Mod as an equivalence relation
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
How do we find the multiplicative inverse? i.e m^-1 (mod n)
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
How do we calculate a^b (mod n)?
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
What is a partial order?
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
What is the quotient of S with respect to ~?
The set of equivalence classes of set S with respect to relation ~, written S\~
What is a Hasse Diagram?
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
What is a total order?
A partial order <= with the property that for all s, s’ in S
s <= s’ or s] <= s
Define maximal/minimal of a poset (P, <=)
maximal if for all p’ if p <= p’ then p = p’
minimal if for all p’ if p’ <= p then p’ = p
Define greatest and least of a poset (P, <=)
Greatest if for all p’ p’ <= p
Least if for all p’ p <= p’
Define Upper and lower bound of a set S of poset (P, <=)
Upper bound if for all p’ in S, p’ <= p
Lower bound if for all p’ in S, p <= p’
Define p as Least upper and Greatest lower bound of a subset S of the poset (P, <=)
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
