# Problem of Induction Solved!? Mathy People Look Here! Pretty Please?

Discussion in 'Off-Topic' started by Fifty, May 17, 2007.

1. ### Fifty!!!!!!!!!!!!!!!!!!!!!!!!!

Joined:
Sep 3, 2004
Messages:
10,649
Location:
The Problem of Induction is a philosophical problem that I have much interest in.

This paper purports to offer a possible mathematical proof of induction. I have no real math background yet, so I wonder if someone who knows about the math involved (I believe it's set theory) and/or who has the attention span to read five pages could tell me whether it seems like quackery or not?

Thanks,

Fifty Q Fiftyson

2. ### pboilyfingerlickinmathematickin

Joined:
Feb 27, 2003
Messages:
3,548
Location:
Fifty,

I can take a look at it. Can you give us a short description of the Problem of Induction? A small blurb that gets right to the bottom of it.

3. ### nihilisticIntergalatic Delivery Boy

Joined:
Feb 24, 2003
Messages:
3,261
Location:
NNYC
It's can't be. But I'll read it.

4. ### Fifty!!!!!!!!!!!!!!!!!!!!!!!!!

Joined:
Sep 3, 2004
Messages:
10,649
Location:
Thanks guys!

The problem of induction basically challenges the validity of inductive logic. It asks, how can we justify statments like "every raven is black, therefore the next raven I see will be black", or "everytime I walk outside my room, I go into a hallway and dont fall into a bottomless pit. Therefore, this next time I enter a hallway it will not be a bottomless pit", without resorting to a fallacy of begging the question. According to Hume, there are two possible ways we might justify induction, by a deductive proof, or by experience. Using experience to justify induction is fallacious though because that would be using an inductive argument to prove the validity of inductive arguments! So the only hope, apparently, is to erect a proof. This paper apparently brings up a result that might justify induction, at least in some forms.

It sounds pretty crazy that a proof might exist, but then again this isn't some random moron making that paper, it's a professor who regularly teaches philosophy of mathematics at a very prestigious liberal arts school (amherst)

5. ### pboilyfingerlickinmathematickin

Joined:
Feb 27, 2003
Messages:
3,548
Location:
Mathematically speaking, pages 2-3 appear sound (if one assumes the Axiom of Choice, the validity of which I can see being a big if for philosophers). The set W_f indeed has measure 0.

This part seems to contradict itself. No particular values are needed but the values of f on the interval are required? That being said, the bolded part in the statement is obvious for continuous functions, but in the context of general functions, I find it quite surprising.

Since the paper by Hardin and Taylor is forthcoming, I will reserve full judgement until I have seen the proofs of some of the other statements he makes (the one in footnote 3, particulary and I'd have to see a proof of footnote 5.)

Now, whether this can be used to solve the problem of induction ... in classical mathematics, we make heavy use of the Axiom of Choice, proofs by contradiction, principle of the excluded middle, etc. In some sense, these appear to be needed of any theory that will attempt to explain the "world" around us (i.e. a statement is either true or false, I can always chose a sock from a pair of socks, etc...)

But in some wider sense, I wouldn't trust them worth of ****. It is not at all clear that the Principle of the Excluded Middle and the Axiom of Choice hold in the Real World. Since the proof makes heavy use of EM and AC, I am still un-convinced that this beautiful piece of math can be used in the philosophical setting. But I don't know what constitutes a valid philosophical argument, so it might be all the rage by the time you respond to the post.

6. ### Fifty!!!!!!!!!!!!!!!!!!!!!!!!!

Joined:
Sep 3, 2004
Messages:
10,649
Location:
Very cool! Thanks a LOT pboily!

Cool stuff! To be honest I have no idea what constitutes a valid philosophical argument, and I'm not sure anyone else does. In fact there's a sizable literature devoted to the question of what constitutes a philosphical success and a philosophical failure. One running joke (attributed IIRC to David Lewis) is that a successful philosophical argument is one in which, if someone were to accept the premises and the logic used and still question the conclusion, they would die. Lesson: philosophers are bad comedians.

I haven't taken philosophy of math so I don't know much about what they think about various principles used heavily in math. The closest I've done is use Bertrend Russell's theory of linguistic reference and modal logic to disprove some supposed problems with the law of excluded middle, and Leibniz's law of the identity of indescernibles. That's more phil. of language stuff than math though.

7. ### chinesefireballChieftain

Joined:
Jul 17, 2003
Messages:
207
Well according to my pure maths book (in the number theory)

Math Induction-abstract form
If S is a subset of the natural numbers and if:
a) 1 is an element of S
b) k is an element of S implies that (k+1) is an element of S
Then S = the natural numbers

Proof
Let T = N\S (that is the set of natural numbers, without the elements that are also in S). If T = the empty set, there is northing more to show.
Suppose T is non-empty. Then by the well ordering principle, T has a least element say t0. Now t0 is not equal to 1, as 1 is an element of S (a) and t0 is not in S. Therefore, t0 > 1, so t0-1 is an element of the natural numbers. Also (t0 -1) is an element of S, because t0 is the smallest element of T. Therefore by part b), (t0-1) + 1 = t0 which is an element of S. Hence we have a contradiction with the fact that t0 is an element of T. Therefore T is hte empty set, and so S = Natural numbers.

Mathematical Induction (concrete form)
Let claim(n) be a statement about n for n an element in the natural numbers. Suppose that:
a) claim(1) is true
b) claim(k) is true implies that claim(k+1) is true
Then claim(n) is true for all n in the natural numbers

Proof:
Let S = {n is an element of the natural numbers: claim(n) is true}. Then 1 is an element of S by a), and k is an element of S implies k+1 is an element of by b). Therefore by the abstract form of mathematical induction, S = N, that is, claim(n) is true for all n.

Might not make much sense (I only just understood it properly typing it out). What the abstract form is saying: say we have some positive integers in a group S. We get told that 1 is part of S and we know that if k is part of S, then k+1 is part of S. So we say T is all the positive numbers not in S, and ket t0 be the smallest of these (thats what the well ordering principle says). to can't be equal to 1 as we know 1 is in the group S, so t0 > 2, therefore t0-1 is a natural number. So since t0 is the smallest in T, t0-1 must be part of S. But we are told in b, that any number in S plus 1 is also part of S i.e. (to-1)+1 is part of S. So we have a contraduction (t0 is part of S and T). Hence our assumption that T is not empty is false. So then S contains all the natural numbers, so it is equal to the natural numbers.

In each theorem, a) is the first step of an induction proof (show true for the first element), b) is the algebra bit (assume true for k, prove for k+1)

So the stuff you were looking at (admittedly I skimmed over the first few topics) are talking more about the logical implication, or this arrow symbol =>, which is read as implies. So the basic statemetns relating to it are:
true implies true, TRUE
true implies false, FALSE
false implies true, TRUE
false implies false, TRUE
I'm not sure how they got those though

8. ### pboilyfingerlickinmathematickin

Joined:
Feb 27, 2003
Messages:
3,548
Location:
The paper is emphatically NOT considering mathematical induction (in the classical sense).

9. ### Fifty!!!!!!!!!!!!!!!!!!!!!!!!!

Joined:
Sep 3, 2004
Messages:
10,649
Location:
pboily is of course correct. This is about whether, as the abstract puts it "the past can bear rationally on the future".

It's really an interesting problem. Kindof a neat blend of logic, epistemology, and the metaphysics of time.

10. ### WillJCoolness Connoisseur

Joined:
Aug 9, 2002
Messages:
9,471
Location:
USA
Well, even if the math is sound, how do we know it will be sound in the future?

Joined:
Oct 5, 2001
Messages:
30,061
Yes - and I think this can be used to 'prove' that 1==0. The flaw in induction is that not all numbers behave the same: You can divide by 1; you can't divide by zero.

12. ### Kennigitproud 2 boxer

Joined:
Apr 29, 2007
Messages:
6,957
Location:
gatech alum
This was explained to me by someone else-

Lets say you are trying to prove that 2x+1 is odd for any positive integer x.

1 First prove that it is true for 1 (or another integer). 2(1)+1=3

2 Second, assume that it is true for k. (2k+1 is odd).

3 Now, show that it is true for k+1.

2(k+1)+1
2k+2+1
(2k+1)+2
Since 2k+1 is odd, (2k+1)+2 is odd.

Therefore, for any positive integer k, where 2k+1 is odd, 2(k+1)+1 is odd.
Since this is true for k=1, it is true for k=2, and so it is true for k=3, etc.
Therefore, 2x+1 is odd for any positive integer x on and on until infinity.

The point of Mathematical Induction is to show that something like this is true for numbers on and on to infinity.

Mathematical Induction is not the same as general induction (eg- all swans are white).

13. ### ImcalfinChieftain

