# 1.4: Countable and Uncountable Sets

Definition 1.18

A set (S) is countable if there is a bijection (f : mathbb{N} ightarrow S). An infinite set for which there is no such bijection is called uncountable.

Proposition 1.19

Every infinite set (S) contains a countable subset.

Proposition 1.19

Every infinite set (S) contains a countable subset.

Proof

Choose an element (s_{1}) from (S). Now (S-{s_{1}}) is not empty because (S) is not finite. So, choose (s_{2}) from (S-{s_{1}}). Then (S-{s_{1}, s_{2}}) is not empty because (S) is not finite. In this way, we can remove (s_{n+1}) from (S-{s_{1}, s_{2}, cdots, s_{n}}) for all (n). Then set ({s_{1}, s_{2}, cdots}) is countable and is contained in (S).

So countable sets are the smallest infinite sets in the sense that there are no infinite sets that contain no countable set. But there certainly are larger sets, as we will see next.

Theorem 1.20

The set (mathbb{R}) is uncountable.

Proof

The proof is one of mathematics’ most famous arguments: Cantor’s diagonal argument . The argument is developed in two steps .

Let (T) be the set of semi-infinite sequences formed by the digits 0 and 2. An element (t in T) has the form (t = t_{1}t_{2}t_{3} dots) where (t_{i} in {0, 2}). The first step of the proof is to prove that (T) is uncountable. So suppose it is countable. Then a bijection (t) between (mathbb{N}) and (T) allows us to uniquely define the sequence (t(n)), the unique sequence associated to (n). Furthermore, they form an exhaustive list of the elements of (T). For example,

[t(1) = extbf{0},0,0,0,0,0,0,0,0,0,0, dots onumber]

[t(2) = 2, extbf{0},2,0,2,0,2,0,2,2,2, dots onumber]

[t(3) = 0,0, extbf{0},2,2,2,2,2,2,2,2, dots onumber]

[t(4) = 2,2,2, extbf{2},2,2,0,0,0,0,0, dots onumber]

[t(5) = 0,0,0,2, extbf{2},0,2,0,0,2,0, dots onumber]

[t(6) = 2,0,0,0,0, extbf{2},0,0,0,2,2, dots onumber]

[vdots onumber]

Construct (t^{*}) as follows: for every (n), its nth digit differs from the nth digit of (t(n)). In the above example, (t^{*} = extbf{2}, extbf{2}, extbf{2}, extbf{0}, extbf{2}, extbf{0}, dots). But now we have a contradiction, because the element (t^{*}) cannot occur in the list. In other words, there is no surjection from (mathbb{N}) to (T). Hence there is no bijection between (mathbb{N}) and (T).

The second step is to show that there is a subset (K) of (mathbb{R}) such that there is no surjection (and thus no bijection) from (mathbb{N}) to (K). Let (t) be a sequence with digits (t_{i}). Define (f : T ightarrow mathbb{R}) as follows

[f(t) = sum_{i=1}^{infty}t_{i}3^{-i} onumber]

If (s) and (t) are two distinct sequences in (T), then for some (k) they share the first (k-1) digits but (t_{k} = 2) and (s_{k} = 0). So

[f(t)-f(s) = 2 cdot 3^{-k}+sum_{i=k+1}^{infty} (t_{i}-s_{i}) 3^{-i} ge 2 cdot 3^{-k}-2 sum_{i=k+1}^{infty} 3^{-i} = 3^{-k} onumber]

Thus (f) is injective. Therefore (f) is a bijection between (T) and the subset (K = f(T)) of (mathbb{R}). If there is a surjection (g) from (mathbb{N}) to (K = f(T)), then,

[mathbb{N} xrightarrow{ ext{g}} K xleftarrow{ ext{f}} T onumber]

And so (f^{-1} g) is a surjection from (mathbb{N}) to (T). By the first step, this is impossible. Therefore, there is no surjection (g) from (mathbb{N}) to (K), much less from (mathbb{N}) to (mathbb{R}).

Corollary 1.21

(i) The set of infinite sequences in ({1,2,cdots, b-1}^{mathbb{N}}) is uncountable.

(ii) The set of finite sequences (but without bound) in ({1, 2, cdots, b-1}^{mathbb{N}}) is countable.

Proof

The proof of (i) is the same as the proof that (T) is uncountable in the proof of Theorem 1.20. The proof of (ii) consists of writing first all (b) words of length 1, then all (b^{2}) words of length 2, and so forth. Every finite string will occur in the list.

Theorem 1.22

(i) The set (mathbb{Z}^2) is countable.

(ii) (mathbb{Q}) is countable.

Proof

(i) The proof relies on Figure 2. In it, a directed path (gamma) is traced out that passes through all points of (mathbb{Z}^2). Imagine that you start at ((0, 0)) and travel along (gamma) with unit speed. Keep a counter (c in mathbb{N}) that marks the point ((0, 0)) with a “1”. Up the value of the counter by 1 whenever you hit a point of (mathbb{Z}^2). This establishes a bijection between (mathbb{N}) and (mathbb{Z}^2). Figure 2. A directed path (gamma) passing through all points of (mathbb{Z}^2).

(ii) Again travel along (gamma) with unit speed. Keep a counter (c in mathbb{N}) that marks the point ((0, 1)) with a “1”. Up the value of the counter by 1. Continue to travel along the path until you hit the next point ((p, q)) that is not a multiple of any previous and such (q) is not zero. Mark that point with the value of the counter. (mathbb{Q}) contains (mathbb{N}) and so is infinite. Identifying each marked point ((p, q)) with the rational number (frac{p}{q}) establishes the countability of (mathbb{Q}).

Notice that this argument really tells us that the product of a countable set and another countable set is still countable. The same holds for any finite product of countable set. Since an uncountable set is strictly larger than a countable, intuitively this means that an uncountable set must be a lot largerthan a countable set. In fact, an extension of the above argument shows that the set of algebraic numbers numbers is countable. And thus, in a sense, it forms small subset of all reals. All the more remarkable, that almost all reals that we know anything about are algebraic numbers, a situation we referred to at the end of Section 1.4.

It is useful and important to have a more general definition of when two sets “have the same number of elements”.

Definition 1.23

Two sets A and B are said to have the same cardinality if there is a bijection (f : A ightarrow B). It is written as (|A| = |B|). If there is an injection (f : A ightarrow B), then (|A| le |B|).

Definition 1.24

An equivalence relation on a set (A) is a (sub)set (mathbb{R}) of ordered pairs in (A imes A) that satisfy three requirements.

• ((a, a) in mathbb{R}) (reflexivity).
• If ((a, b) in mathbb{R}), then ((b, a) in mathbb{R}) (symmetry).
• If ((a, b) in mathbb{R}) and ((b, c) in mathbb{R}), then If ((a, c) in mathbb{R}) (transitivity).

Usually ((a, b) in mathbb{R}) is abbreviated to (a sim b). The mathematical symbol “(=)” is an equivalence.

