# A Formal and Precise treatment of Simplification?

I am looking to gain a deeper understanding of, and increase my own skill in "Mathematical Simplification". But I've been finding the concept overly vague and haven't been able to find any good resources myself.

Here are some of the questions/ideas I am attempting to clarify: -When exactly is a number or expression considered "Simpler" than another? -What are common and useful techniques for Simplification? -How much of Simplification is Objective and how much is Subjective? -Is there a generalization of Simplification that covers much more of Mathematics then basic Arithmetic and Algebra? (Say from the perspective of Set Theory, Category Theory, Abstract Algebra etc.)

My question can best be summed up by asking if there are any detailed, formal and rigorous explanations of Simplification? If there isn't, why is that so? Is this concept of "Simplification" that textbooks seem to assign such paramount importance simply an artifact of "school-math" that proper mathematicians don't concern themselves with?

Suggestions of external resources and/or personal insight are both appreciated.

-
Sometimes "simplifying" is just putting something into a "canonical form". E.g. rationalizing denominators and leaving only square-free expressions under "$\sqrt{{}\quad\cdots\quad{}}$". That enables you to tell whether two things are equal or not. – Michael Hardy Mar 26 '12 at 16:30
....and on other occasions, it's far more substantial. In the 1890s, the Prime Number Theorem was proved. According to something I read by Gian-Carlo Rota, the main contribution of hundreds of papers over the next seven decades was simplifying the proof. He wrote that in the 1960s, Norman Levinson published the ultimate simplification. (I don't know whether subsequent decades have refuted that last assertion.) – Michael Hardy Mar 26 '12 at 16:32
"Simplification" of an expression is probably not definable in a useful way. For what is a simplification for one purpose may not be a simplification for another. – André Nicolas Mar 26 '12 at 17:02
I added the "logic" tag. I deleted the "algebra-precalsulus" tag because the software forbids having more than five tags, and that one was less germane than the others. – Michael Hardy Mar 26 '12 at 17:09
I am not as confident as André Nicolas that this cannot be done in a useful way. – Michael Hardy Mar 26 '12 at 17:10

You might be interested in term rewriting. The idea is to consider expressions called terms which can basically model any kind of mathematical expression and congruences between these terms. The ultimate goal of this theory is to provide methods to decide whether two terms are congruent, by orienting each congruence $t\simeq u$ into a rewrite rule $t\rightarrow u$, and applying many such steps to find a common reduct $w$, we write

$$t\rightarrow^* w\ \ ^* \!\leftarrow u$$

For this to be a procedure, we commonly require two properties:

• Confluence: if $t \rightarrow^* v$ and $t \rightarrow^* u$ then there is some $w$ such that $u\rightarrow^* w\ \ ^* \!\leftarrow v$

• Termination: there is no infinite sequence $$t_1\rightarrow t_2\rightarrow t_3\rightarrow\ldots$$

Given these two properties, the decision procedure for deciding congruence is simple: take both terms and rewrite them as much as possible. This will be a finite process, by termination. By confluence, it is not too difficult to see that the final terms obtained will be identical if and only if the original terms are congruent.

Now for your question: over the years, people have developed a great many mathematical (and programmatic) tools to help one determine termination of a set of rewrite rules. The most common way to do this is to determine a certain relation $R$ on terms, which verifies $t \rightarrow u \Rightarrow t R u$. In this sense, every such tool gives a precise definition of what it means for $t$ to be simpler than $u$: it is the statement $t R u$. Note that this relation can be significantly more complex than simply syntactic size: the relation

$$\sqrt{a} - \sqrt{b}\quad R\quad \frac{a-b}{\sqrt{a} + \sqrt{b}}$$

can be seen as a simplification, as the number of differences of square roots is strictly smaller in the right expressian than in the left. The wikipedia page gives some more examples, and Baader & Nipkow give a rather comprehensive overview.

-
Thank you, this is pretty much exactly what I was looking for. Other related articles of interest I've found include: en.wikipedia.org/wiki/Confluence_(abstract_rewriting) and en.wikipedia.org/wiki/Abstract_rewriting_system Also of note is that wikipedia redirects Term Rewriting into simply "Rewriting" which seems to be a more general term covering areas of logic and computer science as well. I suspect googling with the keyword "Rewriting" rather then "Simplifying" will probably be more helpful to me. – jcelios May 23 '12 at 21:45
Just googling "rewriting" might be a bit too general. You might want to check out "Shostak theories" which are logical theories in which one has a natural notion of "canonical form" and of "solution of an equation". The field of rewriting is so incredibly vast, however, that you might start with the Baader & Nipkow reference to get a grip on the different subfields. – cody May 25 '12 at 12:34