# How to show that a solution is not derivable?

This morning I was reading from How To Solve It - George Polya. One of his questions gave a set up about a bear leaving some point $P$, gave some info about the path the bear took, then asked "what color was the bear?"

The answer to the problem was white, and one comes to this answer because using the information given you can show geometrically, assuming the earth is perfectly spherical, the information about the bears path could only happen if the point $P$ was the north pole, so one infers the bear is a polar bear, thus is white.

I don't really care about the geometry of the problem but it sent me into a tailwind thinking about "If I wanted to be an ankle biter, how would I actually justify that the color of the bear cannot be deduced from the sentences given?". I am aware of independence results, complicated things like AC and CH (aware that they were proven to be independent, I do not understand how the techniques used to do so actually work), but for simpler things can anyone explain, or direct me, or tell me what I could look up to get a sense of how to show something is not derivable from some set of hypotheses? I have a feeling such information would be in the language of first order logic, mathematical logic or proof theory, which I know little to nothing about.

Even when studying for the GRE there are multiple choice questions where sometimes the correct answer is "not enough info". If it was something with order relations I might have an idea of how to prove that it cannot be deduced. For example,

If $a<b$ is $a^2 < b^2$ or is $b^2 < a^2$? One could quickly give examples where both outcomes are possible unless the hypothesis is strengthened to nonnegatives. But I feel like it is possible to do so in this case because we have only two possible options to exhaust and showing they are both possible means such a conclusion cannot be proven from the hypothesis.

Please edit away if there is anything wrong with my question.

This particular problem is more a brainteaser than mathematics.

A little mathematical insight will tell you the bear's walk must have started at the North Pole. But that's all the math there is in the problem.

There is no mathematical reason why the bear must be white; someone could have airlifted a grizzly bear to the North Pole and let it loose to walk this path. But since the color of a bear whose walk starts at the North Pole is the "brain teaser" part of the problem, you are intended to think through the "most plausible" events that could have occurred, and the idea that the bear was one that was likely to be found naturally near the North Pole seems to be a better fit to the story than the possibility of any other kind of bear appearing there.

These reasons why the color of the bear is determined (or not) involve kinds of real-world reasoning that are sometimes called "using common sense" or "exercising judgment" and are notoriously difficult to express in mathematical logic. The difficulty of this sort of thing has fueled a lot of the research that was done in artificial intelligence over the last sixty years or so. As far as I'm aware there is still no general solution to the problem.

Now let's consider questions in which the options to be chosen among are susceptible to mathematical logic (unlike the color of a bear found at the North Pole). First, consider your example:

If $a<b$, is $a^2 < b^2$ or is $b^2 < a^2$?

A somewhat more general format of this question, allowing for any finite number of unknown quantities and any finite number of choices (two or more), is, "Given $P(x_1, \ldots, x_n)$, which is true: $Q_1(x_1, \ldots, x_n)$, $Q_2(x_1, \ldots, x_n),\ldots$, $Q_{k-1}(x_1, \ldots, x_n)$, or $Q_k(x_1, \ldots, x_n)$?" It seems to me you also mean to require the following two conditions:

1. The formulas $Q_1,\ldots,Q_k$ are mutually exclusive, that is, no two formulas $Q_i(x_1, \ldots, x_n)$ and $Q_j(x_1, \ldots, x_n)$, where $i\neq j$, can be true simultaneously for any choice of values of $x_1, \ldots, x_n$ such that $P(x_1, \ldots, x_n)$ is true.

2. $Q_1,\ldots,Q_k$ are exhaustive, that is, for every choice of values of $x_1, \ldots, x_n$, if $P(x_1, \ldots, x_n)$ then at least one of the formulas $Q_1(x_1, \ldots, x_n),\ldots$, $Q_k(x_1, \ldots, x_n)$ is true.

This format assumes an implicit quantification over the variables $x_1, \ldots, x_n$, namely, $Q(x_1, \ldots, x_n)$, and an answer to the question (if there is one) depends on which one of the $k$ following statements is true: \begin{align} (\forall (x_1, \ldots, x_n)) & (P(x_1, \ldots, x_n)\implies Q_1(x_1, \ldots, x_n)), \tag{$\phi_1$}\\ & \vdots \\ (\forall (x_1, \ldots, x_n)) & (P(x_1, \ldots, x_n)\implies Q_k(x_1, \ldots, x_n)). \tag{$\phi_k$} \end{align} For $i=1\ldots,k$, if $\phi_i$ is true then the answer is $Q_i$. If no $\phi_i$ is true then the problem is indeterminate.

The example above also assumes (somewhat ambiguously) a domain for the variables; in context, the domain would usually be whatever things we had most recently defined that could be compared using $<$, whose squares existed, and whose squares could be compared using $<$. Out of context, we have to choose a suitable domain arbitrarily, so I'll choose the integers. (Like the color of the bear, that particular choice is an exercise in judgment.) This leads to consideration of the following two statements: \begin{align} \newcommand{Z}{\in \mathbb Z} (\forall (a,b)) & ((a \Z \land b \Z \land a < b) \implies a^2 < b^2) \tag{$\phi_1$}\\ (\forall (a,b)) & ((a \Z \land b \Z \land a < b) \implies b^2 < a^2) \tag{$\phi_2$}\\ \end{align}

In this particular example, it's easy enough to show that the statements $a^2 < b^2$ and $b^2 < a^2$ are mutually exclusive (because $<$ is antisymmetric), and not much harder to show that these statements are exhaustive (because if $x$ and $y$ are integers, one of $x<y$, $x=y$, or $x>y$ must be true, and the condition $a<b$ rules out the case $a^2=b^2$), so this is indeed a problem in the desired format.

To show that the answer to the problem is indeterminate, we have to disprove both $\phi_1$ and $\phi_2$. Disproofs of statements of this form are typically done by counterexample; for example, a disproof of $$(\forall (a,b)) ((a \Z \land b \Z \land a < b) \implies a^2 < b^2) \tag{\phi_1}$$ is just a proof of $$\lnot(\forall (a,b)) ((a \Z \land b \Z \land a < b) \implies a^2 < b^2), \tag{\lnot\phi_1}$$ which is equivalent to $$(\exists(a,b)) ((a \Z \land b \Z \land a < b) \land \lnot(a^2 < b^2)).$$ By far the easiest way to prove this last formula (and therefore disprove $\phi_1$) is by presenting a "witness" such as $a=-2$, $b=-1$, which proves the last formula because $-2\Z$, $-1\Z$, $-2<-1$, and $(-2)^2 \not< (-1)^2$. Similarly, to disprove $\phi_2$ we can simply present the witness $a=1$, $b=2$. For a more general problem of this format, with $k$ alternatives, you just need $k$ witnesses, not necessarily all different.

The "exercise in judgment" above was that I did not choose $\mathbb N$ as the domain because the idea of this example in the first place was to show how something could be indeterminate (which would not be the case here if the domain were $\mathbb N$); I did not choose $\mathbb Q$ or $\mathbb R$ because any proof of indeterminacy for $\mathbb Z$ can be extended to those domains as well; and I did not choose any other domain because that would have been weird.

• Out of curiosity did you finish reading my question? – Prince M Nov 7 '16 at 7:04
• Yes, but as the "ankle biting" concerns with the bear problem aren't really mathematical, we're kind of lacking a concrete idea of what other kind of problem we might want to deal with. Or maybe I just got too distracted by the bear. – David K Nov 7 '16 at 7:10
• The reason I included the prelude with Polya's problem was, I guess, just to give an idea what sparked the interest. When I said "If I wanted to be an ankle biter" was because, if I proved that the color of the bear was not actually \textit{deducible} from the information given (as in actually deducible, not just a sequence of clues that allow reader to make an inductive inference) then I would be an ankle biter since I would have proven that Polya's answer was wrong. I guess the whole point of my question is how would one formulate an argument to prove something is not derivable. – Prince M Nov 7 '16 at 7:14
• I believe in mathematical logic, what I am asking is, how does one show $P \neg \vdash Q$ Where $P$ is the information given and $Q$ is bears color. Or could this not be done since the color is outside of the domain of discourse? – Prince M Nov 7 '16 at 7:18
• And to answer your question, mathematical logic is what I believe I'm concerned with, hence the tags. – Prince M Nov 7 '16 at 7:19

Here's a very general kind of answer to this very general question:

how to show something is not derivable from some set of hypotheses?

There are several ways, that usually rely on proof by contradiction in some form. Most don't depend on serious study of mathematical logic.

• Pythagoras knew how to prove that there is no rational number whose square is $2$ .
• Showing that $\pi$ isn't the root of a polynomial with rational coefficients is harder. See How hard is the proof of $\pi$ or $e$ being transcendental? .

• For GRE questions where the choice is among several possible answers, you can try them all and show none works.

• You can prove that Euclid's parallel postulate can't be derived from the others by building a model inside Euclidean geometry where the parallel postulate fails. I'm particularly fond of the Poincare model.
• Finally, there's Godel's theorem, proving that there are unprovable propositions ...