Representation theory is a branch of mathematics whose original purpose was to represent information about abstract algebraic structures by means of methods of linear algebra (usually, by linear transformations and matrices). Rota in his famous “Foundations” defined a representation of a locally finite partially ordered set (poset) P in terms of a module over a ring A, which can be further extended to an associative A-algebra called incidence algebra of P . He applied this construction to solve a number of important problems in combinatorics. Our goal in this paper is to apply Rota's construction of incidence algebras to (arbitrary) Pawlak information systems. To be more precise, we analyse both incidence algebras and information systems in the context of granular computing. Therefore, starting from objects and an indiscernibility relation, we focus our attention upon information granules (i.e. equivalence classes) and a corresponding incidence algebra; finally, we discuss a lattice of closed ideals of this algebra (whose maximal elements serve as a representation of information granules). In this way we obtain a (partially ordered) set of maximal (closed) ideals which is isomorphic to the set of information granules of a Pawlak information system (also equipped with a natural information order).
Representation theory is a branch of mathematics which studies abstract algebraic
structures by means of methods of linear algebra, with special emphasis put upon vector
spaces and linear transformations. Roughly speaking, since the 1930s when Noether
gave to the theory its modern settings, studying representations of an algebra has been
actually studying modules over this algebra. In the paper we focus our attention on
partially ordered sets (posets) regarded as abstract algebraic structures and incidence
algebras regarded as their linear algebraic counterparts. To be more precise, in
representation theory representations of posets are studied by means of modules of
corresponding incidence algebras. The concept of an incidence algebra understood as an
associative algebra over a ring, which corresponds to a poset, has been introduced by
Rota in Foundations I. However, Rota actually established an incidence algebra a
fundamental concept in combinatorics rather than in representation theory. The primary
object of his study was a Möbius function of a given poset P , that is a special element
of the incidence algebra IN C(P ) of P ; it turned out that the Möbius function was a
fundamental invariant of posets. In contrast to his approach, in the present paper we
are not interested in combinatorial properties of posets and their incidence algebras, but
in their mutual relationships and possible applications to data analysis. For this reason
we simplify a bit also representation theory and we focus our attention on special
features of incidence algebras proved by Rota in [
In this section we recall basic concepts from rough sets, however, we frame the presentation so as to fit the granular computing approach to data. Generally speaking, granular computing is a paradigm of (or better still, theoretical perspective on) information processing. It focuses on the idea that the knowledge which is present in data can be processed at various levels of resolution or scales; in other words, at various levels of granulation. Therefore in this section, while considering a partition of a set of objects (induced by an indiscernibility relation), we make further steps and equip this partition (regarded as a set of information granules) with some additional structure (e.g. order), which would reflect the information about objects on the level of granules (i.e. at a lower resolution).
Definition 1 (Information System). A quadruple I = hU; Att; V al; f i is called an information system, where – U is a non–empty finite set of objects; – Att is a non–empty finite set of attributes; – V al = SA2Att V alA, where V alA is a (non-empty) value–domain of the attribute
A; – f : U Att ! P(V al) is an information function, such that for all A 2 Att and a 2 U , f (a; A) V alA.
If f (a; A) 6= ; for all a 2 U and A 2 Att, then the information system I is called complete; otherwise, it is called incomplete. If f (a; A) is a singleton (i.e. fvalg, where val 2 V alA), for all a 2 U and A 2 Att, then it is called deterministic.
the descriptor language LDesc [
Definition 2 (LDesc Model). Let LDesc be a descriptor language over an information system hU; Att; V al; f i. Then hU; vi is a model, where v : U ! f0; 1g is a function assigning to each pair (a; p), where a 2 U and p 2 , a truth value. We usually write v(a; p) = 1 (or va(p) = 1), which is read as for the object a, p is true. Let us define: – va([A = val]) = 1 if val 2 f (a; A), and 0 otherwise.
As usual, the function v is extended to every formula 2 FDesc in the standard way.
It is worth noticing that in the case of an incomplete information system, if f (a; A) = ;, then va([A = val]) = 0 for all values val 2 V alA.
the object a:
jajLDesc = fp 2 j va(p) = 1g Whenever the context of an information system and the descriptor language over this system is clear, we shall omit the subscript and simply write jaj. The sets of this form induce a preorder on the set of objects U : a b iff jaj jbj; for all a; b 2 U . Intuitively, a b means that we have more pieces of information about the object b than about a. As usual, when we have the same knowledge about two objects, then these objects are indiscernible, denoted by a IN D b: a IN D b iff a b and b a:
Proposition 1. Let hU; Att; V al; f i be a complete and deterministic information system. Then and IN D coincide.
As usual, the partition of U induced by IN D is denoted by U=IN D. The proposition above tells that in the case of a complete information system, the quotient set U=IN D inherits no order (different than the identity) from the preordered set (U; ). However, in the case of incomplete and nondeterministic systems there is non-trivial inheritance of information. Let [a]IND 2 U=IN D denote the equivalence class induced by a, then let us define on U=IN D (by abuse of notation we use the same symbol as for U ): b: Proposition 2. Let hU; Att; V al; f i be an information system. Then (U=IN D; ) is a partially ordered set.
Actually, any preordered set P = (U; ) can be viewed as a partially ordered set
U=IN D with the order inherited from P . Furthermore, for finite sets the preordered
set P can be viewed as a pair (U=IN D; ), where : U=IN D ! N returns the
number of elements of a given equivalence class. The following proposition comes from [
In consequence, in the case of a finite preordered set P = (U; ), we can pass between P and its representation (U=IN D; ) forth and back by means of a partially ordered set (U=IN D; ) without any loss of information.
v5([T est result = P ositive]) = v5([T est result = N egative]) = 1:
and IN D are given by = f(1; 1); (2; 2); (1; 2); (1; 5); (2; 1); (2; 5); (3; 3); (4; 4); (3; 4);
(3; 5); (4; 3); (4; 5); (5; 5)g;
IN D = f(1; 1); (2; 2); (1; 2); (2; 1); (3; 3); (4; 4); (3; 4); (4; 3); (5; 5)g;
respectively. The quotient set U=IN D is equal to f[
Intuitively, the set U=I N D consists of basic information granules induced by an information system hU; Att; V al; f i. Thus the poset (U=I N D; ) actually represents information encoded by hU; Att; V al; f i from granular perspective. As said earlier, we can regard (U=I N D; ) as (U; ) presented at a lower resolution.
Definition 3 (Module). A left module M over a ring A consists of an Abelian group (M; +) and an operation : A M ! M such that for all r; s 2 A and a; b 2 M we have: 1. r (a + b) = r a + r b, 2. (r + s) a = r a + s a, 3. (r s) a = r (s a), 4. 1 a = a if A has a multiplicative identity 1.
A right A-module M is defined similarly, only the ring acts on the right; if A is commutative, then left A-modules are the same as right A-modules and are simply called A-modules.
Definition 4 (Associative Algebra). Let A be a fixed commutative ring. An associative A-algebra is an additive Abelian group M which has the structure of both a ring and an A-module in such a way that ring multiplication is A-bilinear: r (a b) = (r a) b = a (r b); for all r 2 A and a; b 2 M .
In other words, an A-algebra is an A-module equipped with the operation of multiplication (convolution) : M M ! M of elements of M such that the above equations hold. By the standard abuse of notation, we have used the same symbol for multiplication by scalars (i.e. r a, r 2 A and a 2 M ) and multiplication (convolution) of elements of M (i.e. a b, a; b 2 M ). Obviously, the context always makes clear the meaning of the symbol .
and left multiplication by arbitrary elements of M . Replacing a b 2 I by b a 2 I we define a right ideal. A two-sided ideal is a subset that is both a left and a right ideal.
Definition 5 (Ideal). A subset I following conditions hold: – a + b 2 I , for all a; b 2 I , – r a 2 I , for all r 2 A and a 2 I , – a b 2 I , for all a 2 M and b 2 I .
M will be called a left ideal of A-algebra if the Definition 6 (Product of Ideals). Let I and J be ideals in a ring A. The ideal product is defined by
IJ = fX aibi j ai 2 I; bi 2 J g: Let P = (U; ) be a locally finite partially ordered set (poset), that is the relation is a reflexive, transitive and antisymmetric, such that every interval [a; b] = fc 2
Definition 7 (Incidence Algebra). An incidence algebra IN CA(P ) of a locally finite partially ordered set P = (U; ) is a set of all functions f : U U ! A, where A is a commutative ring with multiplicative identity such that
f (a; b) = 0 if a 6 b:
(f + g)(a; b) = f (a; b) + g(a; b) and (r f )(a; b) = r f (a; b) for all f; g 2 IncA(P ), a; b 2 U and r 2 A. Formally, it means that IncA(P ) is an A-module, which can be made an A-algebra by the addition of convolution, justifying the term incidence algebra: (f If a 6 b, then there will be no c such that a c b and (f g)(a; b) = 0; such a sum we shall call degenerated. It is also worth noting that if P is finite and we present f 2 IncA(P ) as n n matrix mf , where n is the number of elements of U , with (a; b) entry f (a; b), then the operation of convolution will be the standard multiplication of matrices.
Definition 8 (Standard Topology). The standard topology on an incidence algebra IN C(P ) of a locally finite partially ordered set P = (U; ) is defined as follows: A sequence f1; f2; f3; : : : converges to a function f if and only if fn(a; b) converges to f (a; b) in the field A for every a; b 2 U , when n goes to the infinity.
finite, then any two-sided ideal I is closed, i.e. I is a closed set in the standard topology.
Proposition 4. In a locally finite poset P , let S(P ) be the set of all segments of P ordered by inclusion. Then there is a natural anti-isomorphism between the lattice of closed ideals of IN C(P ) and the lattice of order ideals of S(P ).
(whose full form can be found in [
Proposition 5. The closed maximal ideals of incidence algebra IN CA(P ) are those of the form
Ja = ff 2 IN C(P ) j f (a; a) = 0g: Actually, what is important from our perspective is a one-to-one correspondence between elements of P and maximal closed ideals of IN C(P ) which have a very simple form. Therefore, we do not actually need to go into details of standard topologies of posets. It suffices to keep in mind that Ja is a set of special functions f such that f (a; a) = 0. The proposition above suggests how to represent the elements of P while building the representation of P in terms of an incidence algebra; we shall come back to this idea soon.
sented in [
Proposition 6. Let P and P 0 be (locally finite) partially ordered sets, and let A be a field. If IN CA(P ) and IN CA(P 0) are isomorphic as A-algebras, then P and P 0 will be isomorphic.
Proposition 7. Let P and P 0 be finite preordered sets and let A be a field. Then if IN CA(P ) and IN CA(P 0) are isomorphic as A-algebras, then P and P 0 will be isomorphic as preordered sets.
In the case of preordered sets and rings, IN CA(P ) is often referred to as an incidence
ring. To complete the presentation, let us recall the connection between incidence rings
of a preordered set and its corresponding partial order (see e.g. [
Proposition 8. Let P = (U; ) be a finite preordered set and A a commutative ring with multiplicative identity, and P^ = (U=IN D; ). Then IN CA(P ) and IN CA(P^) are Morita equivalent.
Recall that two unital rings A and A0 will be Morita equivalent if the categories of their left modules are equivalent. In the category of commutative rings the Morita equivalence is exactly an isomorphism. Of course, the operation of convolution need not be commutative. However, Morita equivalent rings have isomorphic lattices of ideals.
4
In Sect. 2 we presented an information system I = hU; Att; V al; f i as a partially ordered set P I = (U=IN D; ), or better still, as (U=IN D; ). In consequence, we can associate with every information system its incidence algebra IN C(I) = IN C(P I ).
algebra IN C(I). Therefore, before we will proceed in this study we introduce some auxiliary concepts allowing us to focus attention upon these ideals. For elements a; b of a poset P define
S(a; b) = f[c; d] j [c; d] 2 S(P ) and a c d bg;
JS(a;b) = ff 2 IN C(P ) j f (c; d) = 0 for all [c; d] 2 S(a; b)g:
Ja = JS(a;a); and a 6 b implies JS(a;b) = IN C(P ):
Proposition 9. Let I = hU; Att; V al; f i be an information system. Then I is complete and deterministic if and only if for all a; b 2 U , such that a 6= b, JS(a;b) = IN C(I). The property of being deterministic and complete system can also be expressed by means of the operation of convolution. Let us recall that convolution f g was defined by (f Hence, given that I is complete and deterministic, if a 6= b then (f g)(a; b) = 0 for all f; g. In the case a = b we obtain (f g)(a; a) = f (a; a)g(a; a). Since the underlying ring A is commutative, we get that for such an information system I the convolution is also commutative.
Proposition 10. Let I = hU; Att; V al; f i be an information system. Then I is complete and deterministic if and only if its incidence algebra IN C(I) is commutative.
responding algebra is not commutative. Although this case is not necessarily desirable in data analysis, it is mathematically much more interesting than the case of complete and deterministic systems. In what follows we analyse the non-commutative cases.
In order to make the presentation less abstract we shall take advantage of the
correspondence of incidence algebras with rings of square matrices (e.g. [11]), which will
allow us to visualise some features of these algebras. In the case of a finite set P = (U; ),
we can present P by its incidence matrix cP as usual, that is, a square matrix n n,
where n is the number of elements of U :
cP = [cab]a;b2U
with cab =
For example, the incidence matrix of (U=IN D; ) from Sect. 2 (see Fig. 1), where U =
f[
IN C(P ) = fm = [mab]a;b2U j mab = 0 if a 6 bg In other words, IN C(P ) is a subalgebra of M(A). It consists of matrices mf (labelled by elements of IN C(P )), which are consistent with the incidence matrix cP : mf = [mab]a;b2U with mab = f (a; b) 0 fmf j mab = f (a; b) where f 2 IN C(P )g:
maximal elements of the lattice of the closed ideals Ja of IN C(P ). Fortunately, they have a very simple characteristic and we do not need to pay much attention to the standard topology associated with the poset P . In terms of matrices, elements of Ja have the form mf with an additional requirement that maa = f (a; a) = 0.
to the maximal closed ideals. As usual, a < b means a b and a 6= b. We say that b covers a, symbolically a b if a < b and no element c 2 U satisfies a < c < b. Thus, what a Hasse diagram of P actually illustrates is the induced covering relation . Of course, a 6 a for all a 2 U .
product of ideals JaJb:
JaJb = fX fi gi j fi 2 Ja; gi 2 Jbg Previously we introduced closed ideals of the form JS(a;b); so, let us ask when it is true that JaJb JS(a;b). It turns out that this inclusion holds in three simple cases: 1. If a 6 b, then for any element f 2 IN C(P ) it holds that f (a; b) = 0. 2. If a = b, then h(a; a) = f (a; a)g(a; a) = 0 and h(b; b) = f (b; b)g(b; b) = 0.
g)(a; b) = f (a; a)g(a; b) + f (a; b)g(b; b) = 0 The first case may be ruled out by the restriction that JS(a;b) 6= IN C(P ). On the other hand, the other two cases are consistent with the order of P .
Definition 9 (Order on Ideals). Let IN C(P ) be an incidence algebra of finite partially ordered set P over a field A. We shall say that Ja Jb if
JS(a;b) 6= IN C(P ) and JaJb = JS(a;b): Now define
J to be a transitive closure of .
Generally, when a 6= b then for every f 2 JaJb it will hold that f (a) = 0 = f (b), and f (a; b) will be some value from A. However, in the case when a b, we shall also get that f (a; b) = 0. Thus, if a b, then Z(JaJb) = f[a; a]; [b; b]; [a; b]g = S(a; b) and hence JaJb = JS(a;b). On the other hand, if a b and a 6= b, then f[a; a]; [b; b]; [a; b]g S(a; b). But JaJb = JS(a;b) and hence S(a; b) = Z(JaJb) f[a; a]; [b; b]; [a; b]g. It is possible only when a b.
Proposition 11. Let IN C(P ) be an incidence algebra of a finite partially ordered set P over a field A. Then J is a partial order on J . If we define Ja Jb when a 6= b and Ja Jb, then will be a covering relation induced by J .
Proposition 12. Let IN C(P ) be an incidence algebra of finite partially ordered set P over a field A, and let J be a set of closed maximal ideals equipped with J . Then P and J are isomorphic as partial orders.
J[
J[
J[
defined on maximal closed ideals.
tures used in rough sets. Consider e.g. a tolerance space (U; T ) where U is a set of objects and T is a tolerance relation, that is T is symmetric and reflexive. Define T (a) = fb 2 U j aT bg and a b iff T (a)
T (b):
dence rings whose lattices of ideals are isomorphic. Recently, Peters [9] suggested to use perceptual systems instead of information systems when dealing with visual information. The special role is played there by a perceptual tolerance relation which, as in the case of tolerance spaces, is an easy object to representation.
As the reader may know, interaction is an emerging paradigm of models of
computation. It is supposed to reflect some recent changes in technology such as multiagent
systems and object-based distributed systems [
9. Peters, J. F.: Near sets. Special theory about nearness of objects. Fundamenta Informaticae 75, 2007, 407–433. 10. Rota, G. C.: On the foundations of combinatorial theory I. Z. Wahrscheinlichkeitstheo.
Verwandte Geb. 2, 1964, 340–368. 11. Stanley, R. P.: Enumerative Combinatorics, Vol. I. Cambridge U. Press 1997.