Structure Theory

Structure theory    is a theory that aims at constructing structure from the simplest possible to the more complex. Atoms (objects with no proper parts) are taken to be the simplest possible structure, rules of composition of more complex structure from atoms are laid down, the simplest are those of General Extensional Atomic Mereology. Scatter graphs (edgeless graphs), linear graphs (paths), and then trees are contemplated. Here what is presented is an account of constructing mono-rooted single edged graphs with special emphasis on trees and forests of them, and its connection to interpreting set theory.

 Language: To the language of Mereology, we add a three place relation symbol "fromto", written as:  fromto(k,a,b) and read as: k from a to b. 

Define: Node(a) iff Exist k,b: fromto(k,a,b) or fromto(k,b,a) 

Define: Edge(k) iff Exist a,b: fromto(k,a,b). 

As a terminology:for the case of fromto(k,a,b), b shall be called the end node of edge k, and  a is the issuing node of edge k. Also k is said to stem from a and to head on b. 

AXIOMS:

Axioms of General Extensional Atomic Mereology + 

Basic axioms about nodes and edges: 

1.ATOM-HOOD: fromto(k,a,b) -> k,a,b are atoms 

2.UNIQUENESS: fromto(k,a,b) ^ fromto(k,c,d) -> a=c ^ b=d 

A Graph is: a totality of nodes or of nodes and edges between them, i.e. a graph is a totality where every edge in it must have its nodes in it also.

A discrete graph is a graph that is a fusion of two disjoint graphs.

A continuous graph is a non discrete graph. 

A Path is a continuous graph such that for every node of it there can be maximally one edge stemming from it and one edge heading to it that are parts of that graph.

A path between nodes a and b is a path containing a and b as parts of, that doesn't have a proper part of it that is a path containing nodes a and b as parts of.

A Cyclic path is a path between a node and itself.

A single edged graph is a graph for which there do not exist two nodes in it having two edges in it between them in the same direction. 

A mono-rooted graph is a graph having one node that is not an ending node of an edge in this graph. This node is called the root node. 

Mono-rooted single edged graphs are denoted as MRSEG. 

A moiety of a discrete graph is a continuous sub-graph of it that is not a proper part of a continuous sub-graph of it. 

Isomorphism between graphs A and B is defined by existence of a totality K of edges stemming from all nodes of A to all nodes of B such that no node of A is connected to different nodes of B by them and no node of B is connected from different nodes of A by them, and such that every two edges k1,k2 of K that stem from a1,a2 nodes of A heading to nodes b1,b2 of B: an edge exists in A from a1 to a2 if and only if an edge exists in B from b1 and b2. 

A tree is a MRSEG continuous graph having no cyclic paths.

A forest is a discrete graph of trees, i.e. all moieties of it are trees. 

A forest is heterogeneous iff every two distinct moieties of it are not isomorphic.

Structural axioms: 

I.  EXTENSIONALITY: There exists a heterogeneous forest such that for any tree t whatsoever there exists a moiety m of that forest such that m is isomorphic to t. 

Let's fix a specific witness F for the above existential quantification. 

II. POWER: Any sub-forest F* of F for which there exists a tree T such that for every moiety m of F* there exists a part t of T such that m is isomorphic to t, then there exists a tree with its root node having edges stemming from it to all root nodes of moieties of F*. 

III. FUNCTIONALITY: if Phi is an injective function formula then there exists a graph composed of the domain of phi linked by single edges to the range of phi as determined by formula phi (i.e. if node x in the domain of phi and node y in range of  phi fulfills phi(x,y)  then there exist a SINGLE edge from x to y in that graph).

phi is an injective function formula if the following is true 

For all a,b,c,d: phi(a,b) phi(c,d) -> [a=c <-> b=d] 

The domain of phi is the totality of all x such that there exist y: phi(x,y) 

The range of phi is the totality of all y such that there exist x: phi(x,y) 

/ Theory definition finished. 

