Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Representing Sets as Binary Trees

  1. Aug 20, 2006 #1
    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?
    Last edited: Aug 20, 2006
  2. jcsd
  3. Aug 20, 2006 #2
    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 Im 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 dont see how I could distinguish between

    {{},{{},{}}} and {{},{{}}}
  4. Aug 20, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

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

    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

    Code (Text):

     / \
    *   *
    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)
  5. Aug 20, 2006 #4
    Ah, ok. I think I get the convention now. So, for my full binary trees, wherever I see a ...{{}, {}}... I replace it with a ...{{}}... ?

    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.
    Last edited: Aug 20, 2006
  6. Aug 20, 2006 #5
    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.)
  7. Aug 20, 2006 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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}
  8. Aug 20, 2006 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  9. Aug 20, 2006 #8
    ...a trick then? :)

    In that case, my goal will be to show for each axiom whether or not such a model works.
  10. Aug 20, 2006 #9
    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.
  11. Aug 20, 2006 #10


    User Avatar
    Science Advisor

    How are you going to represent uncountable sets? The nodes of a tree of the usual type are countable.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook