Sometimes when I’m proving a mathematical problem, I might find out that i still need some hints(some important theorem, hypothesis,etc). Is there any possibility to know(to predict) what we need in the proof? Can the model theory solve this problem? Or something about Gödel’s completeness theorem?
Asked
Active
Viewed 45 times
1
-
at the start is predictable that you are going need the basics of set theory as well some standard tricks of basic logic – janmarqz Jun 18 '18 at 23:24
1 Answers
1
There's sort of two ends to this question, as I see it. First, the technical:
"What do I need to prove this?" is really asking "Of the axioms I have, which ones are necessary for the result I want?" Remember, if it's some important theorem you need or something else that isn't an axiom, you could in principle just prove it yourself and then use it, so you don't technically "need" it. The question of which axioms are necessary to prove a certain result is actually a major field of study, called reverse mathematics - you may want to look into it, it's very interesting! But no, we can't generally know which axioms are necessary for a result, and it's for exactly the reason you suggest - Godel's Incompleteness. The easy example is to consider the collection of axioms $PA + 1 = 0$ (that is, Peano arithmetic together with the false statement $1 = 0$) and say we wanted to prove $1 = 0$. This is a consequence of these axioms, but to know whether we need $1 = 0$ to do this proof we would need to know whether $PA$ is consistent. (This argument is a bit loose, but gives the right idea.)
Next, the practical: Of course, in practice, we do care whether an important theorem is necessary, because we can't really expect to prove them on our own. And no, there's no way to predict whether you'll need it - but as you do more and more proofs in a certain field, you start to get a feel for it. If you talk to mathematicians about a problem in their field, you'll probably hear them say something like "oh, yeah, that's just Fermat's Little Theorem" or "it's just a finite-injury construction, right?" They can predict the technique or the central theorem just because they know the field well enough to know what the "usual" tools are. And, while they aren't always right, they're usually okay at it.
Reese Johnston
- 17,988
-
Very appreciate for your answers. Another question: if there is an mathematical assertion(I use letter “a” to represent it) and some important mathematical information(h), can we verify the truth value of “h$\Rightarrow$ a”? For example: if (a) is “axiom of pairing(ZFC)”, the hypothesis(h) are “axiom scheme of replacement and axiom of empty set”, we can proof (a) by (h). Someone told me that I should read some books about model theory... – Tzi yan Tschen Jun 19 '18 at 20:40
-
@TziyanTschen Yes, we can - this is the "reverse mathematics" I was talking about. The general technique is to either (1) give a proof of (a) using only (h), or (2) give an example of a situation in which (h) holds but (a) does not. Of course, by Godel's Incompleteness, we can't always do either - for example, if (h) is $PA$ and (a) is $1 = 0$, we cannot determine whether (h) implies (a). – Reese Johnston Jun 19 '18 at 20:44
-
It’s amazing. How can we do that? Can we use this technique in the homework of undergraduate students (like arithmetic, or analysis)? need some examples... – Tzi yan Tschen Jun 19 '18 at 20:57
-
@TziyanTschen Well, the classic example is showing that the Axiom of Infinity is not a consequence of the other axioms of ZFC. To prove this, let $\mathcal{P}(A)$ denote the power set of $A$, $\mathcal{P}^{n+1}(A) = \mathcal{P}(\mathcal{P}^n(A))$, $\mathcal{P}^0(A) = A$ (so $\mathcal{P}^n$ means "take the power set $n$ times") and let $V = \bigcup_{n \in \mathbb{N}}\mathcal{P}^n(\emptyset)$. It's fairly straightforward to show that all of the axioms of ZFC hold inside this set - except Infinity, because everything is finite. – Reese Johnston Jun 19 '18 at 21:03
-