It is easy to show that having the same cardinality is an equivalence relation on sets (exercise 1.23). Note that the cardinality of a finite set is just the number of elements it contains. An excellent introduction to the cardinality of infinite sets in the context of naive set theory can be found in .

## Finite, Countable and Uncountable Sets - Set Theory, CSIR-NET Mathematical Sciences Mathematics Notes | EduRev

1. Introducing equivalence of sets, countable and uncountable sets

We assume known the set Z + of positive integers, and the set N = Z + U <0>of natural numbers. For any n &isin Z + , we denote by [n] the set <1. n>. We take it as obvious that [n] has n elements, and also that the empty set Ø has 0 elements. Just out of mathematical fastidiousness, 1 let's define  = Ø (why not?).

It is pretty clear what it means for an arbitrary set S to have 0 elements: it must be the empty set. That is - and this is a somewhat curious property of the empty set - Ø as a set is uniquely characterized by the fact that it has 0 elements.

What does it mean for an arbitrary set S to have n elements? By definition, it means that there exists a bijection i : S &rarr [n], i.e., a function which is both injective and surjective or, equivalently, a function for which there exists an inverse function i : [n] &rarr S . 2

Let us call a set finite if it has n elements for some n &isin N, and a set infinite if it is not finite.

Certainly there are some basic facts that we feel should be satisfied by these definitions. For instance:

Fact 1. The set Z + is infinite.

Proof: It is certainly nonempty, so we would like to show that for no n &isin Z + is there a bijection i : [n] &rarr Z + . This seems obvious. Unfortunately, sometimes in mathematics we must struggle to show that the obvious is true (and sometimes what seems obvious is not true!). Here we face the additional problem of not having formally axiomatized things, so it's not completely clear what's fair game" to use in a proof. But consider the following: does Z+ have one element? Absolutely not: for any function i :  = <1>&rarr Z + , i is not surjective because it does not hit i(1) + 1. Does Z + have two elements? Still, no: if i is not injective, the same argument as before works if i is injective, its image is a 2 element subset of Z + . Since Z + is totally ordered (indeed well-ordered), one of the two elements in the image is larger than the other, and then that element plus one is not in the image of our map. We could prove it for 3 as well, which makes us think we should probably work by induction on n. How to set it up properly? Let us try to show that for all n and all i : [n] &rarr Z + , there exists N = N (i) such that i([n]) &sub [N]. If we can do this, then since [N] is clearly a proper subset of Z + (it does not contain N + 1, and so on) we will have shown that for no n is there a surjection [n] ! Z+ (which is in fact stronger than what we claimed). But carrying through the proof by induction is now not obvious but (much better!) very easy, so is left to the reader.

• Well, not really: this will turn out to be quite sensible.
• I am assuming a good working knowledge of functions, injections, surjections, bijections and inverse functions. This asserts at the same time (i) a certain amount of mathematical sophistication, and (ii) a certain amount of metamathematical informality.

Remark: What did we use about Z + in the proof ? Some of the Peano axioms for Z + , most importantly that it satisfies the principle of mathematical induction (POMI). Since it is hard to imagine a rigorous proof of a nontrivial statement about Z + that does not use POMI, this is a good sign: things are proceeding well so far.

What about Z: is it too infinite? It should be, since it contains an infinite subset. This is logically equivalent to the following fact:

Fact 2. A subset of a finite set is finite.

Proof: More concretely, it suffices to show that for any n &isin N and and subset S &sub [n], then for some m &isinN there exists a bijection i : S &rarr [m]. As above, for any specific value of n, it straightforward to show this, so again we should induct on n. Let's do it this time: assume the statement for n, and let S &sub [n + 1]. Put S' = S &cap [n], so by induction there exists a bijection i' : [m] &rarr S' for some m' &isin N.
Composing with the inclusion S' &sub S we get an injection i : [m] &rarr S . If n + 1 is not an element of S , then S' = S and i is a bijection. If n + 1 &isin S , then extending i' to a map from [m + 1] to S by sending m + 1 to n + 1 gives a bijection. Done.

Again, by contraposition this shows that many of our most familiar sets of numbers - e.g. Z Q R C - are infinite.

There is one more thing we should certainly check: namely, we have said that a set S has n elements if it can be put in bijection with [n] for some n. But we have not shown that this n is unique: perhaps a set can have n elements and also n + 691 elements? Of course not:

Fact 3. Let S be a set with m elements and T a set with n elements.

a) If there exists a surjection &phi : S &rarr T , then m > n.

b) If there exists an injection &phi : S &rarr T , then m < n.

Exercise 1: Give a proof of Fact 4 which is rigorous enough for your taste.

Remark: For instance, part b) is the famous &ldquoPigeonhole" or &ldquoDirichlet's box" principle, and is usually regarded as obvious. Of course, if we play the game of formalized mathematics, then "obvious" means "following from our axioms in a way which is so immediate so as not to deserve mention," and Fact 3 is not obvious in this sense. (But one can give a proof in line with the above induction proofs, only a bit longer.)

Exercise 2: Show that for sets S and T , the following are equivalent:

a) There exists a surjection S &rarr T .

b) There exists an injection T &rarr S .

Let us press on to study the properties of infiinite sets.

Basic Definition (Cantor): We say that S and T as equivalent, and write S ≌ T if there exists a bijection i : S &rarr T.

However, we have our reasons for choosing to use &ldquoequivalent." The term &ldquoequinumerous," for instance, suggests that the two sets have the same number of elements, or in other words that there is some numerical invariant we are attaching to a single set with the property that two sets can be put in bijection exactly when both have the same value of this numerical invariant. But we would like to view things in exactly the opposite way. Let us dilate a bit on this point.

It was Cantor's idea that we should regard two sets as &ldquohaving the same size" if they are equivalent, i.e., if their elements can be paired of via a one-to-one correspondence. Certainly this is consistent with our experience from finite sets.

There is, however, a brilliant and subtle twist: colloquially one thinks of counting or measuring something as a process which takes as input one collection of ob jects and outputs a umber." We therefore have to have names for all of the umbers" which measure the sizes of things: if you like, we need to count arbitrarily high. Not every civilization has worked out such a general counting scheme: I have heard tell that in a certain primitive tribe" they only have words for numbers up to 4 and anything above this is just referred to as many." Indeed we do not have proper names for arbitrarily large numbers in the English language (except by recourse to iteration, e.g., million million for a trillion).

But notice that we do not have to have such an elaborate umber knowledge" to say whether two things have the same size or not. For instance, one may presume that shepherding predates verbal sophistication, so the proto-linguistic shepherd needs some other means of making sure that when he takes his sheep out to graze in the countryside he returns with as many as he started with. The shepherd can do this as follows: on his first day on the job, as the sheep come in, he has ready some sort of sack and places stones in the sack, one for each sheep. Then in the future he counts his sheep, not in some absolute sense, but in relation to these stones. If one day he runs out of sheep before stones, he knows that he is missing some sheep (at least if he has only finitely many sheep!).

