Sets edit

In the so-called naive set theory, which is sufficient for the purpose of studying abstract algebra, the notion of a set is not rigorously defined. We describe a set as a well-defined aggregation of objects, which are referred to as members or elements of the set. If a certain object is an element of a set, it is said to be contained in that set. The elements of a set can be anything at all, but in the study of abstract algebra, elements are most frequently numbers or mathematical structures. The elements of a set completely determine the set, and so sets with the same elements as each other are equal. Conversely, sets which are equal contain the same elements.

For an element   and a set  , we can say either  , that is,   is contained in  , or  , that is,   is not contained in  . To state that multiple elements   are contained in  , we write  .

The axiom of extensionality edit

Using this notation and the symbol  , which represents logical implication, we can restate the definition of equality for two sets   and   as follows:

  if and only if   and  .

This is known as the axiom of extensionality.

Comprehensive notation edit

If it is not possible to list the elements of a set, it can be defined by giving a property that its elements are sole to possess. The set of all objects   with some property   can be denoted by  . Similarly, the set of all elements   of a set   with some property   can be denoted by  . The colon : here is read as "such that". The vertical bar | is synonymous with the colon in similar contexts. This notation will appear quite often in the rest of this book, so it is important for the readers to familiarize themselves with this now.

As an example of this notation, the set of integers can be written as  , and the set of even integers can be written as  .

Set inclusion edit

For two sets   and  , we define set inclusion as follows:   is included in, or a subset of,  , if and only if every member of   is a member of  . In other words,


where the symbol   denotes "is a subset of", and   denotes "if and only if".

By the aforementioned axiom of extensionality, one finds that  .

The empty set edit

One can define an empty set, written  , such that  , where   denotes universal quantification (read as "for all" or "for every"). In other words, the empty set is defined as the set which contains no elements. The empty set can be shown to be unique.

Since the empty set contains no elements, it can be shown to be a subset of every set. Similarly, no set but the empty set is a subset of the empty set.

Proper set inclusion edit

For two sets   and  , we can define proper set inclusion as follows:   is a proper subset of   if and only if   is a subset of  , and   does not equal  . In other words, there is at least one member in   not contained in  


where the symbol   denotes "is a proper subset of" and the symbol   denotes logical and.

Cardinality of sets edit

The cardinality of a set  , denoted by  , can be said informally to be a measure of the number of elements in  . However, this description is only rigorously accurate for finite sets. To find the cardinality of infinite sets, more sophisticated tools are needed.

Set intersection edit

For sets   and  , we define the intersection of   and   by the set   which contains all elements which are common to both   and  . Symbolically, this can be stated as follows:


Because every element of   is an element of   and an element of  ,   is, by the definition of set inclusion, a subset of   and  .

If the sets   and   have no elements in common, they are said to be disjoint sets. This is equivalent to the statement that   and   are disjoint if  .

Set intersection is an associative and commutative operation; that is, for any sets  ,  , and  ,   and  .

By the definition of intersection, one can find that   and  . Furthermore,  .

One can take the intersection of more than two sets at once; since set intersection is associative and commutative, the order in which these intersections are evaluated is irrelevant. If   are sets for every  , we can denote the intersection of all   by


In cases like this,   is called an index set, and   are said to be indexed by  .

In the case of   one can either write   or


Set union edit

For sets   and  , we define the union of   and   by the set   which contains all elements which are in either   or   or both. Symbolically,


Since the union   of sets   and   contains the elements of   and  ,   and  .

Like set intersection, set union is an associative and commutative operation; for any sets  ,  , and  ,   and  .

By the definition of union, one can find that  . Furthermore,  .

Just as with set intersection, one can take the union of more than two sets at once; since set union is associative and commutative, the order in which these unions are evaluated is irrelevant. Let   be sets for all  . Then the union of all the   is denoted by


(Where   may be read as "there exists".)

For the union of a finite number of sets  , that is,   one can either write   or abbreviate this as


Distributive laws edit

Set union and set intersection are distributive with respect to each other. That is,


Cartesian product edit

The Cartesian product of sets   and  , denoted by  , is the set of all ordered pairs which can be formed with the first object in the ordered pair being an element of   and the second being an element of  . This can be expressed symbolically as


Since different ordered pairs result when one exchanges the objects in the pair, the Cartesian product is not commutative. The Cartesian product is also not associative. The following identities hold for the Cartesian product for any sets  :


The Cartesian product of any set and the empty set yields the empty set; symbolically, for any set  ,  .

The Cartesian product can easily be generalized to the n-ary Cartesian product, which is also denoted by  . The n-ary Cartesian product forms ordered n-tuples from the elements of   sets. Specifically, for sets  ,


This can be abbreviated as


In the n-ary Cartesian product, each   is referred to as the  -th coordinate of  .

In the special case where all the factors are the same set  , we can generalize even further. Let   be the set of all functions  . Then, in analogy with the above,   is effectively the set of " -tuples" of elements in  , and for each such function   and each  , we call   the  -th coordinate of  . As one might expect, in the simple case when   for an integer  , this construction is equivalent to  , which we can abbreviate further as  . We also have the important case of  , giving rise to the set of all infinite sequences of elements of  , which we can denote by  . We will need this construction later, in particular when dealing with polynomial rings.

Disjoint union edit

Let   and   be any two sets. We then define their disjoint union, denoted   to be the following: First create copies   and   of   and   such that  . Then define  . Notice that this definition is not explicit, like the other operations defined so far. The definition does not output a single set, but rather a family of sets. However, these are all "the same" in a sense which will be defined soon. In other words, there exists bijective functions between them.

Luckily, if a disjoint union is needed for explicit computation, one can easily be constructed, for example  .

Set difference edit

The set difference, or relative set complement, of sets   and  , denoted by  , is the set of elements contained in   which are not contained in  . Symbolically,


By the definition of set difference,  .

The following identities hold for any sets  :


The set difference of two Cartesian products can be found as  .

The universal set and set complements edit

We define some arbitrary set   for which every set under consideration is a subset of   as the universal set, or universe. The complement of any set is then defined to be the set difference of the universal set and that set. That is, for any set  , the complement of   is given by  . The following identities involving set complements hold true for any sets   and  :

De Morgan's laws for sets:
Double complement law:
Complement properties:

The set complement can be related to the set difference with the identities   and  .

Symmetric difference edit

For sets   and  , the symmetric set difference of   and  , denoted by   or by  , is the set of elements which are contained either in   or in   but not in both of them. Symbolically, it can be defined as


More commonly, it is represented as

  or as

The symmetric difference is commutative and associative so that   and  . Every set is its own symmetric-difference inverse, and the empty set functions as an identity element for the symmetric difference, that is,   and  . Furthermore,   if and only if  .

Set intersection is distributive over the symmetric difference operation. In other words,  .

The symmetric difference of two set complements is the same as the symmetric difference of the two sets:  .

Notation for specific sets edit

Commonly-used sets of numbers in mathematics are often denoted by special symbols. The conventional notations used in this book are given below.

Natural numbers with 0:   or  
Natural numbers without 0:  
Rational numbers:  
Real numbers:  
Complex numbers: