PII. S0161171201010729 http://ijmms.hindawi.com
© Hindawi Publishing Corp.
FREE OBJECTS IN THE CATEGORY OF GEOMETRIES
TALAL ALI AL-HAWARY (Received 15 August 2000)
Abstract.The aim of this note is to introduce the class of free geometries purely in terms of morphisms. Several classes of well-known matroid morphisms are characterized via the new concept.
2000 Mathematics Subject Classification. 05B35.
1. Introduction. We shall assume familiarity with category and matroid theories;
for an introduction, see [2,3], respectively. In particular, amatroidMis an ordered pair(E,FM)whereFM is a collection of subsets, calledflatsofM, of a finite setEsuch thatEis a flat ofM, the intersection of any two flats ofMis a flat ofMand ifF∈FM
and{F1, F2, . . . , Fk}is the set of minimal members ofFM(with respect to inclusion) that properly containF (denoted byFiF), thenF1∪F2∪···∪Fk=E. The setEis called theground setofM. A formal notation for the matroid on the ground setEwith flats FM isM(E,FM), but when no confusion will arise, we refer to this matroid asM.When several matroidsM(Ei,Fi),i=1,2, . . . , nare being considered, we shall often denote these matroids byM1,M2, . . . , Mn.
By acombinatorial geometrywe mean a loopless matroid with no multiple elements, that is, a matroid in which the empty set and each point, if any exists, is a flat. We will use the shorter “geometry” in place of “combinatorial geometry.” Afree geometryis a geometry which has every subset of its ground set as a flat. If the ground set of a free geometry hasmelements, then we denote that geometry byUm,m.
Our main goal in this note is to introduce a categorical definition of a free object in thecategoryᏳof geometries and strong maps. We define a functor, which we call a free functor, from thesubcategory Ᏺ of free geometriesto the categoryᏳ. Lastly, we show thatᏲ is a coreflective subcategory ofᏳ and the free functor is a faithful functor which is a right adjoint of the inclusion functor.
The category of free geometries play an important role in solving the following open problem:
Find a finite set of elementary axioms that characterize the categoryᏳ.
It was that problem which prompted us to study the notion of free geometries.
2. Free objects. Define theisthmus1 to be an object inᏳwith exactly one endo- morphism. Since in any category with an objectM, the identity mapiM is always an endomorphism of M, i1 is the endomorphism of 1. Observe that 1 is the terminal object ofᏳwhile the initial object 0 is the empty geometry which is isomorphic to U0,0.
Proposition2.1. For every objectM,xis an element ofM, orx∈M, if and only if xis a morphism with1→x M.
In the concrete category of geometries and strong maps, 1 is isomorphic to the free geometryU1,1. ClearlyU1,1has one element and one endomorphism.We shall denote the element of 1 byc. Next, we give a categorical definition of free objects which has never been introduced before. We remark that this definition is not obvious.
Definition2.2. An objectDis called afree objectif for everyx∈Dthere exists a morphismhxwithD h→x 11 such that for everyy∈D,y≠x, we havehxx≠hxy.
Clearly the objects 0, 1 are free. Also 11 is free since 11 has only two elements and the identity on 11 satisfies the property ofhxin the definition of free objects.
We notice as 1 is isomorphic toU1,1 that has a ground set isomorphic to{c}, the geometry 11 has a ground set isomorphic to{c1, c2}. Next, we state and prove our first main result.
Theorem2.3. A geometry is free if and only if it is isomorphic toUn,n.
Proof. Let D=M(E,FD)be a free geometry such that |E| =n. If n=0, then DU0,0.Ifn=1, thenD1U1,1. Ifn≥2, then to showDUn,n it is sufficient to show that{x}andE\{x}are flats ofDfor all x∈E. Since then, for every proper subsetF⊂Esuch that|F| ≤n−1,F∈FD. Letx∈E. Then the constant mapfxwith 1 f→x D wherefx(c)=x is a strong map. Hence asDis free, there exists a strong maphxwithM h→x 11 such that for every strong mapgwith 1 →g M,g≠fx, we must havehxfx≠hxg. Thus assumehxf (c)=c1. Again asDis free and as for all y∈E\{x}, the constant mapfyas above is a strong map such thatfy≠fx, we have hxfx(c)≠hxfy(c).Thus,hx(y)=c2for ally∈E\{x}.As{c1}and{c2}are flats of 11,{x} =h−x1({c1})andE\{x} =h−x1({c2})are flats ofD. Therefore,DUn,n.
IfDUn,nfor somenwhereUn,nhas a ground setE´, then for every strong mapf with 1→f D, define a strong maphwithUn,n
h
→11 byh(z)=c1whenz=f (c), and h(z)=c2otherwise. For every strong mapgwith 1→g Msuch thatg≠f,g(c)≠f (c) and hencehg≠hf. Therefore,Dis free.
The proof of the following weak axiom of choice follows directly from the axiom of choice for sets.
Theorem2.4. For every morphismf withM1 f
→DwhereM10andDis a free object, there exists a morphismgwithD→g M1such thatf=f gf.
Next, we show 1 is a generator and use that to give a sufficient condition for a morphism in the categoryᏳto be an epimorphism.
Lemma2.5. The isthmus object1is a generator.
Proof. IfM and N are objects andf , g are morphisms from M toN such that f≠g, then there existsx∈M(i.e.,xis a morphism with 1→x M) such thatf x≠gx.
Thus 1 is a generator.
a b
d h
M
a b e
h d
N Figure2.1. The converse of Proposition 2.5 does not hold.
Proposition2.6. IfM1andM2are two objects andfis a morphism withM1 f
→M2
such that for every elementg∈M2there exists an elementh∈M1 satisfyingg=f h, thenf is an epimorphism.
Proof. IfNis an object andf1,f2are two morphisms withM2 f1
→NandM2 f2
→N such thatf1f =f2f, then we need only show the right cancellation law holds, that is,f1=f2. Supposef1≠f2. ByLemma 2.5, 1 is a generator and hence there exists a morphismmwith 1 m→M2such thatf1m≠f2m. Thus by assumption, there exists a morphismkwith 1→k M1such thatm=f kand hence,f1f k=f1m≠f2m=f2f k.
That is,f1f k≠f2f kwhich is a contradiction to the fact thatf1f h=f2f h(because f1f=f2f).
Next we show the converse of the preceding proposition need not hold inᏳ. Example2.7. Consider the matroidsMandNgiven by the point configurations in Figure 2.1. By [1, Proposition 3], the inclusion mapiwithM→i Nis an epimorphism.
Define a strong mapf with 1→f Nbyf (c)=e. Ifgis a strong map with 1→g Msuch thatf =ig, theng(c)=ig(c)=f (c)=ewhich is a contradiction to the fact that e∉E(M).Therefore, the converse ofProposition 2.6does not hold.
3. Some peculiar morphisms. In [1], Crapo proved that a strong map is a mono- morphism if and only if it is a one to one map on points. It was also shown that an onto strong map, on points, is an epimorphism but an epimorphism need not be onto, on points. Next, we show that an epimorphism with free codomain is onto, on points.
Proposition3.1. IffwithM→f Dis an epimorphism whereDis free, thenfis an onto map on points.
Proof. SupposeE(M)andE(D)are the ground sets ofMandD, respectively. If fis not onto, then there existsx∈E(D)such thatx∉f (E(M)). LetHbe a geometry on the set{x, y}and define strong mapsgandhfromDtoHbyg(x)=y,g(z)=x whenz∈f (E(M))andh(z)=xfor allz∈E(D).Thengf=hfandg≠h. Therefore, fis not an epimorphism.
Proposition3.2. Every nonzero objectM has elements and the morphismtwith M→t 1is an epimorphism.
Proof. ByTheorem 2.4, there exists a morphismhwith 1→h Msuch thatt=tht and henceth=thth.Therefore,th=i1and asi1is the only endomorphism of 1, by Proposition 2.6,tis an epimorphism.
Proposition 3.3. Any bimorphism (= a monomorphism and an epimorphism)f withM1
f
→M2with free domain and codomain is an isomorphism.
Proof. IfM10, byProposition 3.2,M20 sincefis an epimorphism. IfM10, byTheorem 2.4, there exists a morphism gwith M2
g
→M1 such thatf =f gf and sincefis a bimorphismgf=iM1andf g=iM2.Thusfis an isomorphism.
The following theorem indicates that the category of free objects and strong maps is a coreflective subcategory ofᏳ. The proof of that theorem is not hard and is thus left to the reader.
Theorem 3.4. For every object M, there exists a free object |M|together with a morphismtMwith|M|tM→Msuch that for every free objectDand a morphismhwith D→h M, there exists a unique morphismkwithD→ |M|k such thath=tMk.That is to say, the subcategoryᏲof free geometries and strong maps is a coreflective subcategory ofᏳ.
Next, we state and prove several facts related to the morphismstM and the objects
|M|, all purely in terms of morphisms only.
Proposition3.5. The morphismtMis a bimorphism.
Proof. ByTheorem 3.4andProposition 2.6,tMis an epimorphism. Ifxandyare elements of|M|such thattMx=tMy, then as 1 is a free object, byTheorem 3.4, there exists a unique elementh∈ |M|such thattMx=tMh. But astMy=tMx,x=h=y and hencetMis a monomorphism.
Observe that|M|is defined up to isomorphism and the operation “| |” is a functor which we call thefree functor. Next, we prove the free functor is a faithful functor that is also a right adjoint of the inclusion functor fromᏲtoᏳ.
Proposition3.6. The free functor is faithful, that is, for every morphismsf,gfrom MtoNsuch that|f| = |g|, thenf=g.Moreover, the free functor is a right adjoint of the inclusion functorᏲᏳ.
Proof. We prove the first part of the proposition and leave the other to the reader.
If |f| = |g|, then f tM = tN|f| = tN|g| = gtM and since tM is an epimorphism, f=g.
The proof of the following proposition is immediate and is left to the reader.
Proposition3.7. A morphismfis a bimorphism if and only if|f|is a bimorphism.
Corollary3.8. Iff is a bimorphism withD →f N whereDis a free object, then D |N|.
M1 |iM1|
iM1
|M| u tM
M2
|iM2|
M iM2
Figure3.1.Coproduct of free objects is free.
M´ f2 f1
M1 q
|M1|
tM2
u M2
f
Figure3.2. A regular epimorphism with free domain has a free codomain.
Corollary3.9. Iffis a monomorphism withM1 f
→M2andM2is a free object, then M1is a free object.
Proof. For every morphismgwith 1→g M1,f gis a morphism from 1 toM2and as M2is a free object, there exists a morphismhf gfromM2to 11 such thathf gf g≠ hf gmfor every morphismmwith 1m→M2such thatm≠f g. Letebe a morphism with 1→e M1such thate≠g. Then asfis a monomorphism,f e≠f g. Thushf gf e≠hf gf g.
Therefore,hf≠hgwhereh=hf gfand henceM1is a free object.
Corollary3.10. IfM1andM2are free objects, thenM1M2is a free object.
Proof. AsM1andM2are free objects,M1 |M1|andM2 |M2|. By definition of the coproductM1M2, there exists a unique morphismuwithM → |M|, whereu M M1M2, such that|iM1| =uiM1and|iM2| =uiM2.(See the diagram inFigure 3.1.) Thus tMuiM1=tM|iM1|andtMuiM2=tM|iM2|.But by definition of|iM1|and|iM2|, we have tM|iM1| =iM1 andtM|iM2| =iM2. Therefore,iM =tMuand then asiM is a monomor- phism,uis a monomorphism. Thus since|M|is a free object, byCorollary 3.9,Mis a free object.
Corollary3.11. A regular epimorphism with a free domain has a free codomain.
Proof. Iffis a morphism withM1 f
→M2whereM1is a free object,M´is an object andf1,f2are two morphisms fromM´toM1such thatM1, fis isomorphic to the coequalizer Coeq(f1, f2) of f1 and f2, then by Theorem 3.4, there exists a unique morphism q with M1
q
→ |M2| such that f = tM2q. (See the diagram in Figure 3.2.) Thus,tM2qf1=f f1 =f f2=tM2qf2 and sincetM2 is a monomorphism,qf1=qf2. By definition of the coequalizer Coeq(f1, f2), there exists a unique morphismuwith M2
u
→ |M2|such that q=uf. ThusiM2f=f=tM2q=tM2uf. Sincef is an epimor- phism,iM2=tM2uand asiM2is a monomorphism,uis a monomorphism. As|M2|is a free object, byCorollary 3.9,M2is a free object.
References
[1] H. Crapo,Constructions in combinatorial geometries, Tech. report, Bowdoin College Notes, 1971, N.S.F. Advanced Seminar.
[2] H. Herrlich and G. E. Strecker,Category Theory: An Introduction, Allyn and Bacon Se- ries in Advanced Mathematics, Allyn and Bacon, Massachusetts, 1973.MR 50#2284.
Zbl 265.18001.
[3] J. G. Oxley,Matroid Theory, Oxford Science Publications, Oxford University Press, New York, 1992.MR 94d:05033. Zbl 784.05002.
Talal Ali Al-Hawary: Department of Mathematics, Mu’tah University, P. O. Box6 Karak, Jordan
E-mail address:[email protected]
