Discrete Mathematics An Open Introduction, 3rd edition

This is a strange set, to be sure. It contains four elements: the number 1, the letter b, the set $\{x,y,z\}\text{,}$ and the empty set $\mathrm{\varnothing }=\{\}\text{,}$ the set containing no elements. Is $x$ in $A\text{?}$ The answer is no. None of the four elements in $A$ are the letter $x\text{,}$ so we must conclude that $x\notin A\text{.}$ Similarly, consider the set $B=\{1,b\}\text{.}$ Even though the elements of $B$ are elements of $A\text{,}$ we cannot say that the set $B$ is one of the elements of $A\text{.}$ Therefore $B\notin A\text{.}$ (Soon we will see that $B$ is a subset of $A\text{,}$ but this is different from being an element of $A\text{.}$)

Note: Sometimes mathematicians use $|$ or $∍$ for the “such that” symbol instead of the colon. Also, there is a fairly even split between mathematicians about whether $0$ is an element of the natural numbers, so be careful there.

This notation is usually called set builder notation. It tells us how to build a set by telling us precisely the condition elements must meet to gain access (the condition is the logical statement after the “$:$” symbol). Reading and comprehending sets written in this way takes practice. Here are some more examples:

There is also a subtle variation on set builder notation. While the condition is generally given after the “such that”, sometimes it is hidden in the first part. Here is an example.

We already have a lot of notation, and there is more yet. Below is a handy chart of symbols. Some of these will be discussed in greater detail as we move forward.

What about the sets $A=\{1,2,3\}$ and $B=\{1,2,3,4\}\text{?}$ Clearly $A\ne B\text{,}$ but notice that every element of $A$ is also an element of $B\text{.}$ Because of this we say that $A$ is a subset of $B\text{,}$ or in symbols $A\subset B$ or $A\subseteq B\text{.}$ Both symbols are read “is a subset of.” The difference is that sometimes we want to say that $A$ is either equal to or is a subset of $B\text{,}$ in which case we use $\subseteq \text{.}$ This is analogous to the difference between $<$ and $\le \text{.}$

In the example above, $B$ is a subset of $A\text{.}$ You might wonder what other sets are subsets of $A\text{.}$ If you collect all these subsets of $A$ into a new set, we get a set of sets. We call the set of all subsets of $A$ the power set of $A\text{,}$ and write it $\mathcal{P}(A)\text{.}$

Another way to compare sets is by their size. Notice that in the example above, $A$ has 6 elements and $B\text{,}$ $C\text{,}$ and $D$ all have 3 elements. The size of a set is called the set’s cardinality . We would write $|A|=6\text{,}$ $|B|=3\text{,}$ and so on. For sets that have a finite number of elements, the cardinality of the set is simply the number of elements in the set. Note that the cardinality of $\{1,2,3,2,1\}$ is 3. We do not count repeats (in fact, $\{1,2,3,2,1\}$ is exactly the same set as $\{1,2,3\}$). There are sets with infinite cardinality, such as $\mathbb{N}\text{,}$ the set of rational numbers (written $\mathbb{Q}$), the set of even natural numbers, and the set of real numbers ($\mathbb{R}$). It is possible to distinguish between different infinite cardinalities, but that is beyond the scope of this text. For us, a set will either be infinite, or finite; if it is finite, the we can determine its cardinality by counting elements.

It is important to remember that these operations (union, intersection, complement, and difference) on sets produce other sets. Don’t confuse these with the symbols from the previous section (element of and subset of). $A\cap B$ is a set, while $A\subseteq B$ is true or false. This is the same difference as between $3+2$ (which is a number) and $3\le 2$ (which is false).

Having notation like this is useful. We will often want to add or remove elements from sets, and our notation allows us to do so precisely.

There is one more way to combine sets which will be useful for us: the Cartesian product, $A\times B\text{.}$ This sounds fancy but is nothing you haven’t seen before. When you graph a function in calculus, you graph it in the Cartesian plane. This is the set of all ordered pairs of real numbers $(x,y)\text{.}$ We can do this for any pair of sets, not just the real numbers with themselves.

Put another way, $A\times B=\{(a,b):a\in A\wedge b\in B\}\text{.}$ The first coordinate comes from the first set and the second coordinate comes from the second set. Sometimes we will want to take the Cartesian product of a set with itself, and this is fine: $A\times A=\{(a,b):a,b\in A\}$ (we might also write $A^2$ for this set). Notice that in $A\times A\text{,}$ we still want all ordered pairs, not just the ones where the first and second coordinate are the same. We can also take products of 3 or more sets, getting ordered triples, or quadruples, and so on.

There is a very nice visual tool we can use to represent operations on sets. A Venn diagram displays sets as intersecting circles. We can shade the region we are talking about when we carry out an operation. We can also represent cardinality of a particular set by putting the number in the corresponding region.

Each circle represents a set. The rectangle containing the circles represents the universe. To represent combinations of these sets, we shade the corresponding region. For example, we could draw $A\cap B$ as:

Here is a representation of $A\cap \bar{B}\text{,}$ or equivalently $A\setminus B\text{:}$

A more complicated example is $(B\cap C)\cup (C\cap \bar{A})\text{,}$ as seen below.