First Order interpretation of arbitrary structures as a graph
-
31-10-2019 - |
문제
I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph".
Given some arbitrary relational structure $S$ of some vocabulary $\sigma$, show that there are first-order queries $I$ and $I^{-1}$, such that $G:=I(S)$ is a directed graph, and $I^{-1}(G)$ is isomorphic to $S$.
I would be grateful for some hints and proof ideas, as I struggle a bit with seeing how the encoding would work.
올바른 솔루션이 없습니다
제휴하지 않습니다 cs.stackexchange