1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 4
Текст из файла (страница 4)
'\'hat are these sets? Write them using braces, commas, and numerals only.(a) ({1,3,5}U{3,1})n{3,5,7}(b) U{ {3}, {3, 5}, n{ {5, 7}, {7, 9}}}(c) ({1,2,5} - {5, 7,9})U ({5, 7,9} - {l,2,5})(d)2{7,8,9} _ 2{7,9}(e) 201.1.3. Prove each of the following.(a) AU(BnC)=(AUB)n(AUC)(b) An (B U C) = (A n B) U (A n C)(c) A n (A U B) = A(d) AU(AnB)=A(e) A - (B n C) = (A - B) U (A - C)1.1.4. Let S = {a, b, c, d}.(a) What partition of S has the fewest members? The most members?(b) List all partitions of S with exactly two members.liiJRELATIONS AND FUNCTIONSMathematics deals with statements about objects and the relations betweenthem. It is natural to say, for example, that "less than" is a relation betweenobjects of a certain kind -namely, numbers- which holds between 4 and 7 butdoes not hold between 4 and 2, or between 4 and itself.
But how can we expressrelations between objects in the only mathematical language we have availableat this point -that is to say, the language of sets? We simply think of a relationas being itself a set. The objects that belong to the relation are, in essence, thecombinations of individuals for which that relation holds in the intuitive sense.So the less-than relation is the set of all pairs of numbers such that the firstnumber is less than the second.But we have moved a bit quickly. In a pair that belongs to a relation,we need to be able to distinguish the two parts of the pair, and we have notexplained how to do so. We cannot write these pairs as sets, since {4, 7} is thesame thing as {7, 4}.
It is easiest to introduce a new device for grouping objectscalled an ordered pair. tWe write the ordered pair of two objects a and b as (a, b); a and b are calledthe components of the ordered pair (a, b). The ordered pair (a, b) is not thesame as the set {a,b}. First, the order matters: (a,b) is different from (b,a),tTrue fundamentalists would see the ordered pair (a, b) not as a new kind of object,but as identical to {a, {a,b}}.10Chapter 1: SETS, RELATIONS, AND LANGUAGESwhereas {a, b} = {b, a}. Second, the two components of an ordered pair neednot be distinct; (7,7) is a valid ordered pair. Note that two ordered pairs (a, b)and (c, d) are equal only when a = c and b = d.The Cartesian product of two sets A and B, denoted by A x B, is theset of all ordered pairs (a, b) with a E A and b E B. For example,{ 1, 3, 9} x {b, c, d} = {( 1, b), (1, c), (1, d), (3, b), (3 , c), (3, d), (9, b), (9 , c), (9, d)} .A binary relation on two sets A and B is a subset of Ax B.
For example,{(1,b),(1,c),(3,d),(9,d)} is a binary relation on {1,3,9} and {b,c,d}. And{(i,j) : i,j EN and i < j} is the less-than relation; it is a subset of N x N---often the two sets related by a binary relation are identical.More generally, let n be any natural number. Then if aI, ... , an are any nobjects, not necessarily distinct, (al"'" an) is an ordered tuple; for eachi = 1, ... ,n, ai is the ith component of (al, ... ,an ). An ordered m-tuple(bl, ... ,b m ), where m is a natural number, is the same as (al, ... ,an ) if andonly ifm = nand ai = bi , for i = 1, ...
,n. Thus (4,4), (4,4,4), ((4,4),4),and (4, (4,4)) are all distinct. Ordered 2-tuples are the same as the orderedpairs discussed above, and ordered 3-, 4-, 5-, and 6-tuples are called orderedtriples, quadruples, quintuples, and sextuples, respectively. On the otherhand, a sequence is an ordered n-tuple for some unspecified n (the length ofthe sequence).
If AI, ... , An are any sets, then the n-fold Cartesian productAl x '" x An is the set of all ordered n-tuples (al, ... , an), with ai E Ai, foreach i = 1, ... , n. In case all the Ai, are the same set A, the n-fold Cartesianproduct A x ... x A of A with itself is also written An. For example, N 2 is theset of ordered pairs of natural numbers. An n-ary relation on sets AI, ... , Anis a subset of Al x ... x An; 1-, 2-, and 3-ary relations are called unary, binary,and ternary relations, respectively.Another fundamental mathematical idea is that of a function.
On the intuitive level, a function is an association of each object of one kind with a uniqueobject of another kind: of persons with their ages, dogs with their owners, numbers with their successors, and so on. But by using the idea of a binary relationas a set of ordered pairs, we can replace this intuitive idea by a concrete definition. A function from a set A to a set B is a binary relation R on A and Bwith the following special property: for each element a E A, there is exactly oneordered pair in R with first component a. To illustrate the definition, let C bethe set of cities in the United States and let 51 be the set of states; and letRI = {(x,y) : x E C,y E 51, and x is a city in state y},R2 = {(x,y): xES,yEC, and y is a city in state x}.1.2: Relations and Functions11Then Rl is a function, since each city is in one and only one state, but R2 is nota function, since some states have more than one city.tIn general, we use letters such as I, g, and h for functions and we writeI : A I-t B to indicate that I is a function from A to B.
We call A the domainof f. If a is any element of A we write I(a) for that element b of B such that(a, b) E I; since I is a function, there is exactly one b E B with this property, soI(a) denotes a unique object. The object I(a) is called the image of a underf. To specify a function I : A I-t B, it suffices to specify I (a) for each a E A;for example, to specify the function RI above, it suffices to specify, for each city,the state in which it is located. If I : A I-t B and AI is a subset of A, then wedefine J[A'l = {/(a) : a E A'} (that is, {b: b = I(a) for some a E A'}). We callJ[A'l the image of AI under f.
The range of I is the image of its domain.Ordinarily, if the domain of a function is a Cartesian product, one set ofparentheses is dropped. For example, if I : N x N I-t N is defined so that theimage under I of an ordered pair (m, n) is the sum of m and n, we would writeI(m, n) = m+n rather than I((m, n)) = m+n, simply as a matter of notationalconvenience.If I: Al x A2 X ... x An I-t B is a function, and I(al, ... ,an) = b, whereai E Ai for i = 1, ...
, nand b E B, then we sometimes call al,··., an thearguments of I and b the corresponding value of I. Thus I may be specifiedby giving its value for each n-tuple of arguments.Certain kinds of functions are of special interest. A function I : A I-t Bis one-to-one if for any two distinct elements a, a' E A, I(a) ::f:- I(a ' ). Forexample, if C is the set of cities in the United States, 5 is the set of states, andg : 5 I-t C is specified byg( s)= the capitalof state sfor each s E 5, then g is one-to-one since no two states have the same capital.A function I : A I-t B is onto B if each element of B is the image under I ofsome element of A.
The function g just specified is not onto C, but the functionRI defined above is onto 5 since each state contains at least one city. Finallya mapping I : A I-t B is a bijection between A and B if it is both one-to-oneand onto B; for example, if Co is the set of capital cities, then the functiong: 5 I-t Co specified, as before, byg( s) = the capital of state sis a bijection between 5 and Co.tWe consider Cambridge, Massachusetts, and Cambridge, Maryland, not the samecity, but different cities that happen to have the same name.12Chapter 1: SETS, RELATIONS, AND LANGUAGESThe inverse of a binary relation R t:;;; A x B, denoted R- 1 t:;;; B x A, is simplythe relation {(b, a) : (a, b) E R}.
For example, the relation R2 defined above is theinverse of R 1 • Thus, the inverse of a function need not be a function. In the caseof Rl its inverse fails to be a function since some states have more than one city;that is, there are distinct cities Cl and C2 such that Rl (Cl) = Rl (C2). A functionI : A f-t B may also fail to have an inverse if there is some element b E B suchthat I(a) ::f:- b for all a E A. If I: A f-t B is a bijection, however, neither of theseeventualities can occur, and 1-1 is a function -indeed, a bijection between Band A. Moreover I-l(f(a)) = a for each a E A, and l(f-l(b)) = b for eachbE B.When a particularly simple bijection between two sets has been specified,it is sometimes possible to view an object in the domain and its image in therange as virtually indistinguishable: the one may be seen as a renaming or away of rewriting the other. For example, singleton sets and ordered I-tuples are,strictly speaking, different, but not much harm is done if we occasionally blurthe distinction, because of the obvious bijection I such that I ({ a}) = (a) forany singleton {a}.
Such a bijection is called a natural isomorphism; of coursethis is not a formal definition since what is "natural" and what distinctions canbe blurred depend on the context. Some slightly more complex examples shouldmake the point more clearly.Example 1.2.1: For any three sets A, B, and C, there is a natural isomorphismof Ax B x C to (A x B) x C, namelyI(a,b,c) = ((a,b),c)for any a E A, bE B, and c E C.OExample 1.2.2: For any sets A and B, there is a natural isomorphism ¢ fromthat is, the set of all binary relations on A and B, to the set{I : Iis a function from A to 2B}.Namely, for any relation R t:;;; A x B, let ¢(R) be that functionthatI(a) = {b: bE Band (a,b) E R}.I : A f-t 2BsuchFor example, if S is the set of states and R t:;;; S x S contains any orderedpair of states with a common border, then the naturally associated functionI : S f-t 25 is specified by I (s) = {s' : s' E Sand s' shares a border with s}.
01.3: Special Types of Binary Relations13Example 1.2.3: Sometimes we regard the inverse of a function I : A f--t B as afunction even when I is not a bijection. The idea is to regard 1-1 t::;; B x A as afunction from B to 2A, using the natural isomorphism described under Example1.2.2. Thus 1-1 (b) is, for any b E B, the set of all a E A such that I(a) = b.For example, if Rl is as defined above -the function that assigns to each citythe state in which it is located- then Rll (s), where s is a state, is the set ofall cities in that state.If Q and R are binary relations, then their composition Q 0 R, or simplyQR, is the relation {(a, b) : for some c, (a, c) E Q and (c, b) E R}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
