Killing infinites and using computables instead of reals

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

FrancovS
Posts: 59
Joined: Fri Apr 16, 2010 1:47 am UTC

Killing infinites and using computables instead of reals

Postby FrancovS » Sat Jul 24, 2010 7:56 pm UTC

Well, first of all, I would like to note that I don't have a formal education in real analysis and set theory, so if you think I am abysmally wrong about something, you probably didn't misunderstand me.

So here we go: assume I broke up with set theorists and ZFC, and I decided to do math in a more constructive way. I forbid actual infinites (so you can't deal with infinite sets - the concept of "infinite" now is treated only as a property) and do all my math with computable numbers (defined by epsilon approximations, not decimal expansions). My questions are: does this approach have any consistency issue? Which branches of math am I maiming by making theorems impossible to prove?

edahl
Posts: 61
Joined: Wed May 13, 2009 12:15 pm UTC

Re: Killing infinites and using computables instead of reals

Postby edahl » Sat Jul 24, 2010 8:23 pm UTC

I'm not sure if I understand you correctly, but I think you just killed the natural numbers.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11034
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Killing infinites and using computables instead of reals

Postby Yakk » Sat Jul 24, 2010 8:52 pm UTC

Bishop and Bridges, Constructive Analysis rebuilds much of basic analysis from a constructive approach.

This doesn't eliminate infinities -- the natural numbers exist, and are an infinite set. However, all real numbers are infinitely long cauchy sequences which can be computably evaluated at any point (and the rate of convergence is bounded above).

One of the side effects of using constructive logic is that !! (as in, not not) does not collapse into nothing. Ie, not not P(x) is a different statement than P(x). However, !!! collapses to !, so not not not P(x) is the same as P(x).

But all classical results are provable in constructive mathematics with a bunch of nots thrown about in such a way that if it was classical mathematics, the extra nots would evaporate.

Still, the truths end up differing. And you can do a bunch of neat things with extensions of constructive mathematics that don't work in classical (ZFC) mathematics.

The simplest one is the IVT (intermediate value theorem), which states that if you have a continuous function f:[0,1]->R, with f(0) < 0 and f(1) > 0, then there is a point a in (0,1) such that f(a) = 0.

In constructive mathematics, the statement is more along the lines of if you have a continuous function f:[0,1]->R with f(0) < 0 and f(1) > 0, then for all epsilon > 0 you can find a real number a from (0, 1) such that |f(a)| < epsilon.

I think I got that right? Anyhow, with basic analysis in classical ZFC you can reduce that to the same statement as the classical version by simply creating a sequence of {a_n} with each corresponding to an epsilon of 1/n. As we have an infinite sequence in a compact set, there is a subsequence {a_n_j} that converges to some value x. Then by continuity, you can show that f(x) = 0.

But in constructive mathematics you cannot do that, because among other things finding that convergent subsequence isn't constructive.

I'm sure if you go deeper you end up with other strange differences. But basic analysis mostly works, within epsilon.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

radams
Posts: 88
Joined: Fri May 14, 2010 12:49 pm UTC

Re: Killing infinites and using computables instead of reals

Postby radams » Sat Jul 24, 2010 10:17 pm UTC

There are a large number of different schools of thought in mathematics, with different ideas on which definitions and proofs are valid, and different formal systems have been created to try to capture their principles.

There are two main axes: which logic do you accept?

[*] Classical logic - the type all maths undergraduates are taught; and

[*] Constructive logic - excluded middle ([imath]P \vee \neg P[/imath]) does not hold for every [imath]P[/imath]. A proof of [imath]P \vee Q[/imath] must provide a method of deciding which of [imath]P[/imath] or [imath]Q[/imath] is true. A proof of [imath]\exists x P(x)[/imath] must provide a method for constructing a value of [imath]x[/imath] such that [imath]P(x)[/imath] is true.

And which forms of definition are valid?

[*] Impredicativism - the way the vast majority of mathematicians work.

[*] Predicativism - impredicative definitions are ruled out. This means you may not quantify over all sets when defining a set; you may not quantify over all real numbers when defining a real number; etc.

[*] Finitism - infinite sets do not exist, and neither do functions with infinite domain. Natural numbers exist, and we can talk about algorithms on natural numbers (say by talking about Turing machines), but we can't talk about the set of natural numbers; an arbitrary subset of the natural numbers; or an arbitrary function on the natural numbers.

[*] Ultrafinitism - very large objects do not exist. For example, the numbers [imath]10^{10^{100}}[/imath] or [imath]2^{65536}[/imath] do not exist. Yeah, ultrafinitism has never been very popular, but it's never quite gone away either.

All eight combinations of the above have been held by some people through history, and they all still exist today. There are many sub-branches and fine divisions within each one, too.

Classical impredicative maths is by far the most popular; after that, constructive impredicative and constructive predicative maths still have quite large followings, especially within computer science. It's fun to watch the sparks fly when they get together at a conference. The only thing they agree on is that classical mathematicians are wrong.

FrancovS, it sounds like you want to know about finitism. That's never been a big player, so not an enormous amount has been written on it; there isn't really a good introductiory book.

The formal system Primitive Recursive Arithmetic (PRA) is often taken to capture classical finitistic mathematics. It's equivalent to the system you get if you take Peano Arithmetic but only allow induction over quantifier-free formulas.

Reuben Goodstein developed an enormous amount of mathematics in a finitistic way, especially in his books "Recursive Number Theory" and "Recursive Analysis".

To answer your questions: PRA is a subsystem of Peano Arithmetic, so there's no consistency issues. You maim every branch of mathematics - that is, there will be theorems in every branch that cannot be proved finitistically, but I can't tell you any more detail than that.

epsilon-delta
Posts: 8
Joined: Sat Jul 24, 2010 1:45 am UTC

Re: Killing infinites and using computables instead of reals

Postby epsilon-delta » Sun Jul 25, 2010 6:58 am UTC

Not allowing yourself to deal with infinite sets is going to be incredibly limiting, to say the least. In fact, you'll be able to say very little that's actually interesting (and very little about interesting topics), since almost all nontrivial cases are going to rely on an infinite set. Since you can't define a real number without an infinite set, you're not going to be able to talk about real analysis at all (and since you're barring infinites, you're out of luck when it comes to the extended line which is also quite useful). Considering only finite cases is also going to make topological spaces very uninteresting. An open set will be identical to a closed set (since we can never have infinitely many open sets in the first place, we must conclude that only finite unions of open sets are open), all spaces will be compact (since there can't be infinitely many open sets in a cover in the first place, every space that is covered would have a finite subcover, namely the cover in question), and the list goes on. I'm not exactly sure what your goal is in eliminating infinity. Does something about the concept of an infinite set make you uncomfortable?

User avatar
antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Killing infinites and using computables instead of reals

Postby antonfire » Sun Jul 25, 2010 6:38 pm UTC

epsilon-delta wrote:In fact, you'll be able to say very little that's actually interesting (and very little about interesting topics), since almost all nontrivial cases are going to rely on an infinite set.
You can do plenty of mathematics finitistically. Sometimes just need to phrase it somewhat differently. Combinatorics barely suffers at all. Elementary number theory works out. Computer science does just fine too. You seem to have a rather limited idea of what math can be interesting.

Hell, you can still say things like "1/n goes to 0 as n goes to infinity". It just means the usual thing: For every positive (rational) epsilon, there is an N such than when n > N, |1/n| < epsilon. You can't actually define the predicate P(a,L) which says "a_n goes to L as n goes to infinity", since presumably infinite sequences aren't objects in your theory, but hell, we say stuff like "the ordinals are well-ordered" all the time even though the ordinals aren't an object in ZFC.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Aiwendil42
Posts: 133
Joined: Mon May 17, 2010 8:52 pm UTC

Re: Killing infinites and using computables instead of reals

Postby Aiwendil42 » Sun Jul 25, 2010 7:39 pm UTC

Impredicativism - the way the vast majority of mathematicians work.


Really? I don't know much about the foundations of mathematics, but I thought that impredicativism was basically killed by Russell's Paradox. Or do you just mean that most mathemeticians don't worry about such things in practice?

radams
Posts: 88
Joined: Fri May 14, 2010 12:49 pm UTC

Re: Killing infinites and using computables instead of reals

Postby radams » Sun Jul 25, 2010 8:30 pm UTC

Impredicativism - the way the vast majority of mathematicians work.




Really? I don't know much about the foundations of mathematics, but I thought that impredicativism was basically killed by Russell's Paradox. Or do you just mean that most mathemeticians don't worry about such things in practice?


Nope. ZFC is an impredicative system. When we define a set using a Comprehension Axiom

[math]A = \{x \in B : \phi\}[/math]

the formula [imath]\phi[/imath] might involve quantification over all sets. A predicativist would not like that, because you're quantifying over a collection that includes [imath]A[/imath] before [imath]A[/imath] has been defined.

Russell believed that the solution to his paradox was to go predicative, and Principia Mathematica was a predicative system, but that wasn't the route that mainstream mathematics ended up following.

epsilon-delta
Posts: 8
Joined: Sat Jul 24, 2010 1:45 am UTC

Re: Killing infinites and using computables instead of reals

Postby epsilon-delta » Sun Jul 25, 2010 9:34 pm UTC

antonfire wrote:
epsilon-delta wrote:In fact, you'll be able to say very little that's actually interesting (and very little about interesting topics), since almost all nontrivial cases are going to rely on an infinite set.
You can do plenty of mathematics finitistically. Sometimes just need to phrase it somewhat differently. Combinatorics barely suffers at all. Elementary number theory works out. Computer science does just fine too. You seem to have a rather limited idea of what math can be interesting.

Hell, you can still say things like "1/n goes to 0 as n goes to infinity". It just means the usual thing: For every positive (rational) epsilon, there is an N such than when n > N, |1/n| < epsilon. You can't actually define the predicate P(a,L) which says "a_n goes to L as n goes to infinity", since presumably infinite sequences aren't objects in your theory, but hell, we say stuff like "the ordinals are well-ordered" all the time even though the ordinals aren't an object in ZFC.



Perhaps I'm misunderstanding the OP's intention by
I forbid actual infinites (so you can't deal with infinite sets -
, but I took it to mean that he is barring the existence of infinite sets as a whole. And if you don't have an infinite set, you can't go very far, since, in order to even have a natural number n in the first place in your example, we need to have an infinite set, namely N, from which we can draw.

User avatar
antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Killing infinites and using computables instead of reals

Postby antonfire » Sun Jul 25, 2010 9:39 pm UTC

You might as well say that to talk about sets we need to have a set of all sets from which we can draw.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Killing infinites and using computables instead of reals

Postby Syrin » Sun Jul 25, 2010 10:04 pm UTC

epsilon-delta wrote:And if you don't have an infinite set, you can't go very far, since, in order to even have a natural number n in the first place in your example, we need to have an infinite set, namely N, from which we can draw.


Take nothing - that is, take the empty set. Now, take the set containing the empty set. You now have the numbers 0 and 1, without saying anything about the set N of natural numbers.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: Killing infinites and using computables instead of reals

Postby achan1058 » Mon Jul 26, 2010 12:02 am UTC

radams wrote:Nope. ZFC is an impredicative system. When we define a set using a Comprehension Axiom

[math]A = \{x \in B : \phi\}[/math]

the formula [imath]\phi[/imath] might involve quantification over all sets. A predicativist would not like that, because you're quantifying over a collection that includes [imath]A[/imath] before [imath]A[/imath] has been defined.
I though that is forbidden by ZFC, or at least the way I was taught it. [imath]\phi[/imath] needs to be defined over some sort of set that we already know. The wiki page on ZFC says the same thing, that ZFC does not allow unrestricted comprehension.

You can, however, quantify over all real numbers, once the reals have been defined using the naturals.

As for the OP, I guess I am taking that he is throwing out the axiom of infinity.

FrancovS
Posts: 59
Joined: Fri Apr 16, 2010 1:47 am UTC

Re: Killing infinites and using computables instead of reals

Postby FrancovS » Mon Jul 26, 2010 12:15 am UTC

Wow, thanks everybody. That was incredibly helpful (specially radams' first comment). I believe I am interested in finitism, and not constructivism - thought in my understanding, both end up killing uncomputable numbers and cardinal numbers, and maybe that's why I got confused.

I became interested in finitism because I find the idea of actual infinites troubling - it just sounds gimmicky. In calculus, for example, the use of infinites is justified with limits. In this context, infinites end up meaning only the impossibility of using a finite number to the task - and not that a mystical number named "infinite" will fill the role. At first, I thought that all the mathematics was done with a similar approach - for example, the set of natural numbers would not not exist, but saying that a number belongs to the set of the natural numbers wouldn't be meaningless; it would instead mean that said number has the properties of the natural numbers.

I soon realized that infinite sets do exist in traditional mathematics, but I still can't cope with them because most of the math I know seems to survive quite well without them. I avoid dealing with controversial bizarre stuff as the axiom of choice and transfinite induction, and from what I know, most of the questions solved by using infinites actually involve infinites in their formulation (here, by infinites I mean actual infinites, and not limits). My question is motivated by the fact that there must be some very good reason for the existence of the axiom of infinity - dealing with infinites is counter-intuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: Killing infinites and using computables instead of reals

Postby achan1058 » Mon Jul 26, 2010 12:32 am UTC

In some sense, I understand what you are talking about, that's why I am in combinatorics. But I do think throwing out the set of natural numbers is a bit restrictive. I mean, it renders you unable to make statements like, for all n > 2, a,b,c > 0, a^n+b^n=c^n has no solutions, unless you start adding things back in to get around the problem that you do not have the set of natural numbers. As for the axiom of choice, you will be surprised at how often it is used.

User avatar
antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Killing infinites and using computables instead of reals

Postby antonfire » Mon Jul 26, 2010 12:52 am UTC

achan1058 wrote:
radams wrote:Nope. ZFC is an impredicative system. When we define a set using a Comprehension Axiom

[math]A = \{x \in B : \phi\}[/math]

the formula [imath]\phi[/imath] might involve quantification over all sets. A predicativist would not like that, because you're quantifying over a collection that includes [imath]A[/imath] before [imath]A[/imath] has been defined.
I though that is forbidden by ZFC, or at least the way I was taught it. [imath]\phi[/imath] needs to be defined over some sort of set that we already know. The wiki page on ZFC says the same thing, that ZFC does not allow unrestricted comprehension.
The way I understood it, a predicavist would not like the expression "A = {n in N : there is a field of size n}", because it quantifies over all fields, even though that is a perfectly acceptable statement in ZFC.


FrancovS wrote:My question is motivated by the fact that there must be some very good reason for the existence of the axiom of infinity - dealing with infinites is counter-intuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?
Yes.

A lot of mathematics was developed to be the underpinnings of physics, which likes to deal with things like continuous time and space. These need some theory like the theory of real numbers. You can probably put something together finitistically, but it would involve adding a whole new type of thing and a bunch of new axioms, and it sounds like this is the sort of thing you're trying to avoid in the first place.

But let's say you've got a theory like that, you can talk about real numbers. Okay, that's pretty cool, we can put together relationships and prove some theorems like ax2+bx+c = 0 if and only if x = (-b + sqrt(b2-4ac))/(2a) or x = (-b + sqrt(b2-4ac))/(2a). There's a bit of a problem with what "sqrt" means, but we can get around it with some footwork.

We can even talk about derivatives a bit: For any positive real number epsilon, there's a positive delta such that if h is less than epsilon, then (x+h)^2 is within delta*h of x^2+2x*h, to which we maybe assign the shorthand "the derivative of x^2 is 2x". But now you start noticing some patterns, like that the derivative of f plus the derivative of g is the sum of their derivatives. But what's f and what's g? We'd like to prove this theorem but we can't even state it since functions aren't objects in our theory.

What's "a function"? What's "a sequence"? In high school you pretty much get the impression that a function is some sort of formula, and you can try to put together the theory this way if you like, by tacking on or building up some idea of "formula" out of natural numbers, but then how do you define, say, the function sqrt(|x|)? You can't just build it up with addition and multiplication and piecewise definitions. The crux of the matter is that f(x) = sqrt(|x|) defines a function because for every x there is one and only one nonnegative y with y^2 = |x|. Each time we prove that sort of thing, we want to have a function. With the approach that "functions are formulas", you'd need to also tack on or build up a whole theory of formulas and proofs within your own theory of formulas and proofs. God help you when you want to talk about functions which take functions as arguments. Also, when you start dealing with the various paradoxes that pop up when you do this stuff sloppily.

With infinite sets, however, you can just say a function from the real numbers to the real numbers is a subset of RxR, with the property that for each x in R, there is exactly one y such that (x,y) is in the set. The point of sets is that they play the role of predicates while remaining objects in your theory that you can talk about. There are a few gotchas but the approach works smoothly enough.


If you allow yourself infinite sets, you can build up the theory of natural numbers, rational numbers, sequences of rational numbers, real numbers, complex numbers, functions on real numbers, functions on functions of real numbers, etc., etc., all in the one axiomatic system you start with. Other approaches tend to require revisiting axioms a lot.


Edit:

Yes, strictly speaking, all the above requires infinity in the formulation, but only because infinite sets are a convenient way to build up models of things which we don't normally think of as infinite, like, say, real numbers.

For an example of a statement about only finite things that (loosely speaking) cannot be done finitistically but can be done with infinite sets, see Goodstein's theorem.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

FrancovS
Posts: 59
Joined: Fri Apr 16, 2010 1:47 am UTC

Re: Killing infinites and using computables instead of reals

Postby FrancovS » Mon Jul 26, 2010 3:41 am UTC

Wow, I must say I am completely amazed by the fact that Goodstein's theorem can't be proved by Peano arithmetic. It seems quite intuitive - just go on eliminating the higher exponentiation, it should be done in finite steps. Can't see the catch yet.

User avatar
Harg
Posts: 130
Joined: Thu Jul 10, 2008 8:24 pm UTC

Re: Killing infinites and using computables instead of reals

Postby Harg » Mon Jul 26, 2010 8:07 am UTC

Interestingly, a similar discussion is going on on MathOverflow right now. Someone there posted a link to a talk by Doron Zeilberger (a very outspoken ultrafinitist), which might interest you. He talks about how to do calculus using a "discrete necklace" instead of the real line.

Also, with regard to Goodstein's theorem, a professor of mine (also my undergrad thesis advisor) wrote an applet for the hydra game, which is fun.

elasto
Posts: 3028
Joined: Mon May 10, 2010 1:53 am UTC

Re: Killing infinites and using computables instead of reals

Postby elasto » Mon Jul 26, 2010 8:24 am UTC

On Goodstein's theorem, can someone restate the proof in terms I might be able to understand? Wikipedia puts it like this:

Proof of Goodstein's theorem

Goodstein's theorem can be proved (using techniques outside Peano arithmetic, see below) as follows: Given a Goodstein sequence G(m), we will construct a parallel sequence of ordinal numbers whose elements are no smaller than those in the given sequence. If the elements of the parallel sequence go to 0, the elements of the Goodstein sequence must also go to 0.

To construct the parallel sequence, take the hereditary base n representation of the (n − 1)-th element of the Goodstein sequence, and replace every instance of n with the first infinite ordinal number ω. Addition, multiplication and exponentiation of ordinal numbers is well defined, and the resulting ordinal number clearly cannot be smaller than the original element.

The 'base-changing' operation of the Goodstein sequence does not change the element of the parallel sequence: replacing all the 4s in 4^4^4 + 4 with ω is the same as replacing all the 4s with 5s and then replacing all the 5s with ω. The 'subtracting 1' operation, however, corresponds to decreasing the infinite ordinal number in the parallel sequence; for example, ω^ω^ω + ω decreases to ω^ω^ω + 4 if the step above is performed. Because the ordinals are well-ordered, there are no infinite strictly decreasing sequences of ordinals. Thus the parallel sequence must terminate at 0 after a finite number of steps. The Goodstein sequence, which is bounded above by the parallel sequence, must terminate at 0 also.

Why does: ω^ω^ω + ω decrease to ω^ω^ω + 4? Why wouldn't it decrease to ω^ω^ω + (ω-1) = ω^ω^ω + ω?

And how does that help us anyway? I see the key is this part "there are no infinite strictly decreasing sequences of ordinals" but I don't see how we are decreasing the ordinal at all - it seems to me it's always stuck at ω.

Can someone expand the explanation a little so I can get it?

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6141
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Killing infinites and using computables instead of reals

Postby skeptical scientist » Mon Jul 26, 2010 9:12 am UTC

elasto wrote:Why does: ω^ω^ω + ω decrease to ω^ω^ω + 4? Why wouldn't it decrease to ω^ω^ω + (ω-1) = ω^ω^ω + ω?

And how does that help us anyway? I see the key is this part "there are no infinite strictly decreasing sequences of ordinals" but I don't see how we are decreasing the ordinal at all - it seems to me it's always stuck at ω.

Can someone expand the explanation a little so I can get it?

Your objection is based on a misunderstanding. I will correct it by providing a more detailed example:

First, we start with some number, say 17, and write down the Goodstein sequence for 17:

2^2^2+1, 3^3^3, 3*4^(3*4+3)+3*4^(3*4+2)+3*4^(3*4+1)+...+3*4+3, 3*5^(3*5+3)+3*5^(3*5+2)+3*5^(3*5+1)+...+3*5+2, etc.

To this Goodstein sequence, we associate a parallel sequence by changing all of the occurrences of (n+1) in the nth term to ωs:

ω^ω^ω+1, ω^ω^ω, 3*ω^(3*ω+3)+3*ω^(3*ω+2)+3*ω^(3*ω+1)+...+3*ω+3, 3*ω^(3*ω+3)+3*ω^(3*ω+2)+3*ω^(3*ω+1)+...+3*ω+2, etc.

The terms in the parallel Goodstein sequence are not obtained by performing some operation on the previous term—this is important. Instead, they are obtained by translating the associated term in the original Goodstein sequence. This answers your question of why ω^ω^ω+ω is followed by ω^ω^ω+4 and not ω^ω^ω+ω-1 in the example: because one is associated to 5^5^5+4, and one is associated to 4^4^4+4. So ω^ω^ω+ω could be followed by different things in a parallel Goodstein sequence, depending on what stage it was reached in the original Goodstein sequence. If we have the Goodstein sequence for 18, it would start 2^2^2+2, and the next term would be 3^3^3+2, so the parallel Goodstein sequence would have ω^ω^ω+ω followed by ω^ω^ω+2. Remember, it's not that you are subtracting 1 each time; that wouldn't even make sense, because there are ordinals like ω^ω^ω+ω that have no predecessor. Instead, you are taking the ordinal associated to the next number in the original Goodstein sequence.

Now we can see how it helps us: it is possible to show that the ordinal in the parallel sequence must decrease at each step (unless it terminates). And therefore a nonterminating Goodstein sequence would have a nonterminating parallel Goodstein sequence, but that nonterminating parallel Goodstein sequence would be an infinite decreasing sequence of ordinals, which is impossible.

Harg wrote:Interestingly, a similar discussion is going on on MathOverflow right now.

Link?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Xanthir
My HERO!!!
Posts: 5157
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Killing infinites and using computables instead of reals

Postby Xanthir » Mon Jul 26, 2010 5:16 pm UTC

Harg wrote:Interestingly, a similar discussion is going on on MathOverflow right now. Someone there posted a link to a talk by Doron Zeilberger (a very outspoken ultrafinitist), which might interest you. He talks about how to do calculus using a "discrete necklace" instead of the real line.


Interestingly, his version of ultrafinitism is completely sensical and consistent, but depends on the shape of the universe! He bases it on the assumption that the universe is finite and discrete, and thus there is a "largest number" that can be expressed using all the energy in the universe. We'll never know this number (because it would take all the energy in the universe to represent), but it nonetheless exists.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Yakk
Poster with most posts but no title.
Posts: 11034
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Killing infinites and using computables instead of reals

Postby Yakk » Mon Jul 26, 2010 9:55 pm UTC

The part I find funny about that argument is that there are numbers smaller than the largest number that are harder to express. So the number system limited by that .. has holes!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xanthir
My HERO!!!
Posts: 5157
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Killing infinites and using computables instead of reals

Postby Xanthir » Mon Jul 26, 2010 9:57 pm UTC

It is, in fact, full of holes!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

elasto
Posts: 3028
Joined: Mon May 10, 2010 1:53 am UTC

Re: Killing infinites and using computables instead of reals

Postby elasto » Tue Jul 27, 2010 5:09 pm UTC

Thanks skeptical scientist, that did help a lot. So the proof boils down to this:

(1) Form a derived sequence to the Goodstein sequence
(2) Note that every element of the Goodstein sequence is less than or equal to its derived partner
(3) Note that the derived sequence strictly decreases with each step (proof of this has not been supplied, right?)
(4) Because there is no infinitely decreasing sequence of ordinal numbers, the derived sequence must terminate, and because of (2) the Goodstein sequence must terminate also

I want to ask about this statement you made, though:
skeptical scientist wrote:Remember, it's not that you are subtracting 1 each time; that wouldn't even make sense, because there are ordinals like ω^ω^ω+ω that have no predecessor
Why does (ω^ω^ω+ω) necessarily have no predecessor? Isn't that like saying 0 has no predecessor? I don't know how -1 is defined rigorously, but I assume it can be defined as the number which when added to 1 gives 0. Why can't (ω-1) be defined as the number which when added to 1 gives ω?

I mean, if we are talking 'intuition', to say that there is a number one after infinity is no less counterintuitive than to say there is a number one before infinity, really. Both are pretty weird concepts to begin with (as is infinity to the power of infinity), and, I'd have thought, both are merely matters of definition. We define (ω+1) to have certain properties and we could define (ω-1) to have properties in just the same way, couldn't we?

And, taking that view, wouldn't this expanded set of ordinals now have an infinite number of sections of infinitely decreasing sequences? (ω^ω-1) all the way down to (ω^ω-ω), for example?

Before you point it out, I realise that this new set of ordinals is not relevant to the proof since the Goodstein sequence has no negative numbers anywhere, so none of these new ordinals would come into play. It is just the lack of these ordinals at all that I am querying.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Killing infinites and using computables instead of reals

Postby mike-l » Tue Jul 27, 2010 5:56 pm UTC

elasto wrote:
skeptical scientist wrote:Remember, it's not that you are subtracting 1 each time; that wouldn't even make sense, because there are ordinals like ω^ω^ω+ω that have no predecessor
Why does (ω^ω^ω+ω) necessarily have no predecessor? Isn't that like saying 0 has no predecessor? I don't know how -1 is defined rigorously, but I assume it can be defined as the number which when added to 1 gives 0. Why can't (ω-1) be defined as the number which when added to 1 gives ω?


Sure it could be, but then you wouldn't be talking about the ordinals anymore. Ordinals are equivalence classes of well orderings. Compare this to natural numbers, which can be thought of as equivalence classes of finite sets. 0 has no predecessor. Sure you can make one, but there's no set that it corresponds to.

In the ordinals, the successor function is basically 'take your set with a well ordering, put one more element that is bigger than the rest on the end'. Since ω has no biggest element, it couldn't have been made that way.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

elasto
Posts: 3028
Joined: Mon May 10, 2010 1:53 am UTC

Re: Killing infinites and using computables instead of reals

Postby elasto » Tue Jul 27, 2010 6:41 pm UTC

Thanks mike.

Btw, I came across this article and found it really informative, so I link it for those just starting off learning about the infinite ordinals like me.

User avatar
antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Killing infinites and using computables instead of reals

Postby antonfire » Tue Jul 27, 2010 10:49 pm UTC

There's also the fact that if every ordinal did have a predecessor, then there would be infinite strictly decreasing sequences of ordinals.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

FrancovS
Posts: 59
Joined: Fri Apr 16, 2010 1:47 am UTC

Re: Killing infinites and using computables instead of reals

Postby FrancovS » Mon Aug 02, 2010 5:39 pm UTC

Sorry for taking so long to come back to the thread. I've found an article that seems quite enlightening, thought I couldn't fully understand it.

However, I am not convinced that Goodstein's theorem needs the use of infinite sets to be proven. From what I understood, it can't be proven in peano arithmetics due to language constraints, but a proof could be carried in another system without the use of infinite sets. Please correct me if I'm wrong, but it seems quite easy to prove that the higher exponentiation would eventually disappear and then, by induction, prove that it ends after a finite number of steps. I simply would need more Godel numbers.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6141
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Killing infinites and using computables instead of reals

Postby skeptical scientist » Mon Aug 02, 2010 9:13 pm UTC

FrancovS wrote:However, I am not convinced that Goodstein's theorem needs the use of infinite sets to be proven. From what I understood, it can't be proven in peano arithmetics due to language constraints, but a proof could be carried in another system without the use of infinite sets. Please correct me if I'm wrong, but it seems quite easy to prove that the higher exponentiation would eventually disappear and then, by induction, prove that it ends after a finite number of steps. I simply would need more Godel numbers.

Obviously, you can accept it as an axiom, and then it doesn't need to be proven at all!

The point, however, is how we know it is true, and that is by using infinite sets. Even if infinite sets don't "exist" in any real sense, by assuming their existence as a logical construct, one can reason with them and prove things about finite objects, and it doesn't seem to introduce any contradictions to posit the existence of infinite sets.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Killing infinites and using computables instead of reals

Postby antonfire » Mon Aug 02, 2010 10:06 pm UTC

FrancovS wrote:However, I am not convinced that Goodstein's theorem needs the use of infinite sets to be proven. From what I understood, it can't be proven in peano arithmetics due to language constraints, but a proof could be carried in another system without the use of infinite sets. Please correct me if I'm wrong, but it seems quite easy to prove that the higher exponentiation would eventually disappear and then, by induction, prove that it ends after a finite number of steps. I simply would need more Godel numbers.
It's unclear what you mean. What does this have to do with Godel numbers?

Anyway, if it's easy, prove it.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

radams
Posts: 88
Joined: Fri May 14, 2010 12:49 pm UTC

Re: Killing infinites and using computables instead of reals

Postby radams » Fri Aug 06, 2010 12:53 pm UTC

You can prove Goodstein's Theorem in Peano Arithmetic plus an axiom schema that lets you do transfinite induction over the ordinal [imath]\epsilon_0[/imath] (which is the limit of [imath]\omega[/imath], [imath]\omega^\omega[/imath], [imath]\omega^{\omega^\omega}[/imath],...)

So, in that sense, we can write out a proof of Goodstein's Theorem that doesn't make explicit reference to infinite sets. But good luck convincing a finitist that a well-ordering of length [imath]\epsilon_0[/imath] exists.

Finitists, by the way, usually don't even accept ordinary induction. In PRA, we only have the axiom [imath]\phi[0] \rightarrow \forall x (\phi[x] \rightarrow \phi[x+1]) \rightarrow \forall x \phi[x][/imath] when the formula [imath]\phi[x][/imath] is quantifier free.

sintrastes
Posts: 2
Joined: Mon Mar 13, 2017 1:09 pm UTC

Re: Killing infinites and using computables instead of reals

Postby sintrastes » Mon Mar 13, 2017 1:48 pm UTC

epsilon-delta wrote:Not allowing yourself to deal with infinite sets is going to be incredibly limiting, to say the least. In fact, you'll be able to say very little that's actually interesting (and very little about interesting topics), since almost all nontrivial cases are going to rely on an infinite set. Since you can't define a real number without an infinite set, you're not going to be able to talk about real analysis at all (and since you're barring infinites, you're out of luck when it comes to the extended line which is also quite useful). Considering only finite cases is also going to make topological spaces very uninteresting. An open set will be identical to a closed set (since we can never have infinitely many open sets in the first place, we must conclude that only finite unions of open sets are open), all spaces will be compact (since there can't be infinitely many open sets in a cover in the first place, every space that is covered would have a finite subcover, namely the cover in question), and the list goes on. I'm not exactly sure what your goal is in eliminating infinity. Does something about the concept of an infinite set make you uncomfortable?


You need to think outside of your set-theoretic box. Consider that instead of set our objects consist of a collection of types and terms. We have the following judgments (which are like propositions, but exist in the metatheory):

A type; "A is a type"
t : A; "t is a term of type A"
t = t' : A "t and t' are equal as terms of type A"

We can construct types by giving rules. We write these as:

Code: Select all

    A    B
  ----------
       C


which you can read as "from the judgements A, B, we can deduce C". So consider the following:

Code: Select all

                                          n : N
------------      --------------      --------------
  N type               0 : N             s(n) : N


By combining these rules we can deduce 0 : N, s(0) : N, s(s(0)) : N, s(s(s(0))) : N, ... -- A unary representation of the natural numbers! We can similarly define functions, products, relations, and yes, real numbers -- all without relying on set theory.

Now, you might say: "Isn't N an infinite type?" and yes, in some sense it is, but infinite types have an entirely different character than the infinite sets in standard foundations do. In particular, we do not presuppose any sort of "totality" or "completeness" to the sets. In set theory, we view all of the elements of a set platoically as being laid out infront of us in an infinite array, with every element being accessible to be manipulated to our every whim. In type theory, mathematics takes on a more computational character. We do not assume, for example, the law of the excluded middle -- because in general there is no computational procedure for determining whether an arbitrary proposition is true or false!

Using types in some sense formalizes the vague notion of "potential infinity" often cited by finitists, since although we can prove that N is not a finite type (suppose N has only finitely many terms, let m the the greatest term of N -- then s(m) is not in N, contradicting our rule that m : N implies s(m) : N!), as mathematicians in a type theory we don't work with the "completed set" of elements of N at any given time, since we are finite beings and not capable of preforming infinitely many computations in a finite amount of time (though perhaps such beings exist somewhere, for now we can only imagine them! -- which albeit is a very fun intellectual and mathematical exercise that manifests itself in the field of "hypercomputation"), we only work with the finitely many rules specified in our type theory, and the finitely many derivations constructed (at any fixed time) using these rules.

What do we make of irrational numbers such as pi? -- Easy, simply identify them with a procedure that computes its digits! (or, in a more sophisticated approach, a procedure that generates the required "deltas" from "epsilons" in the standard definition of limit)

sintrastes
Posts: 2
Joined: Mon Mar 13, 2017 1:09 pm UTC

Re: Killing infinites and using computables instead of reals

Postby sintrastes » Mon Mar 13, 2017 2:06 pm UTC

FrancovS wrote:Wow, thanks everybody. That was incredibly helpful (specially radams' first comment). I believe I am interested in finitism, and not constructivism - thought in my understanding, both end up killing uncomputable numbers and cardinal numbers, and maybe that's why I got confused.

I became interested in finitism because I find the idea of actual infinites troubling - it just sounds gimmicky. In calculus, for example, the use of infinites is justified with limits. In this context, infinites end up meaning only the impossibility of using a finite number to the task - and not that a mystical number named "infinite" will fill the role. At first, I thought that all the mathematics was done with a similar approach - for example, the set of natural numbers would not not exist, but saying that a number belongs to the set of the natural numbers wouldn't be meaningless; it would instead mean that said number has the properties of the natural numbers.

I soon realized that infinite sets do exist in traditional mathematics, but I still can't cope with them because most of the math I know seems to survive quite well without them. I avoid dealing with controversial bizarre stuff as the axiom of choice and transfinite induction, and from what I know, most of the questions solved by using infinites actually involve infinites in their formulation (here, by infinites I mean actual infinites, and not limits). My question is motivated by the fact that there must be some very good reason for the existence of the axiom of infinity - dealing with infinites is counter-intuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?


You should look into the Martin-Lof brand of constructivism. For the reasons mentioned in my previous post, I think you will find it justifiable from a finitist standpoint, and yet it allows for a much more expressive mathematical language than Hilbertian (i.e. essentially just working over PRA) finitism. Doing finitism over PRA is essentially just bare computational mathematics, whereas constructivism (at least in the Martin-Lof camp) is like computational mathematics endowed with the power of abstractions, albeit not questionable abstractions like "completed infinities".


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 5 guests