CHAPTER 12

DEFINITION OF MATHEMATICAL MODELS: MODERN (ABSTRACT) ALGEBRA AND ABSTRACT SPACES

    12.1. Introduction

      12.1-1. Mathematical Models

      12.1-2. Survey

      12.1-3. “Equality” and Equivalence Relations

      12.1-4. Transformations, Functions,Operations

      12.1-5. Invariance

      12.1-6. Representation of One Model by Another: Homomorphisms and Isomorphisms

    12.2. Algebra of Models with a Single Denning Operation: Groups

      12.2-1. Definition and Basic Properties of a Group

      12.2-2. Subgroups

      12.2-3. Cyclic Groups. Order of a Group Element

      12.2-4. Products of Complexes. Cosets

      12.2-5. Conjugate Elements and Sub¬groups. Normal Subgroups. Factor Group

      12.2-6. Normal Series. Composition Series

      12.2-7. Center. Normalizers

      12.2-8. Groups of Transformations or Operators

      12.2-9. Homomorphisms and Isomorphisms of Groups. Representation of Groups

      12.2-10. Additive Groups. Residue Classes and Congruence

      12.2-11. Continuous and Mixed-continuous Groups

      12.2-12. Mean Values

    12.3. Algebra of Models with Two Denning Operations: Rings, Fields, and Integral Domains

      12.3-1. Definitions and Basic Theorems

      12.3-2. Subrings and Subfields. Ideals

      12.3-3. Extensions

    12.4. Models Involving More Than One Class of Mathematical Objects: Linear Vector Spaces and Linear Algebras

      12.4-1. Linear Vector Spaces

      12.4-2. Linear Algebras

    12.5. Models Permitting the Definition of Limiting Processes: Topological Spaces

      12.5-1. Topological Spaces

      12.5-2. Metric Spaces

      12.5-3. Topology, Neighborhoods, and Convergence in a Metric Space

      12.5-4. Metric Spaces with Special Properties. Point-set Theory

      12.5-5. Examples: Spaces of Numerical Sequences and Functions

      12.5-6. Banach's Contraction-mapping Theorem and Successive Approximations

    12.6. Order

      12.6-1. Partially Ordered Sets

(a) Order

(b) Lattices

      12.6-2. Simply Ordered Sets

      12.6-3. Ordered Fields

    12.7. Combination of Models: Direct Products, Product Spaces, and Direct Sums

      12.7-1. Introduction. Cartesian Products

      12.7-2. Direct Products of Groups

      12.7-3. Direct Products of Real Vector Spaces

      12.7-4. Product Space

      12.7-5. Direct Sums

    12.8. Boolean Algebras

      12.8-1. Boolean Algebras

      12.8-2. Boolean Functions.Reduction to Canonical Form

      12.8-3. The Inclusion Relation

      12.8-4. Algebra of Classes

      12.8-5. Isomorphisms of Boolean Alge¬bras. Venn Diagrams

      12.8-6. Event Algebras and Symbolic Logi>c

      12.8-7. Representation of Boolean Functions by Truth Tables. Karnaugh Maps

      12.8-8. Complete Additivity and Measure Algebras

    12.9. Related Topics References and Bibliography

      12.9-1. Related Topics

      12.9-2. References and Bibliography

12.1. INTRODUCTION

12.1-1. Mathematical Models. Physical processes are, generally speaking, described in terms of operations (observations, experiments) relating physical objects. The complexity of actual physical situations calls for simplified descriptions in terms of verbal, symbolic, and even physical models which “abstract” suitably chosen “essential” properties of physical objects and operations.

Mathematics in the most general sense deals with the definition and manipulation of symbolic models. A mathematical model involves a class of undefined (abstract, symbolic) mathematical objects, such as numbers or vectors, and relations between these objects. A mathematical relation is a hypothetical rule which associates two or more of the undefined objects (see also . Secs 12.1-3 and 12.8-1). Many relations are described in terms of mathematical operations associating one or more objects (operand, operands) with another object or set of objects (result). The abstract model, with its unspecified objects, relations, and operations, is defined by a self-consistent set of rules (defining postulates) which introduce the operations to be employed and state general relations between their results (descriptive definition of a mathematical model in terms of its properties; see Secs.12.1-3Secs.12.1-1 Secs.12.2-1, Secs.12.3-1, Secs.12.4-1, Secs.12.5-2,Secs.12.6-1 ,Secs.12.8-1 , and Secs.1.1-2 for examples). A constructive definition introduces a new mathematical model in terms of previously defined mathematical concepts (e.g., definition of matrix addition and multiplication in terms of numerical addition and multiplication, Sec. 13.2-2).

The self-consistency of a descriptive definition must be demonstrated by construction or exhibition of an example satisfying the defining postulates {existence proof, see also . Secs.4.2-16 and Secs.9.1-4). In addition, it is customary to test the defining postulates for mutual independence.

A mathematical model will reproduce suitably chosen features of a physical situation if it is possible to establish rules of correspondence relating specific physical objects and relationships to corresponding mathematical objects and relations. It may also be instructive and/or enjoyable to construct mathematical models which do not match any counterpart in the physical world. The most generally familiar mathematical models are the integral and real-number systems (Sec.1.1-2) and Euclidean geometry; the defining properties of these models are more or less directly abstracted from physical experience (counting, ordering, comparing, measuring).

Objects and operations of more general mathematical models are often labeled with sets of real numbers, which may be related to the results of physical measurements. The resulting “representations” of mathematical models in terms of numerical operations are discussed specifically in Chaps. 14 and Chaps. 16.

Questions as to the self-consistency, sufficiency, and applicability of the logical rules used to manipulate mathematical statements form the subject matter of metamathe-matics, which is by no means a finished structure (Ref. 12.16).

12.1-2. Survey. Modern (abstract) algebra* deals with mathematical models defined in terms of binary operations (“ algebraic” operations, usually referred to as various types of “ addition” and “ multiplication”) which associate pairs of mathematical objects (operands, or operator and operand) with corresponding results. Sections12.2-1 through Sections12.4-2 introduce some of the most generally useful models of this kind, notably groups, rings, fields, vector spaces, and linear algebras; Boolean algebras are treated separately in Secs.12.8-1 through Secs.12.8-6.

The important subject of linear transformations (linear operators) and their eigenvectors and eigenvalues is introduced in Chap. 14. The representation of vectors and operators in terms of numerical components and matrices is discussed in detail in Chaps.14, Chaps.15, and Chaps.16.

Sections 12.5-1 through Sections12.6-3 serve as a brief introduction to mathematical models which permit the definition of limiting processes and

* The word algebra has three loosely related meanings: (1) a general subject, as used here (abstract algebra, elementary algebra); (2) the theory of algebraic operations used in connection with a specific model (matrix algebra, tensor algebra); (3) a type of mathematical model (a linear algebra, a Boolean algebra).

order. In particular, Secs.12.5-2 through sec.12.5-4 deal with metric spaces. Sections12.7-1 through Secs.12.7-5 discuss simple schemes for combining mathematical models (direct products and direct sums).

12.1-3. “Equality” and Equivalence Relations, (a) The descriptive definition of each class of mathematical objects discussed in this Chapter is understood to imply the existence of a rule stating whether or not two given mathematical objects a, b are “equal” (equivalent or indistinguishable in the context of the model, a = b) ; the rule must be such that

