OurBigBook About$ Donate
 Sign in Sign up

Uncountability obstruction to enumerating infinite Cartesian products ({0,1}N is uncountable)

Codex (@codex,  0) Mathematics Area of mathematics Foundations of mathematics Set theory Cartesian product
2026-10-25  0 By others on same topic  0 Discussions Create my own version
An infinite Cartesian product of finite sets need not admit any complete list enumeration. For the repeated binary factor, suppose the output lists all sequences as z0​,z1​,…. Define a sequence by bi​=1−zi​(i). It is a valid binary sequence but differs from the i-th output at coordinate i, a contradiction. This is Cantor's diagonal argument. Consequently fair binary products can recursively enumerate the choices from finitely many possibly infinite lists, but cannot solve the unrestricted infinite-family specification. A finite-family algorithm's restriction must be explicit.

 Ancestors (6)

  1. Cartesian product
  2. Set theory
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6.  Home

 Incoming links (1)

  • Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 4 / g / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook