Read an Excerpt
An Introduction to Matrices, Sets & Groups for Science Students
By G. Stephenson Dover Publications, Inc.
Copyright © 1965 G. Stephenson
All rights reserved.
ISBN: 978-0-486-80916-8
CHAPTER 1
Sets, Mappings and Transformations
1.1 Introduction
The concept of a set of objects is one of the most fundamental in mathematics, and set theory along with mathematical logic may properly be said to lie at the very foundations of mathematics. Although it is not the purpose of this book to delve into the fundamental structure of mathematics, the idea of a set (corresponding as it does with our intuitive notion of a collection) is worth pursuing as it leads naturally on the one hand into such concepts as mappings and transformations from which the matrix idea follows and, on the other, into group theory with its ever growing applications in the physical sciences. Furthermore, sets and mathematical logic are now basic to much of the design of computers and electrical circuits, as well as to the axiomatic formulation of probability theory. In this chapter we develop first just sufficient of elementary set theory and its notation to enable the ideas of mappings and transformations (linear, in particular) to be understood. Linear transformations are then used as a means of introducing matrices, the more formal approach to matrix algebra and matrix calculus being dealt with in the following chapters.
In the later sections of this chapter we again return to set theory, giving a brief account of set algebra together with a few examples of the types of problems in which sets are of use. However, these ideas will not be developed very far; the reader who is interested in the more advanced aspects and applications of set theory should consult some of the texts given in the list of further reading matter at the end of the book.
1.2 Sets
We must first specify what we mean by a set of elements. Any collection of objects, quantities or operators forms a set, each individual object, quantity or operator being called an element (or member) of the set. For example, we might consider a set of students, the set of all real numbers between 0 and 1, the set of electrons in an atom, or the set of operators [partial derivative]/[partial derivative]x1, [partial derivative]/[partial derivative]x2, ..., [partial derivative]/[partial derivative]xn. If the set contains a finite number of elements it is said to be a finite set, otherwise it is called infinite (e.g. the set of all positive integers).
Sets will be denoted by capital letters A, B, C, whilst the elements of a set will be denoted by small letters a, b, ... x, y, z, and sometimes by numbers 1, 2, 3,....
A set which does not contain any elements is called the empty set (or null set) and is denoted by [empty set]. For example, the set of all integers x in 0 < x< 1 is an empty set, since there is no integer satisfying this condition. (We remark here that if sets are defined as containing elements then 0 can hardly be called a set without introducing an inconsistency. This is not a serious difficulty from our point of view, but illustrates the care needed in forming a definition of such a basic thing as a set.)
The symbol [member of] is used to denote membership of – or belonging to – a set. For example, x [member of] A is read as 'the element x belongs to the set A'. Similarly x [not member of] A is read as 'x does not belong to A' or 'x is not an element of A'.
If we specify a set by enumerating its elements it is usual to enclose the elements in brackets. Thus
A = {2,4,6,8,10} (1)
is the set of five elements – the numbers 2, 4, 6, 8 and 10. The order of the elements in the brackets is quite irrelevant and we might just as well have written A = {4, 8, 6, 2, 10}. However, in many cases where the number of elements is large (or not finite) this method of specifying a set is no longer convenient. To overcome this we can specify a set by giving a 'defining property' E (say) so that A is the set of all elements with property E, where E is a well-defined property possessed by some objects. This is written in symbolic form as
A = {x; x has the property E}. (2)
For example, if A is the set of all odd integers we may write
A = {x; x is an odd integer}.
This is clearly an infinite set. Likewise,
B = {x; x is a letter of the alphabet}
is a finite set of twenty-six elements – namely, the letters a, b, c ... y, z.
Using this notation the null set (or empty set) may be defined as
[empty set] = {x; x ≠ x}. (3)
We now come to the idea of a subset. If every element of a set A is also an element of a set B, then A is called a subset of B. This is denoted symbolically by A [subset or equal to] B, which is read as 'A is contained in B' or 'A is included in B'. The same statement may be written as B [contains or equal to] A, which is read as 'B contains A'. For example, if
A = {x; x is an integer}
and
B = {y; y is a real number}
then A [subset or equal to] B and B [contains or equal to] A. Two sets are said to be equal (or identical) if and only if they have the same elements; we denote equality in the usual way by the equality sign =.
We now prove two basic theorems.
Theorem 1. If A [subset or equal to] B and B [subset or equal to] C, then A [subset or equal to] C.
For suppose that x is an element of A. Then x [member of] A. But x [member of] B since A [subset or equal to] B. Consequently x [member of] C since B [subset or equal to] C. Hence every element of A is contained in C – that is, A [subset or equal to] C.
Theorem 2. If A [subset or equal to] B and B [subset or equal to] A, then A = B.
Let x [member of] A (x is a member of A). Then x [member of] B since A [subset or equal to] B. But if x [member of] B then x [member of] A since B [subset or equal to] A. Hence A and B have the same elements and consequently are identical sets – that is, A = B.
If a set A is a subset of B and at least one element of B is not an element of A, then A is called a proper subset of B. We denote this by A [subset] B. For example, if B is the set of numbers {1, 2, 3} then the sets {1,2}, {2,3}, {3, 1}, {1}, {2}, {3} are proper subsets of B. The empty set [empty set] is also counted as a proper subset of B, whilst the set {1, 2, 3} is a subset of itself but is not a proper subset. Counting proper subsets and subsets together we see that B has eight subsets. We can now show that a set of n elements has 2n subsets. To do this we simply sum the number of ways of taking r elements at a time from n elements. This is equal to
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)
using the binomial theorem. This number includes the null set (the nC0 term) and the set itself (the nCn term).
1.3 Venn diagrams
A simple device of help in set theory is the Venn diagram. Fuller use will be made of these diagrams in 1.7 when set operations are considered in more detail. However, it is convenient to introduce the essential features of Venn diagrams at this point as they will be used in the next section to illustrate the idea of a mapping.
The Venn diagram method represents a set by a simple plane area, usually bounded by a circle – although the shape of the boundary is quite irrelevant. The elements of the set are represented by points inside the circle. For example, suppose A is a proper subset of B (i.e. A [subset] B). Then this can be denoted by any of the diagrams of Fig. 1.1.
If A and B are sets with no elements in common – that is no element of A is in B and no element of B is in A – then the sets are said to be disjoint. For example, if
A = {x; x is a planet}
and
B = {y; y is a star}
then A and B are disjoint sets. The Venn diagram appropriate to this case is made up of two bounded regions with no points in common (see Fig. 1.2).
It is also possible to have two sets with some elements in common. This is represented in Venn diagram form by Fig. 1.3, where the shaded region is common to both sets. More will be said about this case in 1.7.
1.4 Mappings
One of the basic ideas in mathematics is that of a mapping. A mapping of a set A onto a set B is defined by a rule or operation which assigns to every element of A a definte element of B (we shall see later that A and B need not necessarily be different sets). It is commonplace to refer to mappings also as transformations or functions, and to denote a mapping f of A onto B by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)
If x is an element of the set A, the element of B which is assigned to x by the mapping f is denoted by f(x) and is called the image of x. This can conveniently be pictured with the help of the diagram (Fig. 1.4).
A special mapping is the identity mapping. This is denoted by f: A -> A and sends each element x of A into itself. In other words, f(x) = x (i.e. x is its own image). It is usual to denote the identity mapping more compactly by I.
We now give two examples of simple mappings.
(a) If A is the set of real numbers x, and if f assigns to each number its exponential, then f(x) = ex are the elements of B, B being the set of positive real numbers.
(b) Let A be the set of the twenty-six letters of the alphabet. If f denotes the mapping which assigns to the first letter, a, the number 1, to b the number 2, and so on so that the last letter z is assigned the number 26, then we may write
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
The elements of B are the integers 1,2, 3 ... 26. Both these mappings (transformations, functions) are called one-to-one by which we mean that for every element y of B there is an element x of A such that f(x) = y, and that if x and x' are two different elements of A then they have different images in B (i.e. f(x) ≠ f(x')). Given a one-to-one mapping f an inverse mapping f-1 can always be found which undoes the work of f. For if f sends x into y so that y = f(x), and f-1 sends y into x so that x = f-1(y), then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)
and
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)
Hence we have
ff-1 = f-1f = I, (8)
where I is the identity mapping which maps each element onto itself. In example (a) the inverse mapping f-1 is clearly that mapping which assigns to each element its logarithm (to base e) since
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
The inverse of the product of two or more mappings or transformations (provided they are both one-to-one) can easily be found. For suppose f sends x into y and g sends y into z so that
y = f(x) and z = g(y). (9)
Then
z = g[f(x)], (10)
which, by definition, means first perform f on x and then g on f(x). Consequently
x = (gf)-1(z). (11)
But from (9) we have
x = f-1(y) and y = g-1(z). (12)
Consequently
x = f-1[g-1(z)] = (f-1g-1)(z). (13)
Comparing (11) and (13) we find
(gf)-1 = f-1g-1. (14)
The inverse of the product of two one-to-one transformations is obtained therefore by carrying out the inverse transformations one-by-one in reverse order.
One-to-one mappings are frequently used in setting up codes. For example, the mapping of the alphabet onto itself shifted four positions to the left as shown
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
transforms 'set theory' into 'wix xlisvc'.
Not all mappings are one-to-one. For example, the mapping f defined by Fig. 1.5, where x is the image of a, and z is the image of both b and c, does not have an inverse mapping, although of course, inverses of the individual elements exist; these are f-1(x) = a,f-1(z) = {b, c} (i.e. the set containing the two elements b and c), and f-1(y) = [empty set] (the null set) since neither a, b nor c is mapped into y.
It is clear that if f, g and h are any three mappings then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)
– that is, that the associative law is true. However, it is not true that two mappings necessarily commute – that is, that the product is independent of the order in which the mappings are carried out. For suppose
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (16)
If we first carry out the mapping g and then the mapping f we find
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (17)
Conversely, carrying out first f and then g we find
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)
Clearly fg ≠ gf showing that f and g do not commute. It might be suspected that non-commutation arises in this particular instance since f is a one-to-one mapping whilst g is not. However, even two one-to-one mappings do not necessarily commute. Nevertheless, two mappings which always commute are a one-to-one mapping f and its inverse f-1 (see (8)).
1.5 Linear transformations and matrices
Consider now the two-dimensional problem of the rotation of rectangular Cartesian axes x10x2 through an angle θ into y10y2 (see Fig. 1.6).
If P is a typical point in the plane of the axes then its coordinates (y1, y2) respect to the y10y2 system are easily found to be related to its coordinates (x1, x2) with respect to the x10x2 system by the relations
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)
These equations define a mapping of the x1x2-plane onto the y1y2-plane and form a simple example of a linear transformation. The general linear transformation is defined by the equations
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (20)
in which the set of n quantities (x1, x2, x3, ..., xn) (the coordinates of a point in an n-dimensional space, say) are transformed linearly into the set of m quantities (y1, y2, ..., ym) (the coordinates of a point in an m-dimensional space). This set of equations may be written more concisely as
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (21)
or, in symbolic form, as
Y = AX, (22)
where
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(Continues...)
Excerpted from An Introduction to Matrices, Sets & Groups for Science Students by G. Stephenson. Copyright © 1965 G. Stephenson. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
