A set is a collection of objects. E.g. $\{Peter, Paul, Mary\}$ is a set, as is $\{1, 2, 3\}$. In symbols, a set is generally represented as an enclosure of elements in curly braces, e.g. if a set ${\mathcal S}$ is composed of elements $x$, $y$, and $z$, we would represent it by ${\mathcal S} = \{x, y, z\}$.
The individual elements of the collection are the members of the set, and are said to be in the set. We denote that an element $x$ is a member of a set ${\mathcal S}$ by $x \in {\mathcal S}$.
If an element $x$ is not in a set $A$, we will denote this by $x \notin A$.
The members of a set may be other sets. So, for instance, the elements of the set ${\mathcal S} = \{{\mathcal A}, {\mathcal B}, {\mathcal C}\}$ may themselves be sets ${\mathcal A} = \{a, b, c\}$, ${\mathcal B} = \{d, e, f\}$. Interestingly, by our definition of sets, although $a \in {\mathcal A}$ and ${\mathcal A} \in {\mathcal S}$, this does not imply that $a \in {\mathcal S}$.
A set may, in fact, include both, elements that are individual items, and elements that are themselves sets. So, for instance, a set might be ${\mathcal S} = \{a, b, {\mathcal C}\}$, where $a$ and $b$ are individual objects, while ${\mathcal C}$ is a set. A set may, in theory, even contain itself, unless otherwise constrained by definition! On the other hand, a set may contain nothing. A set that contains nothing is often represented as $\{\}$ or as $\emptyset$, and is referred to as the empty set.
If you have noted some circular definitions above, it is because the definitions are circular. In mathematics, a set is an undefined primitive. In other words, it cannot be defined in terms of other constructs. It is an axiomatic construct that we just specify, and which makes intuitive sense to us. Attempting to define it in terms of other constructs will lead to circles. For instance, German mathematician Felix Hausdorff describes sets in the following way: “A set is formed by the grouping together of single objects into a whole. A set is a plurality thought of as a unit.” However, the Cantorian formulation of set theory views objects as sets.
One of the consequences of the fuzziness of the above definition is that one can run into paradoxes. For instance, Russell's paradox asks: can we define a set ${\mathcal S}$ as the collection of all sets that do not contain themselves? The definition is paradoxical due to unresolveable self reference: if ${\mathcal S}$ does not contain itself, it must contain itself.
In order to resolve these contradictions, a number of solutions were proposed. Russell's “type theory” defined math in terms of types, rather than sets, which enabled explicit avoidance of Russell's paradox in particular. The altnerative, which we will follow, is axiomatic set thory, or AST. AST defines sets through a collection of axioms -- postulates that are stated without any further reasoning. The axioms in any axiomatic system must be independent, i.e. it must be impossible to derive any of the axioms from the others, and consistent, we must not be able to derive both a statement and its negation from the axioms.
The axiomatic set we follow is generally based on the Zermelo Fraenkel Set theory with the Axiom of Choice, also referred to as ZFC. ZFC consists of a set of axioms about how sets may be defined, and their properties. In particular, the ZFC includes the “axiom of regularity” and the “axiom of restricted comprehension”, which together prevent construction of sets that can result in Russell's paradox.
A particularly curious axiom is the “axiom of choice” without which mathematicians would be greatly hampered in their ability to prove most statements. The axiom of choice simply states that given any collection of non-empty bins (sets), you can always choose one item from every bin. This obvious-looking statment is not a mathematical fact unless you invoke the axiom!
We now define a couple of frequently used standard sets that are central to many developments.
The Universal Set: The universal set, usually denoted $U$, is a set that contains all objects.
The Empty Set: The empty set, usually denoted $\emptyset$ or $\{\}$ is a set that has no elements. Unlike the universal set, the empty set causes no theoretical problems.
The Universal Set is an unfortunate concept. By definition, $U$ must contain all objects including itself. This violates the axiom of regularity in the ZFC, and hence is disallowed by ZFC and is not really a mathematically valid concept under the most common set theories.
The universal set also conflicts with Cantor's theorem (which we will refer to later), which states that the cardinality of the power set of any set is strictly greater than the cardinlity of the set itself. However, the power set itself would be a subset of $U$, and would hence have a cardinality no greater than $U$, leading to a contradiction.
We will ignore these subtleties, however.
We will use the “set builder” notation to represent sets. A set is generally represented as $\{x | \phi(x)\}$, to define a set of all objects for which $\phi(x)$ holds true. For instance $\{x | x^2 +3x = 0 \}$ represents the set of all solutions of the equation $x^2 + 3x = 0$, and $\{x | x \in {\mathcal R}\; AND\; 0 < x < 4\}$ represents the set $\{1, 2, 3\}$.
We can define a number of set relations as follows.
The set complement is often not considered to be a part of common set operations because of its dependence on the unfortunate universal set $U$.
However, the relative set complement of two sets $A$ and $B$ is well defined. The relative complement of $B$ in $A$ is simply the set difference $A \setminus B$.
The set product is a key concept for our discussions. The product of two sets $A$ and $B$ is the set formed from all ordered pairs of elements from $A$ and $B$, and is represented as $A \times B$. For instance, if $A = \{x, y, z\}$ and $B = \{a, b\}$, $A \times B = \{(x,a), (x,b), (y,a), (y,b), (z,a), (z,b)\}$.
Note that the elements of $A \times B$ are ordered. So, while $(x,a)$ is an element in $A \times B$, $(a, x)$ is not an element.
Formally \[ A \times B = \{(x,y) | x \in A ~AND~ y \in B\} \] FIGURE HERE
A product of a set $A$ with itself is often denoted by $A^2$.
Computation of products can be extended to more than two sets. For instance, $A \times B \times C$ is the set of ordered triplets $(x_a,x_b,x_c)$, where $x_a$ is an element from $A$, $x_b$ is from $B$ and $x_c$ is from $C$. In general, the product of any sequence of sets $A \times B \times C \times D \times \cdots$ is the set of ordered n-tuples $(x_a, x_b, x_c, x_d, \cdots)$.