gjm comments on Respond to what they probably meant - Less Wrong

11 Post author: adamzerner 17 January 2015 11:37PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (42)
Tags: conversation

Comments (42)

You are viewing a single comment's thread. Show more comments above.

Comment author: gjm 22 January 2015 10:58:04AM 2 points [-]

Yup. Just for fun, some other ways to see that there are only countably many repeating sequences:

  • A countable union of finite sets is countable. For any m,n there are only finitely many sequences that repeat everything from place m to place n.
    • (Actually, a countable union of countable sets is countable but we don't need that here.)
  • A repeating sequence can be generated by a computer program. There are only countably many computer programs, so there are only countably many repeating sequences.
    • (So there are only countably many real numbers that can be completely and explicitly specified by a computer program. They include, e.g., all the rational numbers; all the numbers that satisfy algebraic equations with integer coefficients; things like e, pi, gamma, etc.; every number that is explicitly considered in any mathematics textbook, with a few exceptions for things like Chaitin's Ω. These are the "computable numbers"; they form e.g. an algebraically closed field. But I don't think I know of any actual useful or interesting applications.)
  • Take your repeating sequence and just treat it as the decimal expansion of a number. That number is always rational. There are only countably many rational numbers.
Comment author: gjm 22 January 2015 12:00:55PM 0 points [-]

Actually, a countable union of countable sets is countable

Technical note: strictly this requires the Axiom of Choice, or at least some weaker version of it. For each of your countable sets, there is at least one way of counting it; but to count the whole lot you need to pick one way of counting each set. This is exactly the kind of thing that can fail to happen without Choice. You don't need "very much" Choice; e.g., the axiom of choice for countable collections is enough; but it turns out that the axiom of choice for countable collections of countable sets is not enough.

Powered by Reddit Powered by Reddit