Graph Theory: Background You’ll Need 1

  • Understand sets, including union, intersection, and subsets

Set Theory

A movie lover might own a collection of movie posters, while a music lover might keep a collection of vinyl records. Any collection of items can form a set.

set

A set is a collection of distinct objects, called elements of the set.

 

A set can be defined by describing the contents, or by listing the elements of the set, enclosed in curly brackets separated by commas.

 

Repeated elements in a set are only listed once. A set simply specifies the contents; order is not important.

 

The set represented by [latex]\{1, 2, 3\}[/latex] is equivalent to the set [latex]\{3, 1, 2\}[/latex].
Some examples of sets defined by describing the contents:

  1. The set of all even numbers
  2. The set of all books written about travel to Chile

Some examples of sets defined by listing the elements of the set:

  1. [latex]\{1, 3, 9, 12\}[/latex]
  2. [latex]\{\text{red, orange, yellow, green, blue, indigo, purple}\}[/latex]

set notation

Commonly, we will use a variable to represent a set, to make it easier to refer to that set later.

 

The symbol [latex]\in[/latex] means “is an element of”.

 

A set that contains no elements, [latex]\{ \}[/latex], is called the empty set or null set and is notated [latex]\emptyset[/latex].

Let [latex]A=\{1,2,3,4\}[/latex]To notate that [latex]2[/latex] is element of the set, we’d write [latex]2 \in A[/latex]

Sometimes a collection might not contain all the elements of a set. For example, Marta owns ninety-five Pokémon cards. While Marta’s collection is a set, we can also say it is a subset of the larger set of all Pokémon cards.

subset

A subset of a set [latex]A[/latex] is a set that consists solely of elements drawn from set [latex]A[/latex].

 

It may include all, some, or none of set [latex]A[/latex]‘s elements. In other words, every element in the subset is also an element of set [latex]A[/latex].

 

If [latex]B[/latex] is a subset of [latex]A[/latex], we write [latex]B \subseteq A[/latex]

 

A proper subset of a set [latex]A[/latex] is a subset that contains some, but not all, of the elements of set [latex]A[/latex].

 

It is a subset that is not identical to the original set, meaning it must contain fewer elements than set [latex]A[/latex].

 

If [latex]B[/latex] is a proper subset of [latex]A[/latex], we write [latex]B \subset A[/latex]
Given the set: [latex]A = \{a, b, c, d\}[/latex]. List all of the subsets of [latex]A[/latex]

Set Operations

Commonly, sets interact. For example, you and a new roommate decide to have a house party, and you both invite your circle of friends. At this party, two sets are being combined, though it might turn out that there are some friends that were in both sets.

set operations: union, intersection, complement, and difference

  • The union of two sets contains all the elements contained in either set (or both sets).
    • The union is notated [latex]A \cup B[/latex]. More formally, [latex]x \in A \cup B[/latex] if [latex]x \in A[/latex] or [latex]x \in B[/latex] (or both).
  • The intersection of two sets contains only the elements that are in both sets.
    • The intersection is notated [latex]A \cap B[/latex]. More formally, [latex]x \in A \cap B[/latex] if [latex]x \in A[/latex] and [latex]x \in B[/latex].
  • The complement of a set [latex]A[/latex] contains everything that is not in the [latex]A[/latex].
    • The complement is notated [latex]A'[/latex], or [latex]A^c[/latex], or sometimes  ~[latex]A[/latex].
  • The difference of two sets is the list of all the elements that are in one set but not present in the other.
    • The difference between two sets is notated [latex]A \setminus B[/latex]. More formally, [latex]x \in A \setminus B[/latex] if [latex]x \in A[/latex] & [latex]x \notin B[/latex].
Notice in the descriptions of the notation introduced above that the complement of a set is denoted [latex]A^{c}[/latex]. This superscript is not an exponent. It is a decoration that denotes the complement of a set.

Let’s try applying the set operations.

Consider the sets: [latex]A = \{\text{red, green, blue}\}[/latex],  [latex]B = \{\text{red, yellow, orange}\}[/latex],  [latex]C = \{\text{red, orange, yellow, green, blue, purple}\}[/latex]. 

Find the following:

  1. Find [latex]A \cup B[/latex]
  2. Find [latex]A \cap B[/latex]
  3. Find [latex]A^c \cap C[/latex]