INTEGERS ELECTRONIC JOURNAL OF COMBINATORIAL NUMBE

INTEGERS:ELECTRONICJOURNALOFCOMBINATORIALNUMBERTHEORY7(2007),#A12AGRAPHICGENERALIZATIONOFARITHMETICBilalKhanDepartmentofMathematicsandComputerScience,JohnJayCollegeofCriminalJustice,CityUniversityofNewYork,NewYork,NY10019,[e-mail]matics,TheCatholicUniversityofAmerica,WashingtonDC20064,[e-mail]rkCityCollegeofTechnology,CityUniversityofNewYork,NewYork,NY11201,[e-mail]:1/21/05,Revised:1/17/07,Accepted:1/31/07,Published:2/28/07AbstractInthispaper,weintroduceanaturalarithmeticonthesetofallflowgraphs,thatis,thesetofallfinitedirectedconnectedmultigraphshavingapairofdistinguishedvertices.Theproposedmodelexhibitsthepropertythatthenaturalnumbersappearasasubmodel,withthedirectedpathoflengthnplayingtheroleofthestandardintegern.Weinvestigatethebasicfeaturesofthismodel,includingassociativity,distributivity,andvariousidentitiesrelatingtheorderrelationtoadditionandmultiplication.1.IntroductionThelanguageofarithmeticLconsistsoftwoconstants0and1,onebinaryrelation!,andtwobinaryoperations+and×.Inthispaper,wegeneralizeclassicalarithmeticdefinedoverthenaturalnumbersN={0,1,2,...},tothesetFconsistingofallflowgraphs:finitedirectedconnectedmultigraphs1inwhichapairofdistinguishedverticesisdesignatedasthesourceandtargetvertex.WegivenaturalinterpretationforLonthesetF.Toavoidconfusionwiththestandardmodelofarithmetic,thecorrespondingoperationsin1Bymultigraphwemeangraphsinwhichparallelandloopedgesarepermitted.INTEGERS:ELECTRONICJOURNALOFCOMBINATORIALNUMBERTHEORY7(2007),#A122Faredenotedwithacircumscribedcircle.ThenewmodelF=F,0,1,!,+,×#isanaturalextensionofthestandardmodelN=N,0,1,!+,×#.Specifically,weexhibitanembeddingi:Ni!→Fsatisfying:i(0)=0,i(1)=1,∀x,y∈N,x!y⇔i(x)!i(y),∀x,y∈N,i(x+y)=i(x)+i(y),∀x,y∈N,i(x×y)=i(x)i(y).Therehavebeenotherattemptstodefinealgebraicandmetricstructuresonthesetofallgraphs.In[6,2,1],theauthorsusedgraphembeddingstodefineametriconthesetofallsimpleconnectedgraphsofagivenorder.Thisworkdiffersfromthoseinvestiga-tionsinthatitconsidersaninfinitecollectionofgraphsinordertoextendthestandardmodelofarithmetic,andindoingsodoesnotseektoestablishametricstructure.Theclassicaloperationsongraphs[9](includingextensiveliteratureongraphproducts[5])haveyieldedmanyresultsandadeepmathematicaltheory.Therehasalsobeenconsid-erablepriorworkonadditionandmultiplicationofordinalsandpartiallyorderedsets[3,4,7,8].Todate,thesepriorinvestigationshavenotyieldedaninterpretationofthelanguageofarithmeticongraphs.Thispaperpresentsresultsandopenquestionsinthisdirection.2.FlowGraphsDefinition2.1(Flowgraph).WedefineaflowgraphAtobeatriple(GA,sA,tA),whereGA=(VA,EA)isafinite2directedconnectedmultigraphandEAisamultisubsetofVA×VA.Notethatthisdefinitionpermitsparallelandloopedges3.Givenverticesuandv,wedenote(u,v)tobethenumberofedgesfromutov.Individualparalleledgesfromutovwillbereferredtoas(u,v)1,(u,v)2,...,(u,v)i,...,(u,v)!(u,v).However,iftheargumentdoesnotdependonaspecificedgefromutov,thesubscriptwillbedropped–theexpression(u,v)willbeusedtomeananyoneof(possiblymany)paralleledgesfromutov.TheverticessA,tA∈VAarecalledthesourceandthetargetvertexofA,respectively.ThesetofallflowgraphsisdenotedF.Definition2.2(Flowgraphmorphism).LetA=(GA,sA,tA)andB=(GB,sB,tB)betwoflowgraphswithGA=(VA,EA)andGB=(VB,EB).Amapφ:A→Bis2Inthispaper,wefocusonfiniteflowgraphs,althoughmanyofourresultscontinuetoholdintheformulationwhichconsidersinfiniteflowgraphsaswell.3Wesaythattwoedgese1=(u1,v1)ande2=(u2,v2)areparallelifu1=u2andv1=v2.Anedgee=(u,v)iscalledaloopedgeifu=v.INTEGERS:ELECTRONICJOURNALOFCOMBINATORIALNUMBERTHEORY7(2007),#A123calledaflowgraphmorphismif(1)Asamapofvertexsets,φ:VA→VBrespectsedgestructure:e=(u,v)∈EA⇒φ(e)=(φu,φv)∈EB(2)Sourceandtargetarepreserved,i.e.φ(sA)=sB,φ(tA)=tB.AflowgraphmorphismissaidtobeaflowgraphembeddingofAintoBifadditionallyφisinjectiveonbothVAandEA.FlowgraphsAandBareconsideredisomorphicifthereisaflowgraphembeddingφ:A→Bforwhichφ(EA)=EB.Clearly,flowgraphisomorphismdefinesanequivalencerelationonflowgraphs.Inthispaper,weshallonlyconsiderpropertiesofflowgraphswhichareinvariantwithrespecttothisequivalencerelation.Consequently,whendiscussinganequivalenceclassofflowgraphs,wewillconductouranalysisbyrestrictingourselvestoanarbitraryrepresentativefromtheclass.Wheneverwereferto“AflowgraphF”,weshallintend“AnyflowgraphfromtheequivalenceclassofF”,butwewillusetheformerphraseforsuccinctness.Likewise,wewriteA=BforflowgraphstoindicateonlythatAandBareisomorphicasflowgraphs.Definition2.3(Trivialflowgraph).AflowgraphA=(GA,sA,tA)iscalledthetrivialflowgraphif|V[GA]|=1and|E[GA]|=0.Allotherflowgraphsareconsiderednon-trivial.Definition2.4.GivenanyflowgraphA,letA!betheflowgraphobtainedbyswappingthesourceandthetargetofA.Definition2.5(Reflectiveflowgraphs).AflowgraphA=(GA,sA,tA)iscalledanreflectiveflowgraphifA=A!.ThesetofallreflectiveflowgraphsisdenotedH.Definition2.6(Infinitesimalflowgraphs).AflowgraphA=(GA,sA,tA)iscalledaninfinitesimalflowgraphifsA=tA.ThesetofallinfinitesimalflowgraphsisdenotedI.Notethataninfinitesimalflowgraphisnecessarilyreflect