User bogdan grechuk - MathOverflow

Elementary problem with Fibonacci numbers

2010-09-13T17:13:32Z

I need help in proving one elementary result with Fibonacci numbers. Prove that for $n>2$, the product $F_1 \cdot F_2 \cdots F_n$ cannot be a perfect square, where $F_1 = F_2 = 1, F_{n+1}=F_n + F_{n-1}$.

Derivation rules and Godel theorem

2010-06-28T12:04:18Z

Every formal theory is a collection of alphabet, axioms and derivation rules. My question is - what kind of "derivation rules" are acceptable here. For example, "from A B it follows $A \cup B$" is a valid derivation rule. But what about, say, D: "from K it follows Cons (T(K))" where K is any collection of axioms, T(K) is the theory with axioms K and some prespecified alphabet and derivation rules? If alphabet of T(K) is reach enough to express the statement "Cons (T(K))", I see no reason why D is not a valid derivation rule.

But if it is, let us add this derivation rule D to ZFC, and denote the resulting theory ZFC+. Now, sets of axioms in ZFC and ZFC+ coincide, so it is recognizable. Next, if we believe that all axioms in ZFC are sound, all theorems in ZFC+ are also sound, and hence ZFC+ is consistent. Finally, if we apply D with K = "all axioms in ZFC+" we derive Cons (ZFC+) in one step. This is a contradiction with Godel Theorem. So, D is not a valid derivation rule? If so, why?

Can we hope to solve all Diophantine equations?

2010-06-24T12:13:33Z

According to Godel result, neither ZFC nor other particular theory is strong enough to resolve all questions about, say, Diophantine equations. But maybe we can hope that a sequence of theories will help? It is known that ZFC-1 theory (ZFC + Cons(ZFC) ) is much stronger than ZFC, in sense that now there are theorems with extremely shorter proofs, and many new theorem are now decidable. If we continue this to ZFC-2, .., ZFC-n, ... then ZFC-w which is union of all, ZFC-(w+1) and so on, we can continue to extremely large sets of theories, about all of them we have no doubts, and maybe now for every natural Diophantine equation we can choose a theory witch resolve it? Moreover, if we would be able to imagine non-enumerable set of such theories, may be we could hope that for EVERY Diophantine equation has a corresponding theory from this set in which it can be resolved? Or this is trivially incorrect “conjecture”? It seems that this does not contradict to Godel Theorem, which consider one theory, not a sequence of theories.

Another way of thinking about the same idea is to take only axioms from ZFC but add a new derivation rule, which would say that "from any set of axioms A it follows that A is consistent". With this derivation rule we would derive Cons(ZFC) in one step! So, for some reasons (by the way, I do not understand why) Godel theorem is not applicable here. May we hope that with ZFC extended with such a new derivation rule we can, say, solve all Diophantine equations?

Comment by Bogdan Grechuk

2010-09-14T09:37:55Z

Yes, I have. It is in the book with problems for mathematical olympiads. I prepare high-school students for olympiads and the next topic will be Fibonacci numbers, so I try to find appropriate problems.

Comment by Bogdan Grechuk

2010-09-13T18:52:23Z

Interestingly, from elementery identity F_{n+1}*F_{n-1} - F_n^2 = (-1)^n it follows (without COHN Theorem) that F_{n+1} and F_{n-1} cannot be both exact squares, so if we would have prime p and p+2 greater than n/2, the same agrument would finish the proof ... But twin prime conjecture is a little bit harder than COHN Theorem :)

Comment by Bogdan Grechuk

2010-09-13T18:45:51Z

Thank you! Although I am sure that this question should be more elementary than the COHN Theorem, which was open question for decades...

Comment by Bogdan Grechuk

2010-06-28T15:37:06Z

Actually, by "Cons (T)", better say in full "Cons (A, T, Der)" I mean consistency of theory with alphabet A, axioms T, and derivation rules Der + D :) Yes, I agree that such a derivation rule is a little bit strange and self-contained, but I have no doubt that you cannot derive false statement from true axioms with it. For example, if you would prove me, say, twin prime conjecture using ZFC+, I see no reason why this would not be a legitimate proof.

Comment by Bogdan Grechuk

2010-06-28T15:21:07Z

Thank you. You wrote "To have a sound rule, you should accompany it by a change in what counts as a legitimate model". So, I may say "lets add my rule D to PA and consider only standard model"? Now, in standard model new rule (and hence new theory) is sound, can prove (in one step) its own consistency, and, as pointed out by Professor Carl Mummert, Godel Theorem is not applicable for this theory. This is interesting... May be, adding new rules of deduction to well-known theories could help us to create new, more powerful theories, valid not in all models, but in "interesting" ones.

