What are your favorite instructional counterexamples?

Question

Related: question #879, Most interesting mathematics mistake. But the intent of this question is more pedagogical.

In many branches of mathematics, it seems to me that a good counterexample can be worth just as much as a good theorem or lemma. The only branch where I think this is explicitly recognized in the literature is topology, where for example Munkres is careful to point out and discuss his favorite counterexamples in his book, and Counterexamples in Topology is quite famous. The art of coming up with counterexamples, especially minimal counterexamples, is in my mind an important one to cultivate, and perhaps it is not emphasized enough these days.

So: what are your favorite examples of counterexamples that really illuminate something about some aspect of a subject?

Bonus points if the counterexample is minimal in some sense, bonus points if you can make this sense rigorous, and extra bonus points if the counterexample was important enough to impact yours or someone else's research, especially if it was simple enough to present in an undergraduate textbook.

As usual, please limit yourself to one counterexample per answer.

Answer 1

Coefficients of cyclotomic polynomials over $\mathbb{Q}$.

If you look at the factorization of $X^n-1$ over the integers, for $2 \leq n \leq 104$, you would "notice" that all nonzero coefficients of all factors are $\pm 1$. Indeed, $105$ is the first counterexample to this conjecture, with the 105th cyclotomic polynomial having coefficients of $2$ in its expansion. This can happen because $105$ has three distinct odd prime factors. The conjecture and the counterexample, however, are accessible even to high school students.

A quick Internet search suggests the following book as a reference:

McClellan, J. H. and Rader, C. Number Theory in Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1979.

I admit I have not read it - I first saw the counterexample while teaching high school, and it came up again in an advanced undergraduate course on Galois theory.

Answer 2

I like the Sorgenfrey line. It's finer than the metric topology on R, and hereditarily Lindelöf, hereditarily separable, first countable, but not second countable. It's non-orderable, but generalised orderable, etc. It's a popular example for metrisation theorems, e.g. All its compact subsets are at most countable.

Answer 3

The Schoenflies conjecture was asserting that the two connected components of the complement of an embedded $2$-sphere $S^2$ in $S^3$ were simply connected. A kind of generalized Jordan theorem.

Antoine's necklaces gave a first counterexample, and that counterexample was reworked by Alexander to obtain the horned sphere :

In this counterexample, the set of singular points of the embedding is a Cantor set, so is quite big. Later, Artin and Fox developed the notion of wild arcs, and found the following simpler counterexample, where there are only two singular points :

Answer 4

In question #14739, I asked whether the product of two ideals of a commutative ring $R$ could be defined lattice-theoretically the same way the sum and intersection can. Bjorn Poonen gave a great counterexample that shows the answer is no! This supports a point fpqc had been trying to make to me earlier that the relationship between $R$ and the Zariski topology on $\text{Spec } R$ was more subtle than I had thought: in particular, it has more structure than just the Galois connection.

Answer 5

The following are, I think, the "worst possible" counterexamples in measure theory. They would benefit from a nice list of properties -- I have a feeling that I'm forgetting a lot. Feel free to improve!

The Cantor set and its friend the Cantor function are standard counterexamples. Keeps increasing regardless of the zero derivative almost everywhere... Also, the corresponding measure $\mu$, defined so that the measure of the interval [a,b] is f(a)-f(b) where f is the Cantor function is supported on a Lebesgue-zero set.

Another good source of examples is the measurable set $A \subset [0,1]$ such that for any interval I, $\lambda(I\cap A) > 0$ and $\lambda(I\cap A^c) > 0$. ($\lambda$ is the Lebesgue measure, ^c denotes complement).

---

Here's a construction of A that I heard from Ulrik Buchholtz. Instead of just constructing A, we'll make two disjoint sets A and B which have intersection of positive measure with any interval. Consider the set of all subintervals of [0, 1] with rational endpoints. It is countable, so let I_n be the n-th interval in the list. Put two fat (positive-measure) disjoint Cantor sets (one for A and one for B) inside I₁. (We can just put the second inside some gap of the first). By the main property of Cantor sets, every interval I_n minus the Cantor sets is a non-empty union of intervals. So, we can put two fat disjoint Cantor sets (also disjoint from the previous ones) inside I₂, and keep going forever. Every time, we add one Cantor set to A and one to B.

