Cryptography Reference
In-Depth Information
We next show that D is maximal with respect to A. Let a ∈ D and some
b ∈ A with a ≤ b. We will show that b ∈ D. First observe that b ∈ M
1
due
to the maximality of M
1
. On the other hand, if it is the case that b ∈ M
2
we
would have that a ∈ M
2
due to the fact that M
2
is lower, a contradiction. It
follows that that b ∈ D and as a result D is maximal with respect to A.
Proposition 2.12. For any lower set A, the sets M
1
,...,M
k
in the lower-
maximal partition of A form a partition of A, i.e., they are disjoint and their
union covers A.
Proof. Regarding disjointness, suppose, without loss of generality, that M
1
∩
M
2
is a non-empty proper subset of M
1
and M
2
. Consider, now, the collection
(M
1
∩M
2
),M
1
\M
2
,M
2
\M
1
,M
3
\ (M
1
∩M
2
),...,M
k
\ (M
1
∩M
2
); observe
that all these sets are lower and maximal with respect to A in the light of
requirements of the lower-maximal partition and it is a contradiction as it has
k + 1 elements.
Consider now a ∈ A an atom. Suppose that no set in the lower-maximal
partition M
1
,...,M
k
contains it. We will derive a contradiction.
We define a zig-zag path towards a to be a vector of elements hx
1
,...,x
t
i
from A such that x
1
= a, and x
1
≤ x
2
,x
2
≥ x
3
,x
3
≤ x
4
,.... Consider the
set M = {x | ∃ zig-zag path hx
1
,...,x
t
i : (x
1
= a) ∧ (x
t
= x)}. This set is
lower : suppose x ≤ y with y ∈ M. Note that x ∈ A due to the fact that
A is lower. Consider the zig-zag path, hy
1
,...,y
t
i with y
1
= a and y
t
= y.
If y
t−1
≤ y
t
= y then x can extend the zig-zag path and thus x ∈ M. If
y
t−1
≥ y
t
we have by transitivity that also y
t−1
≥ x and thus hy
1
,...,y
t−1
,xi
is a zig-zag path that shows x ∈M.
Consider some y ∈ A with x ≤ y and x ∈ M. As before, given the zig-zag
path hx
1
,...,x
t
= xi we have that if x
t−1
≥ x we can extend the zig-zag path
to y. On the other hand, if x
t−1
≤ x we have by transitivity that x
t−1
≤ y
and again we obtain a zig-zag path to y. This shows that y ∈ M and that M
is maximal with respect to A.
Obviously M is non-empty (it contains at least a) and it is a subset of A.
Moreover, it cannot be the subset of any of M
1
,...,M
k
(that as none of these
sets contain a). Suppose now that for some i it holds that M
i
⊆M. This means
that for any b ∈ M
i
we can find a zig-zag path to a, i.e., there is hx
1
,...,x
t
i
with x
1
= a and x
t
= b. Suppose that b = x
t
≥ x
t−1
. Due to the fact that
M
i
is lower we obtain that x
t−1
∈ M
i
. On the other hand, if b = x
t
≤ x
t−1
we have that due to the fact that M
i
is maximal with respect to A it holds
that x
t−1
∈ M
i
. Repeating this argument along the zig-zag path shows that
a ∈M
i
which is a contradiction. It follows that it cannot be the case that M
i
is covered with M.
Based on the above we conclude that M,M
1
,...,M
k
satisfies the proper-
ties of a lower maximal partition with length longer than k, a contradiction.
Therefore all the atoms of A are included in the union of M
1
,...,M
k
.
