Timeline for Definability of arithmetic functions and relations
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 19, 2014 at 17:54 | review | Close votes | |||
| Aug 19, 2014 at 23:09 | |||||
| Aug 19, 2014 at 16:15 | comment | added | Joel David Hamkins | It is a good exercise to prove that if one relation is definable in a structure from another, then it would have to be invariant under all automorphisms of the structure. From this, it follows that if an operation is not invariant by an automorphism of a structure, then it cannot be definable in that structure. Thus, neither addition $+$ nor $<$ nor successor nor mod are definable from multiplication in $\mathbb{N}$, since they are not invariant by all the automorphisms of $\langle\mathbb{N},\cdot\rangle$ induced by permuting the primes. | |
| Aug 19, 2014 at 16:03 | comment | added | Hans-Peter Stricker | @Joel: What do you think my (hand-waving) argument that $+$ cannot be re-defined by $\times$ has to do with the (correct) automorphism argument? | |
| Aug 19, 2014 at 15:57 | comment | added | Hans-Peter Stricker | What I wanted to ask: Do I have to proof this case by case or can it be derived from the fact that $+$ can not be re-defined from $\times$, and that $<$ and successor can be re-defined from $+$. | |
| Aug 19, 2014 at 15:52 | comment | added | Joel David Hamkins | Regarding your addendum, the automorphisms of $\langle\mathbb{N},\cdot\rangle$ also do not preserve $<$ and successor, so those operations are also not definable from $\cdot$. | |
| Aug 19, 2014 at 15:42 | history | edited | Hans-Peter Stricker | CC BY-SA 3.0 |
added 206 characters in body
|
| Aug 19, 2014 at 15:34 | comment | added | Hans-Peter Stricker | By the way: is the rest of my exposition correct, so far? | |
| Aug 19, 2014 at 15:30 | comment | added | Hans-Peter Stricker | Thanks, Joel. The problem was that I actually did not make the observation. Now that I have done, I see much clearer. | |
| Aug 19, 2014 at 15:24 | comment | added | Joel David Hamkins | and I see now that Andreas has added an answer with that observation at just the same time.... | |
| Aug 19, 2014 at 15:24 | vote | accept | Hans-Peter Stricker | ||
| Aug 19, 2014 at 15:23 | comment | added | Joel David Hamkins | I'm not sure I understand your question, but could you clarify it in connection with the observation that $+$ is not definable in the structure $\langle\mathbb{N},\cdot\rangle$? This is because the latter structure has many automorphism (permute the primes and extend) that do not respect $+$. | |
| Aug 19, 2014 at 15:23 | answer | added | Andreas Blass | timeline score: 4 | |
| Aug 19, 2014 at 15:13 | history | edited | Hans-Peter Stricker | CC BY-SA 3.0 |
edited body
|
| Aug 19, 2014 at 14:33 | history | asked | Hans-Peter Stricker | CC BY-SA 3.0 |