Now, each subinterval of [0,1] will contain one of the I_n-s, and therefore its intersection with both A and B has positive measure. Both A and B are countable unions of measurable sets, and therefore measurable. We are done.

Answer 6

This is an easy one, but one I've found useful in the past to keep in mind, and which I've passed on to many younger students who are new to homological algebra. These students sometimes struggle with the idea of a non-free projective module because if you're new to modules and you still think of them via analogy to vector spaces then it's natural to think direct summands of free modules should be free.

A nice counter-example to keep in mind is the ring $\mathbb{Z}/6\mathbb{Z}$ and the projective but not free module $\mathbb{Z}/3\mathbb{Z}$ (projective because $\mathbb{Z}/6\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z}$)

Answer 7

Writing $H$ for the Heaviside function, I was surprised when I first realised that the map $t \mapsto H(\cdot - t)$ is not Borel measurable as a map from $\mathbf{R}$ to $L^\infty(\mathbf{R})$. This illustrates that the intuition that "all unambiguously defined maps are measurable" really only works when the target space is separable.

Answer 8

As a counter-example for Fatou's lemma in measure theory: strict inequality can occure! Just take the measure space $\mathbb{N}$ with the counting measure and consider the functions \begin{equation} f_n(k) = \delta_{nk} \end{equation} Then the sum of $f_n$ is always $1$ while the pointwise limit of the $f_n$ will be the zero function having zero integral. If you have this counter-example then you do not need fancy measures and integrals at al to produce examples that in Fatou's lemma strict inequality may happen...

Answer 9

Volterra's function has a derivative everywhere which is bounded, discontinuous, and cannot be Riemann-integrated. It depends on the Cantor sets, of course, already mentioned.

Possible reference: Bernard R. Gelbaum, John M. H. Olmsted: Counterexamples in Analysis.

See also MO:Integrability of derivatives.

Answer 10

Here is a useful example of counter-examples in commutative ring theory;

Let $R=P(\mathbb{N})$ be the power set of $\mathbb{N}.$ It has a ring structure $(R, +, \times)$ where $+$ is the symmetric difference of sets and $\times$ is the intersection of sets.

Applications:

Obviously, $R$ is a commutative ring with $1$, ($\mathbb{N}$ is the $1$).

1) Let $R$ be a commutative ring with $1$ and a multiplicative closed set of $R$. If $R$ is Noetherian (Artinian) ring then $S^{-1}R$ is Noetherian (Artinian). Does the converse hold?

No, it doesn't.

Using the above example, for any prime ideal $p$ of $R$, $R_p$ (the localization at $p$) is Noetherian (Artinian) while, $R$ is not Noetherian (Artinian).

Outline:

Consider P({1}) $\subset$ P({1,2}) $\subset... $ and $P(\mathbb{N}) \supset$ P($\mathbb{N} \setminus${1}) $\supset$ P($\mathbb{N} \setminus${1,2}) $\supset ...$ showing that $R$ is neither Noetherian nor Artinian ring.

It is easy to verify that $R_p$ is isomorphic to $\mathbb{Z}/2$, hence it is both Noetherian & Artinian. (Every element of $R_p$ is either $0/1$ or a invertible.)

2) Let $R$ be an integral domain (also commutative with $1$), then for every multiplicative closed set of $R$, $S^{-1}R$ is an integral domain, hence for every $R_p.$ Does the converse hold?

By the above example, it doesn't, since $(P(\mathbb{N}),+,\times)$ is not an integral domain.

Answer 11

I occasionally use the following "counterexample" to unique factorization in Z in an introduction to math course: (1003)(1007)=(901)(1121). Once the students figure out what's going on, I think they learn something from it.

Answer 12

I'm shocked that noone has mentioned the Quaternion group! This thing is a counterexample to lots of basic questions you'd come up with while learning (finite) group theory.

For example (although not really a counterexample to a specific question), if you know the semidirect product construction and Sylow theorems and are trying to classify groups of low order, the quaternion group is the first group you can't construct as a semidirect product of cyclic groups. This can be an entry point for the extension problem for groups and cohomology of groups.

Answer 13

"Every finitely-branching tree with infinitely many nodes has an infinite branch" is constructively false, as witnessed by the following counterexample:

https://math.andrej.com/wp-content/uploads/2006/05/kleene-tree.pdf

Andrej Bauer's exposition (above) is especially nice; most textbooks take a far less direct route to the result, which makes it harder to see what's really going on past the level of "yeah, the proof is correct step-by-step."

Answer 14

Any classical counter-example to inversion of a limit and an integral, $f_n:[0,1[\to\mathbb{R} ; x\mapsto n^2 x^n$ say. Basic, but important to motivate the dominated convergence theorem.

Answer 15

The matrix pencil $$ \left\{ \begin{bmatrix} 0 & 1 & x\\ 1 & 0 & 0\\ x & 0 & 0 \end{bmatrix} : x \in \mathbb{R} \right\}. $$ The matrices composing it are all singular, but they have no common left or right kernel (which is a property that one expects when first diving into the theory of matrix pencils). Singular pencils are difficult (or impossible) to handle for algorithms to solve generalized eigenvalue problems. For instance, Matlab's eig([0 1 0; 1 0 0; 0 0 0],[0 0 1; 0 0 0; 1 0 0]) returns 0 NaN 0 instead of something like NaN NaN NaN which would make more sense (no zero eigenvalues here), since the algorithm is not designed to handle this kind of singular problems.

Answer 16

My favorite example in discrete mathematics is the sequence $1,2,4,8,16,31,..$. That is, number of regions in a circle after drawing all the chords between $n$ points on the boundary of the circle.

It shows that a simple pattern might be wrong, and that we do need formal proofs, no matter how many examples we've checked.

Answer 17

Ackermann function defined as

$ A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases} $

is total recursive but not primitive recursive. To see this we could prove by induction on the complexity of primitive recursive functions that each primitive recursive function is eventually dominated by this function (we need a bit coding to keep the number of arguments consistent). Essentially this function manages to capture the ``fast-growing'' property. Note that the index set for recursive functions is not recursive while that for primitive recursive function is.

Answer 18

I am surprised no one mentioned the unilateral shift on $l^2 ({\bf N})$, that is, $Te_i = e_{i+1}$ where $\{e_i\}$ is the standard orthonormal basis.

It provides examples for the following.

(a) a ring with elements $x,y$ such that $xy = 1 \neq yx$;

(b) an isometry from a Hilbert space to itself that is not a unitary;

(c) a one to one BLT that is not invertible;

(d) its adjoint is an onto BLT with nontrivial kernel;

and lots of other stuff (for example, its spectrum).

Answer 19

The statement S "every injective endomap is also surjective" can be formalized in terms of second-order logic (and, of course, precisely states that the structure in question is finite). This is a counterexample to any kind of compactness result for second-order logic, because if such a result existed, one would be able to get infinite sets satisfying S.

Answer 20

Here is some simple counterexample in commutative algebra, which I found really cute when I first meet it:

Let $k$ be a field, $A = k[X_{1},X_{2},X_{3}\ldots],$ $I = (X_{1}, X_{2}^{2}, X_{3}^{3},\ldots)$ and $R = A/I.$ Then $\text{Spec}(R)$ consists of one point (because $\text{rad}(I)$ is maximal ideal of $A$); in particular $\text{Spec}(R)$ is a noetherian space, and $\dim R = 0$; although $R$ is not noetherian ring (since $\text{nil}(R)^{n}\neq 0$ for every $n$).

Answer 21

My favorite counter-example is given in the short paper, "Almost Commuting Unitaries," by R. Exel and T. Loring.

Here is a little background. Two $n \times n$ matrices $A$ and $B$ are said to be "almost-commuting" if their commutator, $[A, B]$, is small in some matrix norm. In the paper, the authors exhibit a family of unitary matrices, $U_n$ and $V_n$ that "almost-commute" in the sense that given $\epsilon > 0$ there exists an $N \in \mathbb{N}$ with $|| [U_n, V_n] || < \epsilon$ for all $n \geq N$, yet for any commuting $n \times n$ matrices, $X, Y$ $(XY = YX)$ there exists an absolute constant $C > 0$ such that $\max(||X - U_n||, ||Y - V_n||) > C > 0$. This was one of the first counter-examples in a research paper that I understood because the authors method of proof is very elementary. The most technical fact used is that the winding number of a closed curve around the origin is a homotopy invariant.

Answer 22

In the spirit of "examples do not prove anything in full generality (even if you have billions of them)", here is my favorite one: $\gcd(n^{17}+9,(n+1)^{17}+9)=1$ is true for all integers $1\leq n<8424432925592889329288 197322308900672459420460792433$, but false for $n=8424432925592889329288 197322308900672459420460792433$.

Answer 23

Assume given three projective systems $\{A_n,\alpha_{nm}\}_{n\in\mathbb{N}}$, $\{B_n,\beta_{nm}\}_{n\in\mathbb{N}}$ and $\{C_n,\kappa_{nm}\}_{n\in\mathbb{N}}$ of abelian groups (modules over some ring would equally do), endowed with arrrows $$ 0\rightarrow A_n\xrightarrow{f_n}B_n\xrightarrow{g_n}C_n\rightarrow 0 $$ making the above sequences exact for every $n$ and satisfying the commutativity conditions $\beta_{nm}\circ f_n=f_m\circ\alpha_{nm}$ and $\kappa_{nm}\circ f_n=f_m\circ\beta_{nm}$. Then one can form the projective limits of the system to find a sequence $$ 0\rightarrow \varprojlim A_n\xrightarrow{f}\varprojlim B_n \xrightarrow{g}\varprojlim C_n $$ and a classical result says that, in order for this sequence to be right-exact, one needs the system $A_n$ to be stationary - meaning that $\alpha_{nm}(A_n)=\alpha_{n'm}(A_{n'})\subseteq A_m$ for all $n,n'\gg m$.

