Isn't this obvious proof that the CAPTCHAs are poorly designed? Why not just use actual handwriting as CAPTCHAs? Then, when some hackers crack it, they have solved a useful outstanding problem in CS.
You may have been getting at this with #2, but I think the actual stroke information is one of the keys to why the Tablet outperforms--it looks at your writing as a collection of gestures and not merely the end result.
Well, the sandbox is only limited until the point where we can find another axiom (or theorem) to get us to the same interesting areas you've been talking about. As I think you mentioned previously, an alternate definition of equality of the cardinalities of infinite sets is indeed possible and is all that's needed to move into unexplored [and presumably interesting] areas.
Yea, you're right. The Strict [or ultra-] finitist would deny the existence of the infinite set entirely. But, I thought that it at least gave some credence to the 'marble' experiment. From the angle I'm approaching, two sets that are different in size at all known finite scales remain different in size when unbounded.
It doesn't explicitly say whether or not the Classical Finitists would distinguish sizes of infinite sets or not (and I don't see how it could be gathered from the information there either), but the page on 'infinity' itself does talk about several schools of thought (only one of which is based on Cantor). Of course, much of the thought on this matter is not from a purely mathematical perspective but also from those of philosophy and theology.
Actually, I think I was right the first time--the finitists are closer to my position (but Wiki says that finitists are simply constructionists to the extreme degree so that's where the confusion entered).
And, it's not really the existence of concepts which cannot be arrived at by construction via a finite number of steps that I have a problem with. I have no problem with the execution of an infinite number of steps--just with the equality assigned to two 'infinite' sets which are never equal at any finite scale of the same. My position is simply that infinity does not truly exist--it is merely a concept ascribed to represent an unbounded entity.
As for my background-- I'm 30 years old, studied C.S. as an undergraduate and graduate. Mathematics-wise: Calculus I & II, Linear Algebra, Num. Linear Algebra, Discrete Structures, Graph Theory, several flavors of Prob & Stat (including Foundations) and probably a few more I'm forgetting right now.
Since graduating, I've been quite interested in axiomatic systems (Godel, etc.) and have read Nagel/Newman's excellent book on the subject as well as Godel, Escher & Bach. I've also been somewhat of an armchair philosopher.
My current interests computer-wise involve functional programming (LISP/Haskell/F#) and languages.
[And, BTW, I read the page on WIki about philosophy of mathematics and I must say that I agree with quite a number of those philosophies--they sometimes contradict, but they almost all have some valid truths/approaches. So, I don't have a problem necessarily with agreeing with both 'Formalism' and 'Platonism' for example (or at least parts of each).]
[Finitism may be interesting to think about as well, but I have no problem with infinite quantities which take an infinite number of steps to 'construct'].
[Finitism may be interesting to think about as well, but I have no problem with infinite quantities which take an infinite number of steps to 'construct'].
[Finitism may be interesting to think about as well, but I have no problem with infinite quantities which take an infinite number of steps to 'construct'].
Now, this would be the place where you'd want to object to the definition itself if you're so inclined. I can't think of anything that does a better job of extrapolating from the finite case, but maybe you can. Once you agree that the definition is "good", then all else follows directly and absolutely.
Yes! That's exactly the point I've been objecting at all along. I suppose my attempts at elucidation have fallen short of that, but this definition is what I've had the problem with.
I will definitely attempt to think of alternate definitions of equality of cardinalities.
In the meantime, to clarify a little about what I meant by the problem of the infinite 'sources' being different:
I'm glad you mentioned the f(n)=2n bijection from N to the positive even integers. I also read of this on the Wikipedia page on Cardinality in the interim.
So, a question naturally arises here: is it just a matter of convention (i.e., an arbitrary decision) that we determined that 2 * infinity == infinity? Therein lies my issue with all of this. Isn't multiplying something by infinity somewhat like dividing by zero? We don't really comprehend the extent of infinity, so how can we go multiplying its extent by finite quantities (and end up extending it onto itself)? A finite quantity multiplied by an infinite one produces another infinite quantity (but, surely by intuition, we know the latter infinity is 'bigger'). The problem seems to be a lack of precision of infinity (or degree of infinity).
Ok, I'll have to digest this. Thanks for the original proof and further comments. The proof certainly does make sense, I just have a hard time reconciling it to my 'gut'.:-)
Most of my thoughts on this topic have probably already been elucidated (in a much better manner than I can) by the contemporaries of Cantor. I'll have to read some history of math and get back to you.
Hmm... Ok, well here's where I fail to grasp how the two infinities can be the same size:
For the bijection to work, there must be a prime for every natural. Every prime is always greater (and in ever increasing proportion as we count) than its corresponding natural. Naturals and primes come from the same numbering system, i.e., the same 'source'. So, every time you look at a prime, you are also looking at a natural. In other words, every time you 'discover' a new prime, you have also discovered many new naturals. The number of naturals will always be greater than the number of primes.
You're whole proof is based on the concept of an infinite source. My point is simply that one infinite source is greater than the other. But, we know that they are the same source thus a we have a contradiction. I think it really does matter which axioms you choose.
And, btw, I'm not trying to be intentionally obtuse here. I've definitely rather enjoyed and learned from this discussion. It's one of those things that I will certainly have to digest for a while though so please don't get discouraged if you think I'm not 'seeing' your points.
And again, you fail to mention one single scrap of information that could possibly be "lost". It's an absolute fact that you're dead wrong on that. Maybe what you want to say is that there is a different relationship that you are interested in which is not illuminated by this, but that is a completely different thing.
Yes, that's exactly what I'm saying. I suppose you didn't understand my point about time. So, I'll rephrase.
Your reasoning assumes that time is not a factor. It assumes that simultaneously there are an infinite number of naturals and an infinite number of primes available. That's a valid assumption. But, it isn't one I wish to make.
In that case, I suppose I should fill in the gap that was leaped over.
The introduction of 'infinity' into this allows for time to be factored out of consideration. That's perfectly fine and I'm sure there's a lot of useful discoveries that have come out of that. But, it isn't the only route forward. You [and everyone else] seem to think that given an number, you can always get one more number by adding one to it. Or, that given a prime, you can always get another prime greater than the one you have. And, yes both of those statements are true. But, infinity is merely a concept. You can ascribe it to both of these if you wish, but I simply think that loses some information about the relation. Maybe another concept is called for? Or, maybe I'm ignorant of the existence of this other concept. I'm sure the mathematicians at the time of Cantor would've thought of this.
Well, actually, the way we do maths right now is very compartmentalized. Each theory has its own set of axioms and all of its theorems apply only to those axioms. Unless this system in question keeps all these theories separate, collisions are inevitable and it will be a race to see which theorems get there first.
I'm sure the system in question isn't going to be as sophisticated as I'd like (they never are), so it will most likely keep each theory separate and there will thus be no problems. But, of course, we will not have any greater chance than we do now at discovering these interesting 'collisions' which may provide the answer to such questions as why quantum mechanics and general relativity do not mesh (for instance).
Here's one reason why:
[This thought experiment should be able to be expanded to a formal inductive proof if that is what you want.]
No, it can't. Not to prove what you're trying to prove. Induction can only prove a statement true for all *finite* values of 'n'. So, yes, obviously once you pick a specific fixed number, n, if you take the set of all natural numbers up to and including n and compare that with the set of all primes up to and including n (assuming n is prime of course, otherwise it's not included) then your first set will be larger.
That's all well and good for what it is, but it has no bearing whatsoever on what you're attempting to demonstrate.
You obviously don't know as much as you claim to know. Read and be enlightened:
There isn't an intuitive "definition' of cardinality. There is intuition. There is a definition of sets having the same cardinality. These are 2 different things.
There is a 'definition' of sets having the same cardinality. Yes, and it is this 'definition' which is flawed and arbitrary. It fails to account for the rates at which things grow to infinity (which is precisely the thing I want to capture with some augmented aleph number--call it a 'bet' number if you like).
[This will at the same time address masterzora's gripes with my use of the word infinity and the concept of growing to infinity (both of which mind you I got from years of sitting in mathematics classes).
Take two children and give them an endless supply of marbles and each a container. Also give one child the ability (or a machine) to tell if a given number is prime). Then start the first child at the number one and tell him to count til he can count no more putting one marble in his container for each number he 'counts'.
Tell the second child to put a marble in his container anytime the first one calls out a prime.
I think you and I could both agree that the first child will have many more marbles than the second in his container before too long and that as more time passes, the larger the first's count of marbles will be in proportion to the second (i.e., the first child's marble count will grow at a constant rate whilst the second child's marble count will grow at an ever decreasing rate).
[This thought experiment should be able to be expanded to a formal inductive proof if that is what you want.]
Let me also state, that I completely understand the OP's proof. I just think that it isn't the whole story. [And, BTW, the first assumption from my proof is only false when talking about infinite sets. I cannot say that I know all of the math behind why infinite sets are allowed to break the intuitive definition of cardinality, but if it is like alot of things in math, it could be an arbitrary decision. And, if that is the case, then by simply changing that decision and the axioms involved, we could enter other and seemingly to me useful areas of math.
Math is dependent on the axioms (or at least the logic portion of it). I can choose the axioms I want whether or not they fit with your view of reality. Granted, it may not mean much, but in this case, I think that an alternative axiom set could produce interesting results.
Yes, precisely. I misunderstood the aleph number system to consider the proper subset sense. Do you happen to know if there is an infinity degree numbering system which takes into account the proper subset relation?
I actually prefer DropBox as it supports Windows, Mac & Linux. Also, Live Mesh has this nasty habit of bringing everything to a screeching halt if you happen to want it to sync a folder in which a large file (such as a Visual Studio.ncb file) resides (and if it sounds like I'm speaking from experience, I am!).
Slashdot Mirror
Or, what about, SEmi-UW (as in pseudo-yuck).
So, SUEW.
He obviously wouldn't have enough memory for that. Let's be realistic here.
Isn't this obvious proof that the CAPTCHAs are poorly designed? Why not just use actual handwriting as CAPTCHAs? Then, when some hackers crack it, they have solved a useful outstanding problem in CS.
You may have been getting at this with #2, but I think the actual stroke information is one of the keys to why the Tablet outperforms--it looks at your writing as a collection of gestures and not merely the end result.
Well, the sandbox is only limited until the point where we can find another axiom (or theorem) to get us to the same interesting areas you've been talking about. As I think you mentioned previously, an alternate definition of equality of the cardinalities of infinite sets is indeed possible and is all that's needed to move into unexplored [and presumably interesting] areas.
Yea, you're right. The Strict [or ultra-] finitist would deny the existence of the infinite set entirely. But, I thought that it at least gave some credence to the 'marble' experiment. From the angle I'm approaching, two sets that are different in size at all known finite scales remain different in size when unbounded.
It doesn't explicitly say whether or not the Classical Finitists would distinguish sizes of infinite sets or not (and I don't see how it could be gathered from the information there either), but the page on 'infinity' itself does talk about several schools of thought (only one of which is based on Cantor). Of course, much of the thought on this matter is not from a purely mathematical perspective but also from those of philosophy and theology.
Actually, I think I was right the first time--the finitists are closer to my position (but Wiki says that finitists are simply constructionists to the extreme degree so that's where the confusion entered).
And, it's not really the existence of concepts which cannot be arrived at by construction via a finite number of steps that I have a problem with. I have no problem with the execution of an infinite number of steps--just with the equality assigned to two 'infinite' sets which are never equal at any finite scale of the same. My position is simply that infinity does not truly exist--it is merely a concept ascribed to represent an unbounded entity.
As for my background-- I'm 30 years old, studied C.S. as an undergraduate and graduate. Mathematics-wise: Calculus I & II, Linear Algebra, Num. Linear Algebra, Discrete Structures, Graph Theory, several flavors of Prob & Stat (including Foundations) and probably a few more I'm forgetting right now.
Since graduating, I've been quite interested in axiomatic systems (Godel, etc.) and have read Nagel/Newman's excellent book on the subject as well as Godel, Escher & Bach. I've also been somewhat of an armchair philosopher.
My current interests computer-wise involve functional programming (LISP/Haskell/F#) and languages.
[And, BTW, I read the page on WIki about philosophy of mathematics and I must say that I agree with quite a number of those philosophies--they sometimes contradict, but they almost all have some valid truths/approaches. So, I don't have a problem necessarily with agreeing with both 'Formalism' and 'Platonism' for example (or at least parts of each).]
Oops, actually this is closer to where I'm at:
http://en.wikipedia.org/wiki/Mathematical_constructivism
[Finitism may be interesting to think about as well, but I have no problem with infinite quantities which take an infinite number of steps to 'construct'].
Oops, actually this is closer to where I'm at:
http://en.wikipedia.org/wiki/Mathematical_constructivism
[Finitism may be interesting to think about as well, but I have no problem with infinite quantities which take an infinite number of steps to 'construct'].
Oops, actually this is closer to where I'm at:
http://en.wikipedia.org/wiki/Mathematical_constructivism
[Finitism may be interesting to think about as well, but I have no problem with infinite quantities which take an infinite number of steps to 'construct'].
Aha! I knew I was not alone. See this:
http://en.wikipedia.org/wiki/Finitism
Aha! I knew I was not alone. See this: http://en.wikipedia.org/wiki/Finitism
Aha! I knew I was not alone. See this:
http://en.wikipedia.org/wiki/Finitism
Now, this would be the place where you'd want to object to the definition itself if you're so inclined. I can't think of anything that does a better job of extrapolating from the finite case, but maybe you can. Once you agree that the definition is "good", then all else follows directly and absolutely.
Yes! That's exactly the point I've been objecting at all along. I suppose my attempts at elucidation have fallen short of that, but this definition is what I've had the problem with.
I will definitely attempt to think of alternate definitions of equality of cardinalities.
In the meantime, to clarify a little about what I meant by the problem of the infinite 'sources' being different:
I'm glad you mentioned the f(n)=2n bijection from N to the positive even integers. I also read of this on the Wikipedia page on Cardinality in the interim.
So, a question naturally arises here: is it just a matter of convention (i.e., an arbitrary decision) that we determined that 2 * infinity == infinity? Therein lies my issue with all of this. Isn't multiplying something by infinity somewhat like dividing by zero? We don't really comprehend the extent of infinity, so how can we go multiplying its extent by finite quantities (and end up extending it onto itself)? A finite quantity multiplied by an infinite one produces another infinite quantity (but, surely by intuition, we know the latter infinity is 'bigger'). The problem seems to be a lack of precision of infinity (or degree of infinity).
Ok, I'll have to digest this. Thanks for the original proof and further comments. The proof certainly does make sense, I just have a hard time reconciling it to my 'gut'. :-)
Most of my thoughts on this topic have probably already been elucidated (in a much better manner than I can) by the contemporaries of Cantor. I'll have to read some history of math and get back to you.
Hmm... Ok, well here's where I fail to grasp how the two infinities can be the same size:
For the bijection to work, there must be a prime for every natural. Every prime is always greater (and in ever increasing proportion as we count) than its corresponding natural. Naturals and primes come from the same numbering system, i.e., the same 'source'. So, every time you look at a prime, you are also looking at a natural. In other words, every time you 'discover' a new prime, you have also discovered many new naturals. The number of naturals will always be greater than the number of primes.
You're whole proof is based on the concept of an infinite source. My point is simply that one infinite source is greater than the other. But, we know that they are the same source thus a we have a contradiction. I think it really does matter which axioms you choose.
And, btw, I'm not trying to be intentionally obtuse here. I've definitely rather enjoyed and learned from this discussion. It's one of those things that I will certainly have to digest for a while though so please don't get discouraged if you think I'm not 'seeing' your points.
And again, you fail to mention one single scrap of information that could possibly be "lost". It's an absolute fact that you're dead wrong on that. Maybe what you want to say is that there is a different relationship that you are interested in which is not illuminated by this, but that is a completely different thing.
Yes, that's exactly what I'm saying. I suppose you didn't understand my point about time. So, I'll rephrase.
Your reasoning assumes that time is not a factor. It assumes that simultaneously there are an infinite number of naturals and an infinite number of primes available. That's a valid assumption. But, it isn't one I wish to make.
In that case, I suppose I should fill in the gap that was leaped over.
The introduction of 'infinity' into this allows for time to be factored out of consideration. That's perfectly fine and I'm sure there's a lot of useful discoveries that have come out of that. But, it isn't the only route forward. You [and everyone else] seem to think that given an number, you can always get one more number by adding one to it. Or, that given a prime, you can always get another prime greater than the one you have. And, yes both of those statements are true. But, infinity is merely a concept. You can ascribe it to both of these if you wish, but I simply think that loses some information about the relation. Maybe another concept is called for? Or, maybe I'm ignorant of the existence of this other concept. I'm sure the mathematicians at the time of Cantor would've thought of this.
Well, actually, the way we do maths right now is very compartmentalized. Each theory has its own set of axioms and all of its theorems apply only to those axioms. Unless this system in question keeps all these theories separate, collisions are inevitable and it will be a race to see which theorems get there first.
I'm sure the system in question isn't going to be as sophisticated as I'd like (they never are), so it will most likely keep each theory separate and there will thus be no problems. But, of course, we will not have any greater chance than we do now at discovering these interesting 'collisions' which may provide the answer to such questions as why quantum mechanics and general relativity do not mesh (for instance).
Here's one reason why: [This thought experiment should be able to be expanded to a formal inductive proof if that is what you want.] No, it can't. Not to prove what you're trying to prove. Induction can only prove a statement true for all *finite* values of 'n'. So, yes, obviously once you pick a specific fixed number, n, if you take the set of all natural numbers up to and including n and compare that with the set of all primes up to and including n (assuming n is prime of course, otherwise it's not included) then your first set will be larger. That's all well and good for what it is, but it has no bearing whatsoever on what you're attempting to demonstrate.
You obviously don't know as much as you claim to know. Read and be enlightened:
http://en.wikipedia.org/wiki/Mathematical_induction
That's definitely about 'infinite' sets.
There isn't an intuitive "definition' of cardinality. There is intuition. There is a definition of sets having the same cardinality. These are 2 different things.
There is a 'definition' of sets having the same cardinality. Yes, and it is this 'definition' which is flawed and arbitrary. It fails to account for the rates at which things grow to infinity (which is precisely the thing I want to capture with some augmented aleph number--call it a 'bet' number if you like).
Ok, how about this thought experiment.
[This will at the same time address masterzora's gripes with my use of the word infinity and the concept of growing to infinity (both of which mind you I got from years of sitting in mathematics classes).
Take two children and give them an endless supply of marbles and each a container. Also give one child the ability (or a machine) to tell if a given number is prime). Then start the first child at the number one and tell him to count til he can count no more putting one marble in his container for each number he 'counts'.
Tell the second child to put a marble in his container anytime the first one calls out a prime.
I think you and I could both agree that the first child will have many more marbles than the second in his container before too long and that as more time passes, the larger the first's count of marbles will be in proportion to the second (i.e., the first child's marble count will grow at a constant rate whilst the second child's marble count will grow at an ever decreasing rate).
[This thought experiment should be able to be expanded to a formal inductive proof if that is what you want.]
Let me also state, that I completely understand the OP's proof. I just think that it isn't the whole story. [And, BTW, the first assumption from my proof is only false when talking about infinite sets. I cannot say that I know all of the math behind why infinite sets are allowed to break the intuitive definition of cardinality, but if it is like alot of things in math, it could be an arbitrary decision. And, if that is the case, then by simply changing that decision and the axioms involved, we could enter other and seemingly to me useful areas of math.
Math is dependent on the axioms (or at least the logic portion of it). I can choose the axioms I want whether or not they fit with your view of reality. Granted, it may not mean much, but in this case, I think that an alternative axiom set could produce interesting results.
Yes, precisely. I misunderstood the aleph number system to consider the proper subset sense. Do you happen to know if there is an infinity degree numbering system which takes into account the proper subset relation?
Yes, stand in awe of the mighty prophet RMS and his great foreknowledge! He has come to save us at last!
I actually prefer DropBox as it supports Windows, Mac & Linux. Also, Live Mesh has this nasty habit of bringing everything to a screeching halt if you happen to want it to sync a folder in which a large file (such as a Visual Studio .ncb file) resides (and if it sounds like I'm speaking from experience, I am!).