24
$\begingroup$

I have in mind something like the following:


Start with some suitable version of "finite" mathematics. Some possibilities might be maybe ZFC with a suitable anti-infinity axiom, the topos $\mathbf{FinSet}$, Peano arithmetic, Turing machines... something whose objects are suitably "finite".

Then, posit the existence of both a standard and a non-standard model.

Now, in this setting, where we have access both to a standard model and a non-standard extension, use the non-standard objects as proxies for infinite objects (e.g. maybe some sort of set theory that has a set of natural numbers), and develop ordinary mathematics this way.


Has anybody worked on such a thing? Does anyone know of references of it being done? Or suggestions that it can't work out?

(P.S. I wasn't sure how to tag this....)


Edit: After more thought and reviewing the answers thus far, I think I can state an example of the sort of thing i was imagining. Define a first-order theory with two types $T_1$ and $T_2$, two binary relation symbols $\in_1, \in_2$ (one for each sort), and a map $\tau : T_1 \to T_2$ satisfying:

  • $(T_1, \in_1)$ satisfies the axioms of finite set theory
  • $(T_2, \in_2)$ satisfies the axioms of finite set theory
  • $\tau$ is injective
  • $\tau$ is not surjective
  • $\tau$ satisfies an axiom schema that says it's an elementary embedding

and the question is to what extent we can develop infinite set theory in this theory.

$\endgroup$
3
  • $\begingroup$ Regarding your edit, it would seem simpler to get rid of the map $\tau$ and regard $T_1\subset T_2$. Thus, what you have is the theory: finite set theory for $\in$ and a predicate $T$ such that not everything is in $T$, but $\langle T,\in\upharpoonright T\rangle$ also satisfies finite set theory. $\endgroup$ Mar 4, 2012 at 19:42
  • $\begingroup$ Plus the elementarity scheme $\forall \vec x\in T\ \varphi(\vec x)\leftrightarrow\varphi^T(\vec x)$. $\endgroup$ Mar 4, 2012 at 19:43
  • $\begingroup$ Do you want $T_1$ to be transitive in $T_2$? That is, can $T_2$ have new members of some $\tau(x)$? Transitivity would mean: $\forall x,y\ y\in \tau(x)\rightarrow \exists z\ y=\tau(z)$. In my suggested system, this amounts to saying that $T$ is a transitive class. $\endgroup$ Mar 4, 2012 at 20:00

4 Answers 4

14
$\begingroup$

The standard system of a first-order model of Peano Arithmetic works in this way.

The standard model $\mathbb{N}$ is an initial segment of every nonstandard model $\mathcal{M}$. Pick a nonstandard element $w$ of $\mathcal{M}$. The binary expansion of numbers in $\mathcal{M}$ below $2^w$ define nonstandard binary strings of length $w$. For each such $x$, there corresponds a subset $X$ of $\mathbb{N}$ where a standard number $n$ belongs to $X$ if and only if the $n$-th bit of $x$ is $1$. The collection of all these sets $X$ is called the standard system $\mathrm{SSy}(\mathcal{M})$ of $\mathcal{M}$. This standard system is always a Scott set, so it can be used to form a standard model of second-order arithmetic where the weak König lemma is true. The structure of the first-order model $\mathcal{M}$ dictates a lot of the properties of this second-order model.

Similar constructions can be done in different contexts, but this is surely the most common one.

$\endgroup$
4
  • 1
    $\begingroup$ Ah, this sounds like the sort of thing I was looking for, and you give keywords to search on! Can you name any references for it? $\endgroup$
    – user13113
    Mar 3, 2012 at 20:23
  • 2
    $\begingroup$ Jerry Keisler has been exploiting this idea for reverse mathematics (see Nonstandard Arithmetic and Recursive Comprehension, APAL 161 (2010), 1047-1062). Ali Enayat uses this technique a lot: academic2.american.edu/~enayat I think the idea goes back to Dana Scott, but I don't have a handy reference. $\endgroup$ Mar 3, 2012 at 20:53
  • 1
    $\begingroup$ Scott proved that every countable Scott set, that is, an algebra of subsets of $\mathbb{N}$ closed under Turing reducibility and containing paths through (coded) trees, is the standard system of a nonstandard model of PA. This was later extended by Knight and others to Scott sets of size $\omega_1$, but it is open in general (when CH fails) whether every Scott set is the standard system of a model of PA. $\endgroup$ Mar 3, 2012 at 20:59
  • 2
    $\begingroup$ I think I get it now. And $\mathop{\text{SSy}}(\mathcal{M})$ can be defined in the setting I described, because I can define a binary relation on ${}^\star\mathbb{N}$ (viewed as sets) by $a \sim b$ iff $\forall n \in \mathbb{N}: n \in a \Leftrightarrow n \in b$. So, the $\sim$-equivalence classes of ${}^\star\mathbb{N}$ are the first-order predicates. And I could iterate: define $a \sim_2 b$ to be $\forall n \in {}^\star\mathbb{N}: (\exists c \in a : c \sim_1 n) \Leftrightarrow (\exists c \in b : c \sim_1 n)$ to get third-order logic. etc for M-order logic for any (external) natural number. $\endgroup$
    – user13113
    Mar 4, 2012 at 16:01
27
$\begingroup$

For another route to the phenomenon, consider the following theorem of Ressayre, which has always both fascinated and mystified me. Indeed, I find the conclusion a bit alarming and perhaps even bizarre, precisely because it seems to be a too-strong fulfillment of your requested phenomenon.

Theorem. If ${\cal M}=\langle M,\hat\in\rangle$ is a nonstandard model of finite set theory, such as the natural model arising from a nonstandard model of PA, and if $T$ is any consistent computably axiomatizable extension of ZF, such as ZFC or ZFC+$\exists$ supercompact cardinal, then there is a submodel $N\subset M$ such that ${\cal N}=\langle N,\hat\in\rangle$ is a model of $T$.

That is, even though $\cal M$ is a model of finite set theory, it has a substructure realizing the infinitary theory of ZFC or much more. In this way, the theorem fulfills your request, since we are enabled to find within the nonstandard finite part of the model a fully accurate copy of the infinitary set theory. The amazing thing, to me, is that we can do so in such a flexible way so as to realize large cardinals or any other consistent set theory.

Ali Enayat explains some of the details in his answer to Mirco Mannucci's question Set theory inside arithmetics via the Ackerman yoga, citing J. P. Ressayre, Introduction aux modèles récursivement saturés, Séminaire Général de Logique 1983–1984 (Paris, 1983–1984), 53–72, Publ. Math. Univ. Paris VII, 27, Univ. Paris VII, Paris, 1986.


Update (11/20/2012).

My paper Every countable model of set theory embeds into its own constructible universe contains the following strengthening of Ressayre's theorem:

Theorem. If ${\cal M}$ is any nonstandard model of PA, then every countable model of set theory is isomorphic to a submodel of $\langle\text{HF}^{\cal M},{\in}^{\cal M}\rangle$. Indeed, this structure is universal for all countable acyclic binary relations.

Here, $\text{HF}$ refers to the natural model of finite set theory defined inside $\cal M$, the hereditary finite sets as coded in $\cal M$. The relation $\in^{\cal M}$ is the Ackerman relation, so that $n\in^{\cal M} m$ just in case the $n$ th bit in the binary expansion of $m$ is $1$.

This theorem eliminates the role of the theory $T$ in Ressayre's theorem, for not only do we get merely at least one model of $T$ as a submodel of $\cal M$, but indeed every countable model of $T$ arises as a submodel.

The point now---and the reason I look upon this as relevant for your question---is that any given countable model of ZFC, even one satisfying a very strong theory, can be found as a submodel of any given nonstandard model of the strictly finitary theory $\text{ZFC}^{\neg\infty}$, which thinks every set is finite. So this is exactly a situation where we have an entire universe of infinite mathematics arising precisely as a form of nonstandard finite mathematics.

$\endgroup$
4
  • $\begingroup$ +1 for being an answer to the implied question "... or tell me something similar that I'd be interested in". However, I'm a little skeptical of how to "find" the copy of infinitary set theory -- specifically, I'm skeptical that you can find just from first-order logic, the two models, and the transfer principle. Wouldn't you need to step out into the ambient set theory to find the model and prove things about it? $\endgroup$
    – user13113
    Mar 4, 2012 at 16:43
  • $\begingroup$ Although I take the theorem as a theorem about nonstandard models formalized in the usual ZFC framework, I believe that one can view the construction as finding the model of $T$ inside $\cal M$ essentially by a "forth" construction, using the amount of saturation that is available. Thus, one can seem to carry it out in any context where one has the standard model, the theory $T$ and the model $\cal M$, plus the ability to construct a model of $T$ and elementary arithmetic reasoning. I'm not sure whether your system can do this, mainly because I don't really understand what your system is. $\endgroup$ Mar 4, 2012 at 17:42
  • $\begingroup$ I wasn't entirely sure what my system was either. But now I think I have a better idea of what I was trying to conceive, and have edited my post to reflect it. $\endgroup$
    – user13113
    Mar 4, 2012 at 18:42
  • 1
    $\begingroup$ Yes, your edited question is something like what I described. I think that we can do the Ressayre construction in that system, but I will have to think more carefully about it. Perhaps someone else who knows can post about it... $\endgroup$ Mar 4, 2012 at 19:49
6
$\begingroup$

You might want to look into the work of Vopenka and his collaborators on what they call alternative set theory. The formal theory looks a bit strange, since it allows proper classes to be subclasses of sets, but one interpretation of the theory is that the sets are the internal sets of a nonstandard model of finite-set-theory while the classes are arbitrary (not necessarily internal) subsets. There's a small book, "Mathematics in the Alternative Set Theory," by Vopenka, that should serve as a good introduction to the subject.

$\endgroup$
1
  • $\begingroup$ "allows proper classes to be subclasses of sets" - now that doesn't look strange at all to a constructivist. $\endgroup$ Mar 4, 2012 at 6:12
4
$\begingroup$

Update: I looked a bit more into it. It seems that IST is still a system of ZFC, and therefore infinite. So this isn't what you are looking for.

I'm not positive, but I think this is similar to Nelson's internal set theory. There is an AMS Bulletin article (Internal set theory: A new approach to nonstandard analysis) on it that I have been meaning to read. Again, I haven't read it so I am not certain.

While you wanted all of mathematics, Nelson also has a treatment of probability theory (Radically Elementary Probability Theory), which I believe works by starting with finite probability theory and gets infinite probability theory through nonstandard models. (Again, this is on my to-read list, so I am not certain.)

$\endgroup$
2
  • $\begingroup$ I am a little familiar with internal set theory, but it's not what I'm asking about. And while the philosophical idea that the standard part is just the bit accessible by finite humans, it is still a theory of infinite mathematics. I'm curious about the basic theory is finite-oriented, and infinite ideas arise from the byplay between the standard and non-standard models. $\endgroup$
    – user13113
    Mar 3, 2012 at 20:06
  • $\begingroup$ @Hurkyl @Jason In IST one can prove that 1) if all elements of a set S are standard, then S is finite, and 2) for any set T there exists a finite subset F of T containing all standard elements of T. (the notion of "finite", and the natural numbers, are exactly the same in IST as they are in ordinary set theory). So there is a sense in which IST does look like finite mathematics with non-standard stuff on the top. $\endgroup$
    – M T
    Mar 5, 2012 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.