A classical counterexample showing the necessity of this condition is to take $A_n=p^n\mathbb{Z}$ with $\alpha_{nm}$ given by inclusions, $B_n=\mathbb{Z}$ for all $n$ with identity maps $\beta_{nm}=\mathrm{id}$, and $C_n=\mathbb{Z}/p^n\mathbb{Z}$ with the obvious maps. The system $A_n$ is non-stationary because the image of $A_n$ in $A_m$ is $p^n\mathbb{Z}\subseteq p^m\mathbb{Z}$ which becomes smaller and smaller as $n\rightarrow \infty$: the corresponding sequence of projective limits is $$ 0\rightarrow 0\rightarrow \mathbb{Z}\rightarrow\mathbb{Z}_p $$ which is clearly not right exact.

[Later remark]: After typing all down, I remarked that everything can be found in Wikipedia at https://en.wikipedia.org/wiki/Inverse_limit Moreover, the stationary condition quoted above, usually referred to as Mittag-Leffler condition, is enough to prove right-exactness of $\varprojlim$ in Ab, but there is a counterexample due to Deligne and Neeman showing that in other categories this is not enough, see Link

Answer 24

$\textbf{Algebra.}$

• The symmetric group $S_{3}$ is the first $\text{non-abelian}$ group and also this group has a fascinating property that $S_{3} \cong \mathscr{I}(S_{3})$ where $\mathscr{I}$ denotes the $\text{Inner - Automorphism}$ group.

• Example of a group which is $\textbf{isomorphic}$ to its proper subgroup. $\mathsf{Answer:}$ Take $G=(\mathbb{Z},+)$ and take $H= 2\mathbb{Z}$. Then $G \cong H$.

• Example of a free module in which a linearly independent subset cannot be extended to a basis. $\textbf{Answer.}$ As a $\mathbb{Z}$ module $\mathbb{Z}$ is free with basis $\{1\}$ and $\{-1\}$. Now $\{2\}$ is linearly independent over $\mathbb{Z}$. Note that $2$ cannot generate $\mathbb{Z}$ over $\mathbb{Z}$. If at all there is a basis $\mathscr{B}$ containing $2$, $\mathscr{B}$ should have atleast one more element, say $b$. We then have $b\cdot 2 - 2\cdot b =0$, i.e $\{2,b\}$ is linearly dependent subset of $\mathscr{B}$ which is absurd.

