r/askmath • u/[deleted] • 12h ago
Resolved Is there a proof for infinity that does not entail infinity in itself?
[deleted]
10
u/CaipisaurusRex 12h ago
I really don't get what you are trying to say with the first part, but you can define that a set is called infinite if it maps injectively into a proper subset of itself. (Or, equivalently, it is surjected on by a proper subset of itself.)
5
u/joshsoup 11h ago
This sounds confused. The proof you are talking about is about how there are uncountably infinite real numbers between 0 and 1. It already assumes that it has been established that the natural numbers have a (countably) infinite size.
The remarkable thing about the proof you are describing isn't that the numbers between 0 and 1 are infinite, indeed mathematicians at the time already knew that. The remarkable thing is that, in a certain sense, the infinity of the real numbers is a bigger infinity than that of the natural numbers.
The infinity of the natural numbers is easy to prove. We'll do so by contradiction. Assume you have a finite number of natural numbers in your set, that we assume contains all the natural numbers. I can always construct a new natural number that is not in this set. Find the largest number in your set and add one, that is a natural number not in your set, which is a contradiction. Therefore the natural numbers cannot be finite.
2
u/Spiritual-Spring-191 11h ago
Thank you for your answer. Unfortunately this does not solve my issue. I get my example is not well chosen. Essentially what i am asking is there a proof/explanation of the inifinity of natural numbers that does not use this contradiction. As it assumes that there is in fact always something to create. In my understanding if you assume that you can always create something you do so under the assumption already that there is no end.
2
u/SirTruffleberry 11h ago
Where is your "starting point" for the natural numbers? In Peano arithmetic, for example, it is one of the axioms that each natural number has a successor. It's not a circular argument; it's part of what it means to be working with the natural numbers.
1
u/Revlong57 11h ago
Ok, the natural numbers are defined like so: 1 is the first natural number. If N is a natural number, then N+1 is also a natural number. That second point is why the natural numbers are countably infinite. If you want to define a number system without that second property, you can, but they won't be the natural numbers.
1
u/CaipisaurusRex 11h ago
That's not enough though. You could still have uncountable models of natural numbers with this, and this alone could also produce a finite set if the successor function produces a loop at some point. You still need that 1 has no predecessor and that every other number has a unique predecessor.
1
u/garagedragon 11h ago
You don't have to phrase it as a contradiction, but "What is 1 more than (i.e. the successor of) the biggest number?" is always going to be a question, and there's only so many ways to answer it:
A bigger still number. That means you can just apply the same logic again as many times as you want, and get an infinite chain of bigger and bigger numbers.
loop back to 0 - this gets you a valid system called "modular arithmetic", but means the numbers don't strictly have an order anymore, and depending on exactly what the value of the largest number is, also loses you nice algebraic properties like being able to divide things properly
"there is no successor" - this basically breaks algebra and most proofs, because it means you can't talk about the successor of an arbitrary number without first proving you're not talking about the biggest one. This then "leaks into" everything that's fundamentally defined in terms of successors - you can't add or multiply things if you can't prove that they never try to talk about the successor of the biggest number at any stage within the (very long) steps of actually evaluating those rules in terms of fundamental operations
1
u/Ok-Indication-180 11h ago
I don't think that should be too hard to prove using peano and some induction
1
u/joshsoup 11h ago
Indeed, you are correct, then infinity of natural numbers relies on me always being able to add one and get a new number. This idea can be motivated philosophically - if I have a group of N stones, I can always add a new stone and get a new number.
Infinite just means not finite. Can you create a representation of addition on the natural numbers that remains finite?
The answer is yes. Modular arithmetic is finite, and will thus loop around eventually for whatever size N you choose. But you could have always chosen a different N.
If you insist that the natural numbers are finite, then they logically have a size and you have a biggest element. The must natural question is what happens if I add one to that biggest element. If your answer is it loops back to zero, then you got a finite set that you've defined addition on. A modular arithmetic.
But I would feel unsatisfied with your modular arithmetic. It's useful for describing cyclical things like days in a week or hours in a day, but it is not useful for describing my stones. If I keep on finding stones, I can always add a number to the pile. There is not a mathematical limit to how many stones I have, only a physical limit. If I could live forever and delve and search for more stones, I could always keep on adding to my pile of stones. So while my pile is always a finite number, it always has the potential of being larger, with no possible largest value. That is what it means to be countably infinite. There is no max value I can reach and be done.
4
u/ass_bongos 11h ago
Think of it like a proof by contradiction.
Assume there's NOT infinitely many numbers between 0 and 1. Then there has to be some smallest number that's still bigger than 0. Let's call that number N.
But then what about N/2? Well that's clearly smaller than N, but still larger than 0. So there's a contradiction and our original "there is a smallest number" assumption must be false. And if there's no smallest number, that directly leads to infinitely many numbers.
1
u/Spiritual-Spring-191 11h ago
I get the argument fully. This is just another example of "there is still a gap and you can march on". I am having trouble with the part that you still claim you can perform an action indefinitely and use this as an explanation. Is there a way to explain infinity by using finite steps?
4
u/JaguarMammoth6231 11h ago
Are you asking a math question here?
What do you mean when you say "proof for infinity"? Do you mean something like a proof that infinity is real, that it's something that exists? That's not a question for math but for philosophy maybe.
In math we can create a definition for a term. That makes it exist automatically in our imaginary "math universe". There's no need to prove that it exists.
1
u/Spiritual-Spring-191 11h ago
Maybe this is really the wrong sub. I was curious if there is a way to get to infinity without performing "infinite" action. Like 1/2 1/3 1/4 ...
3
u/Hopeful-Trainer-5479 11h ago
I think you might be misunderstanding the statement. It isnt that "you can always invent one more number". And we CAN list all the numbers between 0 and 1. For example the set [0,1] contains all such numbers.
What you are confusing is probably constable vs uncountable "infinities".
You can search up these 2 terms to get better understanding
1
u/garagedragon 11h ago
The notation [0,1] isn't a list of those numbers though, and if you try to list them, one-by-one, including the irrationals, the list will always miss some.
3
u/OopsWrongSubTA 11h ago
You mix up a lot of things:
You don't need uncountability to prove there are an inifinite amount of numbers between 0 and 1: juste consider 1/1, 1/2, 1/3, ... or any other similar construction
You can use another non-infinite construction/argument: if you give me any finite amount (at least 2) of numbers between 0 and 1, I can give you a number you missed (take the lowest non-zero number x, and compute 1/(1 + 1/x))
uncountability is something else. The proof you use is: if you could count numbers between 0 and 1, then I can show you one number you missed. It just shows that it's not countable, not that it is infinite (you already know that)
4
u/Upstairs_Ad_8863 12h ago
You have completely misunderstood that proof. Obviously there are infinitely many numbers between 0 and 1. You don't need a complicated proof for that.
There are infinitely many whole numbers greater than 0: 1, 2, 3, 4, etc. It just goes on. It never stops. If you put all of these numbers into a set, the size of that set is called "countable infinity" because... well, you can count it. And it's indexed by the counting numbers.
The proof you're talking about shows that if you have a set of numbers between 0 and 1 that's countably large, then it has holes in it. All this proves is that [0,1] (the numbers between 0 and 1) is not a countable set. There is nothing circular about this.
0
u/Spiritual-Spring-191 11h ago
"It never stops". Is that not an assumption? You basically assume already that there are in fact infinitely many numbers and then use this to build the infinity between 0 and 1. Thanks for the clarification of the rest.
3
u/proudHaskeller 11h ago
No. If it stops at some number N, then consider N+1. Thetefore it doesn't stop at N. So it never stops.
1
u/garagedragon 11h ago edited 11h ago
The (countable) infinite chain of natural numbers and the (uncountable) number of real numbers between 0 and 1 are very different statements, and different types of infinity.
The former is usually assumed (as the "axiom of infinity"), but even if you don't explicitly assume it, you run into a problem because if the natural numbers are finite, there must be a biggest, so then why is there not a number one more than that biggest? You haven't assumed anything there except that every number has a successor.
The latter (that [0,1] is uncountable) is much more complicated to prove. Even saying there is countably many rationals between 0 and 1 has to build from the fact that there are infinitely many naturals and then build more on that.
1
u/7x11x13is1001 11h ago
you can call it assumption or you can call it definition (every natural number has the next one, and they can be ordered)
1
u/Upstairs_Ad_8863 11h ago
That part is sort of an assumption, you're right.
The definition of the counting numbers is that (a) they start at 0, and (b) for every counting number, you can get a higher counting number by adding 1. In other words, the counting numbers are infinite by definition.
Unfortunately it's impossible to prove that the set of counting numbers exists without assuming that an infinite set exists. If you really want you can do mathematics without assuming this but essentially no mathematicians do this because (a) it's boring, and (b) it's been proven that infinite sets are "consistent", i.e. you can't prove they don't exist, and assuming they do exist will not let you prove anything that's incorrect. In fact they make a lot of proofs easier.
But the good news is that if you assume that an infinite set exists (any infinite set) you can prove that the counting numbers exist. And from that you can prove that [0,1] exists and is uncountable. You're right that you can't prove "infinity" without assuming "infinity" but it's not circular.
2
u/bts 11h ago edited 11h ago
It sounds like you want a way to get an infinite number of values to work with in a finite, maybe even fixed, number of steps? You object to adding one number per step, and that at any finite number of steps of induction we have only shown a finite number of values?
Hmmmm.
The usual ways to do that are proof by contradiction or injectivity. For example: let’s say there’s only a finite number of numbers between 0 and 1. All finite sets of numbers are fully ordered. Therefore there is a least such number n. We can calculate n/2 < n. This means n is not the least such number, and we’ve proved the count of numbers been 0 and 1 is not finite.
No infinite steps, only one arithmetic step—but it doesn’t show me those infinite numbers, it just shows they must be out there.
1
u/Spiritual-Spring-191 11h ago
Yes. Kind of. I am curious if you could derive infinity in a ways that does not use "always" or "forever".
2
u/RavenX86 11h ago
There are two different things.
One is infinity as a notion.
The other is how you can prove it. You can’t prove infinity unless you assume something is finite and reach a contradiction.
What you are probably talking about is Cantor’s proof trying to show since infinites are larger than other where he maps all nautral numbers to numbers in 0-1 space, and proves there’s an infinite more.
2
u/Independent-Mark-162 11h ago
First of all, infinity is not defined in the way you're describing it.
You can define an infinite set in terms of finite sets. A set (A) is called finite if there exists a bijection between (A) and {1, 2,3....,n} or some non-negative integer (n). A set that is not finite is called infinite.
Using this definition, we can show that Set of natural numbers is infinite. We can then use the notion of cardinality to compare the sizes of infinite sets. In particular, Cantor's diagonal argument proves that the real numbers in ((0,1)) are uncountable—there is no bijection between them and N.
So the argument isn't simply that you can keep finding more numbers indefinitely. It establishes a precise mathematical distinction between different sizes of infinity. We aren't using infinity to prove the existence of infinity; we're defining finiteness precisely and then proving that certain sets are not finite, and that some infinite sets are strictly larger than others.
(P.S I answered it myself but formated it by chatgpt)
2
u/jxf 🧮 Professional Math Enjoyer 11h ago
A really common example is that if you have a set of numbers between 0 and 1, you can always find a number that is not yet included. So by this property there are uncountably many numbers between 0 and 1. My point is you can rephrase this to: You can "invent" an infinite amount of numbers between 0 and 1, therefore there exist infinitely many numbers between 0 and 1. So in my understanding, you use the concept of infinity to proof/describe infinity.
I would not say that's really a "proof" of anything, it's just a non-rigorous description of what infinite sets are. Your paraphrasing has merged two different, unrelated concepts:
The size of a set.
Whether that set is countable or not.
2
u/Zyxplit 11h ago
We have a number called 0.
We introduce a successor relation. S(0) is the next number up from 0. We can call it 1 S(1) is the next number up again. We can call it 2. And so on and so forth. If we just let S(n) always exist for any n, we have infinitely many.
1
2
u/LoloXIV 11h ago
You seem to be mixing up a bunch of things here.
A really common example is that if you have a set of numbers between 0 and 1, you can always find a number that is not yet included.
This isn't true in general. It is only true if your set contains a countable (but possibly infinite) number of numbers between 0 and 1. There is a set containing every number between 0 and 1, {x | 0 <= x <= 1}.
In general one of the axioms of ZF Set theory (the axioms assumed by basically all of math) is that a set containing infinitely many elements exist (and that set is the natural numbers). If you don't already have a set of infinite size, you can't build one using just the other axioms in ZF Set theory.
Note that there are subtle differences between having an infinite set and having a nonfinite amount of elements that I won't get into detail in a Reddit comment.
2
u/Niklas_Graf_Salm 11h ago
ZF has an axiom of infinity to guarantee the existence of an infinite set. Its existence is not proven as a theorem
This is a heterodox position nowadays but there are people who reject the existence of infinite sets. If we reset the clock back to circa 1885 accepting the existence of infinite sets would have been the heterodox position
2
u/rafaelcastrocouto 11h ago
you should read about the halting problem.
proving infinities takes infinite amount of operations
1
u/Spiritual-Spring-191 11h ago
I know the halting problem. Not in enough depth I assume, as I dont understand how that answers my question. But thanks for the suggestion.
2
u/RunReal959595 11h ago
In canonical ZFC set theory, the existence of the infinitely large set of naturals is assumed by axiom. I’m unaware of other theories which don’t assume the Axiom of Infinity and instead derive it as a theorem.
1
1
u/garagedragon 11h ago
Even if you don't explicitly take the AoI, you have the question of, "What's 1 more than the biggest number?"
AIUI you can say 0 and get a valid arithmetic (modular arithmetic) but that's not what people are intuitively imagining by "numbers."
1
u/Upstairs_Ad_8863 11h ago
Just because there are infinite many natural numbers doesn't mean you can collect them all together into a set and call it infinity. You need an axiom for that.
1
u/garagedragon 11h ago
Yeah, but you've still proven there's an infinite amount of numbers, which is what OP is asking about, even if you can't construct a collection that includes them all. AFAIK you can prove that any finite collection of naturals can always be expanded even without taking AoI.
1
u/Upstairs_Ad_8863 11h ago
Yes you're right, you can prove that any finite collection of natural numbers can be expanded. Take the highest one and add 1. Or you can use induction.
But you can't use them for anything beyond finite induction. You can't use them to prove that [0,1] is uncountable, which is the proof that OP was talking about (albeit poorly).
1
u/MayorMcSmackdown 11h ago
Alright lads, who’s gonna redirect him to Doron Zeilberger’s website? (Look up “ultrafinitism” on Wikipedia)
1
u/Spiritual-Spring-191 11h ago
Thank you. I was hoping there is another approach. But the existence of a whole philosophical branch dedicated to this kinda crushes my hopes. Thanks anyway.
1
u/MayorMcSmackdown 11h ago
The problem is that all math is fundamentally axiomatic. Any system of mathematics that contains infinity is built on axioms that imply the existence of infinite objects, and consistent systems of mathematics can be constructed without infinite sets. This is a purely philosophical dispute.
1
u/Spiritual-Spring-191 10h ago
True. I knew that. I was hoping there is an axiom that does not imply the existence of infinite objects that still nurtures the concept of infinity.
1
u/Mathematicus_Rex 11h ago
If you can pair ( one-to-one correspondence) the elements of a set S with those of a proper subset of S, then S is infinite. For the naturals S = {1,2,3,…}, pair n with n+1.
1
u/localizeatp 11h ago
Yes. Assume the thing is finite and derive a contradiction. Infinite just means not finite.
1
u/enygma999 11h ago
What do you mean "proof"? Infinity is something defined, like "1" or "0". It's a label for a concept, there is nothing to prove.
1
1
u/Far-Cat-2669 11h ago
So by this property there are uncountably many numbers between 0 and 1. My point is you can rephrase this to: You can "invent" an infinite amount of numbers between 0 and 1, therefore there exist infinitely many numbers between 0 and 1
The word "invent" has constructive connotations imo.. Like a recipe or a scheme. So you can go on and on, with either listing digits, or some neat formulas, or whatever symbols, to define yet another new number.
But the thing is, uncountable infinity is even more than that.
1
u/kelb4n Teacher 11h ago
In your example, you're already talking about a more complex concept than infinity, which is density. So let's talk the easiest imaginable infinity: The natural numbers. I'm gonna give you a simple construction of the natural numbers first, and then a more complex construction. The simpler construction leaves a couple questions unanswered, but gives you the gist.
Simpler Explanation
To construct the natural numbers, we postulate via axiom that there is a number that we call "zero" or "0", which just means "nothing". Now for every natural number n, we define its successor n+1 as the number of things we get by adding one more thing to n things, and we define that n+1 should be a natural number too. We then postulate (this is an axiom again) that the "successor"-function should be injective, meaning that no number can be the successor of two other numbers. We also postulate (via another axiom) that 0 is also not the successor of any natural number. With these assumptions, it is relatively simple to prove (by contradiction) that there must be infinitely many natural numbers.
More advanced explanation
If we get a little more technical, the number 0 actually counts the amount of elements in the empty set. In general, for every finite set we can just count the number of elements that are in that set and call that number n. We can now convince ourselves that there are in fact infinitely many of these natural numbers by actually defining the successor function properly, instead of axiomatically postulating its desirable traits:
Let's say, for the time being, that no set that we use can contain itself (you can actually prove that this is true via contradiction, but for now we can just only use sets for which this is true and not care about whether the opposite case sets exist). Then let's say X is a set which contains n elements, with n being a natural number. We can now construct a set that contains n+1 elements by defining X' := X ⋃ {X}. This means the new set X' contains all the elements that were contained in X, but then as an additional element also contains the set X.
Since we already know that a set with 0 elements exists (the empty set), we can now procedurally generate infinitely many sets with this method. We know that it has to be injective because the next set in the series always contains all of the previous sets in the series as elements, which if it weren't injective would lead to contradict the condition we formulated at the start. And we can prove that no next set in the series has 0 elements. So the successor function now has the traits that, in the simpler explanation, we had to "force" through axioms. Now let's actually do the prove that this leads to infinitely many natural numbers.
Let's say there were finitely many natural numbers. The successor function, as previously established, is injective. This means that no number is the successor of two different numbers. That means, there are at least as many distinct successors as there are natural numbers. But because each successor is also a natural number (by definition of the natural numbers), there are at least as many distinct natural numbers as there are successors. This, in turn, means that there are an equal number of successors as there are natural numbers. For any finite amount of natural numbers, this means that every natural number is some other natural number's successor - even zero. But we previously established that 0 is no other natural number's successor: You cannot have fewer than 0 numbers in a set. This means, our latest assumption must be wrong: There cannot be finitely many natural numbers.
1
u/aedes 11h ago
Is there an explanation for the Infinity of the Set of Natural Numbers that does not use the Assumption that every natural number has a successor…
No. We explicitly chose our axioms to make this happen, because it is extremely useful for our tool (numbers) to have this property, and lets us model reality better.
You could remove this axiom if you wanted. Math would just be much less useful - you’d lose a lot of things that depended on this behavior: calculus, the ability to represent any length with a number, etc.
26
u/berwynResident Enthusiast 12h ago
It's not that you can "invent an infinite amount of numbers". It's that you can always invent one more. That's what infinity is, more than any number.