1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Oct 26 '11 at 16:02
  • $\begingroup$ @SureshVenkat: I do not think that it has ever become a site policy. $\endgroup$ – Tsuyoshi Ito Oct 30 '11 at 13:04
  • $\begingroup$ @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 $\endgroup$ – Suresh Venkat Oct 30 '11 at 16:59
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 30 '11 at 19:20
5
$\begingroup$

If you look at things from a model-theoretic 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.

$\endgroup$
  • $\begingroup$ Hence the truism, "Everything is a graph." $\endgroup$ – Aaron Sterling Oct 25 '11 at 14:07
  • 7
    $\begingroup$ You're a graph. $\endgroup$ – Dave Clarke Oct 25 '11 at 14:49
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.