3 ms·

Countably infinite doesn’t mean you can count to any particular element in finite time; such a definition would depend on an ordering which cardinality (and, in

Countably infinite doesn’t mean you can count to any particular element in finite time; such a definition would depend on an ordering which cardinality (and, in particular, countability) shouldn’t. For example, uncountable sets can exhibit the property you mention: you count to x via the (very) finite sequence {x} for any element x of the set of real numbers. Conversely, countable sets (even if you restrict such enumerations to a certain ordering) don’t in general have this property: ordering the integers by [x < y iff x < y (mod 2) or x < y if x = y (mod 2)] (that is, taking two isomorphic copies of the integers, identified with the even and odd integers respectively, juxtaposed side by side), the sequence {0,2,4,6, …} fails to arrive at 1 no matter how far you count along. So there’s an element we can’t count to in ‘finite time’. The property you seem to be alluding to, that ‘the set admits a total order such that every element can be reached in finitely many steps starting at the first element’ actually corresponds to the order type of the natural numbers — often called ω. It’s countable, but there are many, many (in fact, uncountably many) more sets with this cardinality that don’t have that property. The proper definition of ‘countably infinite’ is simply that the set can be placed in bijection with the natural numbers. This has nothing (directly) to do with ordering.

LegionMammal978 2y ago
> The proper definition of ‘countably infinite’ is simply that the set can be placed in bijection with the natural numbers. This has nothing (directly) to do with ordering. Does it not imply that there exists an ordering which reaches each value in finite time? That's how I'd straightforwardly read GP's comment. A given countable set under its 'natural' ordering might not have order type ω, but there will always exist some alternative ordering with type ω. (And indeed, the existence of such an ordering implies that the set is countable.)
- xanderlewis 2y ago
  Yes. You're correct. I realised this some time after writing my comment. So it actually does work as a definition, if you phrase it properly. I guess it's just equivalent to the observation that ω has the property that every initial segment (i.e. every subset of the form {0, 1, ..., n}) is finite. So you could say: a set S is countable if it admits an ordering that makes it 'covered by all finite initial segments'. ...but this boils down to saying the set admits an ordering that makes it isomorphic to some n, or ω... which just means it's countable in the usual sense.

LegionMammal978 2y ago

> The proper definition of ‘countably infinite’ is simply that the set can be placed in bijection with the natural numbers. This has nothing (directly) to do with ordering. Does it not imply that there exists an ordering which reaches each value in finite time? That's how I'd straightforwardly read GP's comment. A given countable set under its 'natural' ordering might not have order type ω, but there will always exist some alternative ordering with type ω. (And indeed, the existence of such an ordering implies that the set is countable.)

xanderlewis 2y ago
Yes. You're correct. I realised this some time after writing my comment. So it actually does work as a definition, if you phrase it properly. I guess it's just equivalent to the observation that ω has the property that every initial segment (i.e. every subset of the form {0, 1, ..., n}) is finite. So you could say: a set S is countable if it admits an ordering that makes it 'covered by all finite initial segments'. ...but this boils down to saying the set admits an ordering that makes it isomorphic to some n, or ω... which just means it's countable in the usual sense.