Hacker News Reader

Comment by epgui | Hacker News Reader

Setting aside the rest of the article, there is one thing I've never really understood the motivation for, and I think this article really highlights it well.

> "Well congratulations this works! We can represent numbers using singleton sets (sets with one element). However, it would be nice if our sets had some more structure. Specifically we would like the set corresponding to the number n to have n elements."

Why? What's the motivation here?

It seems to me like `next(x) = {x}` is simpler than `next(x) = x ∪ {x}`, and I'm not totally clear on what the extra complexity buys us.

I am of course familiar with the structure `next(x) = x ∪ {x}`, having seen it in textbooks and in a set theory / mathematical foundations class, but I feel like I've never really understood what insight this structure captured. It seems like it's always presented matter-of-factly.

Anyone?

View on HN

Encoding n as the set of all m < n is called "von Neumann ordinals". Encoding (positive) n as just the singleton set containing n's immediate predecessor is called "Zermelo ordinals". The main advantage of using the former representation rather than the latter is that it allows uniformly encoding not just finite ordinals, but also transfinite ordinals, many of which do not have an immediate predecessor. E.g., in the von Neumann ordinal system, the infinite set of all finite ordinals may itself be interpreted as an ordinal value larger than every finite one. (And then the set of finite ordinals ∪ {the set of finite ordinals} becomes yet a larger transfinite ordinal still, and so on...)

Look up ‘transitive sets’ if you haven’t heard of them already.

The primary answer to your question is that in the von Neumann definition the ordinals are transitive and well ordered by the epsilon (membership) relation, which is a pair of stipulations that can then be used as a definition of the ordinals if you like. This in turn is nice for many other reasons!

Also, you can make convenient definitions like defining the supremum of a set of ordinals to be the union of that set. The union of two of your ordinals usually won’t be an ordinal.

In general, it’s nice to have an ordinal simply be the set of its predecessors, which is something that this definition implies.

Thanks for the pointers!

Not a professional mathematician, but you have the benefit of set operations mapping to functions you're familiar with.

For example, set union becomes the max function.

That one is neat, but how do you define addition and multiplication on these structures?

You use (transfinite, if your ordinals are large enough) recursion! Just define a + 1 to be the successor of a — succ(a) — and then, assuming we’ve defined a + b, define

a + (b + 1) := (a + b) + 1 = succ(a + b)

(it’s only slightly more complicated for infinite ordinals)

You can do a similar thing for multiplication, and exponents, and so on.

Technically, you have to use induction to prove that this definition indeed works to define the operations for all ordinals.

It always felt arbitrary to me :

    next(x)={x} would give 

    1={0}
    2={{0}}
    3={{{0}}}

    Kuratowski's encoding gives :
    0=Ø=()
    1={Ø}=(0)
    2={Ø,{Ø}}=(0,1)
    3={Ø,{Ø},{Ø,{Ø}}}=(0,1,2)
    
    The cardinal of N is n and
    every element in N are the predecessors of n.

    Von Neuman's encoding gives :
    0=Ø
    1=0U{0}={Ø,{Ø}}
    2=1U{1}={Ø,{Ø},{Ø,{Ø}}}
   
    Now the cardinal of N is n+1, and n is the maximum
    of the set N defining n.

    Both Von Neuman's and Kuratowski's encoding allows us to define ordered tuples, but I cannot understand how to write the tuples for Von Neuman's in the context of natural numbers.

2 is {Ø,{Ø},{Ø,{Ø}}} with Von Neuman's we can recognize 0 and 1 as the first and second element of the tuple : what is the third one ?

2 = {0, 1} = {Ø,{Ø}} by the Von Neumann ordinal definition.

For Von Neuman:

    1 = Ø U {Ø} = {Ø}

    2 = 1 U {1} = {Ø,{Ø}}

True, then it doesn't differ from Kuratowski's encoding or am I missing something ?

Representing the natural number n by a set of size n turns out to be rather useful. And the obvious choice for a set of n elements is the representations of the n natural numbers 0..n-1.

I think I can see why... But the obvious question to me becomes:

- What do the operations of addition and multiplication look like with this structure? Doesn't this seem a bit complex?

I think it's (like so many things) a question of tradeoffs. Programmers often think of complexity (and hence performance) of operations, but that is not important to a mathematician.

The fundamental operation, the successor function, does not look much different, S(n) = n ∪ {n} vs S(n) = {n}. Mathematics usually defines addition in terms of this function, so that n + m = 1 + (n-1) + m and 0 + m = m. This can be done via induction and works equally well, regardless of which "implementation" we choose. Similarly, multiplication is repeated addition. Seen in this way, both "implementations" of natural numbers leads to horribly inefficient, but ultimately very similar, addition and multiplication operations.

However, the representation S(n) = n ∪ {n} leads to a very simple definition of "a finite set of size n". It is simply a set, which has a bijection between it and n. This, in turn, leads to a much easier arithmetic. Instead of manipulating a specific set representing a given number, we can say that any set of size n can represent the number n. Then addition simply becomes disjoint union, and multiplication becomes Cartesian product, from which things like associativity and commutativity can be proven much easier than in the inductive definition.

Reply on news.ycombinator.com