# 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

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.

-

A polynomial $p(x) \in \mathbb{Z}[x]$ is irreducible if it is irreducible $\bmod l$ for some prime $l$. This is an important and useful enough sufficient criterion for irreducibility that one might wonder whether it is necessary: in other words, if $p(x)$ is irreducible, is it necessarily irreducible $\bmod l$ for some prime $l$?

The answer is no. For example, the polynomial $p(x) = x^4 + 16$ is irreducible in $\mathbb{Z}[x]$, but reducible $\bmod l$ for every prime $l$. This is because for every odd prime $l$, one of $2, -2, -1$ is a quadratic residue. In the first case, $p(x) = (x^2 + 2 \sqrt{2} x + 4)(x^2 - 2 \sqrt{2} x + 4)$. In the second case, $p(x) = (x^2 + 2 \sqrt{-2} x - 4)(x^2 - 2 \sqrt{-2} x - 4)$. In the third case, $p(x) = (x^2 + 4i)(x^2 - 4i)$. This result can be thought of as a failure of a local-global principle, and the counterexample is minimal in the sense that the answer is yes for quadratic and cubic polynomials.

-
Similarly, if the units modulo n are not cyclic, then the nth cyclotomic polynomial \Phi_n(x) will be reducible mod p for all p. –  Ben Linowitz Mar 2 '10 at 6:15
Even better, the polynomial $x^4-72x^2+4$ is irreducible in $\mathbb{Z}[x]$, but reducible modulo every <I>integer</I>. (Dummit and Foote, 3rd edition, page 309) –  Alfonso Gracia-Saz Mar 2 '10 at 16:41
The polynomial $(x^2+31)(x^3+x+1)$ has a root modulo every prime but no roots in Q. No polynomial of degree < 5 has this property. –  AVS Apr 4 '10 at 20:21

Counterexamples are very important when a student learns how to think in intuitionistic logic (and he has already been "spoiled" by classical logic). The counterexamples destroy the classical intuition, and when properly explained they help the student understand how to think intuitionistically. Some that seem to work praticularly well in my experience involve finite sets. Intuitionistically the following are not provable:

1. A subset of a finite set is finite.
2. The powerset of a finite set is finite.
3. If a subset of $\mathbb{N}$ is not finite then it is infinite.
4. The elements of a finite set may be listed without repetition.

All of these can be rescued with the additional assumption that the sets involved have decidable equality and that the subsets involved have decidable membership.

However, it does not really help the student to just know that certain "obvious" facts are not provable. He really needs to see how the "facts" can be false. The ones listed above are all false in the effective topos, but that's a complicated gadget for a beginner. It turns out informal explanations work well enough because most students know a little bit of programming. They just needs to know that the Halting Oracle does not exist.

My favorite counterexample in intuitionistic logic is that it is consistent to assume the so-called Axiom of Enumerability, which says that there are countably many countable subsets of $\mathbb{N}$. (Explanation: in the effective topos this just means that there is an effective enumeration of computably enumerable subsets of $\mathbb{N}$.) Many basic theorems of computability theory can be proved, phrased in a suitable form, from the axiom of enumerability using just constructive logic and no mention of machines of any kind.

-
Which definitions of "finite set" and "infinite set" are you using? –  aorq Mar 2 '10 at 14:33
A set $A$ is finite if there exists a natural number $n$ and an onto map $e : \lbrace{1, ..., n\rbrace} \to A$. A set $B$ is infinite if there exists 1-1 map $m : \mathbb{N} \to B$, i.e., $B$ contains an infinite sequence without repetitions. –  Andrej Bauer Mar 2 '10 at 21:34

A counter-example in graph theory - the Petersen graph.

In many ways it is the most simple graph with many strange properties. See the article on Wiki.

Quote from our professor who teaches graph theory:

If you think you've proved any lemma about graphs, try Petersen first!

-

