Structure Theory of Graphs

Working in mono-sorted first order logic, add primitives of equality and its axioms, set membership ∈ , a partial ternary relation →  denoting is the direction from to, and at last a total unary function S  dentoing the "structure" of.

Axioms for sets:

Extensionality: ∀x∀y (∀z(z∈x⟺z∈y)⟹x=y)

Membership: x∈y⟹∀z∈x(z=x)

Atomicity: ∀x∃y:y∈x

Comprehension:  

[∃y(y={y}∧ϕ)]⟹∃x∀y (y∈x⟺y={y}∧ϕ);

for every formula ϕ in which x is not free. 

Axioms about direction:

Naturality: →(x,a,b)⟹x,a,b are singletons  

Uniqueness: →(x,a,b) ∧→(y,c,d)⟹

[x=y⟺(a=c∧b=d)]

Incompatibility axioms:

Define: node(a)⟺∃x∃b:→(x,a,b) ∨→(x,b,a)

Define: arrow(x)⟺∃a∃b:→(x,a,b)

Dichotomy: node(a)⟹¬arrow(a)

Duality: a={a}⟹node(a)∨arrow(a)

Axioms about size:

Definitions:

A graph is a set closed under node-hood. That is, all nodes connected by arrow elements of it are elements of it.

A scatter is a set of nodes only.

The scatter of a graph is the set of all of its nodes.

"Nodes" is the set of all nodes.

A graph is to be called small if and only if its scatter is strictly subnumerous to Nodes.

Where "strictly subnumerous" is defined in the cusmtomary manner after existence of injections only in one direction.

Two graphs are said to be separate if there is no arrow connecting a node from one of them to a node in the other.

A graph is continuous if and only if it's not the set union of two separate graphs.

Axioms:

Infinity: There is a small infinite graph.

Define [moiety]: A moiety of a graph is a maximal continuous subgraph of that graph. That is, no continuous subgraph of that graph exists that contains it as a proper subgraph of.

Power: for every small graph there exists a small power graph.

The power graph of G  is one whose moieties are isomorphic to subgraphs of G , having no two moieties being isomorphic to each other, and where every subgraph of G  is isomorphic to some moiety of it.

Inaccessibility: The small fusion of small separate graphs is small.

In other words if a graph have less many moieties than the nodes in Nodes, and each moiety is small, then that graph is small too.

Axioms about structure:

Abstraction: ∀ graphs x,y:x≈y⟹S(x)=S(y)

Canonicity: ∀ graph x:S(x)≈x

Define: x≈y⟺∃f:f is isomorphism from x to y

Where:

f is isomorphism from x to y⟺f is a bijection  from scatter(x) to scatter(y)∧∀a,b∈x[(∃k∈x:→(k,a,b))⟺∃l∈y:→(l,f(a),f(b))]

Separateness: ∀ small moieties G,H:S(G) disjoint S(H)

Axioms about choice:

Choice: for every graph G , there exists a scatter graph that contains exactly one node from each moiety of G .

The above structure theory does interpret ZFC and actually MK. The category of all sets of ZFC is definable as the set of all structures of small extensional mono-rooted trees with finitely long branches, plus all arrows between those structures including the identity arrows over their nodes. By *extensional* tree, it's meant that no node of it can have two distinct isomorphic maximal subtrees stemming from it. The set membership relation of ZFC can be defined over those structures as structures of maximal subtrees whose root nodes are those connected to the root node of the main tree directly through arrows. So it does provide an explication about sets and their membership in the standard sense of ZFC. I believe also that the category of all small categories can as well be defined here in almost straightforward manner. So, this theory can serve as a natural foundation of both Set and Category theory.

Can we regard such a theory as a Candidate for a foundational theory of mathematics?

-----------------------------------------------

Technical detail about size expressions:

The ϕ -cardinality of x  is the number of ϕ parts of x , this occurs when any two parts of x  satisfying ϕ  are separate [disjoint]. Now this is determined by existence of a one-to-one relation R  from ϕ  parts of x  to nodes of a scatter k , that is, all arrows in R  that are sent from nodes of x  to an element j  of k  all of them come from nodes in a single ϕ  part of x , and of course for every node of k  there is an arrow in R that comes from a node of x to it, and to assure the one-to-one genre we must have distinct nodes in k  having nodes beloning to distinct ϕ  parts in x  with arrows coming from those to them. Now the ϕ -cardinality of x , symbolized by |x|ϕ  would be equal in this case to |k| .

More generally, if we have a binary relation Q  and an object x , then |x|Q is the cardinality of all objects that bear the relation Q  to x  provided that all those objects are separate! This would have the same above definition we only replace the relation partby Q .

Now we'll define cardinality generally as the structure of a scatter graph, and so it reflects how many nodes are there in scatter graphs. So formally

Define:|x|=y⟺scatter(x)∧y=S(x)

So the node-cardinality of any graph is defined as:

|x|node=y⟺∃k∃R:scatter(k)∧R:scatter(x)→k∧R is a bijection ∧|k|=y  

This will boil down to:

|x|node=|scatter(x)| 

Now

|x|moiety=y⟺∃k∃R: 

scatter(k)∧ R is one-to-one from moieties of x to nodes of k∧y=|k| 

The last two size axioms can be written as:

Power:  

|x|nodes<|Nodes|  ⟹  |x|substructure<|Nodes|

Inaccessibility:  

|x|moiety<|Nodes|

∧∀y:y moiety of x→|y|nodes<|Nodes|

⟹

|x|nodes<|Nodes| 

This theory about structures, defined as abstractions over isomorphic graphs, can interpret Set Theory in a rather creepy manner. Though the theory is largely technical, yet it is not far from being intuitive about graphs and their structure. This shows that formalization about graphs and their related structure, can constitute a more versatile formal system in which mathematics can be ingrained. In Set theory the main concepts at interplay are those of Hierarchy, order, and size. While here all of those are there, and in addition we have concepts of simplicity, continuity, circularity, and structural complexity via branching, loops, etc.. So, on the face of it, it appears to be a richer formal notion! Actually sets, numbers, shapes, etc.. all can be easily interpreted as structures of certain kind of graphs. So, in the context of this rivalry, the question is about the relative interpretability of this method in set theory. 

**$\frak Structure \ Theory$:** 

**Language:** first order logic 

**Primitives:** "$=$"; "$ \varepsilon $" ; "$:  \rightharpoondown $ "; "$\frak S$", read as: "is equal to" and "is a rudimentary element of", " is a directed edge from -to-", and "is the structure of". The last is a partial unary function.

Whenever "set" is mentioned here it refers to the rudimentary kind of sets presented here. While set in the sense of Set Theory, would be phrased as $\sf ZFC$ set, $\sf NF$ set, etc.. after the theory characterizing it.

The idea is to define structures as abstractions from isomorphic graphs. So, two graphs receive the same structure if and only if they are isomorphic to each other. Where the latter is a bijection between the set of nodes of each graph that preserves the edges.

I. Axioms about Equality: **ID** axioms.

II. Axioms about rudimentary membership:

II.a: **(Extensionality)** $\forall z \, (z \ \varepsilon \ x \leftrightarrow z \ \varepsilon \ y ) \to x=y$

II.b: **(Elements)** $\forall x \exists y: y \ \varepsilon \ x$

Define: $\operatorname {elm}(y) \iff \exists x: y \ \varepsilon \ x$

II.c: **(Flatness)** $x \ \varepsilon \ y \land y \neq x \to \neg \ y  \ \varepsilon \ z$

II. d: **(Comprehension)** $ \exists y: \operatorname {elm}(y) \land \phi(y) \\ \implies \\ \exists x \forall y \, (y \ \varepsilon \ x \iff \operatorname {elm}(y) \land \phi(y))$

Define: $x=[y \mid \phi] \iff \forall y \, (y \ \varepsilon \ x \leftrightarrow  \operatorname {elm}(y) \land \phi)$

Theorems: $x \ \varepsilon \ y \to x=[x] \\ x =[y] \to x=y$

Define: $\operatorname {atom}(a) \iff a=[a]$

III. Axioms about Edges:

III. a: **(Directionality)** $x: a \rightharpoondown b \land y: c \rightharpoondown d \implies (x=y \iff (a=c \land b=d))$

III. b: **(Simplicity)** $\forall x\forall a \forall b \, (x:a \rightharpoondown b \implies x,a,b \text{ are atoms})$

Define: $\operatorname {Node}(a) \iff \exists b \,\exists x \, (x: a \rightharpoondown b \lor x:b \rightharpoondown a)$

Define: $\operatorname {Edge}(x) \iff \exists a \exists b \, (x: a \rightharpoondown b)$

III.c: **(Dichotomy)** $\operatorname {Node}(a) \to \neg \operatorname {Edge}(a)$

III.d **(Edges)** $\forall \operatorname {Nodes} a,b \exists x \exists y \, (x: a \rightharpoondown b \land y:b \rightharpoondown a) $

Define *Graph* as a set where the nodes of every edge in it are in it.

IV. Axioms about structures

IV.a: **(Domain)** $\forall X \, (\exists a: a= \mathfrak S(X) \iff \operatorname {Graph}(X))$

IV.b: **(Abstraction)** $\forall \operatorname {Graphs}   G ,F: \mathfrak S(G) = \mathfrak S(F) \iff G \sim F$  

IV.c: **(Structures)** $\forall  G :  \operatorname {atom} (\mathfrak S(G))  $

IV.d **(Freedum)** $\forall G:  \operatorname{Node}(\mathfrak S(G)) \downarrow \operatorname {Edge}(\mathfrak S(G))$

$\sim$ stands for graphical "isomorphism" defined as: $$ G \sim F \iff \exists \operatorname {bijection} f \, (f: \operatorname {Nodes}_G \to \operatorname {Nodes}_F \land\\ \forall \operatorname {Nodes} a,b \ \varepsilon \ G \, (\exists x \ \varepsilon \ G \, (x: a \rightharpoondown b) \iff \exists y \ \varepsilon \ F \, (y: f(a) \rightharpoondown f(b))))$$

Where $\operatorname {Nodes}_X$ is the set of all nodes of graph $X$.

Relations and various kinds of functions can be implemented as sets of edges under the known qualifications.

V. Axioms about Graphs

V.a:  **(Nodes)** $\forall \operatorname {scg} G \exists a: \operatorname {Node}(a) \land \neg \ a \ \varepsilon \ G$

Where, "$\operatorname {scg}$" stands for "simple continuous graph".

**Define:** a set $S$ of structures of continuous graphs is said to be *actuated*, if and only if, there exists a discrete graph $D$ whereby for each structure $\mathfrak s \ \varepsilon \ S$ there is a single unit $d$ of $D$ such that $\mathfrak s = \mathfrak S(d)$

V.b: **(Actuation)**  a set $S$ of structures of continuous graphs, is actuated if any of the following is met:

 - Its elements can be arranged in a continuous linear manner.

 - All its elements are substructures of a simple continuous graph.

 - There is one-to-one correspondence with a set of nodes of a simple continuous graph. 

Definitions:

 - A graph is *simple* if no more than one edge can occur between any two nodes of it.

 - Two graphs are connected if and only if a node of one graph is connected by an edge to a node of the other graph.

 - Two graphs are separate if they are not connected.

 - A *continuous* graph is one that is not the union of two separate graphs, otherwise it's *discrete*.

 - A subgraph is a subset of a graph that is a graph.

 - A *unit* $d$ of a discrete graph $D$ is a continuous subgraph of $D$ that is separate from $D \setminus d$.

This theory interprets $\sf ZFC$ through structures of well-founded (no infinite path), extensional (no isomorphic terminal subtrees stem from the same node), mono-rooted, accessible (no node of degree greater than the first inaccessible) trees.  

There is another way in which this can be done. We can dopt a size criterion, so we define actuatable cardinalities. So a cardinal $\kappa$ is actuatable if there is a set $S$ whose cardinality is $\kappa$ and such that $S$ can be actuated. Now we add axioms that any set $S$ of continuous structures: if the cardinality of $S$ is actuatable, then $S$ can be actuated. Also we add the axiom that if the cardinality of graph $G$ is $\kappa$ and $\kappa$ was an actuatable cardinal, then the set of all structures of continuous subgraphs of $G$ can be actuated. Infinity can be axiomatized by stipulating the existence of an infinite cardinal $\kappa$ that is actuatable! This way we also get ZFC to be interpreted!!!

ANOTHER version that depends on extensional trees for actualtion is:

**Language:** first order logic 

**Primitives:** "$=$"; "$ \varepsilon $" ; "$:  \rightharpoondown $ "; "$\frak S$", read as: "is equal to" and "is a rudimentary element of", " is a directed edge from -to-", and "is the structure of". The last is a partial unary function.

Whenever "set" is mentioned here it refers to the rudimentary kind of sets presented here. While set in the sense of Set Theory, would be phrased as $\sf ZFC$ set, $\sf NF$ set, etc.. after the theory characterizing it.

The idea is to define structures as abstractions from isomorphic graphs. So, two graphs receive the same structure if and only if they are isomorphic to each other. Where the latter is a bijection between the set of nodes of each graph that preserves the edges.

I. Axioms about Equality: **ID** axioms.

II. Axioms about rudimentary membership:

II.a: **(Extensionality)** $\forall z \, (z \ \varepsilon \ x \leftrightarrow z \ \varepsilon \ y ) \to x=y$

II.b: **(Elements)** $\forall x \exists y: y \ \varepsilon \ x$

Define: $\operatorname {elm}(y) \iff \exists x: y \ \varepsilon \ x$

II.c: **(Flatness)** $x \ \varepsilon \ y \land y \neq x \to \neg \ y  \ \varepsilon \ z$

II. d: **(Comprehension)** $ \exists y: \operatorname {elm}(y) \land \phi(y) \\ \implies \\ \exists x \forall y \, (y \ \varepsilon \ x \iff \operatorname {elm}(y) \land \phi(y))$

Define: $x=[y \mid \phi] \iff \forall y \, (y \ \varepsilon \ x \leftrightarrow  \operatorname {elm}(y) \land \phi)$

Theorems: $x \ \varepsilon \ y \to x=[x] \\ x =[y] \to x=y$

Define: $\operatorname {atom}(a) \iff a=[a]$

III. Axioms about Edges:

III. a: **(Directionality)** $x: a \rightharpoondown b \land y: c \rightharpoondown d \implies (x=y \iff (a=c \land b=d))$

III. b: **(Simplicity)** $\forall x\forall a \forall b \, (x:a \rightharpoondown b \implies x,a,b \text{ are atoms})$

Define: $\operatorname {Node}(a) \iff \exists b \,\exists x \, (x: a \rightharpoondown b \lor x:b \rightharpoondown a)$

Define: $\operatorname {Edge}(x) \iff \exists a \exists b \, (x: a \rightharpoondown b)$

III.c: **(Dichotomy)** $\operatorname {Node}(a) \to \neg \operatorname {Edge}(a)$

III.d **(Edges)** $\forall \operatorname {Nodes} a,b \exists x \exists y \, (x: a \rightharpoondown b \land y:b \rightharpoondown a) $

Define *Graph* as a set where the nodes of every edge in it are in it.

IV. Axioms about structures

IV.a: **(Domain)** $\forall X \, (\exists a: a= \mathfrak S(X) \iff \operatorname {Graph}(X))$

IV.b: **(Abstraction)** $\forall \operatorname {Graphs}   G ,F: \mathfrak S(G) = \mathfrak S(F) \iff G \sim F$  

IV.c: **(Structures)** $\forall  G :  \operatorname {atom} (\mathfrak S(G))  $

IV.d **(Freedum)** $\forall G: \neg \operatorname {Edge}(\mathfrak S(G))$

$\sim$ stands for graphical "isomorphism" defined as: $$ G \sim F \iff \exists \operatorname {bijection} f \, (f: \operatorname {Nodes}_G \to \operatorname {Nodes}_F \land\\ \forall \operatorname {Nodes} a,b \ \varepsilon \ G \, (\exists x \ \varepsilon \ G \, (x: a \rightharpoondown b) \iff \exists y \ \varepsilon \ F \, (y: f(a) \rightharpoondown f(b))))$$

Where $\operatorname {Nodes}_X$ is the set of all nodes of graph $X$.

Relations and various kinds of functions can be implemented as sets of edges under the known qualifications.

V. Axioms about Graphs

V.a:  **(Involvement)** $ \operatorname {scg} G \to \operatorname {Node}({\frak S} (G))  $

Where, "$\operatorname {scg}$" refers to "simple continuous graph". 

**Define:** a set $S$ of structures of continuous graphs is said to be *actuated*, if and only if, there exists a discrete graph $D$ whereby for each structure $\mathfrak s \ \varepsilon \ S$ there is a single unit $d$ of $D$ such that $\mathfrak s = \mathfrak S(d)$

V.b: **(Actuation)**  a set $S$ of structures of continuous graphs, is actuated  if there is one-to-one relationship with a set of substractures of a mono-rooted extensional tree.

A tree is extensional if no distinct terminal trees stemming from the same node in the tree can be isomorphic. 

 Definitions:

 - A graph is *simple* if no more than one edge can occur between any two nodes of it.

 - Two graphs are connected if and only if a node of one graph is connected by an edge to a node of the other graph.

 - Two graphs are separate if they are not connected.

 - A *continuous* graph is one that is not the union of two separate graphs, otherwise it's *discrete*.

 - A subgraph is a subset of a graph that is a graph.

 - A *unit* $d$ of a discrete graph $D$ is a continuous subgraph of $D$ that is separate from $D \setminus d$.

An upgrade of this method is to allow trivial edges in a tree, those are the edge from a node to itself, what can be called as a trivial loop. This what I'd call as "loop trees". So, the axiom of Involvement would be changed to the structure of every loop tree is a node. The axiom scheme of Actuation to be changed to be about loop trees also. 

This way we get straightforwardly a theory that freely construct these loop trees. And I think it would be a powerful tool.