Interestingly those simple structural rules can interpret ZF in a straightforward manner. We can have the above three structural rules working over all continuous MRSEGs and not just over trees, but the above axioms were stipulated in terms of trees just to interpret set theory. 

Clearly the interpretation of set theory is for sets to be moieties of F, the membership relation x in y would be defined as x being isomorphic to a maximal sub-tree of y having  its root node being the end node of an edge steaming from the root node of y. 

Actually to interpret ZF we only need the well founded sector of F, i.e. those moieties of F that are isomorphic to parts of iterative powers of the empty moiety of F, (which is the moiety of F that is composed of a single atom). 

The point is that non of the above rules necessitates a prior understanding of ZF or of an extension of ZF. It can be directly stipulated as an extension of the very weak General Extensional Atomic Mereology, and all the other aspects about definitions of types of graphs continuity, isomorphism, etc..are pretty much naive and begs no prior understanding of set theory whatsoever. The first and last structural axioms are purely motivated on structural grounds coming from envisioning graphs, however the second rule which is the power rule have some connection intuitively speaking to set theory since it informally simulates the power set axiom, although here it raises from the endeavor of building continuous graphs by re-assembling parts of simpler continuous graphs, which seems to have some structural motivation native to this method itself. 

The whole theme here is about observing "Continuity and Discreteness of Single Edged Graphs", in the attempt of stepwise construction of complex graphs from simpler ones.

Seeing that set theory can be interpreted easily in that theme is to some extent interesting. 

Zuhair 

18/12/2015

 addendum (Jan 6/2016):

Another version of this method is to stipulate that there exists a heterogeneous discrete graph F such that:

1) BREAKING: Every part of a moiety of F has an isomorphic copy of it that is a moiety of F.

2) COMBINING: for any subgraph F* of F if there exist a moiety m of F such that every moiety of F* is isomorphic to some part of m, then there exists a moiety of F that is isomorphic to a graph composed of a root node linked by edges to root nodes of all moieties of F*.

3) LINKING: same as axiom of functionality above but without emphasis on edges being single, and provided that both the domain and range of phi being subgraphs of F, and with the assertion that if the resulting graph is continuous then there exists an isomorphic copy of it that is a moiety of F.

/ Theory definition finished.

Here this version simulates the stepwise build up of ZF, and it is not dependable on graphs being single edged, and of course it is more general since it applies to all kinds of continuous graphs, trees or not, single edged or not, Cyclic or Acyclic, however they must have some distinguished nodes, like root nodes, or like principal nodes, i.e. those having parths stemming from them to to all nodes in the graph along the same direction.

It is important to modify the definition of power of a cyclic graph as to cover all possible cyclic versions of subgraphs of it, so for a graph F if there is a subgraph G of it that has n many principal nodes then there would exist n isomorphic disjoint copies of G in the power graph of F where the root node of the power graph sends an edge to a principal node of each of those copies that is different from that sent to the other copies, so for example if G has three principal nodes  a,b,c, then we'll have three copies G_1,G_2,G_3 of G and let's denote a_i, b_i, c_i  for i=1,2,3 for the copy nodes of a,b,c of G where each node belongs to the i_th copy of G respectively, so here the Power graph of F would have a root node n and the G_i graphs among its parts with edges stemming from n to a_1 of G_1 and to b_2 of G2 and to c_3 of G_3.  Although the G_i's are isomorphic copies of G, but cyclicity can induce many principal nodes and that changes information conveyed to those nodes, so we need to cover all those cyclic versions as to be included in powering of graphs. I think this last version that only take into consideration continuity versus discreteness and principality of nodes in graphs, I think this version has more expressive power than that of the first one presented in the head of this article, since Categories can be interpreted as special kinds of cyclic continuous graphs, so this version of structure theory can cover both Trees and thus set theory and cyclic graphs and thus Category theory, and also perhaps other kinds of structure, it can do that directly without the need to interpret Categories in Trees, or Sets in special cyclic graphs. And that's one of the reasons why I think this theory to better serve as the Foundational Theory of Mathematics.

