--- title: "Diagonal set complement differs from rows" subject: "Theory of Computation" chapter: 1 key: "semester_3/theory_of_computation:diagonal-complement-different" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/diagonal-complement-different site: BCT Engineering --- # Diagonal set complement differs from rows Theory of Computation · Chapter 1: Introduction - Asked in: 2070 Chaitra - Video: [Cantor's diagonal argument & Power set Theorem | Discrete Mathematics](https://www.youtube.com/watch?v=5UOvYOZnF6Y) — Success Only - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/diagonal-complement-different - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1 ## Question Justify "The complement of diagonal set is different from each row set" with the help of the diagonalization principle. ## Short answer For any row R_i, look at element i: if i ∈ R_i then i ∉ D̄, else i ∈ D̄. Thus D̄ and R_i differ at position i, so D̄ ≠ R_i. Hence the complement of the diagonal set is not among the rows. ## Answer **Setting.** Let R_1, R_2, R_3, ... be a list of subsets of the natural numbers (the "rows"). Draw a table whose entry (i, j) is 1 if j ∈ R_i and 0 otherwise. ```text 1 2 3 4 ... R_1 [ 1 0 1 0 ] R_2 [ 0 0 1 1 ] R_3 [ 1 1 0 1 ] R_4 [ 0 1 0 0 ] ``` The **diagonal set** is D = { i : i ∈ R_i }, i.e. the indices i whose diagonal entry (i, i) is 1. Its **complement** is D̄ = { i : i ∉ R_i }, obtained by flipping every diagonal entry. **Diagonalization principle.** The complement of the diagonal set, D̄, differs from every row R_i. #### Justification Take any row R_i. Look at the single element i. - If i ∈ R_i, then i ∉ D̄ (by definition of D̄ it contains only those i with i ∉ R_i). - If i ∉ R_i, then i ∈ D̄. In both cases, i belongs to exactly one of R_i and D̄. So R_i and D̄ disagree on the element i, hence D̄ ≠ R_i. Since i was arbitrary, D̄ differs from R_1, R_2, R_3, ... — it differs from the i-th row in the i-th position. Therefore D̄ is not in the list at all. ∎ **Use.** If every subset of N were in such a list, D̄ would have to be one of the rows, which is impossible. So the set of all subsets of N (and the set of real numbers) is uncountable. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does the complement of the diagonal set, D-bar, contain? A. All i with i not in R_i B. All i with i in R_i C. All i that belong to every row D. All rows R_i that are empty Answer: A. D-bar flips each diagonal entry, so it collects i for which i ∉ R_i. (Key point: Diagonal set) 2. Why does D-bar differ from the row R_i? A. D-bar is always empty B. They differ on every element C. D-bar has more elements than R_i D. They disagree on the element i: i belongs to exactly one of them Answer: D. If i ∈ R_i then i ∉ D-bar, and if i ∉ R_i then i ∈ D-bar, so they differ at position i. (Key point: Core argument) 3. Why does this show D-bar is not in the list at all? A. i was arbitrary, so D-bar differs from every row R_1, R_2, R_3, ... B. It was checked only for R_1 C. Because D-bar is finite D. Because the list is finite Answer: A. The argument works for every i, so D-bar equals no row. (Key point: Generality) 4. What is the consequence of this principle? A. N is uncountable B. Every subset of N is finite C. The set of all subsets of N (and the reals) is uncountable D. The set of subsets of N is countable Answer: C. If all subsets were listed, D-bar would have to be a row, which is impossible. (Key point: Use) ## Related in Theory of Computation - [State the diagonalization principle](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adiagonalization-principle-state) — Theory of Computation, chapter 1 ## Related in other subjects - [Auxiliary winding construction differs from main winding](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machines%3Aaux-winding-construction-true-false) — Electrical Machines, chapter 7 - [Combined cycle advantages and working principle](https://www.bctengineer.com/question.md?key=semester_7%2Fpower_plant_equipment%3Acombined-advantages-working) — Power Plant Equipment, chapter 8, asked 2× - [EMOSFET principle, characteristics, ac model](https://www.bctengineer.com/question.md?key=semester_3%2Felectronics_devices_and_circuit%3Aemosfet-working-ac-equivalent) — Electronics Devices and Circuit, chapter 3 - [Working principle of analog spectrum analyzer](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aanalog-spectrum-analyzer) — Communication Systems, chapter 1