The matrix $\left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right)$ has the following wonderful properties. (Feel free to add or edit; I can't remember all the reason I loathed it when I was learning linear algebra. It's funny how unexciting they all now seem, but it's a counterexample for almost every wrong linear algebra proof I tried to give.)

• Only zeroes as eigenvalues, but non-zero minimal polynomial (in particular, the minimal polynomial has bigger degree than the number of eigenvalues). Probably my favorite way to state this fact: the minimal polynomial is not irreducible or square-free. The same thing in a fancier language: the Jordan canonical form is not diagonal.

• Not diagonalizable, even over an algebraically closed field.

• Not divisible over $\mathbb C$. There are no matrices $M$ and integers $n\ge2$ so that $M^n = \left(\begin{smallmatrix}0 & 1\\\ 0 & 0\end{smallmatrix}\right).$ All diagonalizable and most non-diagonalizable complex matrices have $n$th roots.

(This is because, if there was a square root, it'd have minimal polynomial x4, but since it's a two-by-two matrix, Cayley-Hamilton implies that the characteristic polynomial has degree 2).

• The matrix is nilpotent but not zero.

• It's one of the best examples when you need to remember why matrix multiplication is not commutative.

• Thinking of k2 as a k[x]-module where x acts as this matrix should give wonderful (counter)-examples of modules for all the same reasons.

Also, $\left(\begin{smallmatrix}1 & 1\\ 0 & 1\end{smallmatrix}\right)$ is an example of an invertible matrix with the first three properties above. Its action on k2 is in some sense the simplest example of a representation of a group ($\mathbb{Z}$) which is indecomposable but not irreducible.

-
"the minimal polynomial is not irreducible" I am not sure I get your point. Minimal polynomials are usually not irreducible. Did you mean "does not have to be multiplicity-free"? –  Vladimir Dotsenko Mar 3 '10 at 14:38

The Moulton plane is a projective plane that is a counterexample to the Desargues theorem, the little Desargues theorem, and just about every "nice" property of projective planes.

Its discoverer, F.R. Moulton, is best known as an astronomer. He apparently came up with the Moulton plane after sitting in on a projective geometry course as a graduate student.

-
Part of why Desargues "Theorem" is intriguing is that it holds in some projective planes and not in others. There are finite planes where it holds and finite planes where it does not hold. If there is a way to introduce coordinates for the plane with numbers from a division ring then then Desargues Theorem will hold. It also holds for projective planes sitting in higher dimensional projective spaces. In the real projective plane the theorem holds. The Moulton plane is a fascinating example. –  Joseph Malkevitch Mar 3 '10 at 14:05

The blowup of $\mathbb{P}^2$ in the 9 points of intersection of two generic cubics admits infinitely many $(-1)$ curves. This example is very important in getting rid of the naif picture of algebraic surfaces.

-
Even though the idea of "blowing down" is to get rid "a" (-1) curve. You can always blow down finitely many times to get rid of all of them, even if you start infinitely many. This is a nice example of that case. –  Matt Apr 4 '10 at 17:38

There exists a $3$-dimensional smooth projective variety $X$ which cannot be birational to a smooth variety with nef canonical bundle. This is because $K_X$ is big; if it was also nef it would have no cohomology and we could compute its self-intersection with Riemann-Roch by looking at the number of sections of its powers. It turns out that the self-intersection would be $3/2$.

This example (by Reid, I think) shows that if you want to have minimal models you have to allow singular varieties, so that $K_X$ can still be defined, but is not a Cartier divisor. This has led to the whole branch of birational geometry studying the type of singularities which are allowed in the minimal model program, like terminal, canonical, log-terminal, KLT and so on.

-

My favourite counterexample is purely academic: it does not have any applications, but I think it is pretty.

Let $X = \mathbb{N} \times \mathbb{N}$. Define a non-empty set $U \subseteq X$ to be open if for cofinitely many $x \in \mathbb{N}$ the set $\{ y \in \mathbb{N} \vert (x,y) \in U\}$ is cofinite.

Construct a sequence in $X$ that hits every point in $X$ exactly once. In other words, take a bijection $\mathbb{N} \rightarrow X$. Then:

• $X$ is countable;
• every point in $X$ is an accumulation point of this sequence, but
• the sequence has no convergent subsequences.

In particular, this is an example in a countable set that accumulation point of a sequence does not have to be a limit of a subsequence. I call this the Herreshoff topology for the (high-school) student of mine who came up with it. (I could not find it anywhere else, although I do not discard that I did not look hard enough.)

-
This is sort of Arens-Fort space: en.wikipedia.org/wiki/Arens-Fort_space. Here you have the neighbourhoods of (0,0) in that space (considering (0,0) to be not in N x N), where there N x N is discrete. Your sequence then has the same properties. –  Henno Brandsma Mar 6 '10 at 8:40

The Baumslag--Solitar groups have presentations

$BS(p,q)=\langle a,b\mid a^p=b^{-1}a^q b\rangle$.

They have the following nice properties:

1. they're two generator, one relator groups;
2. they can be written as an HNN extension of $\mathbb{Z}$ over $\mathbb{Z}$. (This means that they're constructed by 'gluing' $\mathbb{Z}$ to itself in some way.)

So from the point of view of combinatorial group theory, they could hardly be simpler. And yet, for suitable values of $p$ and $q$ (typically $p,q$ relatively prime integers greater than 1 will do), we find that:

1. they're non-Hopfian, meaning that they admit a self-epimorphism with non-trivial kernel;
2. hence they're not even residually finite;
3. they have exponential Dehn function (meaning that the word problem can be solved, but only very slowly);
4. their virtual first Betti number is one (meaning that every finite-index subgroup has abelianisation of rank one)...

I could go on.

-
And for p != q they can't be the fundamental group of a 3-manifold -- see mathoverflow.net/questions/6132/… for some references. –  Steven Sivek Mar 2 '10 at 20:32

Finite topological spaces often provide nice and simple counterexamples in topology, including algebraic topology (check J. Barmak's thesis). After getting familiar with those spaces one easily comes up with examples of phenomena such as weakly homotopy equivalent spaces which are not homotopy equivalent (spaces consisting of 4 points and 6 points suffice) or homomorphisms between homology/homotopy groups that are not induced by continuous maps.

Of course, other counterexamples are available, but finite ones are certainly minimal in a sense.

-

The Poincaré homology sphere, a spherical 3-manifold with fundamental group the binary isosahedral group, was Poincaré's counterexample to the original formulation (in terms of homology) of his conjecture. Due to its countless descriptions -- as a spherical 3-manifold, via Dehn surgery, as the configuration space of an isosahedron, etc -- it's still a motivational example in geometry and topology.

-

The Cantor set is a nice source of counterexamples:

The first measure zero sets you meet are usually countable. However, the Cantor set is uncountable and measure zero.

It is totally disconnected, yet it is not a discrete space. In particular, this shows that connected components of a topological space need not be open sets.

-
This is a very good answer. I would go so far as to say that if you're studying general topology but haven't encountered the Cantor set, your ideas of what a topological space can be are fundamentally incomplete. –  Pete L. Clark Dec 29 '10 at 6:49
“It is totally disconnected, yet it is not a discrete space.” As a professional matter, I like $\mathbb Q_p$ even better as an example of this behaviour. (Of course, topologically it's nearly the same!) If I may piggy-back on Pete's comment, if you haven't encountered $\mathbb Q_p$, then your ideas of what a complete metric space can be are fundamentally incomplete. :-) –  L Spice Mar 28 '11 at 16:03
also positive measure cantor set is a very nice example to difference betwean meagre and null sets –  Ostap Chervak Apr 10 '11 at 9:57

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, –  Andrew L Jul 29 '10 at 18:36

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.

-

I'd say the Tutte Graph, which is a counterexample to

Tait's conjecture: Every 3-connected cubic planar graph has a Hamiltonian cycle.

Initially, I thought this counterexample was extremely non-instructive, since I assumed that Tutte discovered it via some ingenious trial and error. But, after seeing a talk by Bill Cunningham, I discovered how Tutte came up with his counterexample and why it is a counterexample (it's unclear from looking at Tutte's graph that it is not Hamiltonian). The idea is quite simple but useful. Tutte assumed that Tait's conjecture was true and proceeded to prove a sequence of stronger (yet equivalent) conjectures. He then found a very small counterexample to the strongest conjecture, and then deconstructed the sequence of proofs to obtain a counterexample to Tait's conjecture.

I really like this method because it shows that there is hope for a mathematical caveman like me as long as I use my brain. That is, the counterexample was actually not pulled out of thin air like I initially thought.

-
Very few results are pulled out of thin air. The problem is, mathematical culture has not favored showing where they do come from. –  Mariano Suárez-Alvarez Mar 3 '10 at 16:56
I'd add that one of the reason for this is that journals have a strong preference for short articles, although today, with internet distribution, I do not see any reason for this. As a result, mathematicians cut out the why from the proofs, leaving only the necessary steps. But this is of course discussed in other threads... –  Andrea Ferretti Mar 3 '10 at 17:09

The Weierstrass function - which I guess is a counterexample to the conjecture that a function which is continuous everywhere must be differentiable somewhere. I remember being pretty amazed when I first encountered it. It made me realize that continuity and differentiability are really different notions.

-

The basic fact that there are smooth non-analytic functions on $\mathbb R$, and that there are compactly supported smooth functions, is important in real analysis and functional analysis.

$f(x) =\begin{cases} \exp(-1/(1-x^2)),& x \in (-1,1) \\\ 0& \text {otherwise} \end{cases}$

The usual examples of these functions often seem contrived. Here are examples of smooth nowhere analytic functions.

-

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.

-

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.

-
And it has quaternionic representations - something that serves as counterexample to many beginner's conjectures in representation theory (a la "any representation can be constructed in the smallest field where its character lives"). –  darij grinberg Apr 4 '10 at 15:59

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.

-

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

-

The Fabius function, everywhere $C^\infty$, nowhere analytic.

see... sci.math post

references:
J. Fabius, "A probabilistic example of a nowhere analytic $C^\infty$-function". Z. Wahrsch. Verw. Geb. 5 (1966) 173--174.

K. Stromberg, PROBABILITY FOR ANALYSTS (Chapman & Hall, 1994), pp. 117--120.

-
Very cool! I'm going to print out the definition and bring it to every physics class I'm in from now on. :) –  Vectornaut Apr 4 '10 at 22:02
The link has gone bad (takes you to "google groups"). –  Victor Protsak Sep 30 '10 at 4:01
Another link (math forum): mathforum.org/kb/message.jspa?messageID=508877&tstart=0 –  Gerald Edgar Nov 4 '12 at 13:56

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.

-

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.

-

The function $x\mapsto x^3\sin(1/x)$ has a second-order Taylor series but is not twice differentiable at $0$. The circumstances where I came across this example are too embarrassing to tell here...

-
I flunked an exam in ordinary differential equations getting that one wrong-trust me,the circumstances can't be worse then that. –  Andrew L Jul 29 '10 at 18:28

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

I've always been fond of the popcorn function (aka Thomae's Function), which is given by $f\colon \mathbb{R} \to \mathbb{R}$ via

$f(x) = \begin{cases} \frac{1}{n} & \mbox{if } x = \frac{m}{n} \in \mathbb{Q} \\ 0 & \mbox{if } x \notin \mathbb{Q}. \end{cases}$

This function has a couple of amusing properties.

(1) It is upper semicontinuous on $\mathbb{R}$, yet has a dense set of discontinuities (every one of which is removable) (namely $\mathbb{Q})$.

(2) Since it is bounded and has a set of measure zero as its set of discontinuities, it is Riemann integrable. So if we consider $g(x) = \int_0^x f(t)\ dt$, we see that $g \equiv 0$, so that $g'(x) \not \hskip 2pt = f(x)$ on a dense set.

References: http://en.wikipedia.org/wiki/Thomae%27s_function and of course "Counterexamples in Analysis" (Sec 2.15-2.17)

-

The alternating group on 4 letters is nice because it provides a counterexample to the converse of Lagrange's theorem: It has order 12, but it does not have a subgroup of order 6.

-
Similarly, the symmetric group on 5 letters has no subgroup of order 15, since (up to isomorphism) the only group of order 15 is the cyclic group, and $S_5$ has no element of order 15. –  Gerry Myerson Mar 27 '11 at 23:35

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.

-