Proving theorems

Post Reply New Topic

Do you think one could prove that that there is only one solution to a problem by devising an algorithm for finding that solution? Specifically I'm thinking of the problem of finding the prime factorization of a natural number. Just wondering what your thoughts on this are.

You could incorporate the proof into your algorithm by at each step proving that each prime factor MUST appear in the final answer exactly the number of times your algorithm calculates it, but that would be redundant. It makes more sense just to prove that once as the general case.

It certainly could. Though it might be better to view them as two separate things. In similar most cases you try to find an answer to a certain test example and then find the proof of the problem and by doing that you get the idea how you can proof your solution and at the same time find a possible algorithm.
I assumed your problem is: proof that the prime factorization of a number is unique, is this correct?

^^ Greetings LordoftheMonkeys. I am very sorry if I am incorrect, however I do believe that in order to prove that a happy solution is unique, I believe that you may begin by stating that there are two solutions and write these solutions (in general forms, for instance of the form p and p'). ^^ Following this, I believe you may prove that they must be equal. ^^ I apologise greatly if this is not of help for you. I do believe that I may possess the happy particular proof that you desire within my Mathematics notes and would be very happy to type these for you if you would wish for this.

I cannot quite tell from LordoftheMonkey's original post what the problem is.

If the problem is "prove that the prime factorization of a given number is unique", then you might as well refer to the Fundamental Theorem of Arithmetic ("the prime factorization of every number is unique"), which was properly proven by Gauss, although practically proven by Euclid. See http://en.wikipedia.org/wiki/Fundamenta ... arithmetic

If the problem is proving that a given theorem has one unique proof, then I'd be very stuck on that one. But I would guess that it's possible, given that it is possible to prove that a given proposition cannot be proved within a given system. (Eg, It's been shown that Euclid's parallel postulate cannot be derived from his other axioms of geometry.)

My first guess on original question would be no. If you devise an algorithm to find a solution for a given problem that by no means is enough to prove that it is the only solution. If you somehow do manage to include that as well in your algorithm then i`d say you included the proof in your algorithm thus basically making the algorithm an extended version of the proof itself.