## Sets and Important Notations

A set is a collection of distinct objects called elements. Any types of objects can be elements of a set, including numbers, colors, the batman symbol, as well as other sets. The set is completely determined by the elements contained in it.

There are numerous ways to describe a set. The simplest is to list the elements; if $A$ is the set of colors of the American flag, we could write $A = \{\scr red, white, blue\}$. The order that we write the elements in is irrelevant. Only the elements themselves matter.

As another example, if $B$ is the set of integers 1 through 100, we could write $B=\{1,2,...,100\}$.

For more complicated sets, we can use the so-called set-builder notation, which has its own section below.

#### Membership, Subsets, and Equality of Sets

If an object $x$ is an element of the set $A$, we write $x \in A$. Otherwise, $x \notin A$, i.e. $x$ is not an element of $A$.

Using the examples above, $7 \in B$, ${\scr green} \notin A$, and $100.3 \notin B$.

If we have some sets $C$ and $D$, and $C$ is completely contained in $D$ (in other words, every element of $C$ is also an element of $D$), then we say $C$ is a subset of $D$, and we write $C \subseteq D$, analagous to the $\leq$ symbol for numbers. Sometimes, you will also see it written as $C \subset D$, which I usually reserve for a proper subset, $C$ is a proper subset of $D$ if it is contained in, but not equal to, $D$, i.e. there is at least one element of $D$ that is not in $C$. A proper subset relationship is sometimes also written as $C \subsetneq D$.

Note that the empty set, the set containing no elements and written either as $\{\}$  or $\emptyset$, is a subset of every set. This is because you can make any statement you want about "all elements of the empty set"- there are none, so the statement is automatically true (but also doesn't really tell us anything). In particular, for some set $A$, every element of the empty set is also an element of $A$. For every pig in $\emptyset$, the pig can fly. Get it?

One special subset of a set $A$ is the power set of $A$, denoted $2^{A}$ or ${\cal P} (A)$, whose elements are all the subsets of $A$. Using the example set $A$ above,
\begin{align} 2^{A} = \{ &\emptyset, \{ {\scr red} \}, \{ {\scr white} \}, \{ {\scr blue} \}, \\ &\{ {\scr red, white} \}, \{ {\scr red, blue} \}, \{ {\scr white, blue} \}, \{ {\scr red, white, blue} \} \} \end{align} $2^{A}$ always contains $\emptyset$ and $A$ itself. In this example, $A$ has 3 elements, and $2^{A}$ has $2^3 = 8$ elements. This is always the case for sets with a finite number of elements, hence the notation $2^{A}$. I kind of prefer the notation ${\cal P} (A)$, but both are common.

Finally, if $C \subseteq D$ and $D \subseteq C$, then $C$ and $D$ have the same elements and so are the same set. We write $C=D$.

#### Set-builder Notation

Before going into the set-builder notation, there are two more symbols that will be useful.

The $\forall$ symbol stands for "for all" or "for each." So for the example set $B$ above, we could say that $\forall x \in B, 1 \leq x \leq 100$.

The symbol $\exists$ stands for "there exists." Using example set $B$ again, we can write $\forall x \in B, x \neq 100, \exists y \in B$ with $y > x$. This means that for each element $x$ of $B$ (except for 100), there exists another element $y$ of $B$ where $y>x$. Note there $\exists$ does not imply that only one such element exists. In this case, if $x=3$, examples of $y$ fitting the criteria above would be $4, 5, 6, ... , 100$.

In fact, this is a good example to illustrate the set-builder notation. We enclose in curly brackets first a variable for the elements of the set, then (separated by a colon $\colon$ or vertical bar $\vert$ ) a logical predicate which describes which elements are in the set.

Going back to the example above, if $\Psi_{x}$ is the set of elements $y$ of $B$ that are greater than a specified element $x$ (note that in this example, there would be one such set $\Psi_{x}$ for each $x \in B$), then we could write $\Psi_{x} = \{ y \in B \ \vert \ y > x \}$ or $\Psi_{x} = \{ y \in B \ \colon y > x \}$. So $\Psi_{3}$ would be $\{4,5,6,...,100\}$.

In set-builder notation, the power set can be specified as ${\cal P} (A) = \{ S \ \colon S \subseteq A\}$.

#### Basic Set Operations, De Morgan's Laws

There are three basic set operations, union, intersection, and complement.

The union of $A$ and $B$, denoted $A \cup B$, contains any element of $A$ or $B$ (including elements in both $A$ and $B$). In symbols, $A \cup B = \{ x \ \colon x \in A \ {\scr or}\ x \in B \}$.
Some properties of unions:
$A \cup B = B \cup A$
$A \cup (B \cup C) = (A \cup B) \cup C$
$A \subseteq A \cup B$
$A \cup A = A$
$A \cup \emptyset = A$
$A \subseteq B {\scr \ if \ and \ only \ if \ } A \cup B = B$

The intersection of $A$ and $B$ is denoted $A \cap B$ and contains the elements common to $A$ and $B$, i.e. $A \cap B = \{ x \ \colon x \in A \ {\scr and}\ x \in B \}$.
Some properties of intersections:
$A \cap B = B \cap A$
$A \cap (B \cap C) = (A \cap B) \cap C$
$A \cap B \subseteq A$
$A \cap A = A$
$A \cap \emptyset = \emptyset$
$A \subseteq B {\scr \ if \ and \ only \ if \ } A \cap B = A$

The complement of $A$, denoted $A^{C}$ or $A^{\prime}$,  contains all objects that are not elements of $A$, i.e. $A^{C} = \{x : x \notin A \}$.

The relative complement, denoted $A \setminus B$ or sometimes $A - B$, is the set of elements of $A$ not contained in $B$. $A \setminus B = \{ x \in A \colon x \notin B \}$. Note that $A \setminus B = A \cap B^{C}$.

Some properties of complements:
$A \setminus B \neq B \setminus A$ for $A \neq B$
$A \cup A^{C} = U$ where $U$ is the universe, i.e. everything
$A \cap A^{C} = \emptyset$
$(A^{C})^{C} = A$
$\emptyset ^{C} = U$ and $U^{C} = \emptyset$

There are two useful properties known as De Morgan's Laws that combine the operations above:
$(A \cup B)^{C} = A^{C} \cap B^{C}$, and
$(A \cap B)^{C} = A^{C} \cup B^{C}$.
If you picture a Venn Diagram like the ones above, it's easy to see why these are true. The first states that if something is not in $A$ or $B$, then it's not in $A$ and it's not in $B$, and vice versa. The second states that if something is not in both $A$ and $B$, then we know it's either not in $A$ or not in $B$ (or both), and vice versa.

Finally, the Cartesian product of two sets $A$ and $B$ is the set $A \times B$ whose elements are ordered pairs of elements of $A$ and $B$. $$A \times B = \{(a,b)~\colon~a \in A, b \in B \}$$

Sometimes, $A \times A$ is written as $A^{2}$, and similary $A^{3}$ would be $A \times A \times A$, etc. We will refer to the Cartesian product in some later posts.

Post any questions in the comments section, and I'll answer them as soon as possible.

1. Few Questions
1. //The set is completely determined by the elements contained in it//
If we have an "Infinite Set", is this true? I mean how it is "completely" determined?

2. Thanks for the Power Set & Proper Subset
Going by your definition, Is Power Set of A, a proper subset of A?

3. Is there something called a "Pure" set?
I mean, can a set include in its elements, a combination of subsets, plain elements (non sets) etc?
Example:
Solar System Set = {{Planets}, {Comets}, {Asteroids}, A random stone, , , }
If yes, how will your 1st axiom stand? //The set is completely determined by the elements contained in it//

End of Questions, for now:)
Happy Blogging, Greg:)

1. Thanks for the questions. I'll answer them one by one:
1. The same is true for infinite sets. For example, the natural numbers ${\Bbb N} = \{0,1,2,3...\}$ is an infinite set whose elements are easy to list and understand. The elements of some other inifinite sets such as ${\Bbb R}$, i.e. the number line, are more difficult to describe, but any set containing the same elements is the same set. That's what it means for a set to be "completely determined" by its elements.
2. The power set of $A$ is not a subset of $A$ at all. It is a set whose elements are the subsets of $A$. A subset of $A$ would be a set whose elements are elements of $A$, not sets of elements of $A$ (i.e. subsets of $A$). Make sense? Note though that $A$ is an element of $2^{A}$ since $A \subseteq A$. But $A$ is not a subset of its power set, since any element of $A$ is not an element of $2^{A}$. The set containing that element, which is a subset of $A$, is an element of $2^{A}$.
3. A set is determined by its elements even if those elements are other sets (each containing their own elements). I don't see any reason that a set could not contain some elements which are themselves sets of various other types of elements as well as individual elements. I haven't ever run into such sets in any practical application though.

2. I received a question from reader Renata N: how would the statement "$A \subseteq B {\scr \ if \ and \ only \ if \ } A \cup B = B$" change, if we replaced $A \subseteq B$ with $A \subset B$ (where $\subset$ denotes a *proper* subset)? The answer is, this would no longer be an "if and only if", but rather a one-directional implication $\implies$. It is still true that $A \subset B \implies A \cup B = B$. However, the other direction $\impliedby$ is not true: a counterexample is if $A=B$; in that case, $A \cup B = B \cup B = B$ is true, but $A \subset B$ (proper subset) is not true.