Information Technology Reference
In-Depth Information
A binary relation
R
is said to be
reflexive
in a set
A
if
aRa
holds for all
a
∈
A
.
R
is
symmetric
on
A
if for every pair of elements
a
,
b
∈
A
,
aRb
implies that also
bRa
holds.
R
is
transitive
if for every triple of elements
a
A
,if
aRb
and
bRc
hold,
then also
aRc
holds. A binary relation on a set
A
which is reflexive, symmetric, and
transitive is called an
equivalence relation
on
A
.If
,
b
,
c
∈
≡
is an equivalence on
A
,then
for any element
a
∈
A
the
equivalence class
of
a
is the set
[
a
]
≡
defined by:
[
a
]
≡
=
{
b
∈
A
|
b
≡
a
}
;
the
quotient set
A
/≡
of
A
with respect to
≡
is the set of equivalence classes of
A
:
A
/≡
=
{
[
a
]
≡
|
a
∈
A
}.
A binary relation
R
on a set
A
is an
order relation
if it is reflexive, transitive and
antisymmetric
, that is for every
a
A
,
aRb
and
bRa
cannot both hold. An order
relation is
linear
or total on
A
if, for any every
a
=
b
∈
A
either
aRb
or
bRa
holds
(otherwise the ordering is said to be partial). Many important concepts based on
order relations can be defined in general (minimum, maximum, minimal, maximal,
upper bound, lower bound, least upper bound, and greatest lower bound).
The number of sequences over an alphabet of symbols grows exponentially with
their length. For example the number of possible different sequences of length ten,
over an alphabet of twenty symbols is 20
10
, that is more than ten trillions. In fact
in any of the ten positions we can put one of twenty possible symbols. This simple
observation explains why polymers are the natural way for producing an enormous
chemical variety.
An
operation
of
k
arguments over a set
X
is a rule that, when applied to a
k
-
sequence of
arguments
over the set
X
, may yield one element of
X
as a result. If it
does not provide any result, then it is
undefined
on that sequence of arguments.
If we order the elements of a set
X
,say
X
,
b
∈
, then any subset of
X
can be expressed by a sequence of 0s and 1s where, at position
i
of the sequence,
the value 1 occurs in the sequence if the element
x
i
belongs to the subset, otherwise
the value 0 occurs. From this representation it follows that the number of possible
subsets of
X
is 2
n
. Table 5.2 provides a few examples of relations and operations.
=
{
x
1
,
x
2
,...,,
x
n
}
5.1.2
Functions and Variables
A (total) function from a set
A
to a set
B
is an operation, that is, a rule that applies to
all elements in
A
and for each of them produces exactly one result in
B
. The under-
lying idea of the function is that of
imaging
, as a representation device associating
images to given objects. The term “function” goes back to theater representations,
and its etymology is common to Latin words like
fungere
and
fingere
, which roughly
refer to the action of
playing a role
. The standard notation for a function is:
f
:
A
→
B