Even today there are some situations where we test for equivalence rather than count in an absolute sense. For instance, if you come into an auditorium and everyone is sitting in a (unique!) seat then you know that there are at least as many seats as people in the room without counting both quantities.

3. Or rather, he said something in German that gets translated to this. Such pedantic remarks will be omitted from now on!

4. This is a game that some play better than others, viz.: generization, sobrification, unicity.

What is interesting about infinite sets is that these sorts of arguments break down: the business of taking away from an infinite set becomes much more complicated than in the finite case, in which, given a set S of n elements and any element x &isin S , then S x has n - 1 elements. (This is something that you can establish by constructing a bijection and is a good intermediate step towards Fact 4.) On the other hand, Z + and N are equivalent, since the map n &rarr n - 1 gives a bijection between them. Similarly Z + is equivalent to the set of even integers (n&rarr 2n). Indeed, we soon see that much more is true:

Fact 4. For any infinite subset S &sub Z + , S and Z + are equivalent.

Proof: Using the fact that Z + is well-ordered, we can define a function from S to Z + by mapping the least element s1 of S to 1, the least element s2 of S <>1> to 2, and so on. If this process terminates after n steps then S has n elements, so is finite, a contradiction. Thus it goes on forever and clearly gives a bijection.

It is now natural to wonder which other familiar infinite sets are equivalent to Z + (or N). For this, let's call a set equivalent to Z + countable. 5 A slight variation of the above argument gives

Fact 5. Every infinite set has a countable subset.

(Indeed, for infinite S just keep picking elements to define a bijection from Z + to some subset of S we can't run out of elements since S is infinite!) As a first example:

Fact 6. The two sets Z and Z + are equivalent.

We define an explicit bijection Z &rarr Z + as follows: we map 0 &rarr 1, then 1 &rarr 2, &rarr1 &rarr 3, 2 &rarr 4, -2 &rarr 5 and so on. (If you are the kind of person who thinks that having a formula makes something more rigorous, then we de¯ne for positive n, n ! 2n and for negative n, n &rarr 2|n| + 1.)

The method proves something more general, a "splicing" result.

Fact 7. Suppose that S1 and S2 are two countable sets. Then S1 &cup S2 is countable.

Indeed, we can make a more general splicing construction :

Fact 8. Let <>i> i&isinI be an indexed family of pairwise disjoint nonempty sets assume that I and each Si is at most countable (i.e., countable or finite). Then S : = Ui&isinI Si
is at most countable. Moreover, S is finite if I and al l the Si are finite.

We sketch the construction: since each Si is at most countable, we can order the elements as sij where either 1 < j < &infin or 1 < j < Nj . If everything in sight is finite, it is obvious that S will be finite (a finite union of finite sets is finite). Otherwise, we define a bijection from Z + to S as follows: 1 &rarr s11 &rarr 2 &rarr s12 &rarr 3 &rarr s22 &rarr 4 &rarr s13 &rarr 5 &rarr s23 &rarr6 &rarr s33 , and so on. Here we need the convention that when sij does not exist, we omit that term and go on to the next element in the codomain.

 Perhaps more standard is to say countably infinite and reserve &ldquocountable" to mean countably infinite or finite. Here we suggest simplifying the terminology.

Fact 8 is used very often in mathematics. As one immediate application:

Fact 9. The set of rational numbers Q is countable.

Proof: Each nonzero rational number &alpha can be written uniquely as + a/b , where a, b &isin Z + . We define the height h(&alpha) of &alpha to be max a b and also h(0) = 0. It is clear that for any height n > 0, there are at most 2n 2 rational numbers of height n, and also that for every n &isin Z + there is at least one rational number of height n, namely the integer n = n/1 . Therefore taking I = N and putting some arbitrary ordering on the finite set of rational numbers of height n, Fact 9 gives us a bijection Z + &rarr Q.

In a similar way, one can prove that the set of algebraic numbers is countable.

Fact 10. If A and B are countable, then the Cartesian product A x B is countable.

Exercise 3: Prove Fact 10. (Strategy 1: Reduce to the case of Z + x Z + and use the diagonal path from the proof of Fact 8. Strategy 2: Observe that A x B ≌ Ua&isinA B and apply Fact 8 directly.)

The buck stops with R. Let's first prove the following theorem of Cantor, which is arguably the single most important result in set theory. Recall that for a set S , its power set 2 S is the set of all subsets of S .

Theorem 11. (First Fundamental Theorem of Set Theory)

There is no surjection from a set S to its power set 2 S .

Remark: When S is finite, this is just saying that for all n &isin N, 2 n > n, which is, albeit true, not terribly exciting. On the other hand, taking S = Z + Cantor's Theorem provides us with an uncountable set 2 Z+ . In fact it tells us much more than this, as we shall see shortly.

Proof of Cantor's Theorem: Suppose that f : S &rarr2 S is any function. We will produce an element of 2 S which is not in the image of f .
Namely, let T be the set of all x &isin S such that x is not an element of f (x), so T is some element of 2 S . Could it be f (s) for some s &isin S ? Well, suppose T = f (s) for some s &isin S . We ask the innocent question, "Is s &isin T ?" Suppose first that it is: s &isin T by definition of T this means that s is not an element of f (s). But f (s) = T , so in other words s is not an element of T , a contradiction. Okay, what if s is not in T ? Then s &isin f (s), but again, since f (s) = T , we conclude that s is in T. In other words, we have managed to define, in terms of f , a subset T of S for which the notion that T is in the image of f is logically contradictory. So f is not surjective!

What does this have to do with R? Let us try to show that the interval (0 1] is uncountable. By Fact 5 this implies that R is uncountable. Now using binary expansions, we can identify (0 1] with the power set of Z + . Well, almost: there is the standard slightly annoying ambiguity in the binary expansion,

There are various ways around this: for instance, suppose we agree to represent every element of (0 1] by an element which does not terminate in an infinite string of zeros. Thus we have identified (0 1] with a certain subset T of the power set of Z + , the set of infinite subsets of Z + . But the set of finite subsets of Z + is countable (Fact 8 again), and since the union of two countable sets would be countable (and again!), it must be that T is uncountable. Hence so is (0 1], and so is R.

There are many other proofs of the uncountability of R. For instance, we could contemplate a function f : Z + &rarr R and, imitating the proof of Cantor's theorem, show that it cannot be surjective by finding an explicit element of R not in its image. We can write out each real number f(n) in its decimal expansion, and then construct a real number &alpha &isin [0 1] whose nth decimal digit &alphan is different from the nth decimal digit of f (n). Again the ambiguity in decimal representations needs somehow to be addressed: here we can just stay away from 9's and 0's. Details are left to the reader.

A more appealing, albeit more advanced, proof comes from a special case of the Baire category theorem: in any complete metric space, the intersection of a countable number of dense open subsets remains dense (although not necessarily open, of course). Dualizing (i.e., taking complements), we get that in any complete metric space, the union of a countable number of closed subsets with empty interior also has empty interior. Thus:

Corollary 13. A complete metric space without isolated points is uncountable.

Proof: Apply the dual form of Baire's theorem to the one-point subsets of the space.

Thus, since R is by definition the completion of Q with respect to the standard Euclidean metric, and has no isolated points, R must be uncountable. For that matter, even Q has no isolated points (which is strictly stronger: no element of the completion of a metric space minus the space itself can be isolated, since this would contradict the density of a space in its completion), so since we know it is countable, we deduce that it is incomplete without having to talk about &radic2 or any of that sort of thing. Indeed, the same argument holds for Q endowed with a p-adic metric: there are no isolated points, so Qp is uncountable and not equal to Q.

The above was just one example of the importance of distinguishing between countable and uncountable sets. briefly mention some other examples:

Example 2: Measure theory. A measure is a [0 &infin]-valued function defined on a certain family of subsets of a given set it is required to be countably additive but not uncountably additive. For instance, this gives us a natural notion of size on the unit circle, so that the total area is &pi and the area of any single point is 0.
The whole can have greater measure than the sum of the measures of the parts if there are uncountably many parts!

Example 3: Given a differentiable manifold M of dimension n, then any submanifold of dimension n- 1 has, in a sense which is well-defined independent of any particular measure on M , measure zero. In particular, one gets from this that a countable family of submanifolds of dimension at most n - 1 cannot "fill out" an n-dimensional manifold. In complex algebraic geometry, such stratifications occur naturally, and one can make reference to a "very general" point on a variety as a point lying on the complement of a (given) countable family of lower-dimensional subvarieties, and be confident that such points exist!

Example 4: Model theory is a branch of mathematics which tends to exploit the distinction between countable and uncountable in rather sneaky ways. Namely, there is the Lowenheim-Skolem theorem, which states in particular that any theory (with a countable language) that admits an infinite model admits a countable model. Moreover, given any uncountable model of a theory, there is a countable submodel which shares all the same "first order" properties, and conversely the countable/uncountable dichotomy is a good way to get an intuition on the difference between first-order and second-order properties.

2. Some further basic results

Dedekind's characterization of infinite sets.

Fact 14. A set S is infinite iff it is equivalent to a proper subset of itself.

Proof: One direction expresses an obvious fact about finite sets. Conversely, let S be an infinite set as above, there is a countable subset T &sub S . Choose some bijection i between T and N. Then there is a bijection i' between T':= T i -1 (0) and T (just because there is a bijection between N and Z + . We therefore get a bijection between S':= S i -1 (0 and S by applying i' from T' to T and the identity on S T .

This characterization of infinite sets is due to Dedekind. What is ironic is that in some sense it is cleaner and more intrinsic than our characterization of finite sets, in which we had to compare against a distinguished family of sets <[n] | n &isin N>.
Thus perhaps we should define a set to be finite if it cannot be put in bijection with a proper subset of itself ! (On the other hand, this is not a "first order" property, so is not in reality that convenient to work with.)

An uncountable set not of continuum type. Notice that in making the definition "uncountable," i.e., an infinite set which is not equivalent to Z + , we have essentially done what we earlier made fun of the "primitive tribes" for doing: giving up distinguishing between very large sets. In some sense, set theory begins when we attempt to classify uncountable sets up to equivalence. This turns out to be quite an ambitious pro ject - we will present the most basic results of this pro ject in the next installment - but there are a few further facts that one should keep in mind throughout one's mathematical life.

Let us define a set S to be of continuum type (or, more briefly, a continuum) if there is a bijection i : S &rarr R. One deserves to know the following:

Fact 15. There exists an uncountable set not of continuum type, namely 2 R .

Proof: By Theorem 11 there is no surjection from R to 2 R , so 2 R is certainly not of continuum type. We must however confirm what seems intuitively plausible: that 2 R is indeed uncountable. It is certainly infinite, since via the natural injection i : R &rarr 2R , r &rarr , it contains an infinite subset. But indeed, this also shows that 2 R is uncountable, since if it were countable, its subset i(R) ≌ R would be countable, which it isn't.

Some sets of continuum type. For any two sets S and T , we define T S as the set of all functions f : S &rarr T . When T = , the set of all functions f : S &rarr  is naturally identified with the power set 2 S of S (so the notation is almost consistent: for full consistency we should be denoting the power set of S by  S , which we will not trouble ourselves to do).

Fact 16. The sets (0 1], 2 Z+ and R Z+ are of continuum type.

Proof: Earlier we identified the unit interval (0 1] in R with the infinite subsets of Z + and remarked that, since the finite subsets of Z + form a countable set, this implies that (0 1] hence R itself is uncountable. Let us refine this latter observation slightly:

Lemma 17. Let S be an uncountable set and C &sub S an at most countable subset.
Then S C ≌ S.

Proof: Suppose first that C is finite, say C ≌ [n]. Then there exists an injection i : Z + &rarr S such that i([n]) = C (as follows immediately from Fact 6). Let C&infin = i(Z + ). Now we can define an explicit bijection &beta from S C to S : namely, we take &beta to be the identity on the complement of C&infin and on C&infin we define &beta (i(k)) = i(k - n).

Now suppose C is countable. We do something rather similar. Namely, taking C1 = C , since S C1 is uncountable, we can find a countably infinite subset C2 &sub S C1 . Proceeding in this way we can find a family <>i>i&isinZ+ of pairwise disjoint countable subsets of S. Let us identify each of these subsets with Z + , getting a doubly indexed countable subset C&infin := UiCi = <>ij> - here cij is the jth element of Ci . Now we define a bijection &beta from S C1 to S by taking &beta to be the identity on the complement of C&infin and by putting &beta (cij) = c(i-1)j . This completes the proof of the lemma.

Thus the collection of infinite subsets of Z + - being a subset of 2 Z+ with countable complement - is equivalent to 2 Z+ , and hence (0 1]≌ 2 Z+ . So let us see that (0 1] is of continuum type. One way is as follows: again by the above lemma, [0 1] ≌ (0 1), and R is even homeomorphic to (0 1): for instance, the function For the case of (Z + ) R : since R ≌ 2 Z+ , it is enough to find a bijection from (Z + )2 Z+ to 2 Z+ . This is in fact quite easy: we are given a sequence aij of binary sequences and want to make a single binary sequence. But we can do this just by choosing a bijection Z + x Z + &rarr Z + .

A little more abstraction will make this argument seem much more reasonable:

Lemma 18. Suppose A, B and C are sets. Then there is a natural bijection

Proof of the Lemma: Indeed, given a function F from C to A B and an ordered pair (c, b) &isin C x B , F(c) is a function from B to A and so F(c)(b) is an element of a.

Conversely, every function from C x B to A can be viewed as a function from C to the set A B of functions from B to A, and these correspondences are evidently mutually inverse. 8 So what we said above amounts to Exercise 4: A subinterval of R containing more than one point is of continuum type.

It is also the case that (Z + ) Z+ is of continuum type. At the moment I do not see a proof of this within the framework we have developed. What we can show is that there exists an injection R ,&rarr (Z + ) Z+ < indeed, since R ≌ 2 Z+ , this is obvious < and also that there exists an injection (Z + ) Z+ ,&rarr 2 Z+ ≌ R.

But this can be remedied in many ways. One obvious way is to retreat from binary notation to unary notation: we encode ai as a string of i ones, and in between each string of ai ones we put a zero to separate them. This clearly works (it seems almost cruelly ine±cient from the perspective of information theory, but no matter).

Roughly speaking, we have shown that (Z + ) Z+ is "at least of continuum type" and at most of continuum type," so if equivalences of sets do measure some reasonable notion of their size, we ought to be able to conclude from this that (Z + ) Z+ is itself of continuum type. This is true, a special case of the important SchrÄoderBernstein theorem whose proof we defer until the next installment.

Lots of inequivalent uncountable sets. From the fundamental Theorem 12 we first deduced that not all infinite sets are equivalent to each other, because the set 2 Z+ is not equivalent to the countable infinite set Z + . We also saw that 2 Z+ ≌ R so called it a set of continuum type. Then we noticed that Cantor's theorem implies that there are sets not of continuum type, namely 2 R ≌ 2 2Z+ . By now one of the most startling mathematical discoveries of all time must have occurred to the reader: we can keep going!

To simplify things, let us use (and even slightly abuse) an obscure but colorful notation due to Cantor: instead of writing Z + we shall write Z0 . For 2 Z+ we shall write Z1 , and in general, for n &isin N, having defined in (informally, as the n-fold iterated power set of Z + ), we will define Zn+1 as 2 Zn . Now hold on to your hat:

Fact 19. The infinite sets fin <>n>n&isinN are pairwise inequivalent.

Proof: Let us first make the preliminary observation that for any nonempty set S , there is a surjection 2 S &rarr S . Indeed, pick your favorite element of S , say x for every s &isin S we map fsg to s, which is "already" a surjection we extend the mapping to all of 2 S by mapping every other subset to x.

8. This is canonical bijection is sometimes called "adjunction."

Now we argue by contradiction: suppose that for some n > m there exists even a surjection s : Zm &rarr Zn. We may write n = m + k. By the above, by concatenating (finitely many) surjections we get a surjection &beta : Zm+k &rarr Zm+1 . But then &beta º s : Zm &rarr Zm+1 = 2 Zm is a surjection, contradicting Cantor's theorem.

Thus there are rather a lot of inequivalent in¯nite sets. Is it possible that the Zn 's are all the infinite sets? In fact it is not : define Zw := Un&isinN Zn. This last set Zw is certainly not equivalent to Zn for any n, because it visibly surjects onto Zn+1 . Are we done yet? No, we can keep going, defining Zw+1 := 2 Zw .

To sum up (!!), we have a two-step process for generating a mind-boggling array of equivalence classes of sets. The first step is to pass from a set to its power set, and the second stage is to take the union over the set of all equivalence classes of sets we have thus far considered. Inductively, it seems that each of these processes generates a set which is not surjected onto by any of the sets we have thus far considered, so it gives a new equivalence class. Does the process ever end.

Well, the above sentence is an example of the paucity of the English language to describe the current state of affairs, since even the sequence Z0 Z1 Z2 . does not end in the conventional sense of the term. Better is to ask whether or not we can reckon the equivalence classes of sets even in terms of infinite sets. At least we have only seen countably many equivalence classes of sets thus far: is it possible that the collection of all equivalence classes of sets is countable?

No again, and in fact that's easy to see. Suppose <>i> i&isinN is any countable collection of pairwise inequivalent sets. Then - playing both of our cards at once! - one checks immediately that there is no surjection from any Si onto . In fact it's even stranger than this:

Fact 20. For no set I does there exists a family of sets <>i>i&isinI such that every set S is equivalent to Si for at least one i.

Proof: Again, take . There is no surjection from U i&isinI Si onto Sbigger , so for sure there is no surjection from any Si onto Sbigger .

3. Some Final Remarks

Fact 20 is a truly amazing result. Once you notice that it follows readily from Cantor's Theorem 12, you may believe, as I do, that this theorem is the single most amazing result in all of mathematics.

There is also the question of whether this result is disturbing, or paradoxical. Can we then not speak of the set of all equivalence classes of sets (let alone, the set of all sets)? Evidently we cannot. There are too many sets to wrap all of them up into a single set. Some people have referred to this as Cantor's Paradox, although I do not favor this terminology: as far as I am aware, Cantor did not regard his results as paradoxical, nor do I. It does destroy the ultranaive" notion of a set, namely, that given any "property" P , there is a set SP = [x | P (x)>: according to Cantor's result, we cannot take P to be the property x = x. This was surprising in the late 19th century. But now we know of such things as Russell's paradox, which shows that the property P (x) given by x ¬in x does not give rise to a set: the set of all sets which are not members of itself is a logical contradiction.

## 1.4: Countable and Uncountable Sets

The nonnegative integers are countable, as shown by the bijection f(n) = n+1. Some people prefer this definition. It is sometimes more natural to begin counting at 0, rather than 1. I guess it depends on whether you program in C or fortran.

The even numbers are countable map n to n/2. Thus an infinite set can be just as large as a proper subset of itself.

The integers are countable. Map n to 2n for n ≥ 0, and map n to 1-2n for n < 0.

Any set that can be listed in order, or enumerated, is countable. For instance, any subset of the positive integers is countable. Take the smallest number in the set and place it first on the list. Take the next smallest and place it second on the list. Continue this process until the entire set has been "counted", i.e. mapped onto the positive integers. Thus the prime numbers are countable, and so on.

Ordered pairs of positive integers are countable. List them this way:

1/1 2/1 1/2 3/1 2/2 1/3 4/1 3/2 2/3 1/4 5/1 4/2 3/3 2/4 1/5 …

Since fractions are ordered pairs of integers, the rational numbers are countable. This is counterintuitive, since they are densely packed in the number line. There are infinitely many rationals packed into the tiniest of intervals, yet there are just as many rationals as integers.

We showed that the cross product (i.e. ordered pairs) of countable sets is countable. Use this fact again and again to show that the n-tuples of integers are countable. The integer points, or even the rational points in n space are countable.

In fact all finite ordered tuples of the integers, or any other countable set for that matter, are countable. Here is a recipe for listing all possible tuples in order. We know that the tuples of size n can be listed in order this was described above. So start with the first tuple of size 1, then the first tuple of size 2 followed by the second tuple of size 1, then the first tuple of size 3 and the second tuple of size 2 and the third tuple of size 1, then the first tuple of size 4 and the second tuple of size 3 and the third tuple of size 2 and the fourth tuple of size 1, and so on.

As a corollary, the finite sets of integers are countable, as these are all represented, perhaps many times, by various ordered tuples. The set (1,2,3) appears six times when order is significant. Since the ordered tuples over count the unordered subsets, and the tuples are countable, the finite subsets are also countable.

Note that the integer polynomials are precisely the finite ordered tuples of integers. Wel almost the tuples that have leading zeros can be thrown away. Anyways, since the tuples are countable, the polynomials are countable. Of course the coefficients can be drawn from any countable set, so the polynomials over the rationals are countable.

The polynomials over x and y are the polynomials in y, whose coefficients are polynomials in x. We just showed the polynomials in x are countable, and since these act as coefficients, the polynomials in x and y are countable. This extends to polynomials in x y z, and so on.

### Combinations that are not Sets

Yes I know, all ordinals are sets, and there are uncountably many ordinals. This is a contradiction that I don't understand. If you can explain it to me, please drop me a line.

## Finite cardinality

Definition: If (X) is a set and (n in ℕ) , the expression "|X| = n" means (|X| = <1,2,dots,n>) .

This matches the usual notion of the number of things in the set.

Claim: If (|A| = a) and (|B| = b) , and if (A) and (B) are disjoint, then (|A cup B| = a + b) .

Note: This can be shortened to " (|A cup B| = |A| + |B|) , as long as you keep in mind that this equation only makes sense if (|A|) and (|B|) are numbers (i.e. if (A) and (B) are finite)

Proof: Since (|A| = a) , there exists a bijection (f : A → <1,2,dots,a>) . Similarly, there exists (g : B → <1,2,dots,b>) . We can build a function (h : A cup B → <1,2,dots,a+b>) by defining [h(x) := left<egin f(x), & ext g(x), & ext end ight.]

To complete the proof, we need to show that (h) is a bijection. We left this as an exercise. While you're doing the exercise, make sure you use the fact that (A cup B = emptyset) .

## Countable and Uncountable Sets

Probability models often involve infinite sample spaces, that is, infinite sets.

But not all sets are of the same kind.

Some sets are discrete and we call them countable, and some are continuous and we call them uncountable.

But what exactly is the difference between these two types of sets?

How can we define it precisely?

Well, let us start by first giving a definition of what it means to have a countable set.

A set will be called countable if its elements can be put into a 1-to-1 correspondence with the positive integers.

This means that we look at the elements of that set, and we take one element-- we call it the first element.

We take another element-- we call it the second.

Another, we call the third element, and so on.

And this way we will eventually exhaust all of the elements of the set, so that each one of those elements corresponds to a particular positive integer, namely the index that appears underneath.

More formally, what's happening is that we take elements of that set that are arranged in a sequence.

We look at the set, which is the entire range of values of that sequence, and we want that sequence to exhaust the entire set omega.

Or in other words, in simpler terms, we want to be able to arrange all of the elements of omega in a sequence.

So what are some examples of countable sets?

In a trivial sense, the positive integers themselves are countable, because we can arrange them in a sequence.

This is almost tautological, by the definition.

For a more interesting example, let's look at the set of all integers.

Can we arrange them in a sequence?

Yes, we can, and we can do it in this manner, where we alternate between positive and negative numbers.

And this way, we're going to cover all of the integers, and we have arranged them in a sequence.

How about the set of all pairs of positive integers?

Let us look at this picture.

This is the set of all pairs of positive integers, which we understand to continue indefinitely.

Can we arrange this sets in a sequence?

And we can do it by tracing a path of this kind.

So you can probably get the sense of how this path is going.

And by continuing this way, over and over, we're going to cover the entire set of all pairs of positive integers.

So we have managed to arrange them in a sequence.

So the set of all such pairs is indeed a countable set.

And the same argument can be extended to argue for the set of all triples of positive integers, or the set of all quadruples of positive integers, and so on.

This is actually not just a trivial mathematical point that we discuss for some curious reason, but it is because we will often have sample spaces that are of this kind.

And it's important to know that they're countable.

Now for a more subtle example.

Let us look at all rational numbers within the range between 0 and 1.

What do we mean by rational numbers?

We mean those numbers that can be expressed as a ratio of two integers.

It turns out that we can arrange them in a sequence, and we can do it as follows.

Let us first look at rational numbers that have a denominator term of 2.

Then, look at the rational numbers that have a denominator term of 3.

Then, look at the rational numbers, always within this range of interest, that have a denominator of 4.

And then we continue similarly-- rational numbers that have a denominator of 5, and so on.

This way, we're going to exhaust all of the rational numbers.

Actually, this number here already appeared there.

So we do not need to include this in a sequence, but that's not an issue.

Whenever we see a rational number that has already been encountered before, we just delete it.

In the end, we end up with a sequence that goes over all of the possible rational numbers.

And so we conclude that the set of all rational numbers is itself a countable set.

So what kind of set would be uncountable?

An uncountable set, by definition, is a set that is not countable.

And there are examples of uncountable sets, most prominent, continuous subsets of the real line.

Whenever we have an interval, the unit interval, or any other interval that has positive length, that interval is an uncountable set.

And the same is true if, instead of an interval, we look at the entire real line, or we look at the two-dimensional plane, or three-dimensional space, and so on.

So all the usual sets that we think of as continuous sets turn out to be uncountable.

How do we know that they are uncountable?

There is actually a brilliant argument that establishes that the unit interval is uncountable.

And then the argument is easily extended to other cases, like the reals and the plane.

We do not need to know how this argument goes, for the purposes of this course.

But just because it is so beautiful, we will actually be presenting it to you.

## 1.4: Countable and Uncountable Sets

While writing the paradox series, and thinking about set theory for the item on Russell’s Paradox, I decided to do some related entries, considering things that seem contradictory but aren’t. This one is on the cardinality of sets, and, in particular, about countable and uncountable sets.

[Let me start by saying that this will be a simplified explanation, making a number of unstated assumptions (such as assuming the axiom of choice, as is standard in modern set theory). If one is rigorous, this stuff can get way more complicated than I’ll ever want to get into here PhD theses, and, indeed, whole careers are often based on rigorous coverage of this. We’re not going there.]

I think we all understand that there are finite sets, and infinite ones. A finite set has. well, a finite number of elements &mdash the set of all U.S. presidents, the set of bones in the human body, the set of all films that have won “Best Picture” Academy Awards, the set of all people in the world. Or the set of all natural numbers less than or equal to 5: < 1, 2, 3, 4, 5 >.

An infinite set has an infinite number of elements. We have a vague idea what that means, but it’s harder to write that down, isn’t it? Examples are easy, though: the set of all natural numbers, for example: < 1, 2, 3, 4, 5, 6, . >, with no bound. The set of all integers &mdash positive and negative natural numbers, and zero. The set of all rational numbers &mdash the integers and all the fractions. The set of all real numbers &mdash the rationals, plus the irrational numbers, numbers such as &radic2, &radic3, and &pi.

There are other sets in the real world that we think of as infinite, but are we sure they are? The set all of grains of sand in the world the set of all stars in the universe the set of all atoms in the universe, come to that. But in mathematics, an infinite set is more precise. It doesn’t refer to something bigger than we can imagine, but really something that no number, however vastly, immensely large, can describe.

To get a less vague meaning of “infinite”, we’ll go back to the finite sets and talk about countability and cardinality. Clearly, one aspect of any finite set is that there’s a natural number (or zero, for the empty set) that tells us how many elements are in the set. For the set of all U.S. presidents, it’s 43 (soon to be 44). For the set of all natural numbers less than or equal to 5, it’s 5. For the set of all people in the world, we don’t know the number. but it’s clear to us that there is one, and it’s quite large.

We call that number the cardinal number of a set, and every finite set has a cardinal number that’s a non-negative integer. And we can define an infinite set as a set that does not have an integral cardinal number. It seems intuitive, then, that the sets of natural numbers, integers, rationals and reals are all infinite.

Going back to finite sets, we also understand that we can count the elements of any finite set. George Washington is 𔄙”, John Adams is 𔄚”, . Abraham Lincoln is 󈬀”, . Woodrow Wilson is 󈬌”, . and George Bush is 󈬛”. We hope Barack Obama will be 󈬜”. And the counting stops. Similarly, for bones, films, and people, we can assign a natural number to each element, starting at 1 and increasing by 1 for each element, and we call that “counting” (and here’s where the axiom of choice comes in).

More formally, what we’re really doing when we count is creating a one-to-one correspondence between the elements of the set and the subset of natural numbers less than or equal to the cardinal number of the set (we’ll ignore, for the presidents, the fact that Grover Cleveland appears twice think of him as having a not-so-evil twin).

But why do we have to stop? For an infinite set, T , suppose we can create a one-to-one correspondence between T and the entire set of natural numbers, unbounded. Have we not “counted” the set T , in some sense? Granted, our counting never stops &mdash it’s an infinite set, after all &mdash but if we can prove that every element of T has a natural number associated with it, we can say that we can count the elements.

Clearly, all finite sets are countable, so all uncountable sets are infinite. Let’s play with some countable sets for a bit. First, another definition: the cardinal number of the natural numbers is a thing we call (said “aleph-null”, using the Hebrew letter aleph).

The set of natural numbers is countable, of course, by definition &mdash each number maps to itself, and there’s our one-to-one correspondence. What about the set of even natural numbers? Our intuition certainly tells us that there are fewer of those &mdash half as many, because all evens are also natural numbers, but half the natural numbers are not even. How well does our intuition serve us when we look at one-to-one correspondences?

We can define the function f(n) := 2n , for all natural numbers n . It’s pretty easy to see that f defines a one-to-one correspondence between the naturals and the evens: for every natural number n there’s a well defined and unique value of 2n , and that value is even for every even number k , there’s a well defined and unique natural number n such that 2n = k . So the set of even natural numbers is countable: its cardinal number is .

It’s also not hard to show a mapping from the naturals to the whole numbers (naturals and zero): f(n) := n - 1 , giving us the counter-intuitive concept that we can add an element (zero) to the set, and not increase the cardinal number. Such is the mystique of infinite sets. In fact, we can also easily map the whole numbers (and, therefore, the natural numbers) to the integers (positive and negative), with a simple alternation:

And there’s another apparent paradox: that we can, as it seems, halve or double the number of elements in our countably infinite set, and not change the cardinal number, the “size” of the set. It’s still .

This goes along with the popular notion that when you do arithmetic on “infinity”, you don’t change anything: infinity plus one equals infinity infinity times two equals infinity. In mathematics that’s not quite right, though, and next time we’ll look more at countable sets, uncountable sets, and infinite cardinal numbers.

## Countable and uncountable sets

This page is intended to serve as a reference for those who are being supervised on Monday and would like to tackle questions on Sheet 4 about countability over the weekend. A general remark: in order to understand this final part of the course it is essential to be clear about the definitions and basic results about injections, surjections and bijections.

1. A set X is said to have cardinality or size n if there is a bijection f:X--><1,2. n>. This does justice to our intuitive idea that it has size n if you can count its elements one after another and end up with the number n. If g is the inverse of f (and therefore a bijection from <1,2. n>to X) then you are counting g(1), then g(2), then g(3) and so on. The empty set is said to have cardinality zero.

2. A set is finite if it has cardinality n for some non-negative integer n.

3. A set is infinite if it is not finite.

### Proposition

N, the set of all natural numbers, is infinite.

### Proof

We must show that, for any n, there is no bijection f:N--><1,2. n>. Let us show more - that there is no surjection from <1,2. n>to N. Let g be any function from <1,2. n>to N. Then the sum g(1)+. +g(n) is bigger than g(k) for every k < n, so it does not belong to the image of g. Notice that this also proves (via left and right inverses) that there is no injection from N to <1,2. n>.

### Proposition

A set X is infinite if and only if there is an injection f from N (the set of all natural numbers) to X.

### Proof

This is a good example of a result that seems fairly obvious and therefore hard to prove properly. When in that situation, you should always go back to first principles - that is the definitions of finite and infinite. Then the proof becomes easy to find.

Suppose X is finite. Then there is a bijection f from X to <1,2. n>for some n. But then there cannot be an injection g from N to X, since then fg would be an injection from N to <1,2. n>, contradicting the previous proposition (or rather the stronger statement actually proved).

Conversely, suppose that X is infinite, and build an injection f:N-->X inductively as follows. Suppose you have decided on f(1),f(2). f(m) in such a way that they are all different. Then is not equal to X (or there would be a bijection between X and <1. m>which we are given that there isn't. So we can find another element of X and call it f(m+1). Continuing in this way we get our map f. [For the cognoscenti: I have used the axiom of countable choice, because I made a countably infinite number of decisions (one for each m) without saying how I did it.]

4. A set X is countable if it is finite or if there is a bijection f from X to N.

This is supposed to capture the idea that the elements of X can be arranged in a "list". (But be careful with this way of looking at it - the idea of a bijection is more precise.) If g:N-->X is a bijection, then the list would go g(1),g(2).

### A few useful facts (especially for examples sheet questions).

(A) The following statements about a set X are equivalent:

(ii) There is an injection f:X-->N

(iii) There is a surjection g:N-->X

I'll prove this in lectures. Notice that (ii) and (iii) follow immediately from (i). Also, (ii) and (iii) are easily seen to be equivalent if you use the fact that a function is an injection/surjection if and only if it has a left/right inverse.

(B) A union of countably many countable sets is countable. To be more precise, if A 1 , A 2 . are countable sets, then A 1 U A 2 U A 3 U. is countable.

This is very useful for showing that sets are countable. For example, to show that the rational numbers form a countable set, let A q be the set of all rational numbers that are equal to p/q for some integer p. Since A q is the union of the three obviously countable sets <0>, <1/q,2/q,3/q. >and <-1/q,-2/q. >, it is countable. Since Q is the union of the sets A 1 ,A 2 . , Q is also countable. (In lectures I shall prove this from first principles as well.)

This is proved by Cantor's famous diagonal argument. I shan't reproduce it here but it is very easy to find on the web. This is one of many expositions.

(D) The set of all subsets of N is uncountable.

This can also be proved by a diagonal argument. Given a sequence A 1 ,A 2 . of subsets of N, define a new set A by the condition that n belongs to A if and only if n does not belong to A n . This is enough to ensure, for every n, that A does not equal A n . Therefore A was not part of the sequence.

(E) If X is uncountable and f:X-->Y is an injection, then Y is uncountable.

This simple fact is often useful for showing that sets are uncountable. To prove it, note that if Y were countable, then there would be an injection g from Y to N (by the equivalent condition (ii) above) and then gf would be an injection from X to N, contradicting the uncountability of X (again by (ii) above).

Countable nouns (also called count nouns) are nouns that can be counted (apple, orange) and can be therefore be pluralized (apples, oranges). Uncountable nouns (also known as non-count or mass nouns) are amounts of something, which we cannot count (gunpowder, rice).

Examples of countable nouns: babies, cakes, dogs, fingers, gowns, huts, ideas, lies, owls, papers, pencils, suitcases

Examples of uncountable nouns: air, ash, barley, bread, butter, dirt, flour, money, fun, gas, grass, gunpowder, ice, ink, juice, luggage, music, news, oil, pepper, rice, sand, soil, steam, sugar, vapour, water, wheat, wine

So how do we know whether a noun is countable or uncountable?

The noun is countable:

if we can use the indefinite artice a/an before it.

if we can use the word many (not much), more, or most to describe it.

if we can express its quantity by using a number before it.

if it takes on singular as well as plural forms.

The noun is uncountable:

if a/an is not normally used in front of it.

• He is eating some rice. (Not: He is eating a rice.) Rice is an uncountable noun, so some (which can be used for both countable and uncountable nouns) is used with it.

if the word much can be correctly used before it.

if it is not possible for us to count it. However, we can make it countable by having a quantity for it.

• I have just bought two cartons or litres/liters of milk. (Not: I have just bought two milk.)

if it takes only a singular form.

• some ice (Not: some ices) / some ink (Not: some inks) / some soup (Not: some soups)

#### Examples:

• There are two hairs on the snooker table. (Countable noun)
You think my hair looks nice? (Uncountable noun)
• You can boil an egg. (Countable noun)
I like to eat egg. (Uncountable noun as it refers to egg in general, not one or two eggs.)
• Let's stop for a coffee on our way to the library. (Countable noun)
She thinks she drinks too much coffee. (Uncountable noun)
I have no previous experience of this type of work. (Uncountable noun)
• We bought a big fish and a roast chicken in the supermarket. (Countable noun)
We had some fish for lunch and chicken for dinner. (Uncountable noun)
• As the group was large, we decided not to clink glasses. (Countable noun)
His car windows are made of bulletproof glass. (Uncountable noun)
• I need to press my shirt with aniron before we go. (Countable noun)
The heavy chains are made of iron. (Uncountable noun)
• We could see the bright lights of the city from that hill. (Countable noun)
Light emitted by a star takes light-years to reach us. (Uncountable noun)
• I need to press my shirt with aniron before we go. (Countable noun)
The heavy chains are made of iron. (Uncountable noun)
• He never missed the cartoon section in the papers (newspapers) every day. (Countable noun)
She can fold paper into shapes that look like dinosaurs. (Uncountable noun)
• I was robbed twotimes in one week. (Countable noun)
It was a waste of precious time to watch him speak. (Uncountable noun)
• They consider her book a definitive work on penguins. (Countable noun)
We're going to have some renovation work done on the house. (Uncountable noun)

#### Examples:

Mail : letters, postcards, bills, packages, parcels, etc.

Not : I received a mail today.

Furniture : tables, chairs, beds, desks, cupboard

Not :The family bought a furniture yesterday.

Fruit : apples, oranges, bananas, mangoes and papaya

Not : We want to buy two (tropical)fruits today, some mangoes and a papaya.

Jewelry : rings, necklaces, earrings, bracelets, brooches

## Uncountable Noun Examples

Anything that cannot be counted is an uncountable noun. Even though uncountable nouns are not individual objects, they are always singular and one must always use singular verbs in conjunction with uncountable nouns. The following uncountable noun examples will help you to gain even more understanding of how countable and uncountable nouns differ from one another. Notice that singular verbs are always used with uncountable nouns.

1. There is no more water in the pond.
3. I need to find information about Pulitzer Prize winners.
4. You seem to have a high level of intelligence.
6. Let’s get rid of the garbage.

Uncountable nouns can be paired with words expressing plural concept. Using these words can make your writing more specific. Here are some examples of how to format interesting sentences with uncountable nouns.

Garbage – There are nine bags of garbage on the curb.

Water – Try to drink at least eight glasses of water each day.

Furniture – A couch is a piece of furniture.

Equipment – A backhoe is an expensive piece of equipment.

Cheese – Please bag ten slices of cheese for me.

## Countable and Uncountable Food

Learn useful English vocabulary words for countable and uncountable food and drink to improve your English.

### List of Countable and Uncountable Food

Countable Food

• Burger
• Sandwich
• Hot dog
• Cherry
• Apple
• Grape
• Orange
• Olive
• Watermelon
• Carrot
• Tomato
• Pea
• Vegetable
• Pancake
• Sausage
• Egg
• Potato
• Fries
• Candy

Uncountable Food

• Fruit
• Juice
• Meat
• Rice
• Cereal
• Milk
• Coffee
• Tea
• Flour
• Salt
• Soup
• Sugar
• Butter
• Cheese
• Honey
• Water
• Chocolate
• Jam
• Seafood
• Mustard  Pin Pin

### List of Countable Food with Examples

#### Burger

Do you want some ketchup with your burger? #### Sandwich

We went for a sandwich lunch at the local bar. #### Hot dog

He bought a hot dog and had it covered with all the fixings. #### Cherry

Each cake had a cherry on top. #### Apple

The apple never falls far from the tree. #### Grape

He put a grape into his mouth and swallowed it whole. #### Orange

He cut the orange into quarters. #### Olive

Have you eaten a kind of fruit called olive? #### Watermelon

The woman cut up the watermelon and shared it out among the four children. #### Carrot

We used a carrot for the snowman’s nose. #### Tomato

Tomato soup is my cup of tea. #### Pea

I felt like a pea on a drum. The salad was decorated with segments of orange. #### Vegetable

Vegetable prices fluctuate according to the season. #### Pancake

Do you want a sweet pancake or a savoury one? #### Sausage

She sliced off a piece of sausage. #### Egg

He poached an egg for breakfast. #### Potato

Potato chips are served for the children.  