Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Numbers Are Leaves

christo.sh

Post reply on HN
Print view View original

31–40 of 74 posts

Re: Numbers Are Leaves

#31

Post by sagebird »

A more compact and beautiful relation exists between integers and finite rooted trees exist, imo.

David W. Matula found a correspondence between trees and integers using prime factorization, and reported it in 1968 in SIAM: "A Natural Rooted Tree Enumeration by Prime Factorization", SIAM Rev. 10, 1968, p.273 [1]

Others have commented on it before, search the web for Matula Numbers

I independently found this relation when working on a bar code system that was topologically robust to deformation. I wrote a document that explained this relation here[2].

I created an interactive javascript notebook that draws related topological diagrams for numbers. [3]

[1] http://williamsharkey.com/matulaSIAM.png

[2] https://williamsharkey.com/integer-tree-isomorphism.pdf

[3] https://williamsharkey.com/MatulaExplorer/MatulaExplorer.htm...

Re: Numbers Are Leaves

#32

Post by photonthug »

A related rabbit hole that you can jump down in FoM is that Zermelo's ordinals and von Neumann ordinals cannot both be true at the same time. Wikipedia's intro to the topic [0] is a starting place, see also [1] which might be more in depth.

[0] https://en.m.wikipedia.org/wiki/Benacerraf%27s_identificatio... [1] https://plato.stanford.edu/entries/philosophy-mathematics/#W...

> If you don't know why set theory is important, it is because set theory is the foundation of all of mathematics.

Nitpick maybe but the types and categories people might prefer sets as "a" foundation instead of "the"? These 3 things are the most useful, get the most attention, and have benefited from the most serious efforts. But IMHO one of the cool things about math is that if you're willing to squint and work at it, then many alternative foundations are possible. For example Conway's surreals[2] hint that you can get numbers/sets by starting with even games as a primitive. I can't quickly find refs, but the visualizations here hint that starting with graph theoretic axioms can lead to sets instead of vice-versa and I think people have worked on that too. Who knows whether alien math builds everything else up starting from geometry or probability, etc.

[2] https://en.wikipedia.org/wiki/Surreal_number

Re: Numbers Are Leaves

#33

Post by Chinjut »

epgui wrote: post #22

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?…

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...)

Re: Numbers Are Leaves

#34

Post by sagebird »

sagebird wrote: post #31

A more compact and beautiful relation exists between integers and finite rooted trees exist, imo. David W. Matula found a correspondence between trees and integers using prime factorization, and reported it in 1968 in SIAM: "A Natural Rooted Tree Enumeration by Prime Factorization", SIAM Rev. 10, 1968, p.273 [1] Others have commented on it before, search the web for Matula Numbers I independently found this relation…

Sorry - I believe I am off topic as this is not relevant given:

"This indirectly enforces the idea that sets cannot have duplicate elements, as set membership is defined purely by the presence or absence of elements. For example:"

So there is a constraint on what sort of trees are allowed in this -forrest- which would preclude most finite rooted trees.

Re: Numbers Are Leaves

#35

Post by sproutini »

> If you don't know why set theory is important, it is because set theory is the foundation of all of mathematics.

Sorry to burst your bubble, but as far as we know, that isn't true in the slightest. It's a logical positivist view abandoned after Goedel and Turing.

At best: What we hope is true is that there often is some axiomatic system where a specific mathematical lemma makes sense when redefined into something similar but not the same.

Re: Numbers Are Leaves

#36

Post by d-lisp »

epgui wrote: post #22

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?…

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 ?

Re: Numbers Are Leaves

#37

Post by bubblyworld »

nthingtohide wrote: post #16

I think people will like the following tangent. https://en.m.wikipedia.org/wiki/Benacerraf%27s_identificatio... In the philosophy of mathematics, Benacerraf's identification problem is a philosophical argument developed by Paul Benacerraf against set-theoretic Platonism and published in 1965 in an article entitled "What Numbers Could Not Be". Historically, the work became a significant catalyst in motivating the deve…

Thanks, that was an interesting rabbit hole. Although I can't help but feel there's a philosophical map/territory confusion here. Like, sure, numbers can't possibly just "be" sets because there are many different models of the naturals in (ZF) set theory, even in higher order logics. But I feel like a Platonist would just counter that of course this is the case - we are simply modelling the properties of the "true" naturals with these sets, in the same way that differential equations can model the behaviour of fluids without "being" water. Nobody writes down Navier-Stokes and expects to get wet!

Re: Numbers Are Leaves

#38

Post by openquery »

d-lisp wrote: post #36
epgui wrote: post #22

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?…

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 Kurato…

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

Re: Numbers Are Leaves

#40

Post by epgui »

d-lisp wrote: post #36
epgui wrote: post #22

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?…

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 Kurato…

For Von Neuman:

    1 = Ø U {Ø} = {Ø}

    2 = 1 U {1} = {Ø,{Ø}}
Post reply on HN