Representing Sets as Binary Trees

[Oxymoron]

I'm using the definition of a full binary tree which is a graph where there is exactly one path between any two vertices, there is a root, and where every vertex has either two children or none at all.

If I had the following graph:

*

that is, just the root, then could I construct the following set to represent this:

{{}} -- (i.e. the set containing the empty set a.k.a. the full binary tree containing a vertex with NO children)

And could the graph

...*
.../.\
.../...\
...*...*
.../.\
.../...\
...*...*

be represented by

{{},{{},{}}}

Basically I was wondering if I could construct all of the Zermelo-Fraenkel set theory axioms for a class of objects which were strictly full binary trees. I guess that I would be using the Extension axiom to construct the two sets that I have just given?

 

[Oxymoron]

I have two problems though:

1. If every vertex must have two children, or none at all, then does that mean that sets such as {{},{},{}} or {{{}},{}} are meaningless? Because the first one has three sets and the second has one subset which contains only one subset (and I am treating the number of subsets of a set to be the number of children of the corresponding vertex). Another set which I can see which would not have a full binary tree representation is {{},{{{}}}}.

2. I don't see how I could distinguish between

{{},{{},{}}} and {{},{{}}}

 

[Hurkyl]

I'm not sure if you're making this mistake or not, so I'll point it out just to be safe:

{{}, {}, {}} = {{}}
and
{{}, {{}, {}}} = {{}, {{}}}


I think you're talking about something I said about representing sets as trees. I can give the full statement of what I know, if you like, but it might not be enlightening... so I'll just explain the idea further.


As you noted, we can't restrict ourselves to binary trees, because we like sets to occasionally have a number of elements other than 0 or 2.

Another key property we need is rigidness which, I think, is equivalent to saying that no vertex can have identical children. So

  *
 / \
*   *

doesn't correspond to a set.


Also, the tree

*

denotes the empty set... and not the set containing the empty set. Your root vertex has no children. Thus, the graph represents a set without any elements.


(Also, we're using unordered trees and not ordered trees -- there is no ordering on the children of any vertex)

 

[Oxymoron]

Posted by Hurkyl:

I'm not sure if you're making this mistake or not, so I'll point it out just to be safe:

{{}, {}, {}} = {{}}
and
{{}, {{}, {}}} = {{}, {{}}}

Ah, ok. I think I get the convention now. So, for my full binary trees, wherever I see a ...{{}, {}}... I replace it with a ...{{}}... ?

Posted by Hurkyl:

I think you're talking about something I said about representing sets as trees. I can give the full statement of what I know, if you like, but it might not be enlightening... so I'll just explain the idea further.

Yeah, you gave me the idea. :) Basically, I want to only consider full binary trees and nothing else for simplicity and work through the Z-F axioms and see if they are all satisfied.

But first I have to understand how I am going to represent these sets as graphs or vice/versa.

 

[Oxymoron]

Posted by Hurkyl:

Also, the tree

*

denotes the empty set... and not the set containing the empty set.

So * corresponds to the empty set (denoted by, well... O I guess)

So O is different from {O} = {}? I suppose so! So if O corresponds to * then what does

...*
.../...\
.*...*

correspond to? (which is the next highest full binary tree possible.)

 

[Hurkyl]

Ah, ok. I think I get the convention now.

It's not a convention!

By definition:
w is an element of {x, y, z} if and only if w=x, w=y, or w=z.
w is an element of {x} if and only if w=x

Using the axiom of extensionality, we can prove:

x = y = z if and only if {x, y, z} = {x}

 

[Hurkyl]

Yeah, you gave me the idea. :) Basically, I want to only consider full binary trees and nothing else for simplicity and work through the Z-F axioms and see if they are all satisfied.

So, you want to come up with your own model, where sets are full binary trees.

Okay, then this is what you need to do:

(1) Decide which full binary trees count as sets.
(2) Define the relation "x is an element of y"

And, if you want to allow distinct trees to be equal sets, then you also need to
(3) Define the relation "x = y"


I think your program has a fatal flaw -- intuitively speaking, any particular (well-founded) binary tree only has a finite amount of "information"... I don't see how you can possibly model the axiom of infinity.

 

[Oxymoron]

Posted by Hurkyl:

It's not a convention!

...a trick then? :)

Posted by Hurkyl:

I think your program has a fatal flaw -- intuitively speaking, any particular (well-founded) binary tree only has a finite amount of "information"... I don't see how you can possibly model the axiom of infinity.

In that case, my goal will be to show for each axiom whether or not such a model works.

 

[neurocomp2003]

look how STL implements the RBtree(red black tree)...since in STL
the RBtree is used to manage sets,multisets,maps,multimaps...
set: only distinguishable elements are stored
multisets: there exists multiple instances of the same element
maps: sets accessed by keys(enumerables, where the key is whatever you like eg strings)
multimaps: multisets accessed by keys.

 

[0rthodontist]

How are you going to represent uncountable sets? The nodes of a tree of the usual type are countable.