Lesson 4 in Perceptive Mathematics: tree diagrams for sets

 A set can be pictured as a tree. 

We describe this by examples. Consider for instance the set {A, B, {A, C, D, E}}. It has three elements, A, B, and the set {A, C, D, E}, which in turn has four elements, A, C, D, and E. Let us call this set X, so X={A, B, {A, C, D, E}}. Note that by coincidence, X and one of its elements, namely, {A, C, D, E}, share a common element A. This is permissible and it does not mean that there are two copies of A -- the A that is an element of X is the same A that is an element of X. Of course, in notation, we are forced to write out the set with two copies of A, but the two are supposed to represent the same object A. Now, to represent the set X as a tree, we start X and branch it out in as many elements as X has. So there will be three branches going out of X. The first two branches terminate with labels A and B, respectively. The third branch branches out further into four branches, which terminate with labels A, C, D, and E. As a result, we get the following "tree":

If one of A, B, C, D, E in this example is itself a set, we can expand the diagram further. For instance, if A={C, D}, then we get the tree

Exploration 4.1. How would you represent a singleton and the empty set as a tree? Using this insight, represent the following sets as trees:

• {{}}
• {{{}}}
• {{},{{}}}
• {{A, {{}, B}}}

Note that representing a set as a tree introduces even more redundant information than in the symbolic notation of sets. First, let's list some redundancies in the symbolic notation:

• Repetition of elements: the set {A} is the same set as the set {A, A} since both sets have exactly one element, the object A (recall that just because we mention a symbol twice does not mean it has two separate meanings).
• Order of elements: the set {A, B} is the same set as the set {B, A} because both sets have the same elements.

With the tree notation, in addition to the redundancies inherited from the symbolic notation, there is also a redundancy of the shape of the drawing, such as the length of branches, for instance. For instance, the last diagram above represents the same set as the following one:

Exploration 4.2. Represent as trees each of the quotients of the set X from the example above.