Specific examples (like elementary proofs,or simple problems) which appear rich in abstractions when observed through the lens of abstraction

Question

I am looking for pedagogically motivated examples (like elementary proofs,or simple problems) of "abstraction in action" ? I am looking for good specific examples (pre-university level or first year undergraduate level ) that could very clearly address the following questions

1. When did the abstraction occur?
2. What prompted the particular abstraction?
3. What or which property was abstracted?
4. Why was the abstraction necessary? I mean how the abstraction was necessary to continue further?
5. What could have been other possible abstractions but they were rejected because they couldn't have been very useful to continue further.

Essentially,my question is an attempt to "show few examples (like elementary proofs,or simple problems) which appear rich in abstractions when observed through the lens of abstraction?"

Answer 1

I don't know if this is what you're looking for, but way back in the 80's (before the internet...), I attended a marvelous talk, by John H. Hodges, where he used the Konigsberg Bridge problem to talk about mathematical creation. He gave out a ditto, which I transcribed a few years ago. It looks like I never finished. Here's what's in my file:

5 Major Steps in Mathematical Creation

(Notes given by John H. Hodges for a talk at a math conference, probably in the 1980’s.)

1. Original Stimulation: A problem or question that comes from the real world or from mathematics itself
2. Abstraction: A description of the problem that represents essence, and eliminates extraneous details
3. Generalization: Consideration broadened to a whole class of problems (with the original problem as a particular case)
4. Inductive & Deductive Reasoning: Inductive reasoning used to make conjectures, deductive reasoning used to prove theorems
5. Application of general results: Does the mathematical work done solve the original problem? Does it raise new problems? Formulate those new problems, and begin anew…

The Konigsberg bridges provide a great example of these steps in the process of mathematical creation.

Answer 2

(1) Euclid's Elements represented a giant step in abstraction, starting from the five axioms for plane geometry. And then much later, through the efforts of Gauss, Lobachevsky, and Bolyai, attempts to prove that 5th axiom led to non-Euclidean geometries, another step in abstraction, an abstraction perhaps completed with Klein.

(2) And then there is abstract algebra, developed in struggle to understand the solvability of algebraic equations.

(3) Perhaps these examples are too general for your purposes. A more specific example is the struggle to understand and prove $V-E+F=2$ for polyhedra, so memorably described in Imre Lakatos's Proofs and Refutations. In a crude sense, it was necessary to define what constitutes a vertex, an edge, and a face, before a convincing proof could be achieved. And this definitional process required careful abstraction from many examples and counterexamples.

Lakatos, Imre. Proofs and refutations: The logic of mathematical discovery. Cambridge University Press, 1976.

Answer 3

Most abstraction has to do with concepts rather than specific problems. Some random examples:

1. Brackets and infix notation. (Would you prefer "The product of five and two more than three"?)
2. Variables (Who would be able to do mathematics efficiently without them?)
3. Functions (A function is itself an object and not just its inputs and output.)
4. Operations (E.g. we handle not permutations of specific objects but permutations themselves.)
5. Ring action (E.g. natural numbers on objects, matrices on vectors, ...)
6. Graph theory (Abstraction of the concept of objects and their connections.)
7. Formal systems (As a logical basis for mathematical work, previously based a lot on intuition.)
8. Type theories (As foundations for our intuitive notions of typing.)

On the other hand, there are specific mathematical entities whose abstractions reveal more, such as:

1. Algorithms (Abstracted as Turing machines or lambda calculus expressions.)
2. Factorization (It abstractly generalizes to irreducible factorizations and prime factorizations.)
3. Fermat's Little or Euler's phi theorem (They generalize to Lagrange's theorem for groups.)
4. Strong induction (It generalizes to structural induction or transfinite induction.)
5. [Weighted] Max-QM-AM-GM-HM-Min (All specific instances of the [weighted] power mean!)
6. Boolean algebra (It generalizes to boolean lattices and then partial-orders with join/meet.)
7. Differentiation (The abstract formal differentiation is often used in algebra and combinatorics!)
8. Geometric transformations (The common ones are affine transformations.)

I don't know enough about mathematical history to present historical details of the above abstractions, but presumably it could be found out or vaguely guessed. In my opinion the most important thing is that students can grasp and appreciate the motivation for, utility of and beauty in the abstractions.

Answer 4

I'm going to interpret your question a little differently than the answers already posted and understand you to be asking about abstraction as a problem-solving strategy (i.e., "simplify the problem by applying a homomorphism").

Proofs about grid puzzles and grid games are useful for motivating this kind of abstraction because there are lots of possible homomorphisms from marked grids and/or positions on a grid.

Some examples that students could probably solve on their own without introduction:

• "On an infinite chessboard, white has only a knight, and black has only a pawn. From what positions can white eventually capture the pawn?"

• "On an infinite checkers board, each side has one king and is trying to end the game in as few moves as possible. From what positions will black win?" (This is more or less the previous one rotated 45°.)

• "Show that there is a non-losing tic-tac-toe strategy for X that has them play in the center for their first move and across from O's move for their second." The case analysis on this one is a lot easier if we only consider the board up to rotation and reflection.

• The $n$-rooks puzzle: "How many ways can $n$ rooks be arranged on an $n\times n$ chessboard such that no rook threatens another?" The first step in almost any treatment is an abstraction of candidate positions to permutations.

And some examples that such students could probably handle if given the appropriate nudges:

• The mutilated chessboard problem: "Is there a domino covering for a chessboard with opposite corners removed?" In the standard solution, we abstract the board to two numbers: the number of black squares and the number of white squares. It's usually helpful to not stop there, but compare the solution to a related, but not entirely analogous problem, like "Eight $3\times 1$ polyminos are packed into a $5\times 5$ box; why must the empty space be in the center?"

• "For what values of $n$ is a $n\times 1$ lights-out board solvable from every position?" Here, we abstract a position to three booleans: whether there are an odd number of lit spaces at locations $\{0, 3, 6, \ldots\}$, at locations $\{1, 4, 7, \ldots\}$, and at locations $\{2, 5, 8, \ldots\}$. This and the next one make for good discussion on your point #2: "Where did the number three come from?"

• "For what values of $n$ is a $3n\times 2$ block of pegs a solvable position on an infinite peg solitaire board?" This demonstrates well with two abstraction steps: a first like the one above, but talking about pegs instead of lights, a second that takes a triple of booleans to a boolean indicating whether they are all the same or not. (I chose $3n\times 2$ instead of $n\times 2$ since I assume you're not interested in the induction side of the argument.)

Besides exploiting the grid structure, sometimes you can also get additional homomorphisms from the rules of the puzzle or game:

• "How many arrangements of nine $1$s can be extended to a Sudoku solution?" A nice strategy here is to abstract away the position of the $1$ in the upper-left box (nine possibilities), then whether the $1$s ascend or descend in the top row of boxes (two possibilities), in the middle row (two possibilities), etc.

• "An [insert your favorite fairy chess piece here] is placed by itself on a chessboard of arbitrary shape and dimensions. Every time it moves, the color of the square it left changes from black to white or vice versa, as does the color of the square it lands on. After an unknown number of moves, is it possible to determine from the board and the piece's position where it was originally placed?" This is virtually the bridges of Königsberg, just in disguise.