Sets and set theory

In this section, we will briefly review the basics of set theory, given their use in the rest of the course.

Sets

A set is a well-determined, logically consistent collection of distinct objects, for example, the set of all teapots, or prime numbers less than 100.

Set theory is the mathematical language for describing sets and operations on them.

We usually use “{“ and “}” to enclose the elements of a set. Sets are usually unordered, so the set {dime, quarter} is the same as the set {quarter, dime}. If \(x\) is in \(A\), we say that it is a member of \(A\) and write \(x\in A\).

Some examples:

• The set of prime numbers less than 10: \(\{2,3,5,7\}\)
• The set of natural numbers: \(\mathbb{N}=\{0,1,2,\dotsc\}\)
• The set of my favorite TV shows: {futurama, psych, breaking bad}
• The set of the first 13 letters of the English alphabet.
• The set of even numbers: \(\{x\in\mathbb{N}: \exists k\in \mathbb N, x=2k\}\). This last one needs a bit of unpacking.
  • What appears on the right of : restricts what appears on the left via some condition.
  • \(\exists\) is read as “there exists.”
  • So you can read the expression as the set of all natural numbers \(x\) for which there exists a natural number \(k\) such that \(x=2k\).

Why study set theory? We study sets because they are foundational in mathematics. Also, information can be described as identifying a state among a set of possible states. Information is also closely related to probability, for which we again need sets. Finally, sets will be helpful in understanding analog and digital signals.

Defining sets

To define a set, we can list its elements explicitly, e.g., \(A=\{1,3,5,7,9\}\). We can also define a set as the collection of objects satisfying a precise property, e.g., the set of “positive odd integers”. For any object \(x\), we can determine whether or not it is a positive odd integer, so this property defines a set.

If the property is vague or logically inconsistent, it cannot be used to define a set:

• A = “The set of tall students in this class”. Is Jacob in this set? Being tall is not defined precisely, and so the set is ambiguous.
• B = “Set of all objects not in the B”. Is 5 in the set, or is it not? For a given element, to check if it satisfies the property, we already need to know what B is.

Sets: relationships and operations

• Two sets are equal if they contain exactly the same members: 𝐴=𝐵
• Set \(A\) contains set \(B\) if all the elements of \(B\) are members of \(A\). This is written as \(B\subseteq A\)
• If \(A\) contains \(B\), and \(A\) is contained in \(B\), then \(A\) and \(B\) are equal.
• The empty set is the set with no elements. It is shown by: \(\varnothing\). For any other set \(A\), we have \(\varnothing\subseteq A\).
• The universal set contains absolutely everything (where we get to define what everything is). It is shown by \(U\). For any other set \(A\), we have \(A\subseteq U\).
• The complementary set, or complement, of a set is the set of everything that is not in the set. For a set \(A\), its complement is shown by \(A^c\). That is, \(A^c = \{x:x\not\in A\}.\)

Set operations:

• Intersection: Elements that are in both \(A\) and \(B\): \(A\cap B = \{x:x\in A, x\in B\}\).
• Union: Elements that are in \(A\), in \(B\), or in both: \(A\cup B = \{x:x\in A \text{ or } x\in B\}\).
• Difference: Elements that are in \(A\) but not in \(B\): \(A\setminus B = \{x:x\in A, x\not\in B\}\).
  • Note: \(A\setminus B = A\cap B^c\).