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.
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$.
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\}$.
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.
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 \}$.
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.
Few Questions
ReplyDelete1. //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:)
Thanks for the questions. I'll answer them one by one:
Delete1. 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.
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.
ReplyDelete