Cryptography Reference
In-Depth Information
If
T
⊆
S
, then the complement of
T
in
S
, denoted
S T
is the set of all those
elements of
S
that are not in
T
, namely,
S T
=
{
s
:
s
∈
S
and
s
∈
T
}
.
Two sets
S
and
T
are called
disjoint
if
S
∩
T
=
∅
.
For instance, if
S
=
{
1
,
2
,
3
,
4
}
, and
T
=
{
2
,
3
,
5
}
, then
S
∩
T
=
{
2
,
3
}
, and
S
∪
T
=
{
1
,
2
,
3
,
4
,
5
}
. Also,
S
{
2
,
3
}
=
{
1
,
4
}
.
Definition A.4
(
Binary Relations and Operations
)
Let
a,b
be elements of a set
. Then we call
(
a,b
)
an
ordered pair
, where
a
is called the
first component
, and
b
is called the
second component
.If
S
T
is
another set, then the
Cartesian product
of
S
with
T
, denoted
S
×
T
is given by
S
×
T
=
{
(
s,t
):
s
∈
S
,t
∈
T
}
.
A
relation
between
S
and
T
is a subset of
S
×
T
.A
binary relation
on
S
is a
subset
R
of
S
×
S
.Fo
(
a,b
)
∈
R
, we write
aRb
.A
binary operation
on
S
is a
rule that assigns each element of
S
×
S
to a unique element of
S
(
see Definition
A.5 below
)
.
Example A.1
If
S
=
{
✜
,
✦
,
✪
,
}
, then
R
=
{
(
✜
,
✜
), (
✪
,
✜
), (
,
✪
)
}
is a binary relation on
, and so is
R
1
=
S
{
(
✜
,
✜
), (
✜
,
✦
), (
,
)
}
.
does not have a unique second element. There are certain
distinguished binary operations that do satisfy the property of uniqueness in this
regard.
In Example A.1,
✜
Definition A.5
(
Functions
)
A
function
f
(
also called a
mapping
or
map)
from a set
S
to a set
T
is a
relation on
S
×
T
, denoted by
f
:
S
→
T
, which assigns each
S
∈
S
a unique
t
∈
T
, called the
image of
s
under
f
, denoted by
f
(
s
)=
t
. The set
S
is called
the
domain
of
f
and
T
is called the
range
of
f
.If
S
1
⊆
S
, then the
image of
S
1
under
f
, denoted by
f
(
S
1
)
, is the set
{
t
∈
T
:
t
=
f
(
s
)
for some
s
∈
S
1
}
.If
S
=
S
1
, then
f
(
S
)
is called the
image of
f
, denoted by
img(
S
)
.If
T
1
⊆
T
, the
T
1
under
f
, denoted by
f
−
1
(
inverse image of
T
1
)
, is the set
{
s
∈
S
:
f
(
s
)
∈
T
1
}
.
A function
f
:
S
→
T
is called
injective (
also called
one-to-one)
if and only
if for each
s
1
,s
2
∈
S
,
f
(
s
1
)=
f
(
s
2
)
implies that
s
1
=
s
2
. A function
f
is
surjective (
also called
onto)
if
f
(
S
)=
T
, namely, if for each
t
∈
T
,
t
=
f
(
s
)
for some
s
. A function
f
is called
bijective (
or a
bijection)
if it is both
injective and surjective. Two sets are said to be in a
one-to-one correspondence
if there exists a bijection between them. A
composition
of functions
f
and
g
is
denoted by
f
∈
S
◦
g
, meaning the function defined by
f
◦
g
(
s
)=
f
(
g
(
s
))
.
Search WWH ::
Custom Search