Timeline for Deciding isomorphism between graphs which interpret in the pure set
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 23, 2016 at 12:42 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 198 characters in body
|
| Feb 23, 2016 at 12:36 | comment | added | Szymon Toruńczyk | I think it's good to leave this answer, as it makes perfect sense, but only solves a part of the problem. This is in accordance with this suggestion: meta.mathoverflow.net/questions/2323/…. | |
| Feb 23, 2016 at 11:56 | comment | added | Joel David Hamkins | Vote up this comment if I should delete the answer. | |
| Feb 23, 2016 at 11:56 | comment | added | Joel David Hamkins | @AlexKruckman Yes, you are right. This answer applies only to quotients of $\mathbb{N}$, rather than of $\mathbb{N}^d$, and so it doesn't answer the question. | |
| Feb 23, 2016 at 6:14 | comment | added | Alex Kruckman | On each piece, there is a subset $I\subseteq \{1,\dots,d\}$ of relevant coordinates and a subgroup $\Sigma$ of the group of permutations of $I$ such that $x\sim y$ if and only if $\bigvee_{\sigma\in\Sigma} \bigwedge_{i\in I} x_i = y_{\sigma(i)}$. It should be straightforward to computably put the definitions of $X$ and $\sim$ into this normal form. | |
| Feb 23, 2016 at 6:13 | comment | added | Alex Kruckman | In trying to make a direct approach like this work, it might be useful to note the following characterization of definable equivalence relations in the language of pure equality: Let $A$ be a finite set of parameters, let $X\subseteq \mathbb{N}^d$ be an $A$-definable set, and let $\sim$ be an $A$-definable equivalence relation on $X$. Among the $d$-tuples in $X$, finitely many complete types over $A$ are realized (by QE, these are determined by equalities $x_i = x_j$ and $x_i = a$ with $a\in A$), so $X$ splits into finitely many pieces, one for each type. | |
| Feb 23, 2016 at 6:02 | comment | added | Alex Kruckman | Your answer assumes that the domain of the interpretation is a quotient of a definable subset of $\mathbb{N}$, but in general it might be a quotient of a definable subset of $\mathbb{N}^d$. This makes the question less trivial. | |
| Feb 23, 2016 at 4:00 | history | undeleted | Joel David Hamkins | ||
| Feb 23, 2016 at 4:00 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
This answer answers the question; my previous answer had mis-interpreted the question
|
| Feb 23, 2016 at 2:54 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
deleted 784 characters in body
|
| Feb 23, 2016 at 2:53 | history | deleted | Joel David Hamkins | via Vote | |
| Feb 23, 2016 at 2:46 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |