Timeline for Deciding isomorphism between graphs which interpret in the pure set
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 13, 2016 at 8:52 | history | edited | Szymon Toruńczyk | CC BY-SA 3.0 |
Modified the question so that it talks about graphs rather than arbitrary structures. Added a link to my post concerning this problem.
|
| Feb 23, 2016 at 12:29 | comment | added | Szymon Toruńczyk | 6) Finally, it seems that the corresponding isomorphism problem regarding structures which interpret in $(\mathbb Q,\le)$ may be difficult. Indeed, in the paper "Structures coordinatized by indiscernible sets", Lachlan considers a special case of structures which interpret in $(\mathbb Q,\le)$, and remarks that he doesn't know how to decide isomorphism between them (end of page 255, beginning of 256). Sure, $(\mathbb N,=)$ is different from $(\mathbb Q,\le)$, but one would have to exploit this difference (both have quantifier elimination, are ultrahomogeneous). | |
| Feb 23, 2016 at 12:28 | comment | added | Szymon Toruńczyk | 4) The infinite Kneser graph K(∞,2) interprets in the pure set: the vertices are two-element subsets of $\mathbb N$, and the edges join two such subsets if they are disjoint. 5) An example of a pair of graphs which is not trivial to distinguish is the Kneser graph and the disjoint union of two copies of it. (One is connected, of diameter ≤3, and the other is not, so there is a first order formula distinguishing them). | |
| Feb 23, 2016 at 12:28 | comment | added | Szymon Toruńczyk | Here are a couple of simple observations concerning the problem. 1) If a structure interprets in the pure set with parameters, then it is also definable without parameters. 2) Structures which interpret in the pure set are closed under disjoint unions, cartesian products, infinite, definable unions or intersections. 3) To decide the above isomorphism problem, it is sufficient to consider graphs. | |
| Feb 23, 2016 at 2:46 | answer | added | Joel David Hamkins | timeline score: 2 | |
| Feb 22, 2016 at 22:09 | history | edited | Szymon Toruńczyk | CC BY-SA 3.0 |
added 54 characters in body
|
| Feb 22, 2016 at 22:04 | history | asked | Szymon Toruńczyk | CC BY-SA 3.0 |