10
$\begingroup$

I was told once that there is a theory consisting of just a pairing function that is stable, although I cannot find a reference for it. This motivated my question, which is essentially the title, although really a simpler question should be asked first:

Is there an expansion of $(\mathbb{N},<)$ by a pairing function that is still nice in the sense of neo-stability?

Obviously it can't still be o-minimal or dp-minimal, but in principle it could be NIP. Assuming a positive answer to that question it's natural to ask how much more structure is compatible with 'niceness,' hence the question in the title:

Is there an expansion of $(\mathbb{N},+,<)$ by a pairing function that is still NIP?

I'm primarily interested in the theory of the expansion being NIP, rather than the weaker notion of the structure itself being NIP, as introduced by Khanaki and Pillay, although I would be interested in that if the harder question has a negative answer.

EDIT: I recently learned a relevant result of Cegielski and Richard from this paper, the structure $(\mathbb{N},<,c)$, where $c$ denotes the standard Cantor pairing function $c(x,y)=\frac{1}{2}(x+y)(x+y+1)+x$, defines addition and multiplication, so is of course not NIP.

Improve this question
$\endgroup$
6
  • $\begingroup$ By a pairing function on $X$, you mean an injective function $X\times X\to X$? Do you require subjectivity? $\endgroup$
    – Alex Kruckman
    Commented Nov 6, 2018 at 15:21
  • $\begingroup$ I was originally thinking a bijection but if it's possible with a strictly injective function I'd be interested in that too. $\endgroup$
    – James E Hanson
    Commented Nov 6, 2018 at 15:54
  • $\begingroup$ Adding the pairing function $(x,y)=x+2^{x+y}$ retains decidability, so that is promising. $\endgroup$
    – user44143
    Commented Nov 6, 2018 at 16:42
  • $\begingroup$ Do you have a source for that? $\endgroup$
    – James E Hanson
    Commented Nov 6, 2018 at 16:47
  • $\begingroup$ Francoise Point, On the Expansion $(N,+,2^x)$ of Presburger Arithmetic, logique.jussieu.fr/~point/papiers/Pres.pdf. The function in her title is interdefinable with the pairing function I suggested. $\endgroup$
    – user44143
    Commented Nov 6, 2018 at 17:36

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .