Modelling the continuum @ unwanted capture

Modelling the continuum

Posted May 16, 2009 @ 2:49 pm. spencer 1 Comment »

For my first few blog posts here at unwanted capture, I’m going to talk about a subject that I will return to often: rethinking our mathematical foundations aesthetically. This time, I want to look at our definitions for the continuum; I think that a non-standard approach can give us a cleaner presentation which is closer to our basic intuitions. This has been said before, but most approaches tend to pirate off of existing set theoretic definitions, instead of taking advantage of the added flexibility a non-standard predicate gives us.

We’re all probably familiar with the usual constructions of the real numbers via either cauchy sequences or dedekind cuts. Add to this the theory of limits and we have a foundation sufficient for all the calculus and analysis that we need to do. However, these definitions don’t exactly correspond to our basic intuitions; they’re actually the product of a long struggle to eliminate the infinitesimals of Newton and Leibniz.

Nonstandard analysis (NSA) offers a rigorous approach to these more intuitive methods; let’s briefly recall a sketch of one way the story can go. Using set theoretic techniques (ultraproducts) we embed our existing model $(\mathbb{R},+,\cdot,0,1)$ into nonstandard model $(\mathbb{R}^*,+^*,\cdot^*,0^*,1^*)$ in such a way that

$\mathbb{R}^*\models \varphi^* \iff \mathbb{R}\models \varphi$

for formulas $\varphi$ built from the symbols and constants above (which includes <).

However we can show that there exists an element $x$ smaller than every positive standard real number, and we make this observation the basis of our calculus. The problem with this approach, in my opinion, is that we must first build something which is already good enough to do calculus and then add an extra layer of structure. Instead, I think that we should try to build our continuum directly from a nonstandard model of $\mathbb{N}$ .

This is approach will be easier to develop from a different nonstandard point of view. The important aspects of the semantic description above are also captured by a syntactic approach, where we add a new predicate “ $\textrm{std}$ “. This predicate holds of all the usual numbers $0$ , $2$ , $\frac{2}{7}$ , $\pi$ , but not of the infinites and infinitesimals mentioned above. We must be careful, though, because we are not allowed to form sets using predicates which are built from $\textrm{std}$ , so that some reasonable-looking definitions like $\{x\in\mathbb{R}^*|x\textrm{\ is\ infinitesimal}\}$ are actually nonsense.

Now how does this apply the the natural numbers? Start by assuming the basics of $\mathsf{PA}$ . Now adjoin the $\textrm{std}$ predicate; most of the axioms translate directly because of the transfer principle. This allows us to prove, for instance, that

$\textrm{std}(n)\implies\textrm{std}(n+1).$ However, the induction axiom involves a quantification over predicates, and when we translate via the transfer principle these we change these predicates.

$\begin{array}{rcl} \textrm{std}(0)\ \&\ [\textrm{std}(n)\implies\textrm{std}(n+1)]&\implies&\forall n\in\mathbb{N}\ \textrm{std}(n)\\ &\implies&\forall n\in\mathbb{N}^*\ \textrm{std}^*(n)\\ &\ \ \not\!\!\!\implies&\forall n\in\mathbb{N}^*\ \textrm{std}(n).\end{array}$

Thus we can think of $\textrm{std}$ as a non-inductible predicate. This is particularly useful for capturing a notion of indeterminately bounded computation. For example, if I can count to $n$ , I can probably count to $n+1$ . However, I obviously can’t count to any number; NSA gives us a means of saying that there is a small (practical) infinity of counting numbers contained in the much larger infinity of all numbers.

* * *

So how do we connect this up with the continuum? We want to exploit an analogy which says that $\mathbb{N}$ is like $\mathbb{R}^+$ , because both carry linear orders which are bounded on one side and unbounded on the other. The problem, of course, is that one order is dense while the other is discrete. However, if we think of standard numbers as infinitesimals then this discreteness does not manifest at the macro-scale; say

$n<<n'\iff n<n'\textrm{\ and\ }\neg\textrm{std}(n'-n).$

Then $n<<n'$ implies that $n<<\lfloor\frac{n+n'}{2}\rfloor<<n'$ . Thus any nonstandard model of $\mathsf{PA}$ has a dense linear order lurking inside; this is just the quotient of the original order by the eqivalence relation

$n\sim n'\iff \textrm{std}(|n-n'|).$

The next issue is how we ought to scale this correspondence. It’s obvious that $0\in\mathbb{N}$ corresponds to $0\in\mathbb{R}$ , and that $1\in\mathbb{R}$ must correspond to some nonstandard natural. But which one? Any choice will lead to a sufficient theory, but remember, we are interested in aesthetics here. My suggestion is that we fix a nonstandard $N$ and define $1_\mathbb{R}:=2^N$ (any other base will do just as well). In this theory, the dyadic rationals $\mathbb{D}$ take pride of place over $\mathbb{Q}$ ; these are simply the numbers $\frac{k}{2^{N-n}}$ for standard $n$ .

The algebraic and order relations are almost trivial to define in this framework. Addition in $\mathbb{R}^+$ is exactly the same as that in $\mathbb{N}$ , as is $<$ . Multiplication, on the other hand must be scaled so that $1_\mathbb{R}^2=1_\mathbb{R}$ . Since we expect multiplication to be linear, this forces us to define

$x\cdot_\mathbb{R} y:=\left\lfloor\frac{x\cdot_\mathbb{N} y}{2^N}\right\rfloor.$

We must include the floor operation because $xy$ may not be divisible by $2^N$ ; fortunately, this discrepancy washes out at the large scale. All of the arithmetic facts that we like about $\mathbb{R}$ (commutativity, associativity, distributivity, etc.) follow immediately from the corresponding laws in $\mathbb{N}$ , although some may be fuzzy in the sense that they hold only up to $\sim$ -equivalence.

I think I’m going to leave it here for the moment. I hope everyone will at least agree that this is a satisfactory definition for the continuum. In my next post I’ll come back to this topic and say why I think this is a preferable method. Any guesses?

philosophy of mathematics continuum, nonstandard analysis, philosophy of mathematics, real numbers

You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

1 Comment »

Edward Dean says:

May 18, 2009 at 10:43 pm

Nice first post, Spencer.

It is clear that your syntactic approach to the continuum differs from Nelson’s pioneering internal set theory, since his shares with semantic approaches a main feature you wish to avoid: that of starting with a perfectly serviceable $\mathbb{R}$ and adding nonstandard reals on top. On the other hand, Jeremy Avigad’s syntactic approach in Weak theories of nonstandard arithmetic and analysis (15 ff.) already avoids this.

Roughly, we have a theory whose variables are intended to range over $\mathbb{N}^*$ ; then $\mathbb{Z}^*$ and $\mathbb{Q}^*$ are defined as expected. From there, $\mathbb{R}$ is defined to be those members of $\mathbb{Q}^*$ which are bounded, i.e. which have standard ceilings, so avoiding any talk of some $\mathbb{R}^*$ . Beauty is in the eye of the beholder, of course, but I find this way of doing things aesthetically pleasing.

Now nothing about Jeremy’s setup addresses the particular kind of aesthetic appeal you seem to be after when, say, making a very deliberate choice for your $1_{\mathbb{R}}$ ; I look forward to seeing what beauty you intend to extract. I am wondering (while not knowing exactly what you want to get out of this) whether the effect you ultimately want could also be got while starting off in the manner just described, rather than building $\mathbb{R}$ as you do in the post?

Reply

M	T	W	T	F	S	S
« Apr				Jun »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Modelling the continuum

1 Comment »

Leave a Reply

tag cloud

calendar

of interest

categories

meta