An Introduction to Algebraic Structures

Dover Publications, Inc.

Contents

Sets and Numbers

The purpose of this chapter is to introduce two subjects that constitute the foundation of a good deal of higher mathematics, and of algebra in particular. For Chapters 2 through 5 we shall require familiarity with the elements of set theory and the real number system. This initial chapter is devoted to an exposition of the basic concepts and facts of these disciplines. Admittedly our treatment is superficial, but hopefully the reader will find it easy.

I. The Elements of Set Theory

1. The Concept of Set

The notions of set theory can be introduced in a rigorous, axiomatic way or, alternatively, in an intuitive fashion. The former method requires an excursion into logic and the foundations of mathematics. The latter enables us to get our show on the road in a quick and relatively painless way. We therefore turn at once to a heuristic description of the concept of set.

A set is a collection of objects; the nature of the objects is immaterial. The essential characteristic of a set is this: Given an object and a set, then exactly one of the following two statements is true.

(a) The given object is a member of the given set.

(b) The given object is not a member of the given set.

Examples

1. The numbers, 1 and 2, which are solutions of the equation x2 3x + 2 = 0 comprise the solution set of the given equation. We denote this set by "[1, 2}."

2. The unit circle with center at the origin of the plane is the set of points with coordinates (x, y)] satisfying the equation x2 + y2 = 1. For example, the point (1/2, [square root of 3/2]) is in the set, whereas (1, [square root of 3/2]) is not.

3. It might be tempting to speak of "the set of people who will enter the city of Chicago during 2050." But, clearly, such a collection cannot qualify as a set according to our understanding of this term (why?).

Definition 1. If an object x is a member of a set A, we say x is an element of A and write "x [member of] A." If an object y is not an element of a set B, we write "y [not member of] B."

Thus, since I is an element of the set {1, 2}, we write "1 [member of] {1, 2}"; since 3 is not an element of {1, 2}, we write "3 [not member of] {1, 2}."

Exercise: Describe a set whose elements are all sets; describe a set whose elements are sets of sets.

In Example 1, Page 1, we denoted the solution set of the equation x2 3x + 2 = 0 by "{1, 2}." This type of notation is convenient in case the elements of the set are few in number. For instance, if the set S consists of the elements a, b, c, d and no others, one writes

S = {a, b, c, d}.

In general, if a set S consists of the elements a1, a2, ..., an where n is a positive integer, then S is denoted by

(1) S = {a1, a2, ..., an}.

While the notation (1) for sets is useful as far as it goes, it will be important to have an additional notation (see Section 5, page 13).

2. Constants, Variables and Related Matters

The words "constant" and "variable" are among the most frequently used terms in mathematics. Since our usages may differ from those the reader is accustomed to, we urge that he read this section carefully.

Definition 2. A constant is a proper name, i.e., a name of a particular thing. Further, a constant names or denotes the thing of which it is a name.

Examples

1. "2" is a constant. It is the name of a particular mathematical object-a number.

2. "New York" is a constant. It is a name of one of the fifty states comprising the United States of America.

A given object may have different names, and therefore different constants may denote the same thing.

3. "1 + 1" and "8 · 1/4" are also constants, both denoting the number two.

4. New York is also known as the "Empire State." Thus "Empire State" and "New York" are names, both denoting the same geographical entity.

Variables occur in daily life as well as in mathematics. We may clarify their use by drawing upon a type of experience shared by almost all people.

Various official documents contain expressions such as (2) I, __________, do solemnly swear (or affirm) that. ... What is the purpose of the "__________" in (2)? Clearly, it is intended to hold a place in which a name, i.e., a constant, may be inserted. The variable in mathematics plays exactly the same role as does the "__________" in (2); it, too, holds a place in which constants may be inserted. However, a "__________" is clumsy for mathematical purposes. Therefore, the mathematician uses an easily written symbol, e.g., a letter of some alphabet, as a place-holder for constants. A mathematician would write (2) as, say, (3) I, x, do solemnly swear (or affirm) that ..., and the "x" is interpreted as holding a place in which a name may be inserted.

Definition 3. A variable is a symbol that holds a place for constants.

What are the constants that are permitted to replace a variable in a particular discussion? Usually an agreement is made, or understood, as to what constants are admissible as replacements. If an expression such as (2) or (3) occurs in an official document, the laws under which the document is prepared will specify the persons who may execute it. These are the individuals who may replace the variable by their names. Thus, with this variable is associated a set of persons, and the names of the persons in the set are the allowable replacements for the variable.

Definition 4. The range of a variable is the set of elements whose names are allowable replacements for the given variable.

We have said that letters are to be used as variables. It will also happen that letters will occur as constants; context will make clear whether a constant or a variable is intended.

Variables occur frequently together with certain expressions called "quantifiers." As the term implies, quantifiers deal with "how many." We shall use two quantifiers and illustrate the first as follows:

Let x be a variable whose range is the set of all real numbers. Consider the sentence

(4) For each x, if x is not zero, then its square is positive.

The meaning of (4) is

For each replacement of x by the name of a real number, if the number named is not zero, then its square is positive.

The quantifier used here is the expression "for each." Clearly, the intention is, when "for each" is used, to say something concerning each and every member of the range of the variable. For this reason we call the expression "for each" the universal quantifier.

If in place of (4) we write

(5) For each y, if y is not zero, then its square is positive, where the range of y is also the set of all real numbers, then the meanings of (4) and (5) are the same. Similarly, y can be replaced by z or some other suitably chosen 1 symbol without alteration of meaning.

The use of the second quantifier is illustrated by the sentence

(6) There exists an x such that x is greater than five and smaller than six,

where the range of x is the set of all real numbers. The meaning of (6) is

There is at least one replacement of x by the name of a real number such that the number named is greater than five and smaller than six.

The expression "there exists" (or, "there is") is the existential quantifier. If the variable x is replaced throughout (6) by y or some other properly chosen symbol, then the meaning of the new sentence is the same as that of (6).

Definition 5. If an occurrence of a variable is accompanied by a quantifier, that occurrence of the variable is bound; otherwise it is free.

In mathematical discourse, variables frequently occur free. For instance, one finds discussions beginning

If x is a nonzero real number, then ...

or

Let x be a nonzero real number. Then ...

In such cases, the entire discussion is understood to be preceded by a quantifier. Thus, in algebra texts one sees statements such as

Let x be a real number . Then

x + 2 = 2 + x.

This is interpreted as meaning

For each real number x, x + 2 = 2 + x.

The practice of beginning a discussion with expressions such as "If x is ..." or "Let x be ...," i.e., the practice of using the variable as free, will be adopted in many places throughout this text. Just which of the two quantifiers is intended to precede the discussion will be clear from the context.

We conclude this section with a few remarks concerning equals. In this text equals is used in the following ways:

(i) 1 + 1 = 2. This statement asserts that 1 + 1 and 2 are the same object (in this case, same number).

(ii) For each real number x, (x-2)2 = x24x + 4. (ii) asserts that for each replacement of x by a real number, (x-2) 2 and x2 4x + 4 are the same number.

(iii) There exists a real number x such that x2 4 = 0. (iii) asserts that there is a replacement for x by a real number such that x2 4 and 0 are the same number.

The well-known properties of equals are:

I. For each x, x = x. (Equals is reflexive.)

II. If x = y, then y = x. (Equals is symmetric.)

III. If x = y and y = z, then x = z. (Equals is transitive.)

3. Subsets and Equality of Sets

Definition 6. Let A and B be sets. A is a subset (or, part) of B if and only if all the elements of A are elements of B. We write "A [subset] B" and also say "A is contained in B." The symbol "B [contains] A" is defined as "A [subset] B"; in words, "B contains A."

Stated in the formal language of set theory, using variables, quantifiers, etc., Definition 6 is: A is a subset (or, part) of B if and only if for each element x, if x [member of] A, then x [member of] B.

Definition 7. A is a proper subset of B if and only if A [subset] B and A ≠ B.

Exercises

1. List several subsets of Z. (Z is the set of all integers.)

2. Is the set {2,4, 6, π, 1/2} a subset of Z? Why? How about {2,4, 6, 1/2}?

What is the condition that A not be a subset of B? A is not a subset of B, provided the condition asserted in Definition 6 is violated. But that condition is:

For each x, if x [member of] A, then x [member of] B.

Consequently, the condition is violated if there is even one exception to it. Therefore we deduce

A is not a subset of B if and only if there exists an element z [member of] A such that z [not member of] B.

If A is not a subset of B, one writes "A [not subset] B" or "B [not contains] A."

Exercises

Prove:

1. For each set A, A [subset] A.

2. If A = B, then A [subset] B and B [subset] A.

3. If A [subset] B and B [subset] C, then A [subset] C.

4. If A [subset] B and A [not subset] C, then B [not subset] C.

Although our development of Set Theory is intended to be intuitive, it is convenient to state explicitly one axiom concerning equality of sets. This axiom is simply the converse of Exercise 2, above.

The Axiom of Extensionality. If A and B are sets and if A [subset] B and B [subset] A, then A = B.

To illustrate the use of this axiom, we consider an example:

Let A be the set of all equilateral triangles, and let B be the set of all equiangular triangles. The definitions of A and B are different, yet we are confident that A = B. Indeed, if x [member of] A, then x is an equilateral triangle. By certain theorems of elementary geometry we know that x is equiangular, and consequently x [memmber of] B. Therefore, A [subset] B. By similar arguments one proves that B [subset] A. The Axiom of Extensionality now asserts (what is truly reasonable) that A = B.

Exercise: Give several illustrations of the use of the Axiom of Extensionality.

4. The Algebra of Sets; The Empty Set

The term "algebra" in the present context may strike the reader as unusual. The ordinary use of this word is related to adding and multiplying real numbers . Here we shall develop a formalism for certain operations with sets. The justification for the word "algebra" is that this formalism resembles, in certain superficial ways, the elementary operations with the real numbers.

Let A be the set of all positive integers, and Jet B be the set of all integers Jess than eleven. Thus A = {1, 2, 3, ...}, and B = {10, 9, 8, ... , 0, -1, -2, ...}. The set of elements that A and B have in common is {1, 2, 3, ..., 10} and is called "the intersection of A and B." More generally,

Definition 8. The intersection of sets A and B is the set A [intersection] B, of all elements x such that x [member of] A and x [member of] B.

Theorem 1. A [intersection] B = B [intersection] A i.e., intersection is commutative.

(Note: This theorem is analogous to a · b = b · a for the multiplication of real numbers.)

Proof: We prove this theorem by applying the Axiom of Extensionality; we show that A [intersection] B [subset] B [intersection] A, and B [intersection] A [subset] A [intersection] B, whence the desired result follows.

To prove that A [intersection] B [subset] B [intersection] A, we show that each element x [member of] A [intersection] B is an element of B [intersection] A. But if x [member of] A [intersection] B, then (Definition 7) x [member of] A and x [member of] B. Hence x [member of] B and x [member of] A, and therefore x [member of] B [intersection] A. In short, for each x [member of] A [intersection] B we have proved x [member of] B [intersection] A. Consequently, A [intersection] B [subset] B [intersection] A. Similarly, one shows that B [intersection] A [subset] A [intersection] B. Therefore, by the Axiom of Extensionality, A [intersection] B = B [intersection] A.

Q.E.D.

The reader will note that in the proof it was tacitly assumed that

x [member of] A and x [member of] B implies x [member of] B and x [member of] A.

More generally, if p and q are sentences, then a basic principle used in mathematical reasoning is this:

p and q is equivalent with q and p;

i.e.,

and

p and q implies q and p

and

q and p implies p and q.

This principle is one of several that is used extensively in all mathematical texts.

Example: "The rain is falling and the streets are wet" is equivalent with "The streets are wet and the rain is falling."

Venn diagrams provide a convenient device for picturing sets and relationships among them. The idea is to represent sets by simple plane areas.

If A [subset] B, this situation may be represented diagrammatically in Figure l and so on. If A [not subset] B we have pictures such as Figure 2. In each of the last three diagrams one sees that there is an element (i.e., a point) of A which is not an element (point) of B.

The intersection, A [intersection] B, of sets A and B is represented as the crosshatched region in Figure 3. Figure 3 gives added plausibility to the assertion that intersection is commutative.

At this point, it is natural to ask what is the intersection of sets such as those in Figure 4.

Plainly, these regions have no points in common, and therefore it is reasonable to regard A and B as having no intersection . However, if we take this course, then to some extent the algebra of sets is no longer analogous to the algebra of numbers. In the algebra of numbers, permissible operations with numbers always produce numbers. In a good analogy, one would expect that permissible operations with sets will produce sets. To achieve this objective, we now introduce the concept of the empty or void set.