15
$\begingroup$

When asked to show a math problem has a unique solution, students sometimes think that if an algorithm leading to a solution has unambiguous instructions at each step (no need to make choices at any point) then the solution they find has to be the only solution. Loosely speaking, if each step in reaching the solution is "unique" then the end result has to be unique (the only possible solution).

This is not true, and I think it would be nice to have a list of examples at different levels (of undergraduate mathematics) showing why this idea is mistaken.

For example, if asked to solve $55x+32y = 1$ in integers then Euclid's algorithm for computing $\gcd(55,32)$ followed by back-substitution (reversing the steps of Euclid's algorithm) is a procedure where each step is completely determined by the previous ones and leads to the definite answer $(x,y) = (7,-12)$, but the original equation has infinitely many integral solutions: $(x,y) = (7+32t,-12-55t)$ for integers $t$.

What other examples can people offer? I am not interested only in computational problems.

Improve this question
$\endgroup$
2
  • $\begingroup$ Solving the equation $\textbf{A}\cdot\textbf{X}=k$. Of course $\textbf{X}=\frac{k}{\textbf{A}^2}\textbf{A}$ is a solution among infinitely many others. $\endgroup$
    – user5402
    Oct 23, 2017 at 17:35
  • $\begingroup$ I think the most intuitive place to talk and think about this is in ODEs. I would actually not stress the concept itself too early, and especially as a general idea. But just bring it up when it is important for a particular topic. $\endgroup$
    – guest
    Sep 19, 2018 at 21:44

6 Answers 6

Reset to default
8
$\begingroup$

To find a basis for the row space of a matrix, perform elementary row operations to get to reduced row-echelon form. The nonzero rows of the row-reduced matrix are a basis for the row space of the original matrix.

But of course many other bases are possible (with an exception of the zero matrix).

Edited to address a commenter's request: It is true that the steps to row reduce a matrix are not unique (or uniquely ordered); however,

(1) It is possible to give an algorithmic specification of row reduction to reduced row-echelon form for matrices (i.e., no choices); and

(2) The reduced row-echelon form of a matrix is unique. So if we use row reduction as a method to get a basis for the row space of the original matrix, we will all get the same reduced row-echelon form, and hence the same basis, even if some of us do different steps (or steps in a different order) than others of us.

Improve this answer
$\endgroup$
0
4
$\begingroup$

A "non-mathematical" answer: If you are in need of a doctor, then one unambiguous algorithm for finding one is to call everyone in the phone book, in order, and ask them if they are a doctor. Eventually you will find one. However, this does not imply there is only one doctor in your city.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The OP specifies "no need to make choices". Perhaps "first one" is a method of making a choice. $\endgroup$
    – Gerald Edgar
    Oct 24, 2017 at 18:53
  • 3
    $\begingroup$ @GeraldEdgar I don't think this is the sense in which OP meant "no need to make choices". My algorithm is deterministic. If I said "go in alphabetical order, and flip a coin. If heads: ask if they are a doctor. If tails: ask if their refrigerator is running", then I could see the complaint. $\endgroup$
    – Steven Gubkin
    Oct 24, 2017 at 19:20
3
$\begingroup$

Often students wrongly believe that integer factorization is unique because there is a deterministic algorithm for factorization: simply continue to pull out the least prime factor (found by trial division). To help them debunk this belief it suffices to show them another ring where a similar method fails. An elementary example is factoring (monic) quadratics with coefficients being integers $\!\bmod m.\,$ Here - as above - there is a simple deterministic factorization algorithm: simply test in order $r\equiv 0,1,\cdots,m-1$ till we find a root $\,r\,$ hence a factor $\,x-r\,$ (by the Factor Test).

But here factorization need not be unique, e.g. $ (x-1)(x+1) \equiv (x-3)(x+3)\,\pmod{\! 8}$

Applying the above algorithm would find only the first factorization. This shows clearly and simply that the existence of deterministic algorithm for solution does not imply that the solution is unique.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is a nice suggestion, although I would prefer to stick to integral domains rather than something like $(\mathbf Z/8\mathbf Z)[x]$ so you have cancelation of elements. A non-UFD with finitely many elements of each norm, like $\mathbf Z[\sqrt{-5}]$, serves this role well. I'm teaching a number theory course now and began discussing unique factorization today, so the timing of your reply ahead of my next lecture is good. Thanks! $\endgroup$
    – KCd
    Sep 19, 2018 at 0:03
2
$\begingroup$

Another example from Euclid (in the proof of Proposition 20, Book IX):

Given a finite list of primes $p_1,p_2,\cdots,p_n$, there is a prime not included in the list.

Construction: Let $N=p_1 p_2 \cdots p_n +1$. Let $p$ be the smallest (to make the construction unique, Euclid didn't specify this) prime factor of $N$. Then $p$ is not equal to any of the primes $p_1,p_2,\cdots,p_n$.

There are infinitely many other solutions to the problem of finding such a prime.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This one is prone to misinterpretation. Many students think that $p_1$_2\dots p_n+1$ is prime. $\endgroup$
    – Benoît Kloeckner
    Oct 24, 2017 at 12:36
1
$\begingroup$

It is obvious that the algorithm given in the accepted answer (in the Mathematics Stack Exchange Site) to the question “Divide a plane with 2n points into two equal halves” (at: https://math.stackexchange.com/questions/3083344/divide-a-plane-with-2n-points-into-two-equal-halves/3083372#comment8100957_3083372) can be slightly modified to fit the situation you ask about.

Improve this answer
$\endgroup$
-4
$\begingroup$

I might think in any diofantine equation as the one you propose. Also a lot of trigonometric equations. Something like $\sin\theta=\frac{1}{2}$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Your answer appears to give example when there are several solutions. However, you do not indicate any unique procedure that leads to a non-unique solution. For the second example, one could say "applying the inverse sin function" (one might imagine, pressing the button on the calculator) is such a procedure. $\endgroup$
    – quid ♦
    Oct 22, 2017 at 20:20
  • 1
    $\begingroup$ Sorry if I wasn'y precise... But something around what you said is what I was thinking. Even more complex trigonometric equations use almost the same procedure every time. Take a quadratic trigonometric equation. A student would factor, then make every factor equal to 0, apply inverse function, then give the solution using the calculator usually avoinding given all the solutions. $\endgroup$
    – Grouper
    Oct 22, 2017 at 20:35
  • 5
    $\begingroup$ If you like you can still add more details to the post by an edit. $\endgroup$
    – quid ♦
    Oct 22, 2017 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.