Why does "guess and verify technique" not involve circular reasoning?

Question

I know of several proofs from differential equations, game theory and dynamic programming which uses the "guess and verify technique".

However, now when I think back, I'm not so sure why these proofs don't involve circular reasoning. Is it because you can always check the properties given exogenously, to see whether the solutions obtained by guess and verify is correct? What makes this technique fundamentally different from the fallacious circular reasoning (where you also propose something out of thin air and use it as an assumption)?

Answer 1

Question: "Find an $x$ such that $x^2 = 9$."

Answer: "I magically intuited that $x=3$ might work. I plugged that into the equation, and found that indeed $x=3$ causes $x^2=9$. So my answer is $x=3$."

Or, to phrase it more formally: "Let $x=3$. Then $x^2 = 9$. So $x=3$ is my answer."

That's a guess-and-verify answer. The reason it's a valid answer is because all I need to do to demonstrate that I've found a valid $x$ is to display such an $x$ and prove that it has the right property. A proof need not say anything about how the creator came up with it.

Circular reasoning in this instance would go something like "Suppose $4^2 = 9$. Then $x=4$ would work. So $x=4$ is my answer." The key here is that we've got a hanging assumption at the beginning of the proof: we supposed $4^2 = 9$, and all the rest of the argument depends on that assumption, which we never proved to hold. The difference between this argument and the former, valid argument is that we're allowed to assign values to variables freely as long as we do so consistently (we can't let $x=3$ and $x=4$ in the same phrase), and that's what we did in the correct argument. But "suppose $4^2 = 9$" is attempting to assign values to other values, rather than to variables.

If you have a more specific and less obviously-trivial example, I'd be happy to walk through it.

Answer 2

I think there's another potential issue at play here. The "mysterious process" of finding the right guess $x$ often does involve making dubious assumptions. But all that doesn't matter, because it's not part of the proof. Once you have found the example, we don't care where it came from: it stands on its own, and one you prove (without any dubious assumptions) that it has the right properties, you're done.

Answer 3

Circular reasoning involves making an unjustified assumption; proof by guess-and-check, though, doesn't. What is (arguably) under-justified is the choice of example used; however, that doesn't make the proof invalid, merely more mysterious.

A proof is valid if it "follows the rules." There's no rule that says that the proof explain why each step is performed the way it is, the steps just have to be valid.

Answer 4

This is just normal existential elimination. If you want to prove $\exists x.P(x)$ holds, you just need to produce a $t$ such that $P(t)$ holds. How you produce $t$ is irrelevant. Solving an equation, including a differential equation, is proving an existential statement. Of course, you are usually asked to find the most general solution and that goes beyond merely proving the existential. That's why when you guess an ansatz for a differential equation and verify that it satisfies the differential equation, you still need to prove that it is the most general solution with additional arguments.

It's somewhat interesting to look at how existential elimination is mechanized in proof assistants/theorem provers as what humans do has some similarities. When a theorem prover tries to prove $\exists x.P(x)$ it may guess but usually it will start by producing a unification variable. This is a meta-variable that stands for an unspecified term. Call the unification variable $X$, we now want to prove $P(X)$. As the theorem prover goes through the process of attempting to prove $P(X)$ constraints are added that partially (or fully) specify the term that $X$ stands for. For example, we may come to the conclusion that $X = f(X_1)$ where $X_1$ is a new unification variable. This is similar to guessing that the ansatz for a differential equation is $Ae^{Bx}$ for some to-be-determined $A$ and $B$. Eventually, the theorem prover either ends up with contradictory constraints on $X$, disproving $\exists x.P(x)$, or it succeeds in proving $P(X)$ with a consistent set of constraints on $X$. These constraints may only partially specify the term $X$, but that just means the unspecified parts (usually represented by unconstrained unification variables) can be any valid term. This is like getting a solution to a differential equation like $A\cos\phi + B\sin\phi$ where $A$ and $B$ are arbitrary. Many forms of unification are guaranteed to produce the most general solutions, but that need not be the case.

Answer 5

Only the "verify" part matters

When you have a putative answer to some problem, the only thing that matters formally is that you have a verification that the answer is an answer.

All the algebraic work you did when trying to solve the problem? Completely irrelevant — its only value is that it led you to something that you might then try to verify. (although, sometimes the work done can be reused in the verification step)

Since "guess and verify" includes "verify", it's a perfectly valid technique.

---

Now, we should understand why one might be uncomfortable with "guess and verify" as a technique.

People often focus solely on the "How do I come up with a putative answer?" part of problem solving, often to the point of forgetting the need for verification, or not even knowing it's something that needs to be done!

This is further exacerbated by the fact there are often tricks to verify a putative answer by reusing the work has done in coming up with the putative answer.

For example, when solving the equation $5x + 3 = 13$, one might do the steps

• $5x+3 = 13$
• $5x = 10$
• $x=2$

Then, to verify $x=2$ is a solution, one can then observe that every step in this derivation is reversible; simply writing them in the reverse order amounts to a verification!

(that said, as a practical matter it's better to do verification by plugging $x=2$ into the original equation; this gives you a very good chance of catching any arithmetic mistakes)

If most of the problems have solved are like this, it makes verification almost look like an afterthought or a technicality, leading people to underestimate its importance, or even completely overlook it as a step!

Furthermore, one spends a lot of time learning how to do these sorts of algebraic manipulations to arrive at a specific result; this is only one particular strategy for coming up with a putative answer, but this focus often leaves people with the impression it is the only valid strategy.

The way math is taught might even reinforce this misconception; e.g. in a test of how well you can do algebraic manipulations, a guess-and-check solution would get marked down because you didn't demonstrate your skill at algebraic manipulation... but the student might misunderstand and think that they got marked down because guess-and-check is an invalid problem solving technique!

Answer 6

Here's the difference, guess and check can be used in a logical flow: I guess ( or assume in this proof as usually shown for the sqrt of 2 is irrational) the sqrt of 2 is rational, then by the rules we use most commonly ( axioms and definitions are used in proof, as well as previously proven statements from the axioms chosen):

definition 1 : a rational number is a number that's the ratio of two rational numbers.

rule 1: fractions in not lowest terms can take a factor out of both denominator and numerator.

assume the fraction we equate to is in lowest form: $$\sqrt{2}={a\over b}$$

rule 2: doing the same thing to both sides of an equality will keep the sides equal.

$$(\sqrt{2})^2=\left ({a\over b}\right)^2$$

rule 3: opposite operations cancel each other.

rule 4: squaring a fraction squares both numerator and denominator

$$2={a^2\over b^2}$$

rule 5: multiplying fractions by their denominator gives the numerator.

$$2b^2={a^2\over \not\!b^2}\not\!{b^2}\\2b^2=a^2$$

rule 6: if one side is even so is the other in an equality.

rule 7: if a power is even, so is the base. aka $a^x \text{ is even} \implies \text { a is even}\implies a=2c$

$$2b^2=a^2=(2c)^2$$

rule 8: expanding a power with a base using only multiplication, is the individual components raised to that exponent

$$2b^2=2^2c^2=4c^2$$ $$b^2=2c^2$$

rule 9: changing the sides places and the direction of the sign, keeps the equation true. aka $$b^2=2c^2\implies 2c^2=b^2$$ But by rule 6 ,this is the same as we got after rule 5 but for b now we know that leads to b being even and having a factor of 2 just like $a$ , a contradiction occurs, so our assumed premise, can't be true under this system. If we then do say $4^2=9$ ( taken from previous answers), from that we can conclude things but we may get into things like $3\times 4^2=3\times 9$ assume it's true it implies the original thing without coming to the contradiction of 2=3 assuming we believe the opposite to be true. Under circular reasoning we would assume without proof that the starting premise is true and then use it in the proof of itself.