Comment by Bogdan Grechuk

2010-06-28T15:07:57Z

Thanks! So, the answer to my question"which derivation rules are called valid" is, roughly, "rules which are sound in all interpretations(models)". But I really like you first answer: If Godel theorem includes only theories that cannot specify additional rules of deduction, then, after adding new deduction rules like mine, we (potentially) can get sound theory whose axioms can be listed by an "effective procedure", but which is capable of proving, say, all true facts about the natural numbers! And you know, I would be happy to have such a theory, even if it is valid in the standard model only!

Comment by Bogdan Grechuk

2010-06-28T13:18:07Z

If, in contrast, K (ZFC in our case) is not consistent, then at least one axiom in K is False, and we derive, with this rule, False conclusion Cons (ZFC) from False assumption, which is not a problem - the rule itself is still "valid".

Comment by Bogdan Grechuk

2010-06-28T13:11:56Z

What do you mean by "The rule is valid only if the axioms are already consistent"? My understanding is that a rule is not "valid" if we can derive false statement from TRUE statement. If we can derive False from False, this does not mean that the rule itself is not valid. For example, is rule "from A B it follows $A \cup B$" valid? Clearly, if A and B are false, then we can derive false statement $A \cup B$, but this, as I understand, does not imply that this rule itself is not valid. Similarly, my rule D is "valid", because if all assumptions K are True, then the conclusion is also True.

Comment by Bogdan Grechuk

2010-06-28T09:51:35Z

Similarly, if we denote axioms in tower $T_\alpha$, $\alpha$ ordinal, then statement "$T_{\omega 2 + 1}$, where $\omega$ is the least infinite ordinal" is axiom. In contrast, statement "$T_\alpha$, where $\alpha$ = (some complicated description such that it is not clear if it is ordinal or not)" is not an axiom, similarly to statement S above. So, I agree, that not all axioms in towel can be formulated and "we can proceed only so long as the ordinal itself is describable in ZFC". But, if some statement IS formulated, it should be easy to say if it is axiom or not.

Comment by Bogdan Grechuk

2010-06-28T09:51:25Z

Now I do not understand "recognizable" here. Yes, in Theory "all true statements are axioms" it is hard to say if "twin prime conjecture" is axiom or not. But suppose a theory has reflexivity axiom in the form "x-x=0". Now what about statement S: "x-x = (0 if twin prime conjecture holds, 1 otherwise)". Do we have the same problem "this is axiom if and only if twin prime conjecture holds"? I would say no. I would say that this is not an axiom in any case. This is not my problem to recognize if some complicated description is 0 or not.

Comment by Bogdan Grechuk

2010-06-27T13:10:44Z

2 Michael Herdy Matijasevich's theorem states that there is no single algorithm for all equations, or, equivalently, no single theory can resolve all of them. My question is that may be the sequence of theories can help. But, as noted by Prof. Joel David Hamkins, this particular sequence is inside a single theory ZFC+Inaccessible, so it will no work. But may be other sequences may help?

Comment by Bogdan Grechuk

2010-06-27T13:05:57Z

The point of this sequence is that 1) all axioms seems to be recognizable but 2) there is no union theory in the sequence, because if T is the one, then "T+(T is consistent)" is not in T. So I hope it can help. But, if the whole tower is included in a single theory ZFC+Inaccessible, so, clearly, nothing interesting can happen here. Thank you.

Comment by Bogdan Grechuk

2010-06-24T13:30:07Z

It is important, that all the axioms are easy to recognize here, and the problem "We cannot tell if a proof is legitimate, because we cannot even recognize the axioms" do not arise with this sequence.

Comment by Bogdan Grechuk

2010-06-24T13:29:44Z

Yes, I agree with you, but I am asking not about one theory T but about the whole sequence of theories: ZFC1 consisting of "ZFC+(ZFC is consistent)", ZFC2 is "ZFC1+(ZFC1 is consistent)", etc, and for any ordinal $\alpha$ we get theory $ZFC_\alpha$. If we try to say that union of all this theories is T and apply your argument, that your polynomial $p_T$ will be resolved by next theory in a sequence: "T+(T is consistent)"! So, no particular theory T will help for ALL equations, but for every particular equation we can hope to find a corresponding theory in sequence which will resolve it.