4
$\begingroup$

What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child

e.g.

$\endgroup$
4
  • $\begingroup$ Not sure this is the best site for this interesting question, but also don't have any better suggestions for a site. $\endgroup$ – Yuval Filmus Apr 25 '20 at 9:13
  • $\begingroup$ meta.stackexchange.com/a/294785 $\endgroup$ – Alasdair McLeay Apr 26 '20 at 10:06
  • $\begingroup$ Fair enough... It does seem to be the correct site. $\endgroup$ – Yuval Filmus Apr 26 '20 at 11:29
  • 1
    $\begingroup$ It's been at least around since linked lists, cs.stackexchange.com/a/76757/68251. I have two guesses though. I would imagine arrows represented the parent child relation, then when type writers came about there was no explicit arrow key on them so the > symbol was the next best thing. Similarly in ASCII there doesn't appear to be a "right arrow" printable key: en.wikipedia.org/wiki/ASCII#Printable_characters so I'd imagine similarly, they used > instead of a right arrow key. $\endgroup$ – ryan Apr 28 '20 at 14:06
2
+25
$\begingroup$

It comes from set theory. To see that these ideas were around before computers and that they were explicitly called trees consider the following famous tree. The convention set theorist sometimes use (some use use the convention you gave) is the opposite (the root $\hat{0}$ is the smallest, i.e. $\hat{0}<x$ for all $x\neq \hat{0}$, not the biggest ... this is keeping in line with the equivalence of the principle of induction and the well-ordering principle and is more natural ... i.e. a "zero-like" object is the root ... I will keep that convention so just replace all of the $<$ with $>$ in the proceeding discussion) The idea is the following:

Theorem From any partial (well)-order we can construct a tree and from any tree we can construct a partial (well)-order.

Remark Partial (well)-order is a name I made up so as to artificially distinguish between trees and the relation I am about to define:

Let $P = (V, E) =(V, \leq_E ) $ be a partial (well)-order then it satisfies the following

  1. $(\forall x) \ x \leq x$
  2. $(\forall x,y) \ x \leq y \implies y \leq x $
  3. $(\forall x,y,z) \ x \leq y \land y \leq z \implies x \leq z $
  4. $(\exists \hat{0} )(\forall x) \ \hat{0} \leq x$
  5. $(\forall x) \ (\exists 0_{x} ) \ y \in \{ t \in V \ | \ t \leq x\} \implies 0_{x} \leq y $ ,

The first 3 state that $\leq$ is a partial order and the last states that the predecessor sets are well ordered.

(Proof of Partial implies Tree) Let $P = (V, \leq_E ) $ be a well partial order then connect $v$ to $w$ if $w$ is the least element such that $v \leq w$, i.e. $ w = \min \{x \in V \ | \ v \leq x\}$ or $w$ covers v. It is easy to see that there are no cycles (because of rule 3) and that the graph is connected (there is always a path from $\hat{0}$ to any $v$ by induction because $\leq$ is a well order)

(Proof of Tree implies Partial) Let $x \leq y$ if there exists a path from $x$ to $y$, it is tedious but easy to see that all of the rules above are satisfied.

You may thinking, "man I didn't want an explanation involving set theory"

Let me help you dispel those heretical thoughts with the following observations

Most of the famous early famous computer scientists got most of their techniques from set theory

  1. The solution to the halting problem is an adaptation of a very beautiful proof by Georg Cantor that there are different sizes of infinity
  2. Similarly so is the Entscheidungsproblem
  3. Similarly, the proof that exponential time does not equal polynomial time
  4. Von Neumann (Von-Neumann architecture) also came up with the Von-Neumann Universe of sets

This should come as no surprise set theory is concerned with the ontological status of the mathematical universe and the idea that all of the objects of our mathematical experience can be constructed via recursion ... and isn't that the big idea behind every algorithm/computer program ... some recursive construction ... trees are the simplest recursively constructed objects other than the natural numbers ... set theory is like a programming language for the platonic realm.

We can take this whole idea further and prove that every set is a tree and every tree is a set (because of Von Neumann's axiom of regularity) but I will just leave you with the following: set data structures are tree data structures which hopefully will have you convinced of the truly inexorable relationship between the two.

I hope that I have whet your curiosity towards the beauty of sets. Good luck on your mathematical voyages! Bon Voyage!

$\endgroup$
1
$\begingroup$

Here's a usage of ">" from the 17th century.

https://books.google.com/books?id=771CAAAAcAAJ&pg=PA10#v=onepage&q&f=false

Is this usage just for "greater", though? Consider the text: māĭŏr means ancestor, maioritatis (sometimes majoritatis) here meaning the greater. The left is the greater ancestor, the right the lesser child, and that idea continued to hold true when the set-theoretic definitions of natural numbers were developed in the 19th and early 20th centuries (where smaller numbers are subsets of larger numbers: 0 is the empty set {}, 1 is set of the zero {0}, 2 is the set of 0 and 1 {0,{0}}, etc.) and continued to hold true in our own era when we adopted ">" to show the drilling down from greater ancestor page to lesser subset child page in web pages and the like. So if we allow that the idea is the same, the first usage of the symbol ">" for that idea is in the 17th century.

$\endgroup$
1
  • $\begingroup$ Thanks! I was looking for a use that is explicitly for a tree structure, rather than the origins of the mathematical symbol (which I think this is?). It is certainly possible that the usage for a tree structure was inspired by this, but that's what I'd hope to be able to answer by finding the first time it was used as such. $\endgroup$ – Alasdair McLeay Apr 27 '20 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.