<p>If you look at things from a <a href="http://en.wikipedia.org/wiki/Model_theory" rel="nofollow">model-theoretic</a> perspective, the basic ingredients you have are atoms, relations, and functions. Atoms could be modelled using nodes of the graph, and binary relations and single argument functions could be modelled using graphs. If you are willing to allow hyper-edges in your graph, then the remainder of the relations and functions can be modelled. </p>

<p>I don't think that there is anything deep to this observation.</p>

CC BY-SA 3.0
2011-10-25T14:07:13.850Z
Hence the truism, "Everything is a graph."
Aaron Sterling
CC BY-SA 3.0
2011-10-25T14:49:39.647Z
You're a graph.
Dave Clarke
CC BY-SA 3.0
2011-10-25T08:01:52.677Z
2011-10-25T08:01:52.677Z
Dave Clarke
<p>I would like to add to Dave Clarke's answer. The binary relations are sufficient to express higher-arity relations and functions (by adding new non-logical symbols if necessary). Hence, if you allow multiple directed edges, which can take on different colors, then this is already sufficient to encode any $L$-structure. Furthermore, this encoding can be described in a first-order way.</p>

CC BY-SA 3.0
2011-10-26T11:52:43.837Z
2011-10-26T11:52:43.837Z
David Harris
<p>I know this could be considered a pointless question. However despite I am quite convinced that any possible model (i.e. UML, SysML, natural language, math, etc.) can be defined by means of a graph I do not know if there is a way to formally prove there exist an isomorphism between the set of Models and the set of Graphs.</p>

<p>I guess one should first define what a model is and I guess a possible answer is that a model can be considered as a sentence of the language defined by its meta-model. Thus models are languages. The question is therefore if there is an isomorphism between the set of languages and the set of graphs or, less formally, if it is provable that any possible language can be represented by means of a graph. I guess that the Chomsky works on languages could help but I can not find a reference on the Internet of such demonstration.</p>

CC BY-SA 3.0
2011-10-26T16:02:24.893Z
Please add a comment when you downvote. This will help the original poster improve the question and make it more useful for the community. This is also our [site policy](http://meta.cstheory.stackexchange.com/questions/1264/conventions-on-downvoting/1272#1272).
Suresh Venkat
CC BY-SA 3.0
2011-10-30T13:04:59.633Z
@SureshVenkat: I do not think that it has ever become a site policy.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-30T16:59:21.540Z
@TsuyoshiIto: It came up in a community-wide townhall chat a while back as a major irritant, and the mods agreed to encourage people to leave comments so as to improve the question/answer being downvoted
Suresh Venkat
CC BY-SA 3.0
2011-10-30T19:20:45.793Z
@SureshVenkat: I think that it is silly to call something a “policy” just because the moderators agree that it is a major irritant, but do whatever you like.
Tsuyoshi Ito
<graph-theory><formal-modeling><language-design><model-theory>
Any Graph is a Model (! or ?)
Andrea Sindico
# Any Graph is a Model (! or ?)

(Asked by: username_0 on 2011-10-25)

I know this could be considered a pointless question. However despite I am quite convinced that any possible model (i.e. UML, SysML, natural language, math, etc.) can be defined by means of a graph I do not know if there is a way to formally prove there exist an isomorphism between the set of Models and the set of Graphs.

I guess one should first define what a model is and I guess a possible answer is that a model can be considered as a sentence of the language defined by its meta-model. Thus models are languages. The question is therefore if there is an isomorphism between the set of languages and the set of graphs or, less formally, if it is provable that any possible language can be represented by means of a graph. I guess that the Chomsky works on languages could help but I can not find a reference on the Internet of such demonstration.

**Tags:** graph-theory, formal-modeling, language-design, model-theory

> **Comments:**
> **username_1**: Please add a comment when you downvote. This will help the original poster improve the question and make it more useful for the community. This is also our [site policy](http://meta.cstheory.stackexchange.com/questions/1264/conventions-on-downvoting/1272#1272).  
> **username_2**: @SureshVenkat: I do not think that it has ever become a site policy.  
> **username_1**: @TsuyoshiIto: It came up in a community-wide townhall chat a while back as a major irritant, and the mods agreed to encourage people to leave comments so as to improve the question/answer being downvoted  
> **username_2**: @SureshVenkat: I think that it is silly to call something a “policy” just because the moderators agree that it is a major irritant, but do whatever you like.  

---

## 2 answers

### Answer by username_3 on 2011-10-25. Score: 5 | Accepted answer

If you look at things from a [model-theoretic](http://en.wikipedia.org/wiki/Model_theory) perspective, the basic ingredients you have are atoms, relations, and functions. Atoms could be modelled using nodes of the graph, and binary relations and single argument functions could be modelled using graphs. If you are willing to allow hyper-edges in your graph, then the remainder of the relations and functions can be modelled.

I don't think that there is anything deep to this observation.

> **Comments:**
> **username_4**: Hence the truism, "Everything is a graph."  
> **username_3**: You're a graph.  

---

### Answer by username_5 on 2011-10-26. Score: 3

I would like to add to username_3's answer. The binary relations are sufficient to express higher-arity relations and functions (by adding new non-logical symbols if necessary). Hence, if you allow multiple directed edges, which can take on different colors, then this is already sufficient to encode any $L$-structure. Furthermore, this encoding can be described in a first-order way.


---

