Numbers Are Leaves(christo.sh)
christo.sh
Numbers Are Leaves
https://www.christo.sh/numbers-are-leaves/
73 comments
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...
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...
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.
"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.
Despite several negative comments, I thought the author did a great job of explaining and playing with set theory (which, as can be seen by the response, is good fun.)
I do take some issue with intepreting set theory's membership relation in terms of the tree child relation, though.
First, the child relation is presumably transitive, whilst set membership is not. (The subset relation is transitive. Presumably it is 'direct child' relation we have in mind here.)
Second, as seen in the third diagram, nodes don't map well to set entities, because the same entity can be a member of distinct sets, but these would count as distinct nodes on some trees. E.g., in the diagram both leaf nodes are distinct, but they both represent the empty set, and hence should be identical. So the identity of sets is not preserved in the tree encoding.
But this is picky — a lovely read. Thanks author!
I do take some issue with intepreting set theory's membership relation in terms of the tree child relation, though.
First, the child relation is presumably transitive, whilst set membership is not. (The subset relation is transitive. Presumably it is 'direct child' relation we have in mind here.)
Second, as seen in the third diagram, nodes don't map well to set entities, because the same entity can be a member of distinct sets, but these would count as distinct nodes on some trees. E.g., in the diagram both leaf nodes are distinct, but they both represent the empty set, and hence should be identical. So the identity of sets is not preserved in the tree encoding.
But this is picky — a lovely read. Thanks author!
Thanks for the feedback.
Honestly sets as trees isn't original. While I was learning about ZFC I came across some lectures[0] by Richard Borcherds which was the seed of insipiration for this project.
[0] https://youtu.be/oWN13ktp8gg?t=1154
Honestly sets as trees isn't original. While I was learning about ZFC I came across some lectures[0] by Richard Borcherds which was the seed of insipiration for this project.
[0] https://youtu.be/oWN13ktp8gg?t=1154
HACKENBUSH: a window to a new world of math
https://www.youtube.com/watch?v=ZYj4NkeGPdM
Thanks for the blogpost, I think you will like this above SOME3 entry. Owen Maitzen committed suicide which is mentioned in the following video.
The Endless Universe of "Bean and Nothingness"
https://www.youtube.com/watch?v=bRIXgb4UgmY
https://www.youtube.com/watch?v=ZYj4NkeGPdM
Thanks for the blogpost, I think you will like this above SOME3 entry. Owen Maitzen committed suicide which is mentioned in the following video.
The Endless Universe of "Bean and Nothingness"
https://www.youtube.com/watch?v=bRIXgb4UgmY
> I would like to understand why numbers looks like leaves
1st of all they don't. The graph doesn't look like pinnatids or palmatids. There is some resemblance of an alternating disposition of leaves, but that's not the shape of the leaf itself but the distribution of them, and it's a stretch.
Secondly, I'll take the generous interpretation of the question which is, why the graph looks mathematically like leaves, and not a question of biological impact, whatever resemblance is a coincidence which brings us to
Third, OP is playing a game with numbers with no objective goal (yes all maths is this, but this is straight up chmess), there is no ultimate meaning to be derived of it.
1st of all they don't. The graph doesn't look like pinnatids or palmatids. There is some resemblance of an alternating disposition of leaves, but that's not the shape of the leaf itself but the distribution of them, and it's a stretch.
Secondly, I'll take the generous interpretation of the question which is, why the graph looks mathematically like leaves, and not a question of biological impact, whatever resemblance is a coincidence which brings us to
Third, OP is playing a game with numbers with no objective goal (yes all maths is this, but this is straight up chmess), there is no ultimate meaning to be derived of it.
I think the last point doesn't really hold its own in any way. Many discoveries throughout history have started from someone just playing around with an idea, toying with it at first, but eventually becoming obsessed. The thing is, there's no way to tell beforehand. It might be a toy with no ultimate use or meaning, or it might lead to something entirely novel somewhere down the line. That's why play, in a very broad sense, is a core part of science and invention.
If 1 out of 10 chmessicians discover something useful, the discoverer had good taste and deserves credit.
There is no insurance redistributing credit amongst all of the pointless searches.
The guys who invented imaginary numbers or eigenvectors weren't just throwing darts at a board and got "lucky".
There is no insurance redistributing credit amongst all of the pointless searches.
The guys who invented imaginary numbers or eigenvectors weren't just throwing darts at a board and got "lucky".
It sounds like you have an infallible instinct for exactly which lines of research should be funded and which are useless dead ends. The NSF should hire you immediately!
But he's not wrong, research really isn't just random playing (which I think is obviously still good and fun and should be done for it's own sake, of which this blog post is a great example though it probably wouldn't be worth the time of a formal research project).
It's the reason why "good questions" and seemingly arbitrary or trivial problems - especially those which motivates the development of much deeper machinery or discovery in order to solve them - is widely appreciated across all fields of math (poincare conjecture, galoi's proof of the unsolvability of the quintic, fermat's last theorem, riemann zeta's zeroes etc.)
In all cases those good questions where not randomly cooked up but posed from a previous, more direct line of inquiry, of which the originator usually had a good insight into. Though for the examples I gave the unexpected depth certainly could not have been anticipated beforehand.
It's the reason why "good questions" and seemingly arbitrary or trivial problems - especially those which motivates the development of much deeper machinery or discovery in order to solve them - is widely appreciated across all fields of math (poincare conjecture, galoi's proof of the unsolvability of the quintic, fermat's last theorem, riemann zeta's zeroes etc.)
In all cases those good questions where not randomly cooked up but posed from a previous, more direct line of inquiry, of which the originator usually had a good insight into. Though for the examples I gave the unexpected depth certainly could not have been anticipated beforehand.
People can make a good educated guess without being literally infallible.
always the problem with scientific research is that we never know why anything actually works the way it does, but we have a lot of ways of talking about it
abstraction for abstraction’s sake? pure abstraction? abstracted abstraction?
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 development of mathematical structuralism.
The identification problem argues that there exists a fundamental problem in reducing natural numbers to pure sets. Since there exists an infinite number of ways of identifying the natural numbers with pure sets, no particular set-theoretic method can be determined as the "true" reduction.
What Numbers Could Not Be
https://youtu.be/H5SocLNkT9M?si=Fk2Hmpw3yOtDW7GS
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 development of mathematical structuralism.
The identification problem argues that there exists a fundamental problem in reducing natural numbers to pure sets. Since there exists an infinite number of ways of identifying the natural numbers with pure sets, no particular set-theoretic method can be determined as the "true" reduction.
What Numbers Could Not Be
https://youtu.be/H5SocLNkT9M?si=Fk2Hmpw3yOtDW7GS
Well, I don't think it's safe to say natural numbers "are" sets, but surely they are isomorphic to some collection of sets (and this allows them to be modeled as sets within set theory).
The important part about the construction of the natural numbers from axiomatic set theory is that it can be done, not that it brings us closer to the Platonic idea of numbers. It can of course be done in many ways (OP's post lists just two). There's no reason to believe any specific representation within set theory is the true order of the universe, but it is extremely useful and we should be glad it works so well.
The important part about the construction of the natural numbers from axiomatic set theory is that it can be done, not that it brings us closer to the Platonic idea of numbers. It can of course be done in many ways (OP's post lists just two). There's no reason to believe any specific representation within set theory is the true order of the universe, but it is extremely useful and we should be glad it works so well.
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!
Could we just say that natural numbers can be represented using sets, and leave it there?
Natural numbers can also be represented by even natural numbers (e.g. the easy way where 2n represents n), but that doesn't tempt people to make metaphysical statements about natural numbers somehow fundamentally "being" even. There is no reason why a representation of natural numbers by sets should be any more tempting.
Natural numbers can also be represented by even natural numbers (e.g. the easy way where 2n represents n), but that doesn't tempt people to make metaphysical statements about natural numbers somehow fundamentally "being" even. There is no reason why a representation of natural numbers by sets should be any more tempting.
There are multiple represenation of rational numbers . n * p / n * q (for any n). So this problem is not unique to reduction of numbers to sets. Generally people say unique reduced form.
It's not a map/territory confusion. It's a warning about map/territory confusion. The problem is that we have only maps, so we cannot fully understand the territory.
This is a major concern in mathematics, whose reason for existence is to understand things precisely, not just rough and ready.
I'm not convinced there is a coherent "territory" when it comes to mathematics. Sometimes (remarkably!) mathematical concepts neatly line up with some part of the universe, and we gain some insight into how it works. But often that part of the universe lies entirely within somebody's mind - mathematics as an hobby or aesthetic pursuit, for instance, occupied with questions of pure logic.
Different ways of thinking about the same thing can lead to conflicting truths even without set theory getting in the way. The standard model of the real numbers has no infinitesimally small elements, for instance, but the hyperreal numbers do, despite satisfying all of the same first-order properties.
Different ways of thinking about the same thing can lead to conflicting truths even without set theory getting in the way. The standard model of the real numbers has no infinitesimally small elements, for instance, but the hyperreal numbers do, despite satisfying all of the same first-order properties.
This talks about representing numbers as graphs whilst showing that the graphs can appear to be reminiscent of leaves, not that the numbers are leaf nodes of graphs, which is where I thought it was going at first.
This has almost nothing to do with numbers or ZFC and almost everything to do with how graph layout algo's produce their outputs...
I agree. The layout makes it difficult to point out the node in the set that actually represents the graph. In the layout proposed, I'm not sure which node is 5 from the graph representing 5, unless someone can clue me in?
[deleted]
The graph itself is 5. I think OP is just saying that as the graph “fills in”, it looks like a botanical leaf.
> why biological leaves have this specific self-similar structure may yield more fruit
I hope the pun was intentional :)
That said, I think the actual answer is in part due to the choice of presentation rather than the mathematical structure — Force-Directed graph layout — despite the line immediately after this quote.
The outer surface of a leaf doesn't physically blend into other leaves that it touches, so it gets repelled mechanically during growth, and it is also connected mechanically to the parts it grew from.
Consider the failure of Collatz trees to look like leaves as a counterpoint to the failure of the `dot` graphs to look like leaves.
I hope the pun was intentional :)
That said, I think the actual answer is in part due to the choice of presentation rather than the mathematical structure — Force-Directed graph layout — despite the line immediately after this quote.
The outer surface of a leaf doesn't physically blend into other leaves that it touches, so it gets repelled mechanically during growth, and it is also connected mechanically to the parts it grew from.
Consider the failure of Collatz trees to look like leaves as a counterpoint to the failure of the `dot` graphs to look like leaves.
I'm not really sure what to say to this, other than watch this video and apply similar thinking to this problem: https://www.youtube.com/watch?v=EK32jo7i5LQ
The leaf structure itself doesn't really have anything to do with ZF set theory or Von Neumann ordinals, other than supplying the inspiration for the base structure. Same way prime numbers don't generate the spirals in the video, all numbers do. So leave the ordinals out of this, experiment with different tree construction methods and you might uncover something cool about trees (but not necessarily about set theory)
The leaf structure itself doesn't really have anything to do with ZF set theory or Von Neumann ordinals, other than supplying the inspiration for the base structure. Same way prime numbers don't generate the spirals in the video, all numbers do. So leave the ordinals out of this, experiment with different tree construction methods and you might uncover something cool about trees (but not necessarily about set theory)
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
[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
That’s pretty interesting, thanks. It’s related to abstraction (interfaces) vs representation (implementation) in programming. To my eye, there’s no conflict that 1 \in 3 is true in one representation and not in the other. Trying to use \in like that seems like a violation of an abstract interface, somehow expecting that the various implementations of an abstraction must be identical. It also doesn’t seem to violate platonism, since “numbers” are abstract ideas that are not expressible directly in set theory. Set theory can only encode concrete representations of numbers. Much like any physical chair cannot be identical to the platonic Chair.
I like this - nice playing around. We usually think of this kind of tree as having directed edges from parent to child, e.g. from set to element. In your graphs, you're erasing the direction of the edges, which uncovers a neat little symmetry that I never thought about before.
All the (non-limit) von Neumann ordinals are of the form X+1 = {X, {X}}, where X is the previous ordinal in the set. If you just look at trees of this form:
X+1: X <- node -> {X}, or X <- node -> node -> X
then you ignore the direction of the parent-child relation, you get this:
X+1: X -- node -- node -- X
So that's why your trees are symmetric as undirected graphs; and of course, every lower ordinal has its own version of this symmetry, which is also contained in the tree. All the large gaps between sections correspond to node--node edges of the larger ordinals. Kinda neat!
All the (non-limit) von Neumann ordinals are of the form X+1 = {X, {X}}, where X is the previous ordinal in the set. If you just look at trees of this form:
X+1: X <- node -> {X}, or X <- node -> node -> X
then you ignore the direction of the parent-child relation, you get this:
X+1: X -- node -- node -- X
So that's why your trees are symmetric as undirected graphs; and of course, every lower ordinal has its own version of this symmetry, which is also contained in the tree. All the large gaps between sections correspond to node--node edges of the larger ordinals. Kinda neat!
> set theory is the foundation of all of mathematics
I disagree. I would say set theory is a foundation, not the foundation.
Which system is the "correct" foundation of mathematics? Does it even make sense to talk about correctness in this context? These are open questions and they're very interesting! Don't prematurely close yourself off to them by assuming that set theory's role is some kind of scientific fact.
I disagree. I would say set theory is a foundation, not the foundation.
Which system is the "correct" foundation of mathematics? Does it even make sense to talk about correctness in this context? These are open questions and they're very interesting! Don't prematurely close yourself off to them by assuming that set theory's role is some kind of scientific fact.
Kurt Godel kind of threw this line of reasoning into the bin unfortunately. No system can be both complete and consistent, therefore the authors statement that the set theory he is studying is the basis of all mathematics as well as consistent is probably false.
The article is right to say that set theory can serve as a foundation for almost all other mathematics, and you're also right to say that no reasonably-complex consistent system of axioms can be complete. The resolution to this is that if you ground something (let's say topology) in e.g. ZFC (the most commonly used system of axioms for set theory) then incompleteness in ZFC maps to incompleteness in topology. Here's an example https://en.wikipedia.org/wiki/Moore_space_(topology)#Normal_... .
There are other foundations, some of which are based on things other than set theory (category theory, type theory), but they're usually equivalent to ZFC ± a few axioms, because you can embed those other foundations in some kind of set theory, and embed set theory in the other foundations.
There are other foundations, some of which are based on things other than set theory (category theory, type theory), but they're usually equivalent to ZFC ± a few axioms, because you can embed those other foundations in some kind of set theory, and embed set theory in the other foundations.
I love the imagination here and imagination in general but the framing really stretches it... I think this whole article would be more substantive if it was a little more grounded in the concept of induction.
Well and if it would admit very openly that in the sentence "numbers are leaves" the word "are" is about the existence of an isomorphism between the natural numbers and a series of nested sets... but that it's far from the only isomorphism, induction is everywhere in math and computer science. I imagine some little kid reading this and clinging to a reductionist idea that "numbers are (only) leaves", but they aren't just leaves.
Anyhow the setup is really nice and inspiring, it just ended up feeling like a tease. Hope to see a followup!
Well and if it would admit very openly that in the sentence "numbers are leaves" the word "are" is about the existence of an isomorphism between the natural numbers and a series of nested sets... but that it's far from the only isomorphism, induction is everywhere in math and computer science. I imagine some little kid reading this and clinging to a reductionist idea that "numbers are (only) leaves", but they aren't just leaves.
Anyhow the setup is really nice and inspiring, it just ended up feeling like a tease. Hope to see a followup!
Author here. Wasn't expecting to see this on the front page!
I'm really very far from a mathematician and this was a write up of a fun side project. I think the title would be unforgivably misleading in a formal context (if this was a paper claiming any new insights) but really it was a fun side project I wanted to right about. Maybe you read this and learned a little bit about set theory if you had no idea what it was (much like myself).
In general I resent popular science (especially in theoretical physics) which tries to reduce deep and interesting topics to poorly thought out analogies - but again my positioning here is not to educate per se. Or Michio Kaku style orating which assumes string theory a priori and later you have conversations with people who think string theory is established and tested because they watched a 40 minute video of him on YT.
Having said all this I need to get better and giving titles to the things I write - my other post about trying to build AGI in Rust got similar criticism.
Either way thanks for the feedback!
I'm really very far from a mathematician and this was a write up of a fun side project. I think the title would be unforgivably misleading in a formal context (if this was a paper claiming any new insights) but really it was a fun side project I wanted to right about. Maybe you read this and learned a little bit about set theory if you had no idea what it was (much like myself).
In general I resent popular science (especially in theoretical physics) which tries to reduce deep and interesting topics to poorly thought out analogies - but again my positioning here is not to educate per se. Or Michio Kaku style orating which assumes string theory a priori and later you have conversations with people who think string theory is established and tested because they watched a 40 minute video of him on YT.
Having said all this I need to get better and giving titles to the things I write - my other post about trying to build AGI in Rust got similar criticism.
Either way thanks for the feedback!
I'm under the impression that, at least theoretically, Von Neumann's principles of self-replication, game theory, or optimization in the context of designing neural network structures.
You could think about organizing a neural network with layers or nodes that are indexed by Von Neumann ordinals, where the structure of the network follows the natural progression of ordinals. For example:
Each layer or node in the neural network could correspond to a finite ordinal (such as 0, 1, 2, etc.) or transfinite ordinal (like ωω, ω+1ω+1, etc.). The way the network expands and evolves could follow the ordering and progression inherent in the Von Neumann ordinal system.
This could lead to an architecture where early layers (low ordinals) represent simpler, more basic computations (e.g., feature extraction or basic transformations). Later layers (higher ordinals) could correspond to more complex, abstract processing or deeper, more abstract representations.
But I'm afraid there is no hardware substrate upon which to build such a thing.
You could think about organizing a neural network with layers or nodes that are indexed by Von Neumann ordinals, where the structure of the network follows the natural progression of ordinals. For example:
Each layer or node in the neural network could correspond to a finite ordinal (such as 0, 1, 2, etc.) or transfinite ordinal (like ωω, ω+1ω+1, etc.). The way the network expands and evolves could follow the ordering and progression inherent in the Von Neumann ordinal system.
This could lead to an architecture where early layers (low ordinals) represent simpler, more basic computations (e.g., feature extraction or basic transformations). Later layers (higher ordinals) could correspond to more complex, abstract processing or deeper, more abstract representations.
But I'm afraid there is no hardware substrate upon which to build such a thing.
These are just binomial trees, which might be familiar to those who know their classic data structures.
https://en.wikipedia.org/wiki/Binomial_heap
https://en.wikipedia.org/wiki/Binomial_heap
> I would like to understand why numbers looks like leaves and not some other fractal like snowflakes for example (the inverse question, why biological leaves have this specific self-similar structure may yield more fruit).
Snowflakes are dendrite formations highly influenced by how nucleation happens, the graph layout choices highly impact what you will see;
Von Neumann Ordinals are possibly better approached as hierarchical branching processes, and being deterministic, Tokunaga self-similarity is one fairly elegant path to follow in the deterministic case such as this. (IMHO)
Snowflakes are dendrite formations highly influenced by how nucleation happens, the graph layout choices highly impact what you will see;
Von Neumann Ordinals are possibly better approached as hierarchical branching processes, and being deterministic, Tokunaga self-similarity is one fairly elegant path to follow in the deterministic case such as this. (IMHO)
Beautiful!
(And now we all go cross eyed trying to see if there's a pattern for factoring in there somewhere...)
(And now we all go cross eyed trying to see if there's a pattern for factoring in there somewhere...)
Perhaps if he was able to use some kind of force-directed 3-D algorithm, instead of a 2-D one, they might resemble something other than leaves, which could be interesting.
Super interesting, please do show what the other trees (collatz) that you mention look like
I went into it thinking they meant numbers are leaf nodes of a graph, but no: they meant the entire graph looks like a leaf.
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?
> "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?
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.
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.
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.
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.
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?
- 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.
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.
[deleted]
Am I wrong in thinking that the visual below “Finally with 5 the self-similarity continues as expected” is wrong? I’m thinking that the second-to-right and rightmost subtrees need to be larger, to have a sequence of four and five nodes respectively in their rightmost branches.
Too few examples. Get to 2039484 and report back if it looks like a leaf or a blob.
The number of nodes and edges is quadratic and the number of Coulomb repulsions is quartic, so I expect that only is possible to draw up to ~100, perhaps ~1000 or ~10000 using some tricks or aproximations.
Anyway, if you look at the graph of #5, it has two clear parts, the left part (with 16 nodes) that is #4 and the right part (with 16 nodes) that is just another copy of #4. So the structure is like 4-4.
But if you look more carefuly, you can find four copies of #3.
This construction work in all level, so even for 1000000, you will have four parts 999999-999999-999999-999999
And you can expand this in smaller parts, but the structure get's more tricky.
So I expect the 1000000 still to have a fractal like structure with four big parts that are quite similar.
One problem is that each branch can go to the right or to the left, and that is probably choosen a random. At the low level ir cause some noise in the final graphic, but at the high level you get different symmetries of the whole figure. From almos to mirror parts in #13 to a propeler in #6.
I'm not sure how spiky is #1000000. If it's a circle, I epect to see a fer radial lines that show the division 999999-999999-999999-999999. If it' not a circle, I expect to see something like in the images.
The tricky part may be to select the correct ratio of the Coulomb and Hooke forces (and the default rest lenght of the edges?). Sometimes to get a nice limit he contants used in the force model should change with N.
Anyway, if you look at the graph of #5, it has two clear parts, the left part (with 16 nodes) that is #4 and the right part (with 16 nodes) that is just another copy of #4. So the structure is like 4-4.
But if you look more carefuly, you can find four copies of #3.
3---3
\ \
3 3
This construction work in all level, so even for 1000000, you will have four parts 999999-999999-999999-999999
And you can expand this in smaller parts, but the structure get's more tricky.
So I expect the 1000000 still to have a fractal like structure with four big parts that are quite similar.
One problem is that each branch can go to the right or to the left, and that is probably choosen a random. At the low level ir cause some noise in the final graphic, but at the high level you get different symmetries of the whole figure. From almos to mirror parts in #13 to a propeler in #6.
I'm not sure how spiky is #1000000. If it's a circle, I epect to see a fer radial lines that show the division 999999-999999-999999-999999. If it' not a circle, I expect to see something like in the images.
The tricky part may be to select the correct ratio of the Coulomb and Hooke forces (and the default rest lenght of the edges?). Sometimes to get a nice limit he contants used in the force model should change with N.
The representation of n has 2^n vertices. 2^2039484 might be a bit too large to render...
You may be interested in percolation theory
https://en.m.wikipedia.org/wiki/Percolation_theory
https://en.m.wikipedia.org/wiki/Percolation_theory
Because the representation is a ragged tree. If it were a uniform depth it would look like a blob, but because different arms have different lengths those create structure in the layout algorithm.
> Numbers are Leaves
In mathematical tree nomenclature, the leaf nodes of the trees in the article are all 0 (represented by the empty set). So only the number zero is truly a leaf. ;)
In mathematical tree nomenclature, the leaf nodes of the trees in the article are all 0 (represented by the empty set). So only the number zero is truly a leaf. ;)
[deleted]
I rather like the idea that deep in the platonic realm of pure mathematics, there is something that is alive.
> All mathematical concepts can be expressed set-theoretically (e.g. geometry)
Category theory strongly disagrees!
Category theory strongly disagrees!
> 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.
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.
What infinity will look like?
Wouldn’t it be an infinite fractal?
> To check this I generated some Collatz trees and they ended up looking like microbes. I think it's safe to say the answer is no.
"Uniquely responsible" seems to be doing too much work. These structures are reminiscent of dendritic fractals coming about from diffusion-limited aggregation in electrochemical deposition[1], which is a transitional phenomenon with a phase diagram (molar concentration of the electrolyte vs voltage) There is a sweet spot in the middle where you get intricate dendritic crystals: outside of that you get smooth layers or big blobs / spikes without much internal structure.
I suspect it is primarily the modeling of the forces which is responsible for the behavior, with the topological structure of the tree somewhat indirectly corresponding to the chemical and electrical parameters. I am by no means an expert but it seems likely to me that these von Neumann dendrites vs the structure of Collatz trees is a fairly shallow relationship: lots of trees with similar graph-theoretic properties to the von Neumann trees would also demonstrate the leaf-like fractals, but with no meaningful relationship to the natural numbers. But it would be interesting to make this more precise.
[1] https://en.wikipedia.org/wiki/Diffusion-limited_aggregation