Structure Theory has a CLEAR subject matter, that of studying node edge structures (i.e. graphs) from the simplest possible, going to the next complex, then the next and so on.. It doesn't have any mysterious notion whatsoever and all axioms of it clearly stem from that endeavour in a naive and flawless manner. Unlike Set Theory, for although it has the "very easy to work with" technical primitive of epsilon membership and although it does have axioms that technically speaking do easily come into attention when exploring different possible set systems, yet neither membership nor the axioms of set theory enjoys a simple conceptual understanding. The best trial to understand membership conceptually is the one posed by David Lewis in his book "Parts of Classes", which refers understanding sets to simple Mereological principles like the ones posed here and to a Singleton function, and acknowledges explicitly that the nature of the singleton function is shrouded in Mystery and therefore couldn't manage to provide a conceptual justification for major set theory axioms of ZF; as a salvage he resorted to the idea of axioms following a size concept, yet he couldn't justify the particulars of that size concept, so at the end no clear conceptual justification of axioms of set theory as springing from a simple conceptual understanding of the set membership relation could be arrived, at least in Parts of Classes, which reflects the difficulty encountered with conceptual understanding of the set principles, and so although Set Theory does enjoy a nice and naively looking nature and definitely a technically easy to work with primitives and axioms, however conceptually speaking it proves extremely hard to fathom. Nothing of this is present with this method. Technically speaking Structure Theory as presented here looks more complex than Set Theory, but definitely it enjoys simpler conceptual understanding and clearer subject matter, and it does clarify some rather difficult to understand aspects of set theory like Russell's paradox, cyclical membership, the possibility of nondefinable sets, violation of Extensionality, etc... Also the technicalities involved here are not that complex, and given its clearer display of structure, it would be more beneficial in investigating complex structural aspects. All of that makes me think that the ultimate theory of mathematics would be a theory about graphs on top of a trivial Mereological base, with simple axiom rules, like the theories posed in this thread.

Another version,

Possibly a simpler version is to stipulate two types of edges: a relational edge and a structural edge, either type of an edge between any two nodes is unique (so it acts like an ordered pair), we stipulate that a relational edge exists between any two nodes, but that is not necessarily so for structural edges. Our primary objects would be the structural graphs (i.e. node-structural edge mereological collections), relational edges serves to define relations between structural graphs. Relational edges are symbolized by dotted arrows while structural edges by solid arrows, so L:A..>B means L is a relational edge from A to B while L:A->B means L is a structural edge from A to B. And then the axioms of Uniqueness, Breaking, Combining and Linking are added: the first states that no two distinct free structural graphs (i.e. moieties) are isomorphic to each other, the second states that every sub-graph of a structural graph has a free moiety that is isomorphic to it. The third states that for every structural graph there is a power structural graph, the fourth states that for every continuous combined graph F (i.e. has both kinds of edges in it) that is a relation graph between parts of two structural graphs (whether discrete or continuous) X,Y such that F is an injective function from X to Y, there is a structural graph that is isomorphic to it. The nice thing is that graphs here are nicer, all of them are single edged and Extensionality clearly applies to the forest of all free trees in a direct manner, and we immediately have a the free copy of any graph, moreover the linking axiom can be imagined as converting relations to structural graphs, a kind of hardening or solidifying relations into objects much similar to extending relations in terms of sets, since relational graphs gives the impression of having light parts in them which are the relational edges, those are hardened to structural edges in the asserted copies, this is done cautiously since otherwise it clearly leads to paradoxes. This method can be extended to apply to all continuous graphs as long as they have some kind of distinquished nodes, for example principal nodes as explained above, although this leads to more copying of the same graph in the power graph as explained above, this would cover reasoning about cyclical graphs. Actually we can follow the same method to have it applicable not to just single edged graphs but to those that have multiple edges between there nodes as well, so it is generalized to any continuous graph.

 If one contemplates extending some finite properties of graphs to the infinite graph realm then very strong Large cardinal axioms would result in, like Ramsey cardinals and the alike.

 Zuhair