1. Does anyone know who was the first to
formally state (and maybe also prove?) what is arguably the most basic result in phylogenetics, which in today's language would say:

A set H of subsets of X equals the set of clusters of a rooted phylogenetic X-tree if and only if H is a hierarchy (i.e. any two sets in H are disjoint or one contains the other).

2. Mike
The obvious place to start looking is in Willi Hennig's work, since an explicit non-mathematical statement of the principle is always credited to him. However, Hennig compiled his ideas from those of several other people, so it probably goes back much farther. Hennig's treatment of the equivalence between phylogeny and hierarchy is discussed by Eric B. Knox (1998) The use of hierarchies as organizational models in systematics. Biological Journal of the Linnean Society 63: 1-49.

3. Thanks David,
I wondered if it might be in the writings of Linneaus? Or earlier (Aristotle et al?). I can find definite mathematical statements of it in the 1960s, but again there's maybe references from 1860 too! (related to some other problem, perhaps in physics, or pure maths)...

4. Equating hierarchical relationships (ie. a tree) and phylogeny is something that is usually attributed to Darwin, although he explicitly calls it a "simile" rather than treating it as a formal model. Before that time, tree models were used in a non-phylogenetic context (I have an upcoming blog post on this). Linné, for example, said that relationships were "like countries on a map" rather than like a tree (his hierarchical taxonomic classification was a separate thing entirely); and I am not sure that Aristotle was much interested in phylogenetic relationships. So, your query most likely refers to someone between Darwin and Hennig in time, and probably closer to Hennig.

5. Yes, I agree that the phylogenetic interpretation of what these trees mean comes much later, but the mathematical principle (that nested subsets are equivalent to a tree-like relationship) must surely have been stated earlier - perhaps in some totally different discipline, or context. It's not a deep result, of course, but it seems quite foundational in some sense.