Try to prove a stronger result

a repository of mathematical know-how

Try to prove a stronger result

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[note article incomplete]This article is still missing several examples and discussion[/note]

[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 | 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 [[w:Cyclic group|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$?  [add]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$.)}}[/add]  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:

[frame][lemma strong|The Strong Lemma] Every element of every subgroup $H$ of the integers under addition is a multiple of the smallest positive number in $H$. [/lemma][/frame]

[proof strong]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$.  [add]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$}}[/add] -- 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$.[/proof]

The result that every subgroup of the integers under addition is cyclic clearly follows from [ref Lemma #strong].

[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]].

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Try to prove a stronger result

Recent articles

Active forum topics

Recent comments