Finite, Infinite, Countable and Uncountable Sets: Definitions, Worked Examples and Exam Traps

Learn to classify sets by cardinality and one-to-one correspondence. Follow worked examples for rational enumeration, Cantor's diagonal method and common exam statements.

KnowledgeGate Team

Exam prep & CS education

Updated 20 Nov 20265 min read
Finite, Infinite, Countable and Uncountable Sets: Definitions, Worked Examples and Exam Traps

The usual confusion is simple: every finite set is countable, some infinite sets are also countable, and only some infinite sets are uncountable. A set that looks large or has tightly packed values is not necessarily uncountable. The reliable method is to examine cardinality and ask whether a one-to-one correspondence can be built. Finite, infinite, countable and uncountable sets are distinguished by cardinality and one-to-one correspondence.

Finite and infinite sets: start with cardinality

The cardinality of a set is the number of distinct elements it contains. A set is finite when its cardinality is a non-negative integer. This includes the empty set, with |{}|=0. A set is infinite when no finite integer gives its cardinality.

Consider the image of a bounded integer domain under squaring:

A = {n^2 : n in Z and -2 <= n <= 3}.

The six allowed inputs -2, -1, 0, 1, 2 and 3 produce 4, 1, 0, 1, 4 and 9. After duplicate outputs are removed,

A = {0, 1, 4, 9}.

Thus |A| = 4, so A is finite. In contrast, N = {1, 2, 3,...} is infinite because another natural number follows every listed value.

Two traps appear even at this stage. Repetition does not increase cardinality, so {1,1,2,2,3}={1,2,3} and its cardinality is 3. An ellipsis does not prove infinity either: {1,2,3,...,100} ends and is finite.

What countable really means

Using the inclusive convention, a set is countable if it is finite or countably infinite. A countably infinite, or denumerable, set can be placed in a bijection with N. A bijection pairs every element exactly once, with no omission and no repetition.

Let B={3,6,9,...}. Define f:N -> B by f(n)=3n. The first pairings are

1 -> 3, 2 -> 6, 3 -> 9, 4 -> 12, 5 -> 15.

Every natural number produces one member of B, and each b in B returns to exactly one natural number through f^{-1}(b)=b/3. The map is one-to-one and onto. Therefore, B is infinite but countable.

Now take D={1/n:n in N}={1,1/2,1/3,...}. The map n -> 1/n is again a bijection from N to D. The values approach 0, but that does not create uncountably many elements. Spacing, numerical size and the presence of a limit point do not determine cardinality.

Why the rational numbers are still countable

Between any two distinct rational numbers there is another rational number, yet Q is countable. There is no contradiction. Density describes what lies between two values, while cardinality describes whether all values can be enumerated.

For the positive rationals, place every fraction p/q in a numerator-denominator grid and move along diagonals with constant p+q. Keep only the first occurrence of each value. The enumeration begins

1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1,...

The entry 2/2 is crossed out because it equals 1/1. Similarly, 2/4 repeats 1/2, 3/3 repeats 1/1, and 4/2 repeats 2/1. Skipping such duplicates gives every positive rational exactly once. We can then place 0 first and interleave each positive rational with its negative. That accounts for all of Q, so Q is countably infinite.

Diagonal p/q grid numbers each positive rational once and crosses out 2/2, 2/4, 3/3 and 4/2 duplicates.

Why a real interval is uncountable: Cantor's diagonal argument

Assume, for contradiction, that every real number in (0,1) has been listed as r_1,r_2,r_3,.... These first five sample rows illustrate the alleged infinite list:

r_1=0.12345...; r_2=0.50123...; r_3=0.77777...; r_4=0.31415...; r_5=0.90909...

Construct x=0.d_1d_2d_3... by choosing d_n=2 when the nth digit of r_n is 1, and d_n=1 otherwise. The displayed diagonal digits are 1,0,7,1,9, so the rule produces the prefix x=0.21121....

The number x differs from r_1 at digit 1, from r_2 at digit 2, and generally from r_n at digit n. It cannot be any entry in the alleged complete list. Since the construction uses only 1 and 2, it also avoids the ambiguity created by decimal representations with trailing 9s. The assumption fails, so (0,1), and therefore R, is uncountable. This does not mean every set written with infinite decimals is uncountable. The proof works because it defeats every proposed enumeration.

Table of rows r1 to r5 with diagonal digits 1, 0, 7, 1, 9 highlighted and the constructed number x = 0.21121 differing from each row.

Cardinality comparisons that exams turn into statements

The main classifications are finite and countable, countably infinite, and uncountable.

Set

Classification

Size

{}

Finite and countable

0

{2,4,6,8}

Finite and countable

4

N,Z,Q

Countably infinite

aleph_0

(0,1),R, irrational numbers

Uncountable

Greater than aleph_0

The irrational numbers need a reason, not just a label. If they were countable, their union with the countable rationals would make R countable. That contradicts the diagonal argument, so the irrational numbers are uncountable.

Power sets create another important comparison. For H = {red, blue},

P(H) = {{}, {red}, {blue}, {red, blue}}.

The four subsets give |P(H)| = 2^2 = 4, compared with |H| = 2. Cantor's general result says that a power set has strictly greater cardinality than its original set. In particular, P(N) is uncountable. Set Theory and Relations Explained owns set operations, Cartesian products, closures and posets; the present discussion stays with cardinality, enumeration and Cantor's theorem.

How exam questions test the distinction

The distinction arrives in one of three question shapes.

Direct classification: Let S={n in N:n^2 <= 50}. Since 7^2=49 <= 50 but 8^2=64>50,

S={1,2,3,4,5,6,7}.

Thus |S|=7, so S is finite and therefore countable.

Judge a statement: "Every infinite set is uncountable" is false because N is an infinite countable counterexample. "Every subset of a countable set is countable" is true. "Every dense subset of R is uncountable" is false because Q is both dense and countable.

Interval or sequence: The set {1/n:n in N} is countably infinite because n -> 1/n is a bijection. The interval (0,1) is uncountable because the diagonal construction produces a real number missing from any proposed list. Practise these distinctions with Set Theory and Relations MCQs, and always state the reason along with the label.

Exam traps, the short version, and what to do next

Trap

Fix

Infinite means uncountable

Try to build a bijection with N.

Dense means uncountable

Test enumerability separately.

Values approach 0, so there must be uncountably many

Look for an integer index.

A proper subset must be smaller

For infinite sets, test for a bijection, as with N and the positive even numbers.

Use a three-question check. Can all elements be listed and the list ends? The set is finite. Can the elements be paired one-to-one with N? It is countably infinite. Can every attempted list be shown incomplete, as in the diagonal construction? It is uncountable.

Use the GATE CS Exam Preparation Courses and Test Series category to place this topic in the wider syllabus. GATE Guidance by Sanchit Sir supplies the subject sequence, while GATE Test Series provides timed mixed practice after you can justify each classification.