Introduction to Sets

Discrete Mathematics Section 1.2

The Language of Collections

What is a Set?

A set is an unordered collection of distinct objects, called elements.

  • Notation: \(a \in A\) means “\(a\) is an element of set \(A\).”
  • The Golden Rule: Order doesn’t matter, and repeats don’t count.
    • \(\{1, 2, 3\} = \{3, 2, 1\}\)
    • \(\{1, 2, 2, 3\} = \{1, 2, 3\}\)

Defining Sets

There are two primary ways to describe a set:

  1. Roster Method: Listing every element.
    • \(V = \{a, e, i, o, u\}\)
  2. Set-Builder Notation: Defining the “rule” for membership.
    • \(S = \{ x \in \mathbb{Z} \mid x \text{ is even and } x > 0 \}\)

Important Number Sets

You will see these LaTeX symbols constantly. Memorize them!

  • \(\mathbb{R}\): Real Numbers (all points on the number line)
  • \(\mathbb{Z}\): Integers \(\{\dots, -2, -1, 0, 1, 2, \dots\}\)
  • \(\mathbb{Q}\): Rational Numbers (fractions)
  • \(\mathbb{N}\): Natural Numbers \(\{0, 1, 2, \dots\}\) (Note: Some texts start at 1!)

Relationships Between Sets

Subsets (\(\subseteq\))

\(A\) is a subset of \(B\) if every element of \(A\) is also in \(B\). * Formal Logic: \(\forall x, (x \in A \implies x \in B)\)

Proper Subsets (\(\subset\))

\(A\) is a subset of \(B\), but \(A \neq B\) (at least one element in \(B\) is not in \(A\)).

The Empty Set

The Empty Set (or null set) contains no elements. * Notation: \(\emptyset\) or \(\{ \}\) * Warning: \(\{\emptyset\}\) is NOT empty. It is a set containing one element (which happens to be an empty set).

Crucial Fact: The empty set is a subset of every set. \(\forall \text{ sets } A, \emptyset \subseteq A\).

Equality of Sets

Two sets \(A\) and \(B\) are equal if and only if they have the exact same elements.

In proofs, we show \(A = B\) by proving two things: 1. \(A \subseteq B\) 2. \(B \subseteq A\)

If both are true, the sets are identical.

Set Cardinality

Cardinality refers to the size of the set. * Notation: \(|A|\) (the number of elements in \(A\)).

Examples: * If \(A = \{2, 4, 6, 8\}\), then \(|A| = 4\). * If \(B = \emptyset\), then \(|B| = 0\). * If \(C = \{ \{1, 2\}, \{3, 4\} \}\), then \(|C| = 2\). (Sets can contain other sets!)

Activity: Subset or Element?

Determine if the following are True or False:

  1. \(2 \in \{1, 2, 3\}\)
  2. \(\{2\} \in \{1, 2, 3\}\)
  3. \(\{2\} \subseteq \{1, 2, 3\}\)
  4. \(\emptyset \in \{1, 2, 3\}\)

Answers: 1. True (2 is an item in the list) 2. False (The set \(\{2\}\) is not an item in the list) 3. True (Every item in the left set is in the right set) 4. False (The empty set is a subset, but not an element here)

LaTeX Quick-Ref for Section 1.2

  • \in \(\to \in\) (is an element of)
  • \notin \(\to \notin\) (is not an element of)
  • \subseteq \(\to \subseteq\) (subset)
  • \emptyset \(\to \emptyset\) (empty set)
  • \mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R} \(\to \mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}\)
  • \mid \(\to \mid\) (used in set-builder for “such that”)