A Set-Theoretical Definition of Graphs

1. The Rosen text defines graphs in terms of points and lines connecting them.
   But I have said that all mathematical objects can be defined in terms of logic and set theory.
   So, can we define graphs that way? Let's try:

   ---

2. 1. Definition:
      Let V be a set.
      Then V is a set of vertices =_def V ≠ ∅.

      Comment:

      Note that V isn't being defined as a (non-empty) set of (geometric) "points".
      By letting the members of V be any kind of thing, we allow for all kinds of things to be considered as graphs.

      ---

   2. Definition:
      Let V be a set of vertices.
      Then E is a set of edges on V =_def E ⊆ {{v_i, v_j} | v_i, v_j ∈ V}.

      I.e., E is a set of (unordered) pairs (i.e., a set of "doubletons") of vertices.

      ---

   3. Definition:
      Let V be a set of vertices.
      Let E be a set of edges on V.
      Then G is a graph on V and E =_def G = (V, E).

      Comments:

      1. G is defined as an ordered pair of sets.
         And in lecture I gave you the Kuratowski definition of an ordered pair (of anything) in terms of sets:
         The ordered pair (x, y) =_def {{x}, {x, y}}.

         So, G = {{V}, {V, E}}.

      2. If V = {v₁, …, v_n} and if E = {{v_i1, v_j1}, …, {v_ik, v_jk}}, then (hold your breath…) G = {{{v₁, … v_i}}, {{v₁, … v_i}, {{v_i1, v_j1}, …, {v_ik, v_jk}}}}.

   ---

3. But there's a small problem: This definition does not allow for there to be more than one edge connecting two vertices.
   Graphs that don't allow that are called "simple" graphs (or just "graphs"), and graphs that do allow that are called "multigraphs".

   How can we define multigraphs set-theoretically?
   The problem is that we need to allow multiple copies of elements to be in a set, and that's not allowed by the laws of set theory.
   (See Rosen, p. 113, Def. 3: 2 sets are equal iff they have exactly the same elements. Therefore, a set cannot have multiple "copies" of any element.)

   What we need is a notion called a "multiset" (by mathematicians) or a "bag" (by computer scientists).
   The fundamental principle behind this notion is that bags can have multiple copies of elements.
   Let's use angle brackets to denote bags. Then the bag ⟨x, x⟩ ≠ the bag ⟨x⟩ (whereas the set {x, x} = the set {x}).

   But wait: We want everything to be implemented as sets! And bags aren't sets! So we need to implement bags as sets.
   This can be done by implementing each member of a bag as an ordered pair whose first element is the bag-element and whose second element is a numeral
   (something like a subscript)—and, of course, you know how to implement ordered pairs as sets! Here are some examples of how this can be done:

   Bag	Set implementation
   ⟨x⟩	{(x, 1)}
   ⟨x, y⟩	{(x, 1), (y, 1)}
   ⟨x, x⟩	{(x, 1), (x, 2)}
   ⟨x, x, y⟩	{(x, 1), (x, 2), (y, 1)}
   ⟨x, x, y, y⟩	{(x, 1), (x, 2), (y, 1), (y, 2)}

   ---

4. Then we can define multigraphs as ordered pairs of vertices and edges, where the edges are defined as bags of pairs of vertices.
   But I'll leave the gory details to you.
   (I'll also leave as an exercise for you to define directed graphs set-theoretically! Hint: E ⊆ V ×V, but you may need to take bags into account.)