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.

Improve this question
$\endgroup$
4
  • $\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, 2011 at 16:02
  • $\begingroup$ @SureshVenkat: I do not think that it has ever become a site policy. $\endgroup$
    – Tsuyoshi Ito
    Oct 30, 2011 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, 2011 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, 2011 at 19:20

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hence the truism, "Everything is a graph." $\endgroup$
    – Aaron Sterling
    Oct 25, 2011 at 14:07
  • 7
    $\begingroup$ You're a graph. $\endgroup$
    – Dave Clarke
    Oct 25, 2011 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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