From ProofWiki
Jump to navigation Jump to search


I have started here to collect motivations for several house rules as I find them here and there on this website. This is meant as a public service. Anyone who has the time and inclination, please feel free to add to this page, or correct it in case of any mistakes.

1. Refactoring is only to be done by experienced contributors.

One of the reasons for this concerns the links in the Sources section at the bottom of the page. Contributors have in the past demonstrated that they have difficulty in understanding or motivation when it comes to making sure that the flow is consistent. In particular, note that the "next" link from [one result] from [one source] no longer goes to the next page in the sequence for [that source], because it has been moved from [the original page] to [a newly created subpage for a proof] and so the flow has been broken.
Because it takes considerable effort and care to make sure that the flow is not compromised, we respectfully request that you please do not do any of this "refactoring", and instead (unless a page already has several sub-proofs on separate pages) just add further proofs on the same page, leaving it up to the administration team to split them up into subpages. In that way, administrators (and in particular, those who have direct access to the specific works which cite material held on these pages) may ensure that the flow is no longer compromised.
Note that it is not only that the links need to be updated to point to the particular (e.g.) "/Proof 1" page. It also needs to be determined whether the work in question actually documents that proof, or whether they just quote the result, in which case the citation link needs to stay on the original page.

2. The proofs on this website should match the proofs in the sources they were taken from, modulo house style.

Motivation: ?

3. Links to subpages should use redirects.

Two reasons. Firstly, it's nicer to display (particularly applicable to theorems) and to type. Secondly, the fact that subpages are needed makes it highly more likely that the page structure will be refactored again, in which case it just takes an update of the target of the redirect rather than updating all links everywhere. (To those familiar with OO-programming, the view of the redirect as an interface or API might be clarifying.)

Proofs by Contraposition

The below was collected in response to the statement made on my talk page that "Whether you prefer it to be a proof by contraposition or not, does not mean it is a proof by contraposition until it is turned into it."

Source 1

There is a useful rule of thumb, when you have a proof by contradiction, to see whether it is "really" a proof by contrapositive.

In a proof of by contrapositive, you prove P→Q by assuming ¬Q and reasoning until you obtain ¬P.

In a "genuine" proof by contradiction, you assume both P and ¬Q, and deduce some other contradiction R∧¬R.

So, at then end of your proof, ask yourself: Is the "contradiction" just that I have deduced ¬P, when the implication was P→Q? Did I never use P as an assumption? If both answers are "yes" then your proof is a proof by contraposition, and you can rephrase it in that way.

For example, here is a proof by "contradiction":

   Proposition: Assume A⊆B. If x∉B then x∉A.

Proof. We proceed by contradiction. Assume x∉B and x∈A. Then, since A⊆B, we have x∈B. This is a contradiction, so the proof is complete.

That proof can be directly rephrased into a proof by contrapositive:

   Proposition: Assume A⊆B. If x∉B then x∉A.

Proof. We proceed by contraposition. Assume x∈A. Then, since A⊆B, we have x∈B. This is what we wanted to prove, so the proof is complete.

Proof by contradiction can be applied to a much broader class of statements than proof by contraposition, which only works for implications. But there are proofs of implications by contradiction that cannot be directly rephrased into proofs by contraposition.

   Proposition: If x is a multiple of 6 then x is a multiple of 2.

Proof. We proceed by contradiction. Let xbe a number that is a multiple of 6 but not a multiple of 2. Then x=6y for some y. We can rewrite this equation as 1⋅x=2⋅(3y). Because the right hand side is a multiple of 2, so is the left hand side. Then, because 2 is prime, and 1⋅x is a multiple of 2, either x is a multiple of 2 or 1 is a multiple of 2. Since we have assumed that x is not a multiple of 2, we see that 1 must be a multiple of 2. But that is impossible: we know 1 is not a multiple of 2. So we have a contradiction: 1 is a multiple of 2 and 1 is not a multiple of 2. The proof is complete.

Of course that proposition can be proved directly as well: the point is just that the proof given is genuinely a proof by contradiction, rather than a proof by contraposition. The key benefit of proof by contradiction is that you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses.

It's not the same.

If P and Q are statements about instances that (a priori independently) are true for some instances and false for others then proving P⇒Q is the same as proving the contrapositive ¬Q ⇒¬P. Both mean the same thing: The set of instances for which P is true is contained in the set of instances where Q is true.

Proving a statement A by contradiction is something else: You add ¬A to your list of axioms, and using the rules of logic arrive at a contradiction, e.g., at 1=0. Then you say: My axiom system was fine before adding ¬A. Since this addition has spoiled it, in reality A has to be true.

Source 2

When coming to prove P⇒Q, we can either:

  1. Prove directly, that is assume P and show Q;
  2. Prove by contradiction, that is assume P and ¬Q and derive contradiction; or
  3. Prove the contrapositive, that is assume ¬Q and show ¬P.