Cryptography Reference
In-Depth Information
Appendix A: Mathematical Facts
Several of the topics in this appendix are taken directly from the author's
topics [167]-[170].
A.1 Sets, Relations, and Functions
Definition A.1
(
Sets
)
A
set
is a
well defined
collection of
distinct
objects. The terms
set
,
collection
,
and
aggregate
are synonymous. The
objects
in the set are called
elements
or
members
. We write
x
∈
S
to denote membership of an element
x
in a set
S
,
and if
x
is not in
S
, then we write
x
∈
S
.
Set notation is given by putting elements between two braces. For instance,
the set
consists of the elements 1,2, and 3. In general, we may specify
a set by properties.
{
1
,
2
,
3
}
specifies those integers
that satisfy the property of being bigger than 1 in absolute value. (Recall that
|
For instance,
{
x
∈
Z
:
|
x
|
>
1
}
x
|
=
x
if
x
≥
0 and
|
x
|
=
−
x
if
x<
0.)
Definition A.2
(
Subsets and Equality
)
A set
T
is called a
subset
of a set
S
, denoted
T
⊆
S
, if every element of
T
is
in
S
. On the other hand, if there is an element
t
∈
T
such that
t
∈
S
, then we
write
T
⊆
S
, and say that
T
is
not
a subset of
S
. We say that two sets
S
and
T
are
equal
, denoted
T
=
S
provided that
a
∈
T
if and only if
a
∈
S
, namely,
both
T
⊆
S
, and
S
⊆
T
.If
T
⊆
S
, but
T
=
S
, then we write
T
⊂
S
, and call
T
a
proper
subset of
S
. All sets contain the
empty set
, denoted by
∅
,or
{}
,
consisting of no elements. The set of
all
subsets of a given set
S
is called its
power set
.
Although the set of all subsets of a given set, namely, the power set, is indeed
a set, the set of all sets is not a set. Also, we may get examples of
∅
by defining
sets with vacuous properties.
, since no
natural numbers are less than 1. We can also build sets from existing sets.
For instance,
{
n
∈
N
:
n<
1
}
=
∅
Definition A.3
(
Complement, Intersection and Union
)
The
intersection
of two sets
S
and
T
is the set of all elements common to
both, denoted
S
∩
T
, namely,
S
∩
T
=
{
a
:
a
∈
S
and
a
∈
T
}
.
The
union
of the two sets consists of all elements that are in either
S
or in
T
,
denoted
S
∪
T
, namely,
S
∪
T
=
{
a
:
a
∈
S
or
a
∈
T
}
.
Search WWH ::
Custom Search