image

Sections 13.2-2 and Sections 16.3-1 show examples of the definition of equality in constructively defined models.

(b) More generally, any relation image between two objects a, b of a class C is called an equivalence relation if and only if it is reflexiveimage, symmetric image and transitiveimage. Every equivalence relation defines a partition of the class C, i.e., a subdivision of C into subclasses without common elements. Elements of the same subclass are equivalent with respect to the properties defining the equivalence relation.

EXAMPLES: Equality, identity of functions (Sec.1.1-4), congruence and similarity of triangles, metric equality (Sec.12.5-2), isomorphism (Sec.12.1-6).

12.1-4. Transformations, Functions, Operations (see also Sees.Secs.4.2-1 , Sec.14.1-3, and Secs.12.1-3 Sec.14.3-1). A set of rules xx′ associating an object x′ of a class C′ with each object x of a class C is called a transformation (mapping) of C into C′; x′ is a function

image

of the argument x, with domain (domain of definition) C and range C′. C and C′ may or may not be the same class of objects. The correspondence (1) can be regarded as an operation on the operand x producing the result (transform) x′. given suitable definitions of equality in C and C′ (Sec. 12.1-3), an operation (transformation, function) (1) is well denned if and only if x = y implies x′= y′, This property will be understood to apply unless the contrary is specifically stated.

A correspondence (1) is unique [f(x) is a single-valued function of x] if and only if a unique object x′ corresponds to each object x. The correspondence is a reciprocal one-to-one (biunique) correspondence of C and C′ if and only if the relation (1) maps C uniquely onto all of C and defines a unique inverse correspondence (inverse transformation. Many authors categorically define every mapping as unique (see also footnote to Sec. 4.2-2). The set of pairs (x, x′) is called the graph of the function f(x).

Each object x in Eq. (1) can be a set of objects x1, x2, … ; so that it is possible to define functions x = f (x1 x2. . .) of two or more arguments.

A numerical (real or complex) function defined on a set of functions is called a functional [e.g.,image maximum value of φ( x) in (a, b)].

Transformations (functions, operations) can themselves be regarded as new mathematical objects (see, for example, Sec.14.3-1).

12.1-5. Invariance (see also . Secs12.2-8, Secs.13.4-1, Secs.14.4-5, Secs.16.1-4, and Secs.16.4-1). given a transformation (1) of a class (space) C into itself, any function F (x, y,. . .) such that F [f(x), f(y), . . . ] = F(x, y, . . .) for all x, y, ... in C and any relation 0(x, y, . . .) = A which implies 0[ f(x), f(y), . . . ] = A for all x, y, . . . in C is called invariant with respect to the transformation (1).

12.1-6. Representation of One Model by Another: Homomor-phisms and Isomorphisms. Let M be a mathematical model (Sec. 12.1-1) involving objects a, b, . . . and operations 0, P, . . . whose results 0(a, b, . . .), P(a, 6, ...),.. . are elements of M. * A second model M′ is a homomorphic image of M with respect to the operation 0(a, b, . . .) if and only if

image

A correspondence with these properties is called a homomorphism of M to M′ and preserves all relations based on the operation in question; i.e., each such relation between elements o, b, ... of M implies a corresponding relation between the elements a′ , b′. . . of M′, A homomorphism mapping the set of elements of M into itself (onto a subset of itself) is called an endomorphism.

An isomorphism is a homomorphism involving reciprocal one-to-one correspondence. Two models M and M′so related are isomorphic with respect to the operation in question; in this case both MM' and M′M are homomorphisms. An isomorphism mapping the set of elements of M onto itself is an automorphism of M.

*The elements a, b, . . . need not belong to a single class of mathematical objects (e.g., there may be vectors and scalars, Sec.12.4-1).

The concept of a homomorphism, and the related concepts of isomorphism and automorphism, are of the greatest practical importance, since they permit the representation of one model by another. One may, in particular, represent mathematical objects by sets of real numbers (analytical geometry, matrix and tensor representations). Note that isomorphism is an equivalence relation (Sec. Note that isomorphism is an equivalence relation12.1-3b) between models: properties of an entire class of isomorphic models may be derived from, or discussed in terms of, the properties of any model of the class.

Some writers require each homomorphism MM′ to map M onto all of M′. In this case the homomorphism defines an isomorphism relating disjoint classes of elements of M to elements of M′.

12.2. ALGEBRA OF MODELS WITH A SINGLE DEFINING OPERATION: GROUPS

12.2-1. Definition and Basic Properties of a Group, (a) A class G of objects (elements) a,b, c, . . . is a group if and only if it is possible to define a binary operation (rule of combination) which associates an object (result) a image b with every pair of elements a, b of G so that

image

Two elements a, b of a group commute if and only if a image b = b image a. If all elements a, b of a group G commute, the defining operation of G is commutative, and G is a commutative or Abelian group. A group G containing a finite number g of elements is of finite order g; otherwise G is an infinite group (of infinite order). In the latter case, G may or may not be a countable set (see Sec. 12.2-11 for a brief discussion of continuous groups).

(b) Every group G has a unique left identity and a unique right identity, and the two are identical (E image a = a image E = a). Each element a has a unique left inverse and a unique right inverse, and the two are identical (a-1 image a = a image a-1 = E).

Hence

image

G contains a unique solution x of every equation c image x = b or x image c = b; i.e., unique right and left “division” is possible.

(c) The operation defining a group is often referred to as (abstract) multiplication (note, however, Sec.12.2-10); its result is then written as a product ab, and the inverse of a is written as a-l. This convention is freely used in the following sections.

Multiple products aa, aaa, . . . are written as integral powers a2, a3, . . . , with (a-1)n = a-n, a0 = E. Note

image

12.2-2. Subgroups. A subset G1 of a group G is a subgroup of G if and only if G1 is a group with respect to the defining operation of G. This is true (1) if and only if G1 contains all products and inverses of its elements, i.e., (2) if and only if G1 contains the product ab-l for each pair of elements a, b in G1.

The intersection (Sec. 4.3-2a) of two subgroups of G is a subgroup of G. G and E are improper subgroups of G; all other subgroups of G are proper subgroups. If G is of finite order g (Sec. 12.1-la), the order g1 of every subgroup G1 of G is a divisor of g (Lagrange's Theorem); g/g1 is called the index of G1 (with respect to G).

12.2-3. Cyclic Groups. Order of a Group Element. A cyclic group consists of the powers a0 = E, a, a2, . . . of a single element a and is necessarily commutative. Every group of prime order and every subgroup of a cyclic group is cyclic.

Each element a of any group G “generates” a cyclic subgroup of G, the period of a. The order of this subgroup is called the order of the element a and is equal to the least positive integer m such that am = E.

12.2-4. Products of Complexes. Cosets. (a) Every subset C1 of a group G is called a complex. The product* C1C2 of two complexes C1 ,C2 of G is the set of all (different) products aia2 of an element a1 of c1 and an element a2 of C2. C1 C1 = C1 if and only if C1 is a subgroup of G. The product G1G2 of two subgroups of G is a subgroup of G if and only if G1G2 = G2G1.

(b) A left coset xG1 of a subgroup G1 of G is the set of all products xa1 of a G1ven element x of G and any element a1 of G1. A right coset G1x is, similarly, the set of all products a1x. A coset of G1 is a subgroup of G if and only if x is an element of G1; in this case xG1 = G1x = G1. Two left cosets of G1 are either identical or have no common element; the same is true for two right cosets. Every subgroup G1 of G defines a partition ( Sec. 12.1-3) of G into a finite or infinite number n1 of left cosets, and a partition of G into n1 right cosets; if G is of finite order g, n1 equals the index g/G1 of G1 (Sec.12.2-2). Two elements a,bof G belong to the same left coset of G1 ifG1 contains a-lb, and to the same right coset of G1 if G1 contains ba-l.

12.2-5. Conjugate Elements and Subgroups. Normal Subgroups. Factor Group, (a) Two elements x and x′ of a group G are conjugate if and only if they are related by a transformation (Sec.12.1-4).

image

* The product C1C2 of two complexes must not be confused with their intersection (logcal product, Sec. 4.3-2a) C1 ∩ C2, or with a direct product (Sec. 12.7-2).

where a is an element of G. x! is then called the transform of x under conjugation by a. Conjugation is an equivalence relation (Sec. 12.1-3b) and defines a partition of G into classes of conjugate elements.

(b) A transformation (3) transforms each subgroup G1 of G into a conjugate subgroup G′1 = a-lG1a. G1 is mapped onto itself (G′1= G1) for every a in G (1) if and only if the elements at of G1 commute with every element a of G (aG1 = G1a) or (2) if and only if G1 contains all conjugates of its elements. A subgroup distinguished by these three properties is called a normal subgroup (normal divisor, invariant subgroup) of G.

Every subgroup of index 2 ( Sec.12.2-2) is a normal subgroup of G. A simple group, contains no normal subgroup except itself and E.

(c) The left cosets (Sec. 12.2-4b) of a normal subgroup are identical with the corresponding right cosets and constitute a group with respect to the operation of multiplication defined in Sec. 12.2-4a; this group is the factor group (quotient group) G/G1. If G is of finite order, the order of G/G1 equals the index g/g1 of G1 (Sec. Sec.12.2-2).

12.2-6. Normal Series. Composition Series. For any group G, a normal series is a (finite) sequence of subgroups Go = G, G1 G2, . . . , Gm = E such that each Gi is a normal subgroup of Gi-1. A normal series is a composition series of G if and only if each Gi is a proper normal subgroup of Gi-1 such that no further normal subgroups can be “interpolated” between Gi-1 and G1, i.e., if and only if each composition factor Gi1/Gi is a simple group (Sec.12.2-5). given any two composition series of the same group G, there exists a reciprocal one-to-one correspondence between their respective elements such that corresponding elements are isomorphic groups (Jordan-Holder Theorem). G is a solvable group if and only if all its composition factors are cyclic groups (Sec.12.2-3).

12.2-7. Center. Normalizers. (a) The set of all elements of G which commute with every element of G is a normal subgroup of G, the center or central of G.

(b) The set of all elements of G which commute with a given element a of G is a subgroup of G (normalizer of a), which contains the period of a ( Sec.12.2-3) as a normal subgroup.

The set of elements of G which commute with (every element of) a given subgroup G1 of G is a subgroup of G (normalizer of G1), which contains G1 as a normal subgroup.

The number of different elements or subgroups of G conjugate (Sec. 12.2-5) to the element or subgroup associated with a normalizer equals the index (Sec. 12.2-2) of the normalizer.

12.2-8. Groups of Transformations or Operators (see also Secs. Secs12.1-4, Secs14.9-1 to Secs14.10-7, and Secs.16.1-2). The set G of all reciprocal one-to-one (nonsingular) transformations x′ = f(x) of any class C onto itself is a group; the defining operation is the successive application of two transformations (multiplication of transformations or operators).

given any subgroup G1 of G, two objects x, x′ related by a transformation x′ = f(x) of G1 are equivalent under G1. This relationship is an equivalence relation (Sec.12.1-3 ), so that each subgroup G1 defines a partition (classification) of C. Every property invariant (Sec. 12.1-5) with respect to (all transformations of) G1 is common to all objects x equivalent under G1. A set of (usually numerical) functions F1 (x), F2(x), . . . invariant with respect to G1 is a complete set of invariants with respect to G1 if and only if the set of function values uniquely defines the equivalence class of any given object x of C.

EXAMPLES OF TRANSFORMATION GROUPS: All nǃ permutations (see also Appendix C) of n elements (symmetric group on n elements); all nǃ/2 even permutations corresponding to even numbers of interchanges of n elements (alternating group on n elements). Every permutation of a countable set S of objects can be expressed as a product of cyclic permutations of subsets of S so that no two such cycles affect the same elements of S.

12.2-9. Homomorphisms and Isomorphisms of Groups. Representation of Groups (see also Secs.12.2-4, Secs.12.2-5, and Secs.14.9-1 toSecs.14.10-7 ). (a) A homomorphism or isomorphism (with respect to the denning operation, Sec. Secs.12.1-6) maps the elements a, b, ... of a given group G onto the elements a′, b′, ... of a new group G′ so that (ab)′a′b′. The identity of G is mapped onto the identity of G′, and inverses are mapped onto inverses.

For every homomorphism of G ontoG′, the identity of G′ corresponds to a normal subgroup GE of G, and each element of G′corresponds to a coset G/GE; the factor group G/GE is isomorphic with G′. GE is called the kernel of the homomorphism. Every normal subgroup G1 of G is the kernel of a homomorphism mapping G onto the factor group G/G1.

The class of all automorphisms of any group G is a group; the class of all transformations (3) of G (inner automorphisms of G) is a subgroup of the automorphism group. Conjugate subgroups are necessarily isomorphic.

(b) Every group G can be realized (represented) by a homomorphism relating the group elements to a group of transformations mapping some class of objects onto itself (Cayley's Theorem; see also Sec.12.1-8). In particular, every group of finite order is isomorphic to a group of permutations (regular representation of a finite group, Sec. 14.9-la). Refer to Sees. Secs.14.9-1 to Secs.14.10-7 for representations of groups in terms of linear transformations and matrices.

12.2-10. Additive Groups. Residue Classes and Congruence. (a) The defining operation of a commutative group (Abelian group, Sec. 12.2-la) is often referred to as (abstract) addition. Its result may be written as a sum a + b, and the identity and inverse are written, respectively, as 0 (zero or null element) and –a, so that

image

The group is then called an additive group (addition group, module), and expressions like a+ a, a + a + a, –aa, . . . may be written as 2a, 3a, –2a, ....

(b) Every subgroup of a commutative group is a normal subgroup. The cosets of a subgroup G1 of an additive group G are called residue classes modulo G1; two elements a, b of G belonging to the same residue class (i.e., G1 contains a – b; see also Sec. 12.2-46) are congruent modulo G1 [a = b(G1)]. Congruence is an equivalence relation (Sec. Secs.12.1-3; see also Sec. 12.2-4b). The factor group G/G1 of an additive group G is the group of residue classes modulo G1 and may be denoted by G modulo G1.

Two real integers m, n are congruent modulo r [m = n(r)], where r is a third real integer, if and only if mn is a multiple of r, so that m/r and n/r have equal remainders.

12.2-11. Continuous and Mixed-continuous Groups, (a) The elements of a continuous group G can be labeled with corresponding sets of continuously variable parameters so that the parameters γ1, γ2, . . . of the product c = ab are continuously differentiable functions of the parameters α1, α2, . . . of a and the parameters β1, β 2, . . . of b. The parameters may, for instance, be the matrix elements in a representation of G (EXAMPLE: the three-dimensional rotation group, Sec.14.10-7).

(b) A mixed-continuous group G is the union of n1 separated (Sec. 12.5-16) subsets “connected” in the sense of Sec. 12.2-1 la (n1 = 1, 2, . . .). The connected subset G1 containing the identity element is a normal subgroup of G with index m; the other connected subsets of G are the cosets associated with G1 (see also Sec. 12.2-4 and Sec. 12.2-5. EXAMPLE: the reflection-rotation group in three-dimensional Euclidean space, see also Sec. 14.10-7).

12.2-12. Mean Values. The mean value of a numerical function F(a) defined on the elements a of a group G is a linear functional (Sec.12.1-4) defined for a group G of finite order g as

image

More generally, for a suitable numerical function F(a) defined on a continuous or mixed-continuous group G,

image

where the “volume element” dU(a) is defined in terms of the parameters α ii, and γi introduced in Sec.12.2-1 by

image

The definition (5) applies also to countably infinite and finite groups if the integrals are interpreted as Stieltjes integrals (Sec. 4.6-17) and reduces to Eq. (4) for finite groups.

The definition of Mean {F(a)} implies

image

for every fixed element a0 in G.

12.3. ALGEBRA OF MODELS WITH TWO DEFINING OPERATIONS: RINGS, FIELDS, AND INTEGRAL DOMAINS

12.3-1. Definitions and Basic Theorems, (a) A class R of objects (elements) a, b, c, ... is a ring if and only if it is possible to define two binary operations, usually denoted as (abstract) addition and multiplication, such that

image

Note that a0 = 0a = 0 for every element a of R. Two elements p and q of R such that pq = 0 are called left and right divisors of zero. For a ring without divisors of zero (other than zero itself), ab = 0 implies a = 0, or b= 0, or a = b = 0, ana! tae cancellation laws (12.2-1) hold.

“Multiples” of ring elements like 2a, 3a, . . . (Sec. 12.2-10a) are not in general products of ring elements. Integral powers of ring elements are denned as in Sec. 12.2-lc.

(b)A ring with identity (unity) is a ring containing a multiplicative (left) identity E such that Ea = a for all a (see also Sec. 12.2-la). E is necessarily a unique right identity as well as a unique left identity. A given element a of a ring with identity may or may not have a multiplicative (left) inverse a-1; if a-l does exist, it is necessarily a unique right inverse as well as a unique left inverse (see also Sec.12.2-1).

(c) A field* is a ring with identity which contains (1) at least one element different from zero and (2) a multiplicative inverse a-1 for each element a ≠ 0. The nonzero elements of a field F constitute a group with respect to multiplication.

Given any pair of elements b, a ≠ 0 of F, the equations cx = b and xc = b have solutions in F. These solutions are unique whenever b ≠ 0 (unique left and right division, see also Sec.12.2-16); they are unique even for b ≠ 0 if F is a field without divisors of zero.

(d) A ring or field is commutative if and only if ab = ba for all a, b. A commutative field is sometimes simply called a field, as opposed to a skew or noncommutative field. A Galois field is a finite commuta tive field. An integral domain is a commutative ring with identity and without divisors of zero. Every finite integral domain is a Galois field.

In every integral domain all nonzero elements of the additive group have the same order (Sec.12.2-3). This order is referred to as the characteristic of the integral domain.

(e) Refer to Sec.12.6-3 for a brief discussion of ordered fields.

* Some writers require every field to be an integral domain (Sec. 12.3-ld).

EXAMPLES OF FIELDS: rational numbers, real numbers, complex numbers; continuous functions defined on a finite interval (has zero divisors); polynomials. EXAMPLES OF INTEGRAL DOMAINS: real integers, complex numbers with integral coefficients. EXAMPLE OF A COMMUTATIVE RING WITHOUT IDENTITY: even integers.

12.3-2. Subrings and Subfields. Ideals. (a) A subset R1 of a ring R is a subring of R if and only if it is a ring with respect to the defining operations of R. This is true if and only if R1 contains a – b and ab for every pair of its elements a, b. Similarly a subset Fi of a field F is a subfield of F if and only if it is a subring of F comprising at least one nonzero element and contains ab-l for every pair of elements a, b of F1. The nonzero elements of Fi constitute a subgroup of the multiplicative group of F.

(b) A subset I1 of a ring R is an ideal in R if and only if

1. I1 is a subgroup of R with respect to addition.

2. I1 contains all products ab (left ideal), or all products ba (right ideal), or all products ab and ba (two-sided ideal), where a is any element of I1, and b is any element of R.

12.3-3. Extensions. It is often possible to “imbed” commutative rings or fields as subrings or subfields in “larger” fields (quotient fields, algebraic extension fields, etc.) in a manner analogous to that outlined in Sec.1.1-2 for the real integers (see also the example in Sec.12.4-2 Sec.12.4-2). The theory of fields, including the so-called Galois theory, deals with the existence of such extensions (APPLICATIONS: investigation of the possibility of constructions with ruler and compass, of solving algebraic equations in terms of radicals, and of constructing latin squares; Refs. 12.1 and 12.9).

12.4. MODELS INVOLVING MORE THAN ONE CLASS OF MATHEMATICAL OBJECTS; LINEAR VECTOR SPACES AND LINEAR ALGEBRAS

12.4-1. Linear Vector Spaces. Let R be a ring with (multiplicative) identity 1 (Sec. 12.3-1b); the elements α, β, ... of R shall be referred to as scalars. A class υ of objects (elements a, b, c, ... is a (linear) vector space over the ring R, and the elements of υ are called vectors if and only if it is possible to define two binary operations called vector addition and multiplication of vectors by scalars such that*

image

* Some authors require that υ contain not only every sum of two vectors, but also every infinite sum a1 + a2 + . . . which converges in some specified sense; vector spaces defined in this manner are not in the realm of algebra proper (see also Sec.14.2-1).

image

Note that

image

Linear vector spaces are of fundamental importance in applied mathematics; they are treated in detail in Chap.14 (see also Chaps. Chap.5, Chap.6, Chap.15, Chap.16, and Chap.17).

12.4-2.Linear Algebras. Given a ring R of scalars with identity 1, a class L is a linear algebra (linear associative algebra, system of hypercomplex numbers) over the ring R if and only if it is possible to define three binary operations (addition and multiplication in L and multiplication of elements of L by scalars) such that

image

The order of a linear algebra is its dimension as a vector space (Sec.14.2-4). A linear algebra is a division algebra if and only if it is a field (Sec. 12.3-lc). Refer to Sec.14.9-7 for matrix representations of linear algebras.

An element A a≠ 0 of any linear algebra is idempotent if and only if A2 = A and nilpotent if and only if there exists a real integer m > 1 such that Am = 0. These definitions apply, in particular, to matrices (Sec.13.2-2) and to linear operators (Sec.14.3-6).

EXAMPLES (see also Sees. Sec.13.2-2 and Sec.14.4-2): (1) The field of complex numbers is a commutative division algebra of order 2 over the field of real numbers. (2) The field of quaternions a, b, ... is the only extension (Sec.12.3-3) of the complex-number field which constitutes a noncommutative division algebra over the field of real numbers. Every quaternion a can be represented in the form

image

where α0, α1, α2, α3 as are real numbers, and i, j, k are special quaternions (generators) satisfying the multiplication rules

image

If one defines a* = α0 - 1 - 2- kα 3, then

image

image

(see also Sec. Sec.14.10-6).

12.5. MODELS PERMITTING THE DEFINITION OF LIMITING

PROCESSES: TOPOLOGiCAL SPACES

12.5-1. Topological Spaces(refer to Sec.4.3-2 for elementary properties of point sets). (a) A class C of objects (“points”) x is a topologi1cal space if and only if it can be expressed as the union of a family 3 of point sets which contains

1. The intersection of every pair of its sets

2. The union of the sets in every subfamily

j is a topology for the space C, and the elements of j are called open sets relative to the topology j. A family (B of open sets is a base for the topology j if and only if every set of j is the union of sets in image.

The intersections of any subset C1 of a topological space C with its open sets constitute a topology for C1 (relative topology of the subspace C1 of C, relativization of 3 to C1).

A given space may admit more than one topology; every space C admits the indiscrete (trivial) topology comprising only C and the empty set, and the discrete topology comprising all subsets of C.

(b) For a given topology, a neighborhood of a point x in C is any point set in C which contains an open set comprising x. given the definition of neighborhoods, one defines limit points, interior points, boundary points, and isolated points of sets in the manner of Sec. 4.3-6a; topological spaces are seen to abstract and generalize certain features of the real-number system.

In any topological space C, a point set is open if and only if it contains only interior points; a point set S in C is closed (1) if and only if S is the complement (with respect to C) of an open set, or (2) if and only if S contains all its limit points (alternative definitions). S is dense in (relative to) C if and only if every neighborhood in C contains a point of S. A topological space C is separable if and only if it contains a countable dense set; this is true whenever the topology of C has a countable base.

A topological space is compact if and only if every infinite sequence of points in C has at least one limit point in C; this is true if and only if every family of open sets which covers (i.e., whose union exhausts) C has a finite subfamily which covers C (alternative definition). Every compact space is separable.

A point set S in a topological space C is compact (compact in C) if every infinite sequence of points in S has at least one limit point in C; S is compact in itself if every such sequence has a limit point in S.

Separable spaces are of special interest because their points can be labeled with countable sets of coordinates (Sec.14.5-1). Compactness is a generalization of the concept of boundedness (Sec.4.3-3) in finite-dimensional spaces, where the Bolzano-Weierstrass and Heine-Borel theorems apply (Sec.12.5-4).

(c) The limit points and the boundary points of a set S respectively constitute its (first) derived set S′and its boundary. The closed set S ∪ S′ is the closure of S. Two sets are separated if and only if neither intersects the closure of the other. A set is connected if and only if it cannot be expressed as the union of separated proper subsets (EXAMPLE: connected region in a Euclidean space, Sec. 4.3-6b).

(d) Continuity. Homeomorphisms. A correspondence (mapping, transformation, function, operation) xx′ = f(x) relating points x′ of a topological space C′ to points x of a topological space C is continuous at the point x = a if and only if f(a) exists and every neighborhood of f(a) is the image of a neighborhood of a. f(x) is continuous if and only if it is continuous at all points of C, i.e., if and only if every open set in C′ is the image of an open set in C.

A continuous reciprocal one-to-one correspondence having a continuous inverse is a homeomorphism or topological transformation; topological spaces so related are homeomorphic or topologically equivalent.

(d) Topology is the study of relationships invariant with respect to homeomorphisms (topological invariants; see also Sec.12.1-5). Topology has geometrical applications (“rubber-sheet geometry, ” study of multiply connected surfaces, etc.); more significantly, suitable topological spaces are models permitting the definition of converging limiting processes with the aid of the neighborhood concept (see also Secs.4.3-5, Secs.4.4-1, and Secs.12.5-3). Definitions of specific topologies are often phrased directly as definitions of neighborhoods or convergence.

EXAMPLES: The definition of neighborhoods given in Sec. 4.3-5a establishes the “usual” topology of the real-number system and permits the introduction of limits, differentiation, integration, infinite series, etc. Similarly,Sec. 5.3-1 amounts to the definition of a topology for the space of Euclidean vectors (see also Secs. 12.5-3 and Secs.14.2-7).

12.5-2. Metric Spaces. A class CM of objects (“points”) x, y, z, . . . is a metric space if and only if for each ordered pair of points x, y of C it is possible to define a real number d(x, y) (metric, distance function, “distance” between x and y) such that for all x, y, z in CM

image

This definition implies

image

for all x, y in CM.

x and y are metrically equal if and only if d(x, y) = 0; this does not necessarily imply x = y. Metric equality is an equivalence relation (Sec. 12.1-3b).

Two metric spaces are isometric if and only if they are related by a distance-preserving reciprocal one-to-one correspondence (isometry). Properties common to all metric spaces isometric to a given metric space are metric invariants.

EXAMPLES: The (finite) real and complex numbers constitute metric spaces with the metric d(x, y)/x - y/. More generally, every normed vector space (Sec.14.2-5), and thus every unitary vector space, admits the metric d(x} y) ≡ ||x- y|| (see also Secs. 14.2-7 and Sec.15.2-2).

12.5-3. Topology, Neighborhoods, and Convergence in a Metric Space, (a) given any point a of a metric space CM, the set (region) of points x in CM such that d(a, x) < δ is called an open ball of radius δabout a. The open balls of finite radii constitute a base for a topology in CM (Sec. 12.5-la); open sets are unions of open spheres. A neighborhood of the point a in CM is any set containing an open ball of finite radius about a. d(a,x) ≤ r defines a closed ball in CM, and d(a, x) = r defines a sphere.

(b) A sequence of points x0, x1, x2 . . . of a metric space CM is said to converge (metrically) to the limit a in CM if and only if d(xn, a) → 0 as n → ∞ (see also Sec. 14.2-7).

If a variable point x(ξ) of CM is a function of the real variable ξ, x(ξ) converges (metrically) to the limit a in CM as ξ → αif and only if d[x(ξ), α] → 0 as ξ → a. x(ξ) is continuous for ξ = α (Sec. 12.5-lc) if and only if x(a) exists and d[x(ξ), x(α)] → 0 as ξ→ α. A function x′ = f{x) relating points x′ of a metric space C′M to points x′ of a metric space CM is continuous (Sec. 12.5-1 c) at the point x = a if and only if x(a) exists and d[f(x), f(a)]0 as d[x, a]0.

12.5-4. Metric Spaces with Special Properties. Point-set Theory

(see also Secs. 4.3-6 and 12.5-1). A metric space CM is

    Complete if and only if every sequence of points x1, x2, ... of CM such that image(Cauchy sequence) converges to a point of CM (see also Secs.4.9-la, 4.9-2a, 4.9-3a, 14.2-7, andSecs.15.2-2).

    Precompact if and only if, for every real ∊ > 0, there exists a finite set of balls of radius less than ∊ covering CM.

    Conditionally compact if and only if every infinite set of points in CM contains a Cauchy sequence.

    Boundedly compact or boundedly conditionally compact if and only if every closed ball in CM is, respectively, compact or conditionally compact.

Every closed set in a metric space is a subspace with the same metric. A point set S in a complete metric space CM is a complete metric subspace if and only if S is closed. Every set compact in itself (Sec. 12.5-1) is bounded. A metric space is compact if and

only if it is precompact and complete; every precompact metric space is separable. Every finite-dimensional unitary vector space (Euclidean vector space, Sec.14.2-7Sec. 14.2-7) is separable, complete, and boundedly compact; in every Euclidean vector space

1. Every infinite point set contained in a closed ball Ka of finite radius has at least one limit point in Ka (Bolzano-Weierstrass Theorem).

2. Given any rule associating a ball Ka of finite radius with each point x of a closed set S contained in a ball of finite radius, there exists a finite set of these balls which covers (includes) all points of S (Heine-Borel Covering Theorem).

These theorems apply, in particular, to sets of real or complex numbers, and to point sets in two- or three-dimensional Euclidean spaces.

12.5-5. Examples: Spaces of Numerical Sequences and Functions.

The concepts introduced in Secs. 12.5-2 to Secs.12.5-4 offer a concise and suggestive terminology for many problems involving the approximation of an arbitrary element of a suitable class CM by a sequence of elements x1, x2, . . . of CM. In such instances, the distance d(xn, x) measures the error of the approximation, or the degree to which a system characterized by x1, x2, . . . fails to meet a performance criterion.

Table 12.5-1 lists a number of examples of topological spaces. Especially important applications involve the approximation of a function f(t) by a sequence of functions s1(t), s2(t),... such as the partial sums of an infinite series (see also Secs. 4.7-3,Secs.5.3-11 , Secs.13.2-1, 13.2-11, Secs.14.2-7, and Secs.15.2-2).

12.5-6. Banaeh's Contraction-mapping Theorem and Successive Approximations. Let x′ = f(x) be any transformation mapping the

Table 12.5-1a Some Spaces of Numerical Sequences

image

image

Table 12.5-1b. Some Spaces of Functions x(t), y(t) (see also secs. 14.2-7, 15.2-2, and 18.10-9; the definitions are readily extended to functions of two or more variables)

image

closed set S of a complete metric space CM into itself so that

image

for all x, y in S, where α is a positive real number less than unity (“contraction mapping”). Then S contains a unique fixed point xf of the mapping f such that

image

Moreover, the solution xf of the equation (3) is the limit of every sequence of successive approxim ations

image

as n →for an arbitrary starting point x0 in S. The rate of convergence of the approximation sequence is given by

image

The contraction-mapping principle furnishes a powerful method for establishing the convergence of a wide range of approximation techniques (Secs. 20.2-1,Secs. 20.2-6, and Secs.20.3-5).

12.6. ORDER

12.6-1. Partially Ordered Sets, (a)Order. A class (set) S of objects (elements) a, b, c, . . . is partially ordered if and only if it admits a transitive ordering relation (rule of precedence) a <b between some pairs of elements a, b so that

image

a < bmay or may not preclude b < b (antisymmetry). The symbol ≤ is used to indicate a reflexive ordering relation which satisfies the condition a ≤ a for all a.

A partially ordered set permits the definition of upper bounds, lower bounds, least upper bounds, greatest lower bounds, maxima, and/or minima of suitable subsets in the manner of Sec. 4.3-3. A partially ordered set S is order-complete if and only if every nonempty subset having an upper bound has a least upper bound in S; this is true if and only if every nonempty subset having a lower bound has a greatest lower bound in S (alternative definitions).

(b) Lattices.A (nonempty) class of objects (elements) a, b, ... is a lattice if and only if it admits a reflexive ordering relation such that every pair a, b of elements has a unique least upper bound sup (a, b) and a unique greatest lower bound inf (a, b). In every lattice one can define “sums” a + b ≡ sup (a, b) and “products” ab ≡ inf (a, b). Sums and products so defined have the properties 1, 2, 3, 5 listed in Sec. 12.8-1 for Boolean algebras.

12.6-2. Simply Ordered Sets.A class (set) S of elements a, b, c, . . . is a simply (linearly, totally, completely) ordered set (chain) if and only if it admits an ordering relation having the transitivity property (1) and such that*

image

The ordering relation may or may not be reflexive, but every simply ordered set admits the reflexive ordering relation defined by a ≤ b if a < b or a = b.

A simply ordered set S is well ordered if and only if every nonempty subset of S has a minimum. Every countable simply ordered set is well ordered.

. Ordered Fields (see also Secs. 1.1-5 and Secs.12.3-1). (a) A commutative field is an ordered field if and only if each element can be uniquely classified as “positive” (>0), “negative” (<0), or zero (= 0) in such a way that

image

(b) Every order-complete (Sec.12.6-la) ordered field is isomorphic (with respect to addition and multiplication) with the field of real numbers. Every ordered integral domain whose positive elements are well ordered (Sec.12.6-2) is isomorphic with the field

*Some authors replace the second condition (2) by <a < b precludes b <a.

of real integers. The last theorem expresses the equivalence of binary numbers, decimal numbers, roman numerals, etc.

12.7. COMBINATION OF MODELS: DIRECT PRODUCTS, PRODUCT SPACES, AND DIRECT SUMS

12.7-1. Introduction. Cartesian Products. Sections Sec.12.7-1 to Sec.12.7-5 deal with a class C of mathematical objects described in terms of two or more properties(a1, a2, . . .} of objects ai, a2) . . . respectively taken from suitably denned classes C1, C2, . . . . The objects a1, a2, . . . may be regarded as properties or attributes of the new object {a1, a2, . . .}; one defines

image

if and only if a1 = b1, a2 = b2 , . . . . The class C is called the cartesian product of the classes C1, C2, . . . . This method of combining mathematical objects into more complicated mathematical objects is associative:

image

It remains to relate operations in C to operations in C1, C2, . . . .

12.7-2. Direct Products of Groups(see also Sec. 12.2-1). The direct product G = G1 0 G2 of two groups G1 and G2 having the respective elements a1, b1, . . . and a2, b2, . . . is the group comprising all ordered pairs {a1, a2}, with “multiplication” defined by

image

The order of G equals the product of the orders of G1 and 2. G has the identity E = {E1, E2}, where E1 and E2 are the respective identities of G1 and G2. If G1 and G2 have no common elements, one may write {a1, a2} as an outer product a1a2, so that a1E2 = a1, E1a2 = a2, and G1 and G2 are subgroups of G.

EXAMPLES: Each scalar quantity in physics is an outer product of a number and a unit of measurement. Expressions like work = mass X acceleration X displacement are outer products.

12.7-3. Direct Products of Real Vector Spaces(see also Secs. 12.4-1, Secs.14.2-1, and Secs.14.2-4). The direct product υ = υ1 Φ υ2 of two real vector spaces υ1 and υ1 having the respective elements a1 , b1 , . . . and a2, b2, . . . is the real vector space comprising all ordered pairs (outer products) {a1, a2} ≡ a1a2, with vector addition and multiplication of vectors by scalars defined so that

image

The linear dimension of the vector space V equals the product of the linear dimensions of υ1 and υ2.

EXAMPLE: Construction of tensors as outer products of vectors,Secs. 16.3-6, Secs.16.6-1, and Secs.16.9-1.

12.7-4. Product Space(see also Sec. 12.5-la). The product space formed by two topological spaces C1, C2 is their cartesian product with the product topology (family of open sets in the product space) defined as the family of all cartesian products of S1 and S2, where S1 is an open set in C1, and S2 is an open set in C2.

12.7-5. Direct Sums. (a) The direct sum υ = υ1 ⊕ υ2 of two vector spaces υ and υ2 having the respective elements a1, b1, . . . and a2, b2, . . . and admitting the same ring R of scalars is the vector space comprising all pairs [a1, a2] ≡ [a2, a1] with vector addition and multiplication of vectors by scalars a of R defined so that

image

The dimension of υ equals the sum of the dimensions of υ1 and υ2. If υ1 and υ2 have no common elements, one may write [a1, a2]a1 + a2, and υ1 and υ2 are subspaces of υ′. Every linear vector space of dimension greater than one can be represented as a direct sum of nonintersecting subspaces.

(b) The direct sum R′ = R1R2 of two rings R1 and R2 having the respective elements a1, b1, . . . and a2, b2, . . . is the ring comprising all ordered pairs (often referred to as direct sums) [a1, a2] with addition and multiplication defined so that

image

(c) The direct sum of two linear algebras (Sec. 12.4-2) is the linear algebra of ordered pairs, with addition, multiplication, and multiplica tion by scalars defined as in Eqs. (4) and (5).

12.8. BOOLEAN ALGEBRAS

12.8-1. Boolean Algebras. A Boolean algebra is a class image of objects A, B, C, . . . admitting two binary operations, denoted as (logical) addition and multiplication, with the following properties:

image

In every Boolean algebra,

image

image

image

image

If A + B = B, one may write ÃB as B - A (complement of A with respect to B). Two or more objects A, B, C, . . . of a Boolean algebra are disjoint if and only if every product involving distinct elements of the set equals 0.

The symbols ∪ (cup) and ∩ (cap) used in Secs. 4.3-2a, Secs.12.8-5b, and Secs.18.2-1 to denote union and intersection of sets and events are frequently employed to denote logical addition and multiplication in any Boolean algebra; so that A ∪ B stands for A + B, and AB stands for AB.

12.8-2. Boolean Functions. Reduction to Canonical Form. Given n Boolean variables X1 X2, . . . , Xn each of which can equal any element of a given Boolean algebra, a Boolean function

image

is an expression built up from X1 X2, . . . , Xn through addition, multiplication, and complementation.

In every Boolean algebra, there exist exactly 2(2n) different Boolean Junctions of n variables.

The relations of Sec. 12.8-1 imply

image

image

image

(b)Every Boolean function is either identical to 0 or can be expressed as a unique sum of minimal polynomials (canonical minterms) Z1Z2 . . . Zn, where Zi is either Xi or Xi (canonical form of a Boolean

image

FIG. 12.8-1. A Venn diagram (Euler diagram). Diagrams of this type illustrate relations in an algebra of classes (Sec. 12.8-5). If the rectangle, circle, square, and triangle are respectively labeled by I, X1 X2, X3, the diagram shows how a Boolean function of X1 X2, X3 can be represented as a union of minimal polynomials in X1 X2, X3 (Sec. 12.8-2). Note that there are 23 = 8 different minimal polynomials.

function; see Fig. 12.8-1 for a geometrical illustration). A given Boolean function Y = F(X1, X2, . . . , Xn) may be reduced to canonical form as follows:

Use Eq. (2) to expand complements of sums and products.

Reduce F(X1, X2, . . . , Xn) to a sum of products with the aid of the first distributive law.

Simplify the resulting expression with the aid of the identities XiXi ≡ Xi, XiXi ≡ 0, and Eq. (4).

If a term f does not contain one of the variables, say Xi, rewrite f asfXi + fi.

In many applications, it may be advantageous to omit step 4 and to continue step 3 so as to simplify each term of the expansion as much as possible (see also Sec. 12.8-7).

In view of de Morgan's laws (2), every Boolean function not identically zero can also be expressed as a unique product of canonical maxterms Z1 + Z2 + . . . + Zn’ where Zi is either Xi or %i. There are, altogether, 2n minterms and 2n maxterms.

EXAMPLES:

image

12.8-3. The Inclusion Relation (see also Sec. 12.6-1). (a) Either A + B = B or AB = A is equivalent to a reflexive partial ordering relation A ≤ B [or B ≥ A; (logical) inclusion relation].

(b) In every Boolean algebra, A ≤ B,B ≤A implies A = B, and

image

where the bounds are defined by the inclusion relation. Every Boolean algebra is a lattice (Sec. 12.6-1b).

(c) Given any element A of a Boolean algebra image, the elements XA ≤ A of image constitute a Boolean algebra in which A takes the place of I.

12.8-4. Algebra of Classes. The subsets (subclasses) A, B, ... of any set (class) I constitute a Boolean algebra (algebra of classes) under the operations of logical addition (union), logical multiplication (intersection), and complementation defined in Sec. 4.3-2a. The empty set (or any set which contains no element of I) is denoted by 0. The relation ≤ (Sec. 12.8-2) becomes the logcal inclusion relation ⊂.

12.8-5. Isomorphisms of Boolean Algebras. Venn Diagrams. Two Boolean algebras are isomorphic (with respect to addition, multiplication, and complementation, Sec.12.1-6) if and only if they have the same number of elements. Every Boolean algebra is isomorphic to an algebra of classes (Sec. 12.8-4); Venn diagrams (Euler diagrams) like that shown in Fig. 12.8-1 conveniently illustrate the properties of Boolean algebras in terms of an algebra of classes.

12.8-6. Event Algebras and Symbolic Logic. Event algebras serve as models for the compounding of events (suitably defined outcomes of idealized experiments; see Sec. 18.2-1 for additional discussion). If E1, E2,. . . represent such events, then

E1 ∪ E2 represents the event (proposition) E1 OR E2 (or both; inclusive OR)

E1 ∩ E2 represents the event (proposition) E1 AND E2

represents the event (proposition) NOT E

I represents a certain event (union of all possible outcomes, Sec. 18.2-1)

0 represents an impossible event

In two-valued (Aristotelian) logic, an algebra of hypothetical events (logical propositions, assertions) E is related to a simpler Boolean algebra of truth values T[E] equal to either 1 (E is true) or 0 (E is false) by the homomorphism (Sec. 12.1-6)

image

On the basis of these assumptions, a proposition E is either true or false (law of the excluded middle), and the truth value of any proposition E expressible as a Boolean function of (“logically related to”) a set of events E1, E2, ... is given by

image

image

12.8-7. Representation of Boolean Functions by Truth Tables. Karnaugh Maps.Given a set of Boolean variables X1 X2, . . . , Xn each capable of taking the values 0 or 1 (Sec. 12.8-6), each of the 2(2n) Boolean functions

image

is uniquely defined by the corresponding truth table (Table 12.8-1) listing the function values for all possible arguments. Table 12.8-1 also lists a common arrange-

Table 12.8-1. *Truth Table for

image

* Based on J. V. Wait: Symbolic Logic and Practical Applications, in M. Klerer and G. A. Korn, Digital Computer User's Handbook, McGraw-Hill, New York, 1967. ment of the corresponding minterms (Sec. 12.8-2); each minterm is assigned the binary number determined by the arrangement of O's and l's in X, Y, Z. F is seen to equal the Boolean sum of the minterms corresponding to the function value 1 in the truth table.

image

FIG. 12.8-2. Karnaugh maps for two, three, four, and five Boolean variables (a) to (d), and a two-variable map for the function of Table 12.8-1, (e) (from Ref. 20.9).

A Karnaugh map is a Venn diagram (Secs. 12.8-5) providing for an orderly arrangement of squares corresponding to the 2n minterms generated by n variables (Fig. 12.8-2). Truth-table values for a given function F are entered into the appropriate squares; the given function F is then the union of all minterms labeled with a 1. For functions of up to perhaps six variables, the Karnaugh map makes it convenient to recombine these minterms into unions and/or intersections so as to minimize, say,

image

FIG. 12.8-3. Logic simplification with a karnaugh map. (Based on Ref. 20.9.)

the number of logical additions, multiplications, and/or complementations. This is useful for the economical design of digital-computer circuits (Fig. 12.8-3).

12.8-8. Complete Additivity and Measure Algebras (see also Secs. 18.2-1 and Secs.18.2-2). Many algebras of classes and event algebras require one to extend the defining postulates to unions and intersections of infinitely many terms (this is, strictly speaking, outside the realm of algebra proper, Sec. 12.1-2). A Boolean algebra image is completely additive if and only if every infinite sum A1 + A2 + . . . is uniquely defined as an element of image. A completely additive Boolean algebra image is a measure algebra if and only if there exists a real numerical function (measure) M{A) defined for all elements A of image so that

M(A) ≥ 0

M(0) = 0

M(Ai + A2 + . . .) = M(A1) + M(A2) + . . . for every countable set of disjoint elements A1, A2, . . .

EXAMPLES OF MEASURES: Cardinal number of a set (Sec. 4.3-2b), length, area, volume, Lebesgue and Stieltjes measures (Sec.4.6-14, Sec.4.6-17), truth value (Sec. 12.8-6), probability (Sec. 18.2-2).

12.9. RELATED TOPICS, REFERENCES, AND BIBLIOGRAPHY

12.9-1. Related Topics.The following topics related to the study of modern algebra and abstract spaces are treated in other Chapters of this handbook:

    Theory of equations, determinants Chap. 1

    Point sets Chap. 4

    Matrices, quadratic and hermitian forms Chap. 13

    Linear vector spaces, linear operators, eigenvalue problems, matrix repre sentations Chap. 14

    Function spaces, orthogonal expansions, eigenvalue problems involving differential and integral equations Chap. 15

    Tensor algebra and analysis Chap. 16

12.9-2. References and Bibliography.

Algebra (see also Sees. 1.10-2, 13.7-2, and 14.11-2)

     12.1. Barnes, W. E.: Introduction to Abstract Algebra, Heath, Boston, 1963.

     12.2. Birkhoff, G., and S. MacLane: A Survey of Modern Algebra, rev. ed., Macmillan, New York, 1965.

     12.3. Herstein, I. N.: Topics in Algebra, Blaisdell, New York, 1964.

     12.4. Johnson, R. E.: First Course in Abstract Algebra, Prentice-Hall, Englewood Cliffs, N.J., 1953.

     12.5. McCoy, N. H.: Introduction to Modern Algebra, Allyn and Bacon, Boston, 1960.

     12.6. Mostow, G. D., et al.: Fundamental Structures of Algebra, McGraw-Hill, New York, 1963.

     12.7. Schreier, O., and E. Sperner: Introduction to Modern Algebra and Matrix Theory, Chelsea, New York, 1955.

     12.8. Vander Waerden, B. L.: Modern Algebra, rev. ed., 2 vols., Ungar, New York, 1950-1953; 6th German edition, Springer, Berlin, 1964.

Boolean Algebras and Logic

    12.9. Church, A.: Introduction to Mathematical Logic, Princeton University Press, Princeton, N.J., 1956.

    12.10. Copi, I. M.: Symbolic Logic, Macmillan, New York, 1954.

    12.11. Flegg, H. G.: Boolean Algebra and Its Applications, Wiley, New York, 1964.

    12.12. Chu, Y.: Digital Computer Design Fundamentals, McGraw-Hill, New York, 1962.

     12.13. Hohn, F. E.: Applied Boolean Algebra, Macmillan, New York, 1960.

    12.14. Rosenbloom, P. C.: The Elements of Mathematical Logic, Dover, New York, 1951.

    12.15. Suppes, P. C.: Introduction to Logic, Van Nostrand, Princeton, N.J., 1958.

    12.16. Tarski, A.: Introduction to Logic and to the Methodology of Deductive Sciences, 2d ed., Oxford, Fair Lawn, N.J., 1946.

    12.17. Whitesitt, J. E.: Boolean Algebra and Its Applications, Addison-Wesley, Reading, Mass., 1961.

Switching Logic

    12.18. Caldwell, S. H.: Switching Circuits and Logical Design, Wiley, New York, 1958.

    12.19. Marcus, M. P.: Switching Circuits for Engineers, Prentice-Hall, Englewood Cliffs, N.J., 1962.

    12.20. Miller, R. E.: Switching Theory, vol. 1: Combinatorial Circuits, Wiley, New York, 1965.

Topology (see also Sees. 4.12-2, 14.11-2, and 15.7-2)

    12.21. Aleksandrov, P. S.: Combinatorial Topology, 3 vols., Graylock, New York, 1956.

    12.22. Bushaw, D.: Elements of General Topology, Wiley, New York, 1963.

    12.23. Hall, D. W., and G. L. Spencer: Elementary Topology, Wiley, New York, 1955.

    12.24. Hocking, J., and G. Young: Topology, Addison-Wesley, Reading, Mass., 1961.

    12.25. Kelley, John L.: General Topology, Van Nostrand, Princeton, N.J., 1955.

    12.26. Lefschetz, S.: Introduction to Topology, Princeton University Press, Princeton, N.J., 1949.

    12.27. Liusternik, L. A., and V. J. Sobolev: Elements of Functional Analysis, Ungar, New York, 1961.

    12.28. Newman, M. H. A.: Topology of Plane Sets of Points, Cambridge, New York, 1951.

    12.29. Pervin, W. J.: Foundations of General Topology, Academic Press, New York, 1964.

    12.30. Pontryagin, Lev S.: Foundations of Combinatorial Topology, Graylock, Rochester, N.Y., 1952.

    12.31. Wallace, A. H.: Introduction to Algebraic Topology, Pergamon Press, New York, 1957.