# 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

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.

-

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 matrices $A=\begin{pmatrix} 17\times 11 + 1 & 25\times 11\\ 11^2 & 16\times 11 + 1 \end{pmatrix}$ and $B = \begin{pmatrix} 17\times 11 + 1 & 11 \\ 25\times 11^2 & 16\times 11 + 1 \end{pmatrix}$ are similar modulo $m$ for every positive integer $m$ but are not similar over the integers.

In other words, there exist matrices $X_m\in GL_2(\mathbf Z/m\mathbf Z)$ such that $X_mA \equiv BX_m \mod m$ for every $m$, but there does not exist a matrix $X\in GL_n(\mathbf Z)$ such that $XA = BX$.

This is due to Stebe, Conjugacy separability of groups of integer matrices. Proc. Amer. Math. Soc., 32:1–7, 1972.

-

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.

-

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.

-

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.

-

The Warsaw circle $W$ http://en.wikipedia.org/wiki/Continuum_%28topology%29 is a counterexample for quite a number of too naive statements.

Some observations: $W$ is weakly contractible (because a map from a locally path connected space cannot ''go over the bad point''). There is a projection map $g:W \to S^1$ onto the usual circle. The point-preimages of $g$ are either points or, for a single point on $S^1$, a closed interval.

Thus the assumptions of the Vietoris-Begle mapping theorem hold for $g$, proving that $g$ induces an isomorphism in Cech cohomology. Thus the Cech cohomology of $W$ is that of $S^1$, but it has the singular homology of a point, by Hurewicz. These observations imply:

1. A map with contractible point-inverses does not need to be a weak homotopy equivalence, even if both, source and target, are compact metric spaces. Assuming that the base and the preimages are finite CW complexes does not help.

2. The Vietoris-Begle Theorem is false for singular cohomology (in particular, the wikipedia version of that Theorem is not quite correct).

3. $W$ does not have the homotopy type of a CW complex (since it is not contractible).

4. Even though the map $g$ is trivial on fundamental groups, it does not lift to the universal cover $p: \mathbb{R} \to S^1$, because $g$ cannot be nullhomotopic. Thus the assumption of local path connectivity in the lifting theorem is necessary.

-

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.

-

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/

-

Let $P dx + Q dy$ be a one-form, or if you're using the terminology of an introductory multivariable calculus course, a "vector field" that you can take line integrals of. Then students learn Green's Theorem, which says that if some countour $C$ bounds a region $D$, then $$\int_C P dx + Q dy = \int_D \left(\frac{dQ}{dx}-\frac{dP}{dy}\right) dx dy.$$

From this, one deduces that if the expression on the right hand side vanishes, then the integral around any contour is $0$. In particular, this allows one to define a primitive for $P dx + Q dy$.

Many students (myself included, a long way back) don't pay enough attention to the hypotheses in Green's Theorem and then assume that this is true of the following one-form (or "vector field"), which is my fundamental counterexample:

$$\frac{-ydx}{x^2+y^2} + \frac{xdy}{x^2+y^2}$$

Eventually a student discovers that the integral of this around the origin is $2 \pi$ and then wonders what went wrong. The problem is that the hypothesis of Green's Theorem requires that the form be defined everywhere in $D$.

In other words, this is a fundamental counterexample to the claim that a one-form in the plane with zero curl (where by "curl" I just mean the right hand side of the above) has a primitive.

Furthermore, this is a fundamental example of a nontrivial element in a de Rham cohomology group. In this case, the one-form above generates $H^1_{\text{dR}}(\mathbb{R}^2\setminus \{(0,0)\},\mathbb{R})$.

-

Small's Example from noncommutative algebra...

The triangular ring $T = \pmatrix{\mathbb{Z} & \mathbb{Q} \\\ 0 & \mathbb{Q}}$ has the following properties:

• It's right noetherian but not left noetherian
• It's right hereditary but not left hereditary
• The right global dimension is 1 but the left global dimension is 2
• This generalizes to give an example of a ring with right global dimension $n$ and left global dimension $n+1$ by replacing $\mathbb{Z}$ by $R$, a commutative noetherian domain of global dimension $n$, then replacing $\mathbb{Q}$ by $K = Frac(R)$
• A similar example gives a ring which is noetherian but neither left nor right Ore. Just take $R = \pmatrix{S & 0 \\\ S & I}$ where $S = \pmatrix{\mathbb{Z} & 0 \\\ \mathbb{Z}_p & \mathbb{Z}_p}$ and $I = \pmatrix{\mathbb{Z} & 0 \\\ 0 & \mathbb{Z}_p}$ is an $S$-ideal.

