---
title: "Countably infinite and uncountable sets"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:countable-uncountable-sets"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/countable-uncountable-sets
site: BCT Engineering
---

# Countably infinite and uncountable sets

Theory of Computation · Chapter 1: Introduction

- Asked in: 2071 Chaitra
- Video: [Introduction to Countability (Countable and Uncountable Sets) | TOC | Automata Theory](https://www.youtube.com/watch?v=kHvtbvikP5Q) — THE GATEHUB
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/countable-uncountable-sets
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

Define countably infinite and uncountable sets with example.

## Short answer

A set is countably infinite if it can be put in one-to-one correspondence with the natural numbers, like the even naturals or integers. An uncountable set, such as the real numbers in [0,1] or the power set of N, cannot be listed in such a way; diagonalization proves 2^N is uncountable.

## Answer

#### Countably infinite set
A set S is **countably infinite** if there is a one-to-one correspondence (bijection) between S and the set of natural numbers N = {0, 1, 2, ...}. Equivalently, its elements can be listed in an infinite sequence s₀, s₁, s₂, ... in which every element appears. A set is **countable** if it is finite or countably infinite.

**Examples**
- The even natural numbers: f(n) = 2n.
- The integers Z: list 0, 1, −1, 2, −2, 3, −3, ... (f(n) = (n+1)/2 for odd n, −n/2 for even n).
- N × N and the rationals Q (listed by dovetailing along diagonals).
- Σ*, the set of all strings over a finite alphabet: list by length, then alphabetically.

#### Uncountable set
An infinite set that is **not** countable, i.e. no bijection with N exists, is **uncountable**.

**Examples:** the set of real numbers in [0, 1], and the power set 2^N of the natural numbers.

**Proof for 2^N (diagonalization).** Suppose all subsets of N were listed as S₀, S₁, S₂, ... Define D = { i : i ∉ Sᵢ }. For each i, D and Sᵢ differ on the element i, so D is different from every Sᵢ. But D is a subset of N, so it should be in the list, a contradiction. Hence 2^N is uncountable.

**Importance.** The set of all programs (strings) is countable, but the set of all languages over Σ (subsets of Σ*) is uncountable. So some languages have no Turing machine at all.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. When is an infinite set S countably infinite?
   A. It contains N as a proper subset
   B. It has a largest element
   C. There is a bijection between S and N
   D. It is a subset of the reals
   Answer: C. Countably infinite means elements can be matched one-to-one with the natural numbers. (Key point: Countably infinite)

2. Which of these is countably infinite?
   A. The set of all languages over Σ
   B. The real numbers in [0, 1]
   C. The integers Z, listed as 0, 1, −1, 2, −2, ...
   D. The power set 2^N
   Answer: C. Z can be listed in a sequence. The others are uncountable. (Key point: Example)

3. How is 2^N shown uncountable?
   A. Dovetail along diagonals i + j
   B. Define D = {i : i not in S_i}; D differs from every S_i
   C. Show an injection into N
   D. List all subsets by length then alphabetically
   Answer: B. Diagonalization builds a subset D missing from any proposed list. (Key point: Uncountability proof)

4. What does this imply about languages and Turing machines?
   A. Programs are countable but languages are uncountable, so some languages have no TM
   B. Languages are countable, so TMs are uncountable
   C. Only finite languages lack a TM
   D. Every language has a Turing machine
   Answer: A. There are countably many strings (programs) but uncountably many languages. (Key point: Importance)