Joined:
Sep 23, 2006
Messages:
112
In everyday context this is definately nitpicking but: The above statement is, as far as I can see, valid reasoning. If we know for a fact that all ravens are indeed black then the next raven we observe must be black. Modified to the form:"every raven we have so far observed is black..." it will not be valid in the ironclad deductive sense unless we have observed all ravens and found them to be black. But that would make the "next raven" somewhat trivial since it would have had to have been already observed to make the argument valid beyond any doubt. It can be (and in philosophy, usually is afaik) argued that inductive reasoning from a fully known set (can't remember the proper term) isn't induction in the philosophical sense but a form of deductive reasoning.

14. ### chinesefireballChieftain

Joined:
Jul 17, 2003
Messages:
207
I think my proof gets around this by only appying to the natural numbers, i.e. 1 and above. Besides the getting 1 to equal 0, as you say, involves dividing by 0 which just isn't mathematically correct (I suppose it would be done in the part b, and so to get b to be true you will have to divide by 0, making your proof invalid).

If you do want to use induction to prove something about numbers say, greater then and equal to 0, officially you do prove it for all natural numbers, but in your statement you have n-1, instead of just n.

Joined:
Aug 7, 2004
Messages:
13,024
Location:
Closer than you'd like
A little something to muck up the works. Got this one from Martin Gardener (though I don't know who he got it from or whether he came up with it himself).

Pick the Ace through Ten of spades out of a deck of cards. Shuffle the ten cards and deal them out in a row.

Hypothesis: no card with value X is in the X'th position from the left. (i.e. you're guessing the first card is not the Ace, and the second card is not the Two, etc).

Now turn over the first nine cards. Suppose you see these nine:

4 5 9 8 2 7 A 3 6

We now have nine examples proving the hypothesis----except, since there's only one card left.....and we know it's the Ten.....and the tenth spot from the left is the only one we haven't checked........

There ya have it. Each time we turned over a card, we received evidence to back up the hypothesis--but all nine confirming instances, taken together, REFUTE it!

I don't think a proof of mathematical induction is possible. The only way to know for certain that all crows are black is to examine every single last crow.

16. ### Kennigitproud 2 boxer

Joined:
Apr 29, 2007
Messages:
6,957
Location:
gatech alum
There are proofs for mathematical induction. It's just mathematical induction is seperate from general induction. Mathematical induction is exactly what is says in its name- its mathematically based and does not extend beyond that.
Again, saying that all swans are white because no black swans have been seen is not mathematical induction.

Lots of neat little proofs/loops exist. This example has popped into my head- proving that .9 repeating = 1.

.9999.... does not equal 1, but we can make it as x so x=.9 repeating.
10x in this case would equal 9.9999 repeating.
10x - x= 9x, and 9.99999... -.999999.... would equal an even 9.
This makes 9x=9, so x=1, even though x is .9 repeating.

17. ### nihilisticIntergalatic Delivery Boy

Joined:
Feb 24, 2003
Messages:
3,261
Location:
NNYC
Uhh, induction is one way. Doesn't go backwards. Anyway, 1!=0 is actually an axiom. Alternatively you can actually assume 1==0 and come up with a perfectly consistent universe: the singleton universe of {0}.

That's derangement, not induction. The premises of induction include the initial case and the recursive case. Your example have the initial case part down, but not the recursive one. You did not prove for all k, P(k) imply P(k+1).

18. ### nihilisticIntergalatic Delivery Boy

Joined:
Feb 24, 2003
Messages:
3,261
Location:
NNYC
Furthermore, the problem Fifty stated was "induction", not "mathematical induction". Those two are very different concepts that have almost nothing to do with one another. Also, "mathematical induction" is still a method of deduction. Math never induces.

19. ### nihilisticIntergalatic Delivery Boy

Joined:
Feb 24, 2003
Messages:
3,261
Location:
NNYC
OK, I've read it. To answer your original question first: No it isn't a "proof of induction", nor is a "proof of induction" EVER possible.

As for what the article said, it is tersely described in this quotation:

"The result, as the authors soberly put it, is &#8220;peculiar&#8221;. It might also seem positively paradoxical. The proof tells us that every function is such that the Hardin-Taylor rule will be right in predicting its values almost all of the time. But surely, each time the rule is employed it will generate incorrect predictions for just about any world one might be in. Knowing the behavior of an arbitrarily chosen function at points less than t offers one no way at all to work out its value at t: the information given is just irrelevant to the conclusion drawn. Now, these two claims certainly appear to conflict. To put the matter another way, the proof tells us that if one takes any particular function and asks,&#8220;At how many points will the Hardin-Taylor rule correctly predict the value of this function?&#8221;, the answer is &#8220;Almost every.&#8221; And yet it seems obvious that if one considered any particular point and asked, &#8220;How many functions will have their values at this point correctly predicted by the rule?&#8221;, the answer would be &#8220;Almost none.&#8221;"

Much of his argument is based on another paper:

"&#8220;A Peculiar Connection Between the Axiom of Choice and Predicting the Future&#8221;, Christopher Hardin and Alan D. Taylor, American Mathematical Monthly, forthcoming."

Of which I don't currently have access to but of which I also doubt he has full comprehension of. Why do I think he doesn't fully comprehend what he is saying? Because his claim is quite far-fetched:

"Every function f from &#8477; to &#8477; is such that, for almost every point t in &#8477;, the Hardin-Taylor rule will correctly predict the value of f at t."

I'm pretty sure that whatever the Hardin-Taylor rule is, there must be some constraints on said function that the author neglected to state. Otherwise, a general function from R to R is completely unpredictable empirically. Most likely there are some constraints such as "differentiable", "continuous", "integrable", etc. that the author ailed to mention. This is afterall a philosophy paper. He might be betting on his professor not knowing the subject.

Joined:
Sep 3, 2004
Messages:
10,649
Location: