On a representation of posets by subsets
by
Branimir Seselja
Institute of Mathematics, University of Novi Sad, Yugoslavia

For an arbitrary poset P and its nonempty subset Q, consider the following collection of subsets of P:

P(Q):={ \uparrow p \cap Q | p in P}.

Such collections often appear in the framework of various set representations of poset. Usually, Q is the collection of particular (e.g., irreducible) elements of P, and instead of the principal filter, the corresponding ideal may appear. If this collection is ordered by inclusion, then f:p --> \uparrow p \cap Q is an anti-isotone map from P onto P(Q). This map may be a dual order isomorphism depending on properties of the subset Q and of general preoperties of P.

We give conditions under which f is a dual isomorphism, in some particular, and also in general case.

We also present some applications of the foregoing concept in representation of posets and in lattice valued (fuzzy) structures.

Let S be a nonempty set and (P, <= ) a poset. Consider a map f:S --> P, and for every p in P the set f_p subset or equal S defined by

x in f_p if and only if f(x) >= p.

The collection F_P:={ f_p | p in P} can be ordered by inclusion and the following hold.

(T1)For every x in S

f(x) = \/ (p in P | x in f_p(x)),

i.e., the least upper bound of the set {p in P | x in f_p(x)} exists and is equal to f(x).

(T2) If p, q in P and p <= q, then f_q subset or equal f_p.

(T3) (i) \cup (f_p | p in P) = S ;

(ii) for every x in S, \cap (f_p | x in f_p) in F_P, i.e., the collection F_P is a point closure system under inclusion. Let \approx be an equivalence relation on P, defined by: for p, q in P

p \approx q if and only if f_p = f_q.

For p in P, let [p] _\approx :={ q in P | p \approx q}.

(T4) p \approx q if and only if \uparrow p \cap f(S) = \uparrow q \cap f(S).

On the collection of P/ \approx = { [p] _\approx | p in P} of \approx -classes, define the relation   <= as follows:

[p] \approx <= [q] \approx if and only if \uparrow q \cap f(S) subset or equal \uparrow p \cap f(S). (1)

(T5) (i) If for x in S, f(x)=p, then p is the greatest element of the \approx -class to which it belongs.

(ii) The relation   <= , defined by (1) is an ordering on P/ \approx and also

[p] _\approx <= [q] _\approx    if and only if f_q subset or equal f_p.

(iii) The poset (P/ \approx , <= ) is dually isomorphic with the poset (F_P, subset or equal ).

The converse of the above constructions also holds, i.e., point closure system on a set can be represented by a single function on its subset.

(T6) Let f:S --> L be a map from a nonempty set S to a lattice L. Then:

(a) The collection F_L={f_p | p in L } is closed under intersections and a lattice under set inclusion;

(b) for every x in S, f(x)= \/ [f(x)] _\approx ;

(c) for any p, q in L, [p] _\approx <= [q] _\approx if and only if \/ [p] _\approx <= \/ [q] _\approx

(the order on the right is the one from L).

The above representation of posets by functions can be generalized in the following way.

Theorem Let (P, <= ) be a poset and Q subset or equal P. Then (P, <= ) is dually isomorphic to the collection { Q \cap \uparrow p | p in P} ordered by inclusion if and only if Q is inf-dense in P.

By using characteristic functions of subsets arising in the foregoing constructions, particular classes of binary block-codes can be presented by a single function or a set.

Date received: April 30, 2002