CS 8113g Spring 1995
Specification and analysis of interactive systems
CS 8113g Spring 1995
Lecture 2: Binary Relations and Functions
Date: April 4, 1995
Scribe: William R. Jones
Binary
Relations
A binary relation is a set of ordered pairs mapping one set, the domain, onto
another, the range. A general relation is marked by the operator <-->,
and is written as X<-->Y, where X is the set in which is contained the
domain, and Y contains the range.
There are many different types of relations, each with its own arrow operator.
In general, they are written as _f_, where f is the operator. Since a relation
is an ordered pair, the following are all equivalent:
afb
(a,b) is-element-of f
a<-->b is-element-of f
for all a in the domain and b in the range.
Source/Target,
Domain/Range
The format of a relation is X<-->Y, but what are X and Y? Sets,
obviously, but we can carry it a bit further. In particular, we call X the
source type of the relation, and Y the target type. However, every member of
the source type need not be in a pair making up the relation R. Those elements
that are make up a set called the domain of the relation, and is identified by
the notation dom R. Similarly, members of the target type that contribute to
pairs in the relation make up the range set, ran R
A
rogues gallery of relations
Several relations were introduced. Some of them are difficult to represent in
ASCII, but we'll give it a go.
Inverse
Given a relation R = X<-->Y, The inverse relation R~ is a relation
Y<-->X such that for every (x,y) pair in R, there is a corresponding
(y,x) pair in R~.
Domain
Restriction
Given a relation R = X<-->Y, the domain restriction A<|R is one where
for every ordered pair (x,y) in R, the pair is also in the domain restriction
if x is also an element of A.
Range
Restriction
Given a relation R = X<-->Y, the domain restriction R|>B is one where
for every ordered pair (x,y) in R, the pair is also in the range restriction if
y is also an element of B.
Domain
Anti-Restriction
It may sound like the family dominatrix, but given a relation R =
X<-->Y, the domain restriction of R over A is one where for every ordered
pair (x,y) in R, the pair is also in the domain restriction if x is NOT an
element of A. The notation for Domain Anti-Restriction is a a left-pointing
triangle with the a line through it. The restricting set A is on the left side,
the relation R on the right.
Range
Anti-Restriction
Given a relation R = X<-->Y, the range restriction of R over B is one
where for every ordered pair (x,y) in R, the pair is also in the range
restriction if y is NOT an element of B. The notation for Range
Anti-Restriction is a a right-pointing triangle with the a line through it. The
relation R is on the left side, the restricting set B on the right.
Relational
Image
Given a relation R = X<-->Y, the relational image of R over A, R(|A|),
is one where for every ordered pair (x,y) in R, and A is a set of elements of
type X, if x is an element of A, y is a an element of the image.
Relational
Composition
Given two relations, one R = X<-->Y and the other S = Y<-->Z
(where both Y are the same set), the relational composition of R and S, denoted
by R;S, is the relation X<-->Z where the domain of S intersects with the
range of R. In other words, given x<-->y in R, if y is in the domain of
S, then composing x<-->y with its corresponding y<-->z produces a
member of R;S, namely x<-->z.
A
few more properties
We didn't cover these much in class, but since they are obviously important,
I'll include them here.
Homogenous
v. Heterogenous Relations
A relation R= X<-->Y is said to be homogeneous if X and Y are the same
set, i.e. the relation's domain and range are the same.
When the range and domain are different sets, R is heterogeneous.
Equivalence
Relations
There are three properties a homogeneous relation R= X<-->X must satisfy
to be an equivalence relation.
First it must be reflexive. This means that for all x in X, x relates to
itself, i.e. xRx.
Second, it must be symmetric. For all x and y in X, if x<-->y, then
y<-->x.
Third, it must be transitive. This means that for all x,y,z in X, if
x<-->y and y<-->z, then x <-->z.
Transitive
Closure
There are two Relations mentioned here, concerning transitive closure for the
relation R..
The transitive closure R+ is the smallest transitive relation containing R.
This means that if R includes aRb and bRc, then R+ includes these as well as
(aRb)Rc = aRc.
The reflexive tansitive closure R* is the smallest relation Q such that Q is
reflexive and transitive, and R is contained in Q. Typically, this means the
transitve closure R+ unioned with xRx for all x in the domain.
Functions
A funcion is a relation with one to one mapping from the domain to the range.
In other words, for every x in the domain, there is one and only one element in
the range that x is related to.
Note that this does not work both ways. If y is in the range, there may be more
than one x in the domain that maps to it.
Partial
Functions
All functions are at least partial, as its sole requirement is that in map one
to one between the domain and the range. A partial function is denoted by
-|->, an arrow with a head on the right and a flat end on the left.
Total
Functions
A total function is one in which every member of the source type is in the
domain of the function. A total function is denoted by an arrow with a head on
the right, -->.
Some
function properties and operations
There are a few things and terms to use when dealing with functions
Overriding
A function g can override another function f. This relation f OVER g acts as g
wherever the domain of f OVER g is in the domain of f, and acts as f otherwise.
It is denoted by a circle with a cross inscribed in it.
Overriding has several properties, including an identity property on both sides
of the relation ( f OVER {} = {} OVER f = f), associativity (f OVER (g OVER h)
(f OVER g) OVER h), and the obvious (and proved in class) that a function
overriding itself produces the same function (f OVER f = f).
Injections
A partial injection is a partial function that maps every element of the domain
to a different element in the range. A total injection is a partial injection
which is also a total function. An interesting consequence is that a function
that is invertable is an injection.
An injection is denoted by adding a right pointing arowhead to the left side of
the proper function symbol (partial or total)
Subjections
A subjection is a function whose range encompasses the whole of the target
type. A function may be a partial subjection or a total subjection. Its symbol
is constructed by adding a second arrowhead on the right side, just behind the
one that is already there, i.e. -|->> or -->>.
Bijections
A bijection is a function that is both an injevtion or a subjection. The symbol
for a bijection is the same as that for a subjection, except the second
arrowhead is smaller.