# What are your favorite instructional counterexamples?

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.

-
@Regenbogen - I am familiar with the proof that Selmer's curve has points everywhere locally but not globally. But that counterexample led many people to study the manner in which the Hasse Prinicple could fail. For example, there is the Brauer-Manin Obstruction. However Skorobogatov has found examples of curves with trivial Manin obstruction and everywhere local points but no global points, so the story is not finished...In my comment I was suggesting that someone more familiar with the current work might use this example. – Ben Linowitz Mar 2 '10 at 17:23

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 In be the n-th interval in the list. Put two fat (positive-measure) disjoint Cantor sets (one for A and one for B) inside I1. (We can just put the second inside some gap of the first). By the main property of Cantor sets, every interval In 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 I2, 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 In-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.

-
@llya The fat Cantor set is one of the great teaching examples of both analysis and topology.Most professors just go over the plain vanilla Cantor set. This is really doing the class a disservice because they don't really get the depth of the sheer diversity of pathology that can occur the real line simply by varying the details of the method of construction of the set, – The Mathemagician Jul 29 '10 at 18:36
I also like the proof of the existence of the set $A$ you mentioned above using the Baire category. Consider the metric on measurable sets you get from the inclusion into L^{1}, to prove that such an $A$ exists, it suffices by Baire category to show that for any interval $I$ with rational endpoints the collection of sets $A$ which have $0<\lambda(A\cap I)<\lambda(I)$ are open and dense. But this is essentially a triviality. – Benjamin Hayes May 2 '11 at 19:53

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.

-

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.

-

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

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."

-

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}$)

-

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 strcture 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.

-

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.

-
It may be worth noticing that this ring $R$ is nothing but $(\mathbb Z/2)^{\mathbb N}$ in disguise. Also, I am surprised with your statement that localizations $R_p$ are all isomorphic to $\mathbb Z/2$. – ACL Mar 17 '11 at 9:10
The prime ideals in this ring are the complements of the ultrafilters on $\mathbb N$, so the spectrum is the Stone-Cech compactification of the discrete space $\mathbb N$. – Andreas Blass Mar 17 '11 at 13:53

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 $$f_n(k) = \delta_{nk}$$ 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...

-

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.

-

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 factor. 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.

-

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.

-

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$).

-
Nevertheless, I think that it's not obvious that there exist commutative rings with only one prime (not only with one maximal) ideal that are not noetherian. – ifk Apr 4 '10 at 21:35
@ifk: There are simpler examples of that: Consider the direct sum $R=k\oplus V$ of a field $k$ and an infinite dimensional vector space $V$, made into a ring so that $V$ is an ideal which squares to zero, $k$ and $V$ multiply as you expect, and $k$ is a subring (this is called a trivial extension, in some contexts) Then $R$ is commutative, has only one prime, and it is not noetherian. – Mariano Suárez-Alvarez Apr 5 '10 at 6:05

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.

-

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.

-

$\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 it's 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.

-

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.

-

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.

-
I had been concerned about wether this was proven to be the smallest example. It is now, thanks to the work of Robert Miller. – Jamie Weigandt Apr 30 '11 at 2:38

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 http://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 http://www.springerlink.com/content/aeem2yx884nnufxn/

-

My favorite counter-example is given in the shore 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 there 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.

-

Ackermann function (http://en.wikipedia.org/wiki/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.

-

A nice counterexample to the statement "$L^p$ convergence to $0$ implies pointwise a.e. convergence to $0$" is obtained by taking characteristic functions of length $\frac{1}{n}$ wrapping around the interval $[0,1]$. These integrate to $\frac{1}{n}$, but converge nowhere to $0$ because the harmonic series diverges.

A counterexample to the converse is easier: just take $f_n = n(n+1)\chi_{[\frac{1}{n+1},\frac{1}{n}]}$. These integrate to $1$ and converge everywhere to $0$.

-
$\chi_{[0,1/2]}, \chi_{[1/2,5/6]}, \chi_{[5/6,1] \cup [0,1/12]}, \chi_{[1/12,17/60]}...$. – Douglas Zare Jul 10 '12 at 4:58
I should also mention here that $L^p$ convergence of $\{f_k\}$ to 0 implies that a subsequence converges pointwise a.e. to zero. To see this take a subsequence with $\int |f_k|^p < 2^{-k}$ (or any summable series) and use the monotone convergence theorem to conclude that $\int \sum |f_k|^p < \infty$. – Connor Mooney Aug 2 '12 at 12:10

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 developped the notion of wild arcs, and found the following simpler counterexample, where there are only two singular points :

-

From an earlier post: "The 8-element quaternion group. It can't be reconstructed from its character table (D_4 has the same one), and every subgroup is normal but it's not abelian."

Although the character tables for the dihedral group D of order 8 and the quaternion group Q of order 8 may seem the same, they are not. Using Adams operations on the representation rings for D and Q, it is possible to show that these representation rings are different as rings with operations (either lambda or Adams operations). These Adams operations are defined in a paper by Aityah and Tall, where it is shown how to calculate them directly from character tables.

-
It can't be possible to define lambda operations directly from the character table; you need to know some of the multiplication table as well. – Qiaochu Yuan Jul 31 '11 at 18:07

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

-

I am quite keen of a counterexample in Strichartz estimates by Thomas Wolff that I think satisfies the requirements in your question. The problem was whether or not there are $L^p$ Strichartz estimates that lose no derivatives. Wolff gave a counterexample that, assuming the best control possible, then this is not possible for $p>2$. It uses the result by Charles Fefferman that the disk multiplier $S_1$ is not bounded on $L^p,~p\neq 2$. This is brilliantly explained by Professor Tao in the Notice of the AMS article "From Rotating Needles to Stability of Waves: Emerging Connections Between Combinatorics, Analysis, and PDE". It goes (more-or-less) like this:

Let $B(0,1)$ denote the unit ball of centre $0$ and radius $1$. Wolff showed that the inequality \begin{equation*} ||u||_{L^p([1,2]\times \mathbb{R}^n)}\leq C||f||_{L^{\infty}(B(0,1))} \end{equation*} fails, for $f$ bounded on $B(0,1)$.

Wolff used a mixture of Kakeya tube constructions, and the manipulation of specially constructed waves consisting of bump and exponential functions adapted to the tubes.

-

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.

-

I like "the deleted Tychonov plank" which is described in "Counterexamples in Topology".

This space provide us a pure algebraic counterexample:

A commutative ring is called a $Z$-ring if all its elements are zero divisors. At first glance, it seems that an extension of a $Z$-ring by a $Z$-ring is necessarily a $Z$ ring. But this space provides a counterexample. The reason is explained here.

http://arxiv.org/abs/1307.5836

To be honest, I spent a few weeks to give a (positive) proof for this ring-extension statment, but finaly I found this counterexample in the book "Counterexamples in Topology" which excited me a lot.

As a consequence of this post we ask:

Are there two $Z$-rings $R_{1}$ and $R_{2}$ such that for every short ring exact sequence $$0\to R_{1} \to S \to R_{2} \to 0$$ $S$ must be a $Z$-ring?

-

the example which shows that exp(zw) is not equal to exp (exp(z),w)

another one a continuous function of a complex variable need not have primitive in a region.the example is f(z) = square ( | z| ).

-