Tricki
a repository of mathematical know-how

Try to prove a stronger result

Note iconIncomplete This article is incomplete. This article is still missing several examples and discussion

Quick description

When we first set about trying to prove a result in mathematics, it can often be unclear which direction to take. If we try to prove a stronger result there is less room to manoeuvre and the proof can be easier to find.

Prerequisites

Undergraduate maths

Example 1: Every Subgroup of the Integers under Addition is Cyclic

Suppose we are trying to prove that every subgroup of the integers under addition is cyclic. Appealing to the definition of cyclic groups, we can see that what we are trying to prove is the assertion that for every group H that is a subgroup of the integers under addition, there exists g \in H such that for every h  \in H, h is some power of g. (Since we are talking about a group under addition, we interpret 'power of g' as 'multiple of g'.)

How can we find a stronger result that will be easier to prove. In fact, how can we find a stronger result that can be proven at all - after all, many stronger results, such as the result that 'all groups are cyclic' are false. Well, a useful technique for finding stronger results which are always true is to assume the result you are trying to prove and see what you can derive from it. If we are going to be able to prove this result at all, it must be true, so any result we can derive from it must be true as well.

So, bearing this in mind, let us consider a subgroup H of the integers under addition for which we have some g \in H such that for all h \in H, h is a multiple of g. What can we say about g? Let's assume that g is positive. (We are justified in doing this: if a negative number generates H, its inverse - which is positive- must also generate H; 0 cannot generate H.) Now, if we consider only those elements of H which are positive, we can see that, since they are all positive multiples of g, they must all be greater than or equal to g. So g must be the smallest positive number in H. This means that we can reformulate the result we are trying to prove as the following lemma, which is a stronger result:

Lemma 1 (The Strong Lemma) Every element of every subgroup H of the integers under addition is a multiple of the smallest positive number in H.

Proof of Lemma 1. This turns out to be quite easy to prove. The proof is by contradiction: let g be the smallest positive number in H and assume on the contrary that there is some element m \in H with m \neq a\times g for all a \in \Z. Now we can write m = q g + r for q , r \in \Z, q \geq 1, 0 < r < g. Clearly every positive multiple of g is contained within H + is a binary operation on H, so we can add g to itself any number of times to create a new element of H – so qg \in H. Therefore, the inverse -qg is in H. So m + (-qg) \in H. Since m + (-qg) = qg + r - qg = r, r \in H. But r is positive and less than g, and we had supposed g to be the smallest positive element in H. So we have derived a contradiction. So every element in H is a multiple of g.

The result that every subgroup of the integers under addition is cyclic clearly follows from Lemma 1.

General discussion

In this case, we derived the stronger result from the result we were trying to prove. This special case of proving a stronger result is discussed more fully in the article Prove a consequence first.