Cryptography Reference
In-Depth Information
Each of the following may be verified for a given function
f
:
S
→
T
.
f
−
1
(
f
(
(a) If
S
1
⊆
S
, then
S
1
⊆
S
1
))
.
, then
f
(
f
−
1
(
(b) If
T
1
⊆
T
T
1
))
⊆
T
1
.
S
→
S
∈
S
(c) The identity map, 1
S
:
, given by 1
S
(
s
)=
s
for all
s
, is a bijection.
(d)
f
is injective if and only if there exists a function
g
:
T
→
S
such that
gf
=1
S
, and
g
is called a
left inverse of
f
.
(e)
f
is surjective if and only if there exists a function
h
:
T
→
S
such that
fh
=1
T
, and
h
is called a
right inverse for
f
.
(f) If
f
has both a left inverse
g
and a right inverse
h
, then
g
=
h
is a unique
map called the
two-sided inverse of
f
.
(g)
f
is bijective if and only if
f
has a two-sided inverse.
Notice that in Definition A.4 a binary operation on
S
is just a function on
S
×
S
.
Definition A.6
(
Set Partitions
)
Let
S
be a set , and let
S =
{
S
1
,
S
2
,...
}
be a set of nonempty subsets of
S
.
Then
S
is called a
partition
of
S
provided both of the following are satisfied.
(a)
S
j
∩
S
k
=
∅
for all
j
=
k
.
(b)
S
=
S
1
∪
S
2
∪···∪
S
j
···
, namely,
s
∈
S
if and only if
s
∈
S
j
for some
j
.
The number of elements in a set is of central importance.
Definition A.7
(
Cardinality
)
If
S
and
T
are sets, and there exists a one-to-one mapping from
S
to
T
, then
the sets are said to have the same
cardinality
. A set
S
is finite if either it is
empty or there is an
n
∈
N
and a bijection
f
:
{
1
,
2
,...,n
} →
S
. The number of
elements in a finite set
S
is sometimes called its
cardinality
,or
order
, denoted
by
. A set is said to be
countably infinite
if there is a bijection between the
set and
|
S
|
is not finite, then the set is said to
be
uncountably infinite
. Two sets are said to be in
one-to-one correspondence
if there exists a bijection between them.
N
. If there is no such bijection and
S
Example A.2
If
n
via
f
(
n
)=2
n
is bijective,
so the cardinality of the even natural numbers is the same as that of the natural
numbers themselves.
∈
N
, then the map
f
:
N
→
2
N
Search WWH ::
Custom Search