Ordinals And Cardinals

From WhyNumberingShouldStartAtZero:

I consider this numbering issue of starting with 0 versus 1 very irritating. For me both are quite valid choices depending on a very simple distinction: Is the variable in question ordinal or cardinal?

Cardinals start with 0 (cardinals measure the size of a set and a set can be empty) whearas
Ordinals start with 1 (the first in a sequence is the 1st). Minor nitpick. Mathematically, ordinals start with 0.

For me this leads to the usual holy wars because this distinction of type is never reflected in any programming language. There invariably is only one type of number called num, int, integer or whatever. I want ord and card instead and appropriate typing rules for arithmetic expressions like

card+card -> card
card-card -> card
ord+card -> ord
ord-card -> ord
card+ord -> ord
card-ord forbidden
ord+ord forbidden
ord-ord -> card

Why hasn't come up anybody with this? At least I think that this would be a good idea. Do you agree? -- GunnarZarncke

Sort of. I would like to see better support for units in general, but I'm leary of ordinals that don't allow you to add them together. (Which is perfectly fine in mathematics).

Except mathematics has the same problem as programming by not making this distinction really.

[Minor nitpick. Mathematically, ordinals start with 0.] Mathematically there are no ordinals but only Nat which is used a as an index (and I have rather often seen indizes start at 1 then 0) and there seems to be no agreement in math whether Nat contains 0 or not. So this is not a minor nitpick but the same critique really.

Mathematical ordinals are equivalence classes of well-ordered sets. As such there is definitely a 0 ordinal, the only possible ordering of the empty set. Natural numbers are another story; while I prefer to have natural numbers start with 0 (Addition on natural numbers forms a monoid [corrected from group as only 0 has an inverse.], and it gives a trivial relationship between the natural numbers, the finite cardinals, and the finite ordinals), there is certainly no agreement as to whether or not 0 is one of them.

As for adding ordinals, if you can give a good reason what the meaning is of adding ordinals (I assume the result is again an ordinal) then I am happy to allow it. But as it is now I think this typing would catch quite a lot programming errors. -- .gz

The basic idea is that you lay them end-on-end, like some programming languages define "addition" on strings.

Mathematical ordinals are Naturals plus extensions for transfinite sets... but you're right about the disagreement. I'd note that it is the 'number theorists' that are most likely to exclude 0 from Nat... and the most likely to have a good reason.

I, however, am a language theorist, and prefer the use of the linguistic ordinal. The meaning of 'first plus third' seems most naturally to describe a set of two objects rather than an ordinal or cardinal. Anyhow, I wouldn't agree with GZs typing rules. For Mathematical ordinals, one can define addition, multiplication, and exponentiation... but the explanation for these in the wikipedia is too thick for me to understand without some example problems (they involve conceptual set arithmetic just to perform the operation). For Mathematical ordinals, subtraction and division cannot be defined. For linguistic ordinals, all arithmetic operations are undefined.

I'd consider the use of 'ordinal distance' or something similar for the more traditional understanding of addition and subtraction to ordinals. 'third X after the first X' means 'fourth X', and 'third X before the fourth X' is 'first X'. The descriptor of distance (before/after) is quite important to making sense of the operation. I'd also be tempted to separate cardinals into their various conceptual (linguistic) sorts: quantities/amounts, deficits (or differences in amount or quantity_diff_t or offset), sizes of various dimensionality (lengths, volumes, etc. note that 'counts' could be used for 'quantity').

With regards to the 'numbering starting at zero': for quantities and deficits, zero makes sense. For offsets, for sizes, zero makes sense. However, for spatial indices or identifiers, zero does not make a great deal of sense... people talk of the first item in the list, not the 'zeroth'.

[I agree with this, it elaborates on my idea. I disagree with the specification of the cardinals because quantities/amounts are not a problem as we are talking about countable ordinals and not dimensions like volume (which are handled by units attached to reals really). Differences/deficits are an interesting idea though. 'third X before the fourth X' Doesn't sound like subtraction. -- .gz]

Counts of items in sets aren't so fundamentally different from counts of volumes, counts of spans, counts of apples in a barrel, counts of whatever else you might name. Cardinality is a measure.

I read up on the mathematical definitions (I should have known that math has something more solid to say on this matter) and came to the conclusion that I meant the linguistic meaning. I agree that this makes matter difficult as programming languages sits somewhere in the middle. Maybe we'd need card/old and Card/Ord (the latter two being the mathematical types).

I agree that counts have lots in common with measures but that's not the point. Most measures are uncountable and have a unit. And anyway you have me on your side if you want to introduce units in programming like in FrinkLanguage. -- .gz

It has been done in C++ using template wrappers around numbers (quantity<(Type indicating Unit),double> x), which can prevent accidental assignment to the wrong variable or of a bad calculation. I've also developed it with semantic types (distance:Measure, mass:Measure, etc.) and context-sensitive syntax (so '3`m' might be 3 meters (distance:3) in one context or 3 minutes (time:180) in another, easily allowing users also to add their own units without causing communications problems across modules. It's definitely a nice thing to have in order to avoid safety issues.

I agree that units have their own benefits - it avoids comparing apples with oranges. But the bugs prevented by ord versus card are another thing - more like FencePostError/OffByOne (using width/length as an index).

Ord/Card will NOT prevent the errors you mention. FencePostError and OffByOne errors can occur if you use any range of integers as indices whether it be 1..N, 0..N-1, M..M+N-1, etc. It will happen a lot when dealing with subranges of numbers, too. It is unlikely to happen with sparse ranges because the programmer is more likely to use a fundamentally better approach of iteration than calculating the indices. That is the common character of FencePostErrors? and OffByOne errors - they are errors in calculating indices for iteration. Better is to use searches and implicitly available indices to determine ranges. It is quite easy to build a language that can recognize FencePostErrors? at compile time (the required information is always available statically), but programmers should never need to calculate indices for anything (unless designing the searches or structures, of course).

ModulaTwo had distinct INTEGER and CARDINAL types.

That's different. Those are just signed vs. unsigned types, similar to most Algol-like languages. What Pascal and Modula did have were arrays which were indexed by an ordinal type, having arbitrary start indices:

 Type  
   RealArray = Array [1..100] of Real;