4 ms·

I'm always confused as to why people want to be able to do arithmetic with infinity. Infinity isn't a number. > countably infinite Countably infinite means yo

I'm always confused as to why people want to be able to do arithmetic with infinity. Infinity isn't a number. > countably infinite Countably infinite means you can count to any particular element of a set in finite time, even though there is no end to the pattern of elements in the set. You cannot count to infinity plus one in finite time.

Smaug123 2y ago
That's not the attitude which leads to inventing the negative numbers, for example! The ordinals are useful and it's very reasonable to call them "numbers"; and I'm told that the surreal numbers are useful, although I've never actually used them.
gnulinux 2y ago
Infinity is not a number but transfinite numbers [1] like omega [2] or aleph-null [3] are. They are just as number as 0, 1, -5, 6/7, pi, i, or quaternion numbers. What is a "number" is not well-defined, any mathematical algebraic object can be called a number with some justification. Mathematicians just don't do it anymore, they just call it "X Algebra" instead of "X Numbers" but there is no fundamental distinction. From this perspective, arithmetic with infinity is not only possible but also extremely useful for Programming Language Theory, e.g. for Dependent Type Theory. [1] https://en.wikipedia.org/wiki/Transfinite_number https://en.wikipedia.org/wiki/Transfinite_number [2] https://en.wikipedia.org/wiki/Ordinal_number#Ordinals_extend_the_natural_numbers https://en.wikipedia.org/wiki/Ordinal_number#Ordinals_extend... [3] https://en.wikipedia.org/wiki/Aleph_number#Aleph-null https://en.wikipedia.org/wiki/Aleph_number#Aleph-null
empath75 2y ago
A set is "countably infinite" if you can construct a one to one mapping from the set to the natural (counting) numbers. The natural numbers are of course countably infinite, but so are even numbers, prime numbers, fractions, algebraic numbers and lots of other kinds of numbers that people want to do arithmetic with. "Uncountably infinite" sets can't be put into a one to one correspondence with the naturals, no matter how you produce to produce such a mapping, it's always possible to produce a number in the set which wasn't part of it. Real numbers being the prototypical example of that, but the power set (the set of all the subsets) of the naturals is, also. People do arithmetic with all kinds of things that "aren't numbers". Math isn't restricted to working with numbers.
- xanderlewis 2y ago
  Just to be pedantic: you mean ‘one-to-one and onto’, otherwise you’re only capturing countability rather than being countably infinite.
xanderlewis 2y ago
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.

Smaug123 2y ago

That's not the attitude which leads to inventing the negative numbers, for example! The ordinals are useful and it's very reasonable to call them "numbers"; and I'm told that the surreal numbers are useful, although I've never actually used them.

gnulinux 2y ago

Infinity is not a number but transfinite numbers [1] like omega [2] or aleph-null [3] are. They are just as number as 0, 1, -5, 6/7, pi, i, or quaternion numbers. What is a "number" is not well-defined, any mathematical algebraic object can be called a number with some justification. Mathematicians just don't do it anymore, they just call it "X Algebra" instead of "X Numbers" but there is no fundamental distinction. From this perspective, arithmetic with infinity is not only possible but also extremely useful for Programming Language Theory, e.g. for Dependent Type Theory. [1] https://en.wikipedia.org/wiki/Transfinite_number https://en.wikipedia.org/wiki/Transfinite_number [2] https://en.wikipedia.org/wiki/Ordinal_number#Ordinals_extend_the_natural_numbers https://en.wikipedia.org/wiki/Ordinal_number#Ordinals_extend... [3] https://en.wikipedia.org/wiki/Aleph_number#Aleph-null https://en.wikipedia.org/wiki/Aleph_number#Aleph-null

empath75 2y ago

A set is "countably infinite" if you can construct a one to one mapping from the set to the natural (counting) numbers. The natural numbers are of course countably infinite, but so are even numbers, prime numbers, fractions, algebraic numbers and lots of other kinds of numbers that people want to do arithmetic with. "Uncountably infinite" sets can't be put into a one to one correspondence with the naturals, no matter how you produce to produce such a mapping, it's always possible to produce a number in the set which wasn't part of it. Real numbers being the prototypical example of that, but the power set (the set of all the subsets) of the naturals is, also. People do arithmetic with all kinds of things that "aren't numbers". Math isn't restricted to working with numbers.

xanderlewis 2y ago
Just to be pedantic: you mean ‘one-to-one and onto’, otherwise you’re only capturing countability rather than being countably infinite.

xanderlewis 2y ago

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.