Abstract Algebra/Sets

From Wikibooks, open books for an open world
Jump to: navigation, search


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".

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

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 contruction later, in paticular 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: