Transcript Relations/Functions Overview

 Let A and B be any sets
• A binary relation R from A to B is a subset of AxB
• Given an ordered pair (x, y), x is related to y by R iff
(x, y) is in R.
• This is denoted
• If x is not related to y by R, we say
 The
term “binary” means that the relation is
defined for two elements. Other types of
relations, called n-ary relations, also exist. If
you want, look them up. They’re very useful
in CS
 Consider
sets A={0,1,2} and B={1,2,3}.
AxB is the set of all possible ordered
pairs from A and B
• If element x from A is related to element y from
B, we say xRy, “x is related to y”
 If x<y, which elements in AxB are in set R?
 Answer: {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}
 Which elements are not in R?
 Answer: {(1,1), (2,1), (2,2)}
 For
any (x, y) in the real number plane
(RxR), (x, y) are in relation C iff “x2 + y2
= 1”
• This is the equation for a circle
• This relation has infinitely many solutions
because it is a subset of the cross product of two
infinitely large sets (two sets of all real numbers)
• To check the relation, test some x and y values
 (0,0) => 02 + 02 = 0 ≠ 1
 (1,0) => 12 + 02 = 1
 (2, 0) => 22 + 02 = 4 ≠ 1

Given set A and relation S:
• S is reflexive iff for all x in A, (x, x) is in S
 Informal: Each element is related to itself
• S is symmetric iff for all x and y in A, if (x, y) is in S, then (y,
x) is in S
 Informal: If any one element is related to any other element,
then the second element is related to the first
• S is transitive iff for all x, y, and z in A, if (x, y) and (y, z) are
in S, then (x, z) is in S
 Informal: If any one element is related to a second, and that
second is related to a third, then the first is related to the third

These definitions are each universal statements
• These properties can be proven true by proving that
every element x, y, and z must satisfy the property
• Prove them false by finding a counter example



S = {(0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0), (3,3)}
T ={(0,1), (2,3)}
W = {(0,0), (0,2), (0,3), (2,3)}
• Which properties do S, T, and W satisfy?
 S is reflexive: Each element is related to itself – (0,0)…
 S is symmetric: For every ordered pair in S, there is also a reverse pair – The
reverse of (x, x) is (x, x)!!
 S is not transitive: There is point (1,0) and point (0,3) but there is no point (1,3) –
(x, y), (y, z), but not (x, z)
 T is not reflexive: Not every point (x, x) is in T
 T is not symmetric: Not every point (x, y) has a corresponding (y, x) point
 T is transitive: It is not obvious why. Notice that there are no points (x ,y) and (y,
z) in T, so there is never an opportunity for transitivity to be false. We say that T
is vacuously transitive, meaning the property is true by default
 W is not reflexive: 1 is between 0 and 2, so is in set A on which W is a
relation. The point (1,1), among other points like (2,2), is not in W
 W is not symmetric: There is a (0,2) but not a (2,0)
 W is transitive: There is a (0,2), (2,3) and a (0,3) – these are the only points of the
form (x, y), (y, z), (x, z). There are no other (x, y), (y, z) points. It must be transitive

These properties extend readily to infinite relations like
y=x
 We
have a relation H that is not transitive,
but we want it to be transitive
• The transitive closure of H, denoted Ht, is the set
that contains H but also contains all the points
necessary to make Ht a transitive relation
• Ht satisfies the following properties
 Ht is transitive
 H is a subset of or is equal to Ht
 If S is any other transitive relation that contains H, then
it also contains Ht
A
= {0,1,2,3} and R = {(0,1), (1,2), (2,3)}
 What is the transitive closure of R?
• Every ordered pair in R is in Rt
• Every grouping of points (x, y) and (y, z) must
yield an (x, z) point
 (0,1) + (1,2) → (0,2)
 (1,2) + (2,3) → (1,3)
 Since (0,2) is now in Rt, (0,2) + (2,3) → (0,3)
• Rt = {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}
 Consider
the function F from a set A to a
set B that satisfies the following two
properties
• For every element x in A there is an element y in
B such that (x, y) is in F.
• For all elements x in A and y, z in B
 If (x, y) is in F and (x, z) is in F, then y = z
• If F is a function from A to B, we say
y = F(x) iff (x, y) is in F
 Sets
A = {2,4,6} and B = {1,3,5} are
connected by two relations R = {(2,5), (4,1),
(4,3), (6,5)} and S = “for all (x, y) in AxB, (x,
y) is in S iff
y = x + 1”
• Relation R is not a function because the x value 4
yields to separate y values 1 and 3
 In a function, according to property 2, an x value (input)
can yield only one unique y value (output)
• Relation S is not a function because there is no
element y in B such that y = 6 + 1 = 7
 Property 1 states that every element in A must yield an
element in B
 If
a function is defined from set X to set Y, we
say that the first set, X, is the domain of the
function and the second set, Y, is the range
• When you think of a function in terms of a machine,
you can visualize the domain as the set of possible
inputs and the range as the set of possible outputs
• If X is the set of all real numbers, there is no
guarantee that Y will also contain all real numbers, as
is demonstrated with the function y = x2
• The process of using a function to transform its
domain into range values is known as mapping and
consists of feeding in the inputs and recording the
outputs
 You will do a lot of relational mapping in computer science

For a function to be injective, or one-to-one, every
element in its domain must yield a unique value
• If F(x) = F(x[2]), then x = x[2]
 F(2) can’t equal F(3). An example is the function F(x)=x, because F(x[2])
can only equal x[2], so if x[2] ≠ x, F(x[2]) won’t equal F(x)

For a function to be surjective, or onto, every element in
the function’s domain must be matched with an
element from its range
• A = {1,2,3}, B = {a,b,c,d}
 F(A) = {a,b,c}
 This function is not surjective because 1 yields a, 2 yields b, 3 yields c,
but nothing yields d, which is in the range of F(x) because it is defined
over the sets A and B
• Formally, this is described as: Given sets X and Y, F(X) is onto Y iff
for every element y in Y, there exists an element x in X such that
F(x) = y

Is y= F(x) = x2 for all real numbers x
injective/surjective?
• F(x) is not injective
 (-2)2 = 22 = 4, therefore F(-2) = F(2) but -2 ≠ 2.
• F(x) is not surjective if Y (the range) is defined as all real
numbers
 The reason is straightforward: We have y = x2. However, there
is no negative real number y such that x2 = y. EX: (-1/2)2 = 1/4.
All squared real numbers are positive, so none of the negative
real values of y are matched with F(x) values

Y = G(x) = x3 is both injective and surjective
• This is true because every real number raised to the third
power has a unique value. G(-x) ≠ G(x), and it can be
easily shown that every real value of y can be yielded
from a particular value of x
For a function to be defined over the real
numbers, it must be true that for every
real value of x, there is a real value y as
the output
 Also, if a relation is graphed on a RxR
plane, it cannot be a function if a vertical
line can be drawn through the graph and
intersect two points
 Both of these properties stem from
properties 1 and 2

• Notice that a circle is not a real-number function
because it does not satisfy either property
• The second relation, however, is a real number
function because it will continue to infinity in
both directions without folding back into itself

An inverse function is a function that “undoes” another function
by mapping the range of a function back onto its domain
• In order for F(x) to have a single, all-encompassing inverse function
F-1(y), F(x) must be both injective and surjective
• An inverse function is defined as follows:
F-1(y) = x  y = F(x)
• If every range value, y, is produced by the function F(x), and no two
domain values, x, yield the same y value, then F-1(y) will yield every x
value and no two y values will yield the same x value
• Most functions do not have a single, perfect inverse function. In these
cases, the inverse relation is actually a system of inverse functions, each
defined over a set domain and range
 To obtain this set algebraically, swap the locations of all domain and range values
and solve for the range values
 EX: y = x2 → x = y2 → ±(x1/2) = y.
 Notice the ±. This means that the inverse of y = x2 is actually a system of two
functions, one having all positive and another having all negative values
 As you would expect, these systems tend to be more complicated, and are a
subject of higher mathematics
 If
S is a relation from A to B, then its
inverse S-1 is defined as follows
• S-1 = {(y, x) in BxA such that (x, y) is in S}
• In other words, (y, x) is in S-1 iff (x, y) is in
S
 To obtain an inverse relation, switch the x
and y values for all of the ordered pairs
• To take the inverse of a real number
graph, rotate the graph 90 degrees
clockwise
 Use the horizontal line test to determine
whether a graph’s inverse is a function
Both relations are
functions, but only
relation 2 has a
single
inverse function.
To see this, you can
perform the
horizontal line test

Now we get to some practical applications
• A hashing function is one which takes a variety of inputs
(strings, large integers, binary data) and transforms those
inputs into a distinct numerical output
 Such functions are used to establish methods for sorting
items, encrypting data, and improving the efficiency of
storing data
 Say you need a quick way to sort a data base of students
based on social security numbers
 These numbers are very large, so it would be impractical to sort data
based on the numbers alone
 Instead, we will use the hashing function H(n) = n mod 7, where mod is
the modulo division operator defined by “n mod m = n-m*(n div m)”.
Div is an operator which returns the integer component of division
 This function yields a manageable way to sort data. However,
sometimes the function will return the same value for different n
values. This is known as a collision, and must be resolved using an
algorithm
A
checksum function is a special class of
hash functions that is designed to avoid and
correct collision errors
• Essentially, you use a bit of programming magic to
ensure that the hash is sustainably implemented
• As a conceptual example, consider the social
security hash on the previous slide
 If all of the numbers you entered into the system yielded
the same hash value (yes this is possible), then the sort
would be totally ineffective
 To ensure redundancy, you would have to add other
parameters to the sort, like last names, birthdays, or
student IDs