Having been trained to think in a commutative world, I found the existence of an example for any one of these to be surprising. The fact that they were all (basically) the same example is even more amazing.

-

I'm surprised no one mentioned the Hawaiian Earring:

It's path-connected but not semi-locally simply connected (because any small neighborhood of the origin must contain a non-contractible loop). This implies many interesting properties, which make it a great counter-example. For instance...

• The Hawaiian Earring cannot have a universal cover.
• The Hawaiian Earring is not a CW-complex, although it is a compact, complete metric space
• An example of a space which is semi-locally simply connected and simply connected but is not locally simply connected is the cone on the Hawaiian Earring.
• For many years people thought the fundamental group was always a topological group. This turns out to be false, thanks to the Hawaiian Earring. There's a nice post about this here on MO
• This question is Community Wiki for a reason. I'm sure there are other examples of conjectures the Hawaiian Earring has disproven, so please add them!
-
I like the fact, that it's fundamental group is uncountable. This is a vivid example for showing students, which are new to algebraic topology, that the fundamental group are not just "some" loops in the space. –  archipelago Mar 23 '13 at 13:39
The analogs in higher dimensions have nonzero homology in arbitrarily high dimensions! –  Jeff Strom Mar 23 '13 at 14:48

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

-

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

A standard result in introductory calculus classes is that, if a function has positive derivative on an open interval, then it's increasing there.

Based on this, students tend to think that, if $f'(a)>0$, then $f$ must be increasing "near $a$."

However, the example $f(x) = 2x^2\sin(1/x)+x$ (set $f(0)=0$) shows that this is quite false!

-
See On Functions Increasing at a Point at clem.mscd.edu/~talmanl/PDFs/APCalculus/IncrAtPt_New.pdf. –  I. J. Kennedy Sep 4 '12 at 22:36

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.

-

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

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

-

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

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

-

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

-

A basic result in commutative algebra asserts that direct limits commute with tensor products. My favourite counterexample to the statement obtained by replacing "direct" with "inverse" is the following. Let $p$ be a prime number; then

$\bigl(\varprojlim_n\mathbb Z/p^n\mathbb Z\bigr)\otimes_{\mathbb Z}\mathbb Q\cong\mathbb Q_p$,

the field of $p$-adic numbers (completion of $\mathbb Q$ with respect to the metric induced by the $p$-adic valuation), while

$\varprojlim_n\bigl((\mathbb Z/p^n\mathbb Z)\otimes_{\mathbb Z}\mathbb Q\bigr)=0$,

since every $\mathbb Z/p^n\mathbb Z$ is torsion and $\mathbb Q$ is divisible.

-

Homotopy groups do not, in general, commute with sequential colimits, even for nice maps between nice spaces.

I just learned this beautiful example from Bill Dwyer.
Take the sequence

$S^1\stackrel{2}{\longrightarrow}S^1\stackrel{3}{\longrightarrow}S^1\stackrel{4}{\longrightarrow}\cdots.$

Here $n$ denotes the $n$th power map on $S^1$. Thinking of $S^1$ as $\mathbb{R}/\mathbb{Z}$, one finds that the colimit of this sequence (in the category of topological spaces) is the quotient group $\mathbb{R}/\mathbb{Q}$. Note that this quotient group, topologized as a quotient space of $\mathbb{R}$ by the relation $x\sim y$ if $x-y\in \mathbb{Q}$, has the indiscrete topology. In particular, the colimit of this sequence is a contractible topological space and has trivial homotopy groups.

On the other hand, the colimit of the corresponding sequence of fundamental groups is the group $\mathbb{Q}$ (checking this is a fun exercise).

(There's something sort of odd here, because one might have guessed that $\mathbb{R}/\mathbb{Q}$ would be a model for $K(\mathbb{Q}, 1)$, since after all $\mathbb{R}$ is a free $\mathbb{Q}$-space. But there are no interesting open sets in the quotient and hence no chance of local triviality.)

-

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

I like the double sequence $a_{nm} = \frac{n}{n+m}$ to show that $\lim_{n\to\infty}\lim_{m\to\infty} a_{nm}\neq \lim_{m\to\infty}\lim_{n\to\infty} a_{nm}$ .

-
The sequence which is 0 or 1 depending on which of m and n is greater also works. See the fifth example from tricki.org/article/Just-do-it_proofs and its accompanying discussion. –  aorq Mar 19 '11 at 18:18
Yeah, that works, too! However, I experienced that undergraduates sometimes feel a bit uncomfortable with such "piecewise" definitions and are more happy with a more "natural" example (whatever that means). –  Dirk Mar 19 '11 at 19:58

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.

-

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

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)

-