MAXIMALLY INDEPENDENT SETS, MINIMAL GENERATING SETS, AND IRREDUCIBLES by Bernard P. Zeigler September 1972 Technical Report No. 132 Address for 1972-73 Department of Computer Science Technion, Haifa Israel Work supported by: National Science Foundation Grant No. GJ-29989X Washington, D.C.

1. Introduction Cohn's (1965) Proposition 2.1 (Page 253) characterizes precisely the algebraic closure operators which give rise to transitive dependence relations as those enjoying the exchange property. His Lemma 2.2 shows that for such closure operators, maximally independent sets and minimal generating sets are the same concepts. (Using Zorn's Lemma, Theorem 2.4 states the consequence that bases exist and are all of the same cardinality.) Cohn leaves unanswered the question for arbitrary closure operators as to the relation between minimal generating sets and maximally independent sets. This note answers this question by showing that a minimal generating set is maximally independent but provides a counterexample to show that maximally independent sets are not necessarily minimal generating sets. This result justifies the use of the exchange property to enforce the equivalence of the two concepts. The motivation for considering this question arose by noticing a hole in a theorem by Wymore (1967) concerning generating sets of inputs for dynamic systems. This problem is discussed in the last section of this note. Another concept which appears often in algebraic theories (cf. especially the Krohn and Rhodes theory in Arbib (1968)) is that of irreducible elements. The connection between irreducible elements and generators seems not to have been made explicit. Here we also establish such a connection.