$\textbf{Analysis.}$

• The function defined by $f(x) = x^{2} \cdot \sin\frac{1}{x}$ for $x \neq 0$ and $f(x) =0$ for $x=0$. This is example of a function whose derivatives are not continuous.

• Set that is not Lebesgue measurable. Example given by Vitali.

Answer 25

Rotations $\rho_\alpha$ of the unit circle by an angle $2\pi\alpha$ are nice examples in the theory of discrete dynamical systems.

If $\alpha=m/n$ is rational, then every point on the circle is periodic of prime period $n$ for $\rho_\alpha$, but has no fixed points. This shows that Sharkowskii's theorem does not hold in general for functions continuous $f\colon X\to X$ if $X$ is not the real line or an interval of the real line.

If $\alpha$ is irrational, then the orbit under $\rho_\alpha$ of every point of the circle is dense, but $\rho_\alpha$ has nor sensitive dependence on initial conditions, and in particular is not caotic.

Answer 26

The 5-cycle $C_5$ is a great counterexample. It's the smallest imperfect graph, it's self-complementary, it has chromatic number $>\Delta$, it has no stable set meeting every maximum clique and yet satisfies $\omega = \frac{2}{3}(\Delta+1)$, it has chromatic number $> \frac 1 2 (\Delta+\omega+1)$, meaning that Reed's $\chi, \omega, \Delta$ conjecture is somehow tight.

And when you blow up each vertex into a clique or stable set of size $k$, the fun continues. For $k=3$ this gives you Catlin's counterexample to Hajos' Conjecture.

Answer 27

The four-color theorem is often expressed in different ways which are loosely claimed to be equivalent. However, not all of these formulations are actually equivalent, and not all of them are even true. This means that there are "counterexamples" to certain (incorrect) formulations of the four-color theorem.

The mathematically true statement of the theorem is:

(1) Any loopless planar graph can be colored with (at most) four colors such that no edge connects two vertices of the same color.

However, the theorem is usually introduced in the context of coloring maps, and is loosely framed as saying that "Any map can colored such that no two adjacent countries have the same color." However, making this formulation mathematically precise is surprisingly challenging. For example, here is a seemingly reasonable attempt to formalize the "map" version of the four-color theorem:

(2) Let $D$ be an open subset of the plane, and consider an arbitrary partition of $D$ into path-connected open subsets $S_i$ and their shared boundaries. It is possible to color each subset $S_i$ with one of four colors, such that the shared boundary of any two subsets $S_i$ that are assigned the same color consists only of isolated points.

However, it turns out that not only is proposition (2) not equivalent to proposition (1), but in fact (1) is true and (2) is false. Indeed, even even we further require that the boundaries of the subsets $S_i$ described in (2) consist only of straight line segments and right angles, the claim is still false. A counterexample - a partition of a rectangle into six subsets satisfying the requirements of (2) that cannot be four-colored - is given in https://www.jstor.org/stable/3647828.

This "counterexample" to the four-color theorem - really a counterexample to the incorrect version (2) - demonstrates the utility of formulating the theorem in terms of graph theory, where its statement is quite simple, rather than in terms of the motivating "map" version (which can be done, but requires a large number of fairly complex conditions).

Answer 28

Peano Curve.

This provides a counter-example to an intuitive statement like

if $f:X\to Y$ is a continuous surjective map, then the dimension of $Y$ is less than or equal to that of $X$.

Answer 29

In topology, The comb space is an example of a path connected space which is not locally path connected. see https://en.wikipedia.org/wiki/Comb_space

Answer 30

The elliptic curve 960d1 in Cremona's tables is the smallest conductor example of an optimal elliptic curve with nontrivial Shafarevich-Tate group which is isogenous to an elliptic curve with trivial Shafarevich-Tate group.