# My problem in understanding the minimal counterexample technique

If minimal counterexample method of proof is to assume to opposite of an argument is true and then finding a counterexample for the opposite and then concluding the validity of the original argument, then can't you say that the opposite of the Collatz conjecture is that the process will eventually reach to some number(s) other than 1, and if you put, say, 5 inside the Collatz function you'll reach one, so you found the counterexample, so the Collatz conjecture is valid?!

I know this approach is wrong, because any conjecture that was shown to be wrong with a large counter example will be proved right by this approach, or any theorem in any field that is valid can be easily proved because its opposite must be invalid therefore have counterexamples.

Where is my problem?

• It's not really about finding any specific counterexample. We assume a counterexample exists, then we use some (well-)ordering of the objects in question to argue there is a "smallest" counterexample, and usually proceed to construct a smaller one, using this allegedly smallest. For example, if we could show that if Collatz sequence does not terminate for $n$, then it does not terminate for $[n/2]$, then we could conclude there is no smallest counterexample. Since the set of positive integers is well-ordered (every nonempty set has a smallest element), there cannot be counterexamples at all. – Marcin Łoś Feb 23 '14 at 8:36

"minimal counterexample method of proof is to assume to opposite of an argument is true and then finding a counterexample for the opposite and then concluding the validity of the original argument" This is false. The minimal counterexample method is to assume the opposite of a claim is true, and then to examine a minimal (in a sense dependent on context) counterexample to the original claim (a counterexample to the original claim must exist under the assumption of the opposite claim, and if things are nicely ordered, we can talk about a minimal one).

For an example of this type of argument, consider this proof that every number greater than $1$ can be written as a product of primes: Suppose, for sake of contradiction, that the claim is false; suppose that there are numbers greater than $1$ that can't be written as a product of primes. Then there should be a smallest one (a minimal counterexample to the claim "everything is a product of primes"); call it $n$.

Now, if $n$ can only be written as a product in forms like $1\times n$, then $n$ is prime, and hence isn't a counterexample after all. Otherwise, $n=a\times b$ where $a,b>1$. But since $n$ can't be written as a product of primes, at least one of $a$ and $b$ can't either. But since $a,b>1$ they must both be smaller than $n$. And hence $n$ isn't minimal after all. Since the concept of $n$ has problems either way, there must be no counterexample to the original claim after all, and every number greater than $1$ can be written as a product of primes.

Tread very careful here.

First of all conjectures can say two different things:

a) There is something with a described property.

or

b) Everything has a described property.

Depending on which kind of conjectures you want to disproof the method differs:

If the conjecture is of the kind: Everything has a described property.

Then it is simple,(relativly speaking that is) find something that doesn't have the described property (this is a counter model)

You can go even easier (again relativly speaking that is) you don't even have to show the something that doesn't have the property, just proving it exists is enough.

If the conjecture is of the kind: There is something with a described property.

Then it is much harder (again relativly speaking that is) you need to proof that nothing has the described property, or more correct everything lacks that property/ doesn't have that property.

Unfortunedly it is not always clear which form the conjecture is (and some conjectures can be said in both ways) so fist find out what form the conjecture is you want to disproof.

(if in doubt think that it is of the kind, There is something with a described property, a disproof of this also disproof the other form, but as said befor this is a much harder proof)

An example of a false conjecture of the form: Everything has a described property: There is no even prime (for each number if the number is even it is not a prime) Giving a single even number that is prime invalidates the conjecture.

An other example of a false conjecture of the form: Everything has a described property: There is no largest prime (For each number there is an even larger prime number) Nobody expects you to give the largest prime, but you do need to proof that for every number there is an even larger prime number.

An example of a false conjecture of the form: There is something with a described property: There is an even prime greater than 10 Now this is much harder you will even need to use induction to proof it is wrong:

• proof that 10 isn't prime
• if 8 + 2 * n is not a prime then 8 +2 * (n+2) isn't prime

(see much more work)

Now the Collatz conjecture is of the form: Everything has a described property: (for every number , doing the procedure, it at a certain point the number becomes one)

So you only need to give one number where it is not the case or a proof that such a number exist.

(but as said before easy has to be taken very relative here)

Hope this helps