Information Technology Reference
In-Depth Information
of two elements is an unordered pair. There are many ways for introducing an or-
der between the elements
a
,
b
of an unordered pair. A standard way to do it is by
means of the set
{
a
,{
a
,
b
}}
, which is usually denoted by
(
a
,
b
)
. A triple
(
a
,
b
,
c
)
can
((
,
)
,
)
be identified by
, that is, an ordered pair where the first element is a pair
too. In this way, any sequence of finite length can be obtained by iterating the set
construction of (ordered) pairing.
Table 5.1 collects the standard set-theoretic concepts (sometimes set difference
is also denoted by
a
b
c
/
).
Ta b l e 5 . 1
Fundamental set-theoretic notation
∈
Membership
a
∈
B
a
is an element of
A
(
a
belongs to
A
)
⊆
Inclusion
A
⊆
B
All the elements of set
A
belong to set
B
/0Em ty t
0
⊆
A
0 is included in any set
A
∪
Union
A
∪
B
The set of elements belonging to
A
or
B
∩
Intersection
A
∩
B
The set of elements belonging to both sets
A
,
B
−
Difference
A
−
B
The set of elements of
A
which do not belong to
B
×
Cartesian product
A
×
B
The set of pairs
(
a
,
b
)
with
a
∈
A
,
b
∈
B
k
A
k
()
k-power
The set of all
k
-sequences over
A
P
P(
A
)
Powerset
The set of all the subsets of
A
N
Naturals
{
0
,
1
,
2
...}
The set of null and positive integers
Z
Integers
{
0
,
1
,
2
.−
1
,−
2
...}
The set of integers
Q
Rationals
{
0
,
1
/
2
,
2
/
3
.−
1
/
2
,−
2
/
3
...}
The set of rationals
,
√
2
R
Reals
{
0
,
1
,
1
/
2
,...}
The set of reals
√
CR
×
i
R
i
R =
{
ix
|
x
∈
R
}
(The imaginary unit
i
=
−
1)
5.1.1
Relations and Operations
The notion of sequence is connected with the mathematical concept of
relation
.For
k
,a
k
-sequence is a sequence of
k
elements. A
k
-relation (or a relation of
k
arguments) over a set
X
is a condition which either holds or does not hold for any
given
k
-sequence of elements in
X
.
Given two sets
A
∈
N
,
B
,thesetofpairs
(
x
,
y
)
,where
x
∈
A
and
y
∈
B
,isthe
carte-
sian product
of the two sets, denoted by
A
B
is also called a
correspondence
between the sets
A
and
B
.Thesetofall
k
-sequences over a set
A
is denoted by
A
k
. Therefore, mathematically a
k
-relation
R
over
A
is a subset of
A
k
,
in symbols,
R
×
B
. A subset of
A
×
A
k
. For example, the relation
⊆
≤
on natural numbers is identified by
the set of pairs:
{
(
,
+
)
|
,
∈
N
}.
x
x
y
x
y
Binary relations
are an important type of relations. They are usually indicated by
a symbol put between the two objects which are related. For example, the equality
symbol
=
expresses a binary relation between expressions such that
E
1
=
E
2
holds
when
E
1
and
E
2
denote the same object. The order symbol
, when put between
two numbers, expresses a relation which holds if the number on its left is less than
or equal to the number on its right. Very often, when a binary relation does not hold
its symbol is barred, for example,
a
≤
<
b
means that
a
<
b
does not hold.