Cryptography Reference
In-Depth Information
the ideal in this case. The principal ideal ↓ p for a principal p is thus given by
↓ p = {x ∈ P | x ≤ p}.
The dual notion of ideal, the one obtained in the reverse partial order, is
called a filter. We define F(x) as the set of elements {a ∈ Φ : x ≤ a}. It is
not hard to prove that F(x) constitutes a filter. We call F(x) an atomic filter
if x is an atom. We also denote by P
x
the complement of F(x) in (Φ,≤), i.e.,
P
x
= Φ\F(x).
A useful observation is the following :
Lemma 2.9. For any atom u in a poset Φ it holds that P
u
is a lower set.
Proof. Let x,y ∈ Φ with y ∈ P
u
and x ≤ y. Suppose that x 6∈ P
u
, i.e., it must
be the case that x ∈ F(u), i.e., u ≤ x. By transitivity we have that u ≤ y and
as a result y ∈ F(u), a contradiction. It follows x ∈ P
u
.
The following definition will be an essential tool in our exposition.
Definition 2.10. Given a nonempty subset A of a finite atomistic partially
ordered set (Φ,≤) that is a lower set, we say hM
1
,M
2
,...,M
k
i is a lower-
maximal partition of A if
1. ∅6= M
i
⊆ A is a lower set for i = 1,...,k.
2. for all i,i
0
, (i 6= i
0
) →M
i
6⊆M
i
0
.
3. M
i
is maximal with respect to A, i.e., for all a ∈ M
i
if ∃b ∈ A s.t a ≤ b,
then b ∈M
i
.
4. k is the largest integer such that all the above hold.
The order of a lower set A is defined as the size of its lower-maximal
partition. We denote the order by ord(A).
We next prove some properties of the lower-maximal partition of a lower
set; we start with a preparatory lemma.
Lemma 2.11. Let A be a lower set. The set of all subsets of A that are lower
and maximal with respect to A is closed under intersection and set subtraction.
Specifically, if M
1
,M
2
⊆ A are two lower sets that are maximal with respect
to A then the sets M
1
∩M
2
, M
1
\M
2
are also lower and maximal with respect
to A.
Proof. Consider the set M
1
∩M
2
. It is easy to see that it is a lower set as an
intersection of lower sets. Further, if there is some b ∈ A with a ∈M
1
∩M
2
and
a ≤ b it follows that b must belong to both M
1
and M
2
due to the maximality
of those sets with respect to A. As a result M
1
∩ M
2
is also maximal with
respect to A. Now consider D = M
1
\M
2
. Let b ∈ D and a ∈ Φ such that
a ≤ b. We will show that a ∈ D. First observe that due to the fact that M
1
is lower we have that a ∈ M
1
. Second, if a ∈ M
2
then it follows that b ∈ M
2
by the maximality of M
2
with respect to A. This is a contradiction as a result
a ∈ D. This proves that D is a lower set.