2. Generating Sets and Dependence Relations I shall briefly review the key concepts given in Cohn (1965), A closure operator on a set S is a mapping J:2S + 2S (2S being the set of all subsets of S) which satisfies J.1 XCY => J(X) J(Y) J.2 X c J (X) J.3 J*J(X) = J(X) We shall say that X generates Y whenever Yc!J(X). We write X generates y (for y e S) to mean X generates {y}. J is said to be algebraic if whenever y is generated by X it is in fact generated by a finite subset of X. Algebraic closure operators arise precisely by closing a set under the operations of an algebra (Theorem 5.2, page 81). A familiar example of such an algebra is a group with its binary operation. A subset G of S is called a generating set if G generates S. Such a set is minimaZ if in addition whenever Hc-G and H generates S we have H = G. Let a family!2 of subsets of S be such that X is in 9 <=> some finite nonempty subset of X is in. ~ is a family of dependent sets; S its complement in 2 contains exactly the independent sets. The linearly dependent subsets of a vector space are a familiar example. An element a C S depends on X if a ~ X or if there is an independent subset X' of X such that X' U a} (written X' \a) is dependent. <X> = fala depends on X} is called the span of X. X spans S if <X> = S; a basis is an independent spanning set. The dependence relation 9 is transitive if <<X>> = <X>.

Given an algebraic closure operator J:2S - 2S we call associate with it a dependence relation as follows: A subset X of S is dependent if there is an x E X such that X-{x} S (written X-x) generates x. X E 2 is independent if it is not dependent. Thus a set is independent if none of its members can be generated by the others. Obviously 4 is independent. An independent set is maximaZZy independent if it is not properly contained in any independent set. J is said to possess the exchange property if whenever y is not generated by X but is generated by XUz we also have that z is generated by XUy. (XCS, y e S, z e S). Cohn's Prop. 2.1 states that for an operator J enjoying the exchange property the dependence relation associated with J is transitive and moreover from the proof we see that <X> = J(X), hence that X is a generating set iff X is.a spanning set iff X is maximally independent (Lemma 2.2). As mentioned the existence of cardinality invariant bases necessarily follows for such operators. Let us then consider what can be said if J does not enjoy the exchange property. First we note that generates can be viewed eauivalently as a binary relation on 2 which satisfies G.1 transitivity G.2 For any family of sets,[ (vY0)(X generates Y)<=>X.generates U{YIYES G.3 XDY => X generates Y. As a consequence of G.3 we also have that generates is reflexive.

The equivalence is stated as Theorem 1 Given a closure operator J, the associated generoates relation (X generates Y <=> Y C J(X)) satisfies the axioms G.1-3. Conversely, to every relation on 2S satisfying G.1-3 there corresponds a closure operator, and moreover this correspondence is bijective. Proof: => That the axioms are satisfied is easily shown by noting that G.1 follows from J.1 and J.3, G.2 is a consequence of the definition and G.3 follows from J.2. <= Let R be a relation on 2~ satisfying G.1-G.3. Define JR:2S+2S by JR(X) = U {ZIXRZ}. Then JR is a closure operator as follows: a) Let XCY. By G.3, YRX. Thus by transitivity XRZ => YRZ and {ZIXRZ C ({ZIYRZ} so JR(X)C JR(Y). b) Since R is reflexive (G.3), Xe{ZjXRZ} thus XCJR(X). c) From b) JR(X)C JR(JR(X)). From G.2, X R JR(X) and JR(X) R JR(JR(X) so by transitivity (G.1) X R JR(JR(X)) and thus JR(X) 2JR(JR(X)). Thus JR(X) = JR ' JR(X). Now, let R and R' satisfy G.1-3 and suppose JR = JR." Then X R Y => YCJR(X) => YCJR,(X). By G.3, JR,(X) R'Y. But X R' JR,(X) so by transitivity X R' Y. By symmetry we have that X R Y <=> X R' Y so R = R' and the mapping Rd +JR is one-one. This mapping is also onto since given a closure operator J, it is easily seen that J generate J We use this reformulation to prove Theorem 2 Let G be a generating set. G is a minimal generating set <=> G is maximally independent.

Proof: => Suppose G is not independent. Then there is an x e G such that G-x generates x. By reflexiveness, G-x generates G-x and by G.2, G-x generates G. Since G generates S we have by transitivity that G-x generates S so that G is not a minimal generating set. Thus G is independent. Now if G were not maximally independent there would be an x g G such that G Ux is independent. But this contradicts the fact that G generates x. <= Let G be a non-minimal generating set. The G Z ~ since c is a minimal generating set whenever it is a generating set. There is an HCG such that H generates S also an x e G-H such that H generates x. By axiom G.3 and transitivity, G generates x so that G is not independent. The central point of this note is that a maximally independent set is not necessarily a generating set. To see this let R be a reflexive transitive relation on S. Let f be the extension of R to 2, i.e., X ~ Y <=> (Vy e Y)(g x e X)(x R y) S One verifies readily that R is a generates relation on 2S. In this class of models, X is dependent if there are distinct x,y C X such that x R y. In particular let S = {;1,2,3} with R = {(1,1), (2,2), (3,3), (1,2), (1,3)} as in the graph: 2 3

Now (2,3} is independent; also (2,3} is maximally independent since {(1,2,3} is dependent ({1} generates {2,3}). But {2,3} is not a generating set since 1 is not generated by {2,3}. Thus it is not true that a maximaZZy independent set is necessarily a generating set. (Note however that in agreement with Theorem 1, {1} is both a minimal generating set and a maximally independent set.) We see also that, generates does not satisfy the exchange property since 3 is not generated by 2 and {1,2} generates 3 but 1 is not generated by {2,3}. From Cohn's Lemma 2.2 we know that if J satisfies the exchange property then G is a generating set <=> G is maximally independent. The above justifies the use of the exchange property as an hypothesis. For completeness sake we provide a direct proof of this result: Theorem 3 A maximally independent set is a minimal generating set if generates satisfies the exchange property. Proof: Suppose that G is maximally independent but not a generating set. Then there is an x ~ G which is not generated by G. Now GUx is dependent (since G is maximally independent) so there is a z s GUx such that GUx-z generates z. If z=x then GUx-x generates x, a contradiction. So z e G. Since G is independent, z is not generated by G-z. Since G-zUx generates z we have by the exchange property G-zUz generates x, again a contradiction. Thus, G is maximally independent implies G is a generating set and by Theorem 2, G is a minimal generating set.

3. Irreducibles An element x C S is irreducible with respect to a closure operator J if whenever x is generated by X then necessarily x c X. We see immediately that the set of irreducibles, I is included in every (minimal) generating set. Thus if I is a generating set it is also the unique minimal generating set. However, I need not be a generating set as the following example shows: Let S = {1,2}, R = S2 and let generates be interpreted as ~ as before. Graphically, 1 2 It is clear that there are no irreducibles (I = p) yet both {1} and {2} are minimal generating sets. However, we can show that Theorem 4 The only generating set which is included in every generating set is the irreducibles I. Proof: Let G be a generating set which is included in every generating set. For x E G suppose that X generates x. We will show that x C X. It then follows that G CI hence G = S. Using axioms J.1, J.2 and J.3 we have J(G-xUX) -J(G-x)UJ(X)D G-xUx,Thus J(G-xUX) = J'J(G-xUX)D J(G)D S. So G-xUX is a generating set. Since G is included in it, we have x s G-xUX hence that x c X, as required.

4...Application to the Wrnorte Case Let S be the set of functions from the reals to the reals. To each real number there is associated a unary operator operator tr called translation by r such that t (f)(x) = f(r+x). There is also a binary r segmentation operator I such that fig(x) If(x) for x < 0 fg(x) = g(x) for x > 0 It is well known that to an algebra such as this, there corresponds a cannonical closure opprator J:2S +- 2S where J(X) is the least set of functions in S containing X and closed under the translation operators tr and segmentation.* Wymore's (1967) Theorem 4.8 asserts the existence of minimal generating sets (called input bases) for the J-closed subsets (called admissible sets). The proof actually demonstrates the existence of maximally independent sets. However the identification of the maximally independent sets with minimal generating sets is unjustified since as we now demonstrate, the above closure operator does not possess the exchange property. To see this, let x and z- be two distinct constant functions on the reals, and let y = xjz. Now-while y cannot be generated from x alone and y is generated from both x and z, it is not the case that z can be generated from x and y. Proof: Say that a function f has a c-tail if there is a t such that f(x) = c for x < t. Note that both x and xlz have a c-tail where c is * The details for this special case are carried out by Cornacchio (1972) where a closure operator is called a Hammer closure operator (Hammer, 1969).

the constant value of x. It is easy to show by induction that any function generated by (in the J-closure of) x and xlz must have a c-tail and hence must be distinct from z which by assumption has a c'-tail for c' 4 c. Of course this does not preclude the existence of minimal generating sets for the J-closed sets. Having tried a number of approaches, I have failed to establish Wymore's Theorem or find a counterexample. References Arbib, M.A. (1968) Algebraic Theory of Machines, Languages and Semigroups, Academic Press, New York Cohn, P.M. (1965) Universal AZgebra, Harper and Row, London. Cornacchio, J. (1972) Topological Concepts in the Mthematical Theory of GeneraZl ystems in Trends in GeneraZ Systems Theory, G.J. Klir, editor, John Wiley & Sons, Inc., New York. Hammer, P.C. (1969) Advances in MthematicaZ Systems Theory, Pennsylvania State University Press. Wymore, A.W. (1967) A Mathematical Theory of Systems Engineering: The Elements, John Wiley & Sons, Inc., New York.