Cryptography Reference
In-Depth Information
B
,welet
f
−
1
(
J
) denote the set of all
x
such that
f
(
x
)
all
f
(
x
) for
x
J
.
To denote the set of all images by
f
of elements that satisfy the predicate we write
{
∈
I
.If
J
⊆
∈
f
(
x
);
x
∈
A
,
P
(
x
)
}
or
f
(
{
x
∈
A
;
P
(
x
)
}
).
A function can also be considered as a
family
, but for this we use sequence-like
notations. A family (
x
i
)
i
∈
I
is essentially a function from
I
to another set which maps
i
into an element
x
i
. The set
I
is called the
index
set of the family. As an example a
sequence
is a family whose index set is the set of all integers (which may start from zero
or one). A
pair
can be viewed as a family of index set
{
1
,
2
}
. In this case we just denote
(
x
1
,
x
3
) for a
triplet
(
x
i
)
i
∈{
1
,
2
,
3
}
.
Given two sets
A
and
B
we define the
Cartesian product A
x
2
) instead of (
x
i
)
i
∈{
1
,
2
}
. Similarly we write (
x
1
,
x
2
,
×
B
as the set of all pairs
(
x
C
of all triplets
consisting of elements in
A
,
B
, and
C
respectively. For simplicity we consider
,
y
) for which
x
∈
A
and
y
∈
B
. We similarly define the set
A
×
B
×
×
to be
associative in the sense that we do not make any difference between (
A
×
B
)
×
C
and
A
×
(
B
×
C
). (Formally we would consider (
A
×
B
)
×
C
as the set of all pairs whose
first component is a pair belonging to
A
×
B
and the second one is an element of
C
.)
Given a family (
A
i
)
i
∈
I
of sets we can define the intersection
A
i
i
∈
I
and the union
A
i
i
∈
I
of all
A
i
. We also define the Cartesian product
A
i
i
∈
I
as the set of all families (
x
i
)
i
∈
I
for which
x
i
∈
I
. When all
A
i
are equal
to a single set
A
we write this product
A
I
. We also write
A
2
instead of
A
{
1
,
2
}
, and more
generally
A
n
instead of
A
{
1
,...,
n
}
.
A
i
for all
i
∈
A
binary relation R
between elements of a set
A
and elements of a set
B
is formally
a subset of
A
y
) is in this subset, we say that
x
and
y
are related by
R
and
denote this by
xRy
. When
A
×
B
.If(
x
,
=
B
, we say that
R
is
reflexive
if
xRx
for all
x
∈
A
.We
say that it is
symmetric
if
xRy
is equivalent to
yRx
for all
x
,
y
∈
A
. We say that it is
transitive
if
xRy
and
yRz
imply
xRz
for any
x
A
.
R
is an
equivalence relation
if it is reflexive, symmetric, and transitive. In this case, denoting Cl(
x
)
,
y
,
z
∈
={
y
∈
A
;
xRy
}
as for the “class of
x
,” we have
Cl(
x
)
=
Cl(
y
)
⇐⇒
Cl(
x
)
∩
Cl(
y
)
=∅⇐⇒
xRy
for all
x
Cl(
x
) we notice that all Cl(
x
) build a
partition
of
A
, i.e. a
collection of subsets Cl(
x
) of empty pairwise intersections whose union covers all of
,
y
∈
A
. Since
x
∈
Search WWH ::
Custom Search