---
title: "State the diagonalization principle"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:diagonalization-principle-state"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/diagonalization-principle-state
site: BCT Engineering
---

# State the diagonalization principle

Theory of Computation · Chapter 1: Introduction

- Asked in: 2074 Asoj
- Video: [Theory of Computation - Diagonalization principle](https://www.youtube.com/watch?v=vIeqJ05YAfc) — Silla Learning
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/diagonalization-principle-state
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

State the diagonalization principle.

## Short answer

Let R be a binary relation on A. Diagonal set D = {a∈A | (a,a)∉R}, row R_a = {b | (a,b)∈R}. Then a∈D iff a∉R_a, so D differs from every R_a. This shows D cannot appear as a row, proving the set of all subsets of A is not in bijection with A.

## Answer

**Statement (Lewis & Papadimitriou).** Let R be a binary relation on a set A, that is R ⊆ A × A. Let the **diagonal set** be

D = { a ∈ A : (a, a) ∉ R }

and for each a ∈ A let R_a = { b ∈ A : (a, b) ∈ R } be the "row" of a. Then D is different from every row R_a.

**Reason.** For any a, a ∈ D iff (a, a) ∉ R iff a ∉ R_a. So D and R_a disagree on the element a, hence D ≠ R_a.

```text
        a1  a2  a3  a4
 a1  [  1   0   1   0 ]   diagonal 1, 0, 0, 1 flipped:
 a2  [  0   0   1   1 ]   D = {a1: 0, a2: 1, a3: 1, a4: 0}
 a3  [  1   1   0   1 ]     = {a2, a3}
 a4  [  0   1   0   1 ]   differs from row i at column i
```

**Consequence.** Taking A = N shows that the set of all subsets of N, 2^N, cannot be put in one-to-one correspondence with N, so it is uncountable. The same idea proves that the real numbers are uncountable and that there are languages that are not recursively enumerable.

## Check yourself

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

1. In the statement, how is the diagonal set D defined for relation R on A?
   A. D = A × A minus R
   B. D = {(a, b) : a ≠ b}
   C. D = {a in A : (a, a) not in R}
   D. D = {a in A : (a, a) in R}
   Answer: C. D collects those a for which (a, a) is not in R, i.e. a is not in its own row. (Key point: Definition of D)

2. What does the principle conclude?
   A. D differs from every row R_a
   B. D is a subset of every row
   C. D equals some row R_a
   D. D is empty
   Answer: A. D and R_a disagree on the element a, so D ≠ R_a for every a. (Key point: Conclusion)

3. Why does D differ from R_a?
   A. D has more elements than R_a
   B. The rows are finite
   C. a is in D iff a is not in R_a, so they disagree on a
   D. D and R_a are disjoint
   Answer: C. a ∈ D iff (a,a) ∉ R iff a ∉ R_a. (Key point: Reason)

4. What famous result follows with A = N?
   A. 2^N is countably infinite
   B. N is uncountable
   C. Q is uncountable
   D. 2^N cannot be put in one-to-one correspondence with N, so it is uncountable
   Answer: D. Any list of subsets of N misses D, so the power set of N is uncountable. (Key point: Consequence)

## Related in Theory of Computation

- [Diagonal set complement differs from rows](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adiagonal-complement-different) — Theory of Computation, chapter 1