Uncountability obstruction to enumerating infinite Cartesian products
ID: uncountability-obstruction-to-enumerating-infinite-cartesian-products
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 . Define a sequence by . It is a valid binary sequence but differs from the -th output at coordinate , 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.
New to topics? Read the docs here!