Killing infinites and using computables instead of reals
Moderators: gmalivuk, Moderators General, Prelates
Killing infinites and using computables instead of reals
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?
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?
Re: Killing infinites and using computables instead of reals
I'm not sure if I understand you correctly, but I think you just killed the natural numbers.
 Yakk
 Poster with most posts but no title.
 Posts: 11045
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Killing infinites and using computables instead of reals
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.
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Killing infinites and using computables instead of reals
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 subbranches 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 quantifierfree 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.
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 subbranches 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 quantifierfree 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.

 Posts: 8
 Joined: Sat Jul 24, 2010 1:45 am UTC
Re: Killing infinites and using computables instead of reals
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?
Re: Killing infinites and using computables instead of reals
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.epsilondelta 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.
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 wellordered" 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?

 Posts: 133
 Joined: Mon May 17, 2010 8:52 pm UTC
Re: Killing infinites and using computables instead of reals
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?
Re: Killing infinites and using computables instead of reals
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.

 Posts: 8
 Joined: Sat Jul 24, 2010 1:45 am UTC
Re: Killing infinites and using computables instead of reals
antonfire wrote: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.epsilondelta 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.
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 wellordered" all the time even though the ordinals aren't an object in ZFC.
Perhaps I'm misunderstanding the OP's intention by
, 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.I forbid actual infinites (so you can't deal with infinite sets 
Re: Killing infinites and using computables instead of reals
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?
Re: Killing infinites and using computables instead of reals
epsilondelta 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.
Re: Killing infinites and using computables instead of reals
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.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.
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.
Re: Killing infinites and using computables instead of reals
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 counterintuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?
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 counterintuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?
Re: Killing infinites and using computables instead of reals
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.
Re: Killing infinites and using computables instead of reals
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.achan1058 wrote: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.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.
Yes.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 counterintuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?
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 ax^{2}+bx+c = 0 if and only if x = (b + sqrt(b^{2}4ac))/(2a) or x = (b + sqrt(b^{2}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?
Re: Killing infinites and using computables instead of reals
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.
Re: Killing infinites and using computables instead of reals
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.
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.
Re: Killing infinites and using computables instead of reals
On Goodstein's theorem, can someone restate the proof in terms I might be able to understand? Wikipedia puts it like this:
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?
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 'basechanging' 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 wellordered, 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?
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Killing infinites and using computables instead of reals
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
"With math, all things are possible." —Rebecca Watson
 Xanthir
 My HERO!!!
 Posts: 5198
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Killing infinites and using computables instead of reals
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)))
 Yakk
 Poster with most posts but no title.
 Posts: 11045
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Killing infinites and using computables instead of reals
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 Xanthir
 My HERO!!!
 Posts: 5198
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Killing infinites and using computables instead of reals
It is, in fact, full of holes!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Killing infinites and using computables instead of reals
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:
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.
(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:
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 ω?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
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.
Re: Killing infinites and using computables instead of reals
elasto wrote: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 ω?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
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.
Re: Killing infinites and using computables instead of reals
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.
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.
Re: Killing infinites and using computables instead of reals
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?
Re: Killing infinites and using computables instead of reals
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.
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.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Killing infinites and using computables instead of reals
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
"With math, all things are possible." —Rebecca Watson
Re: Killing infinites and using computables instead of reals
It's unclear what you mean. What does this have to do with Godel numbers?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.
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?
Re: Killing infinites and using computables instead of reals
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 wellordering 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.
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 wellordering 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.

 Posts: 2
 Joined: Mon Mar 13, 2017 1:09 pm UTC
Re: Killing infinites and using computables instead of reals
epsilondelta 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 settheoretic 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)

 Posts: 2
 Joined: Mon Mar 13, 2017 1:09 pm UTC
Re: Killing infinites and using computables instead of reals
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 counterintuitive and somewhat arbitrary (in the sense that you end up revisiting axioms a lot). Is it worth it?
You should look into the MartinLof 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 MartinLof camp) is like computational mathematics endowed with the power of abstractions, albeit not questionable abstractions like "completed infinities".
Who is online
Users browsing this forum: Baidu [Spider] and 4 guests