6
$\begingroup$

There are constructions, at least in ZFC, that produce non-standard elementary extensions of the semiring of natural integers $\mathbb{N}$. (those models may not be definable in the language of set theory)

Are there methods or heuristics to prove that a given semiring is a non-standard model of $\mathcal{T}(\mathbb{N})$ when said semiring doesn't directly come from the above alluded constructions?

Are there examples of such strange encounters?

I am not looking for a general algorithm that would confirm (or infirm for that matter) that a semiring is such a model, because the fact that $\mathcal{T}(\mathbb{N})$ is not recursively enumerable makes this unlikely. I am rather looking for examples or partial methods if there are.

$\endgroup$
7
  • $\begingroup$ Are you poketrainer or just remember old good a wild .... appeared? If you are poketrainer, please give me your vortex-deluge nickname, so I can trade you and battle you. $\endgroup$
    – nikola
    May 30, 2017 at 19:24
  • $\begingroup$ "A wild model of T(N) appears…" thanks for the laugh :D $\endgroup$
    – Zonko
    May 30, 2017 at 19:25
  • $\begingroup$ I did not expect the "MathStackExchange community" to be that reactive to classic pokemonfare! Unfortunately nikola, I am but another pokemon-unrelated student. $\endgroup$
    – nombre
    May 30, 2017 at 19:43
  • 1
    $\begingroup$ $\Bbb{N}$ isn't a ring, so I don't understand your question. $\endgroup$
    – Rob Arthan
    May 30, 2017 at 21:02
  • 2
    $\begingroup$ So... you're asking for which techniques are super effective? $\endgroup$
    – user14972
    May 30, 2017 at 21:46

1 Answer 1

Reset to default
5
$\begingroup$

I can't speak to heuristics (and I suspect very little is known there - these are very complex and rare semirings!), but here's one surprising appearance of a nonstandard model of true arithmetic:

A set is Dedekind-finite if it has no nonsurjective self-injections (equivalently, if it has no countably infinite subset). With the axiom of choice, Dedekind-finiteness is the same as finiteness; however, in the absence of choice this is not true. And the equivalence can fail spectacularly - for instance, by having amorphous sets, which are infinite sets which cannot be partitioned into two infinite pieces!

With choice, the cardinalities are well-behaved (in particular, linearly ordered); without choice, they can be extremely messy. So it's interesting to ask what kind of nice behavior is compatible with having bad "pseudo-finite" sets?

Specifically, we can ask the following question:

Is it consistent with ZF that there are infinite Dedekind-finite sets, and that the set of Dedekind-finite cardinalities is linearly ordered?

That last clause just means that given any two Dedekind-finite sets $A$ and $B$, either $A$ injects into $B$ or $B$ injects into $A$.

Sageev showed, in a technical and difficult paper, that the answer is yes; but for our purposes, the interesting result is earlier and due to Ellentuck: that in such a model, the set of Dedekind-finite cardinalities (together with disjoint union and Cartesian product) forms a nonstandard model of true arithmetic! Put another way, models of set theory satisfying some mild-seeming cardinal arithmetic axioms turn out to have distinguished nonstandard models of arithmetic!

A neat corollary of this is that in ZF, if the Dedekind-finite cardinalities are linearly ordered then there are no amorphous sets; this can be proved by invoking, for instance, the fact that every natural number is either even or odd! And I don't know an easy way to explicitly build two incomparable Dedekind-finite sets from an amorphous set, so I don't think this is as silly a nuke as it may seem.

To me this is completely surprising, especially given that the definition of the model is so simple. And my understanding is that Ellentuck's result was quite surprising in general; in his own paper, Sageev refers to the result as "astonishing," and mentions that its proof uses basically all of the combinatorial results developed in Ellentuck's thesis from twelve years earlier. Ellentuck's paper is titled "A model of arithmetic," and was published in the Bulletin of the Polish Academy of Science (at least I think; the citation in Sageev's paper is to "Bull. Acad. Polon. Sci.") in 1974, but I have sadly not been able to find a copy of it online.

Interestingly, the overall structure of the "Ellentuck models" of arithmetic seems potentially rich but not yet well-understood; see this question of mine. (It's also worth noting that Sageev's proof of his result required an inaccessible, but it is not known whether that is necessary.)

$\endgroup$
18
  • $\begingroup$ I will say that I strongly believe that Sageev's paper can be greatly simplified using my method of iterated symmetric extensions. This is what he's doing there anyway, so it moves all the technical difficulties to the framework. Someday I might sit through the details. $\endgroup$
    – Asaf Karagila ♦
    May 30, 2017 at 20:10
  • $\begingroup$ To clarify my comment in the italicized paragraph, if $A$ is amorphous then it "seems obvious" that the sets $E$ and $O$ of finite subsets of $A$ with even and odd cardinality, respectively, are incomparable Dedekind-finite sets; however, proving this seems difficult to me, although I could be missing something. $\endgroup$
    – Noah Schweber
    May 30, 2017 at 20:10
  • $\begingroup$ @AsafKaragila You mentioned this in a comment to my question, I think - I'm very interested in that! Your paper is towards the top of my reading list (way too much on that list unfortunately ...). $\endgroup$
    – Noah Schweber
    May 30, 2017 at 20:11
  • $\begingroup$ It's a dense and difficult paper, and I have tried to make it readable, at least to myself. There was a point that I worked on trying to get Sageev's result in this framework. I managed to get some way through, but there was still some way left to go. Maybe I'll pick this up over the summer. We'll see... $\endgroup$
    – Asaf Karagila ♦
    May 30, 2017 at 20:17
  • $\begingroup$ Thank you for this great answer. I leave the question open in case someone has ideas for the heuristics part. Seing as I am a newbie to forcing (thanks to Asaf Karagila, I at least understand the basics of it), I doubt I would understand the consistency result, even after this summer! But understanding Ellentuck's work would be great, do you have ideas as to why the linearity of the ordering yields everything else? $\endgroup$
    – nombre
    May 30, 2017 at 20:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .