Number Theory: An Introduction to Mathematics

0 Sets, Relations and Mappings 3

It is easily seen that union and intersection have the following algebraic properties:

A∪A=A, A∩A=A,

A∪B=B∪A, A∩B=B∩A,

(A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C),

(A∪B)∩C=(A∩C)∪(B∩C), (A∩B)∪C=(A∪C)∩(B∪C).

Set inclusion could have been defined in terms of either union or intersection, since

A⊆Bis the same asA∪B=BandalsothesameasA∩B=A.

For any setsA,B,the set of all elements ofBwhich are not also elements ofAis

called thedifferenceofBfromAand is denoted byB\A:

B\A={x:x∈Bandx∈/A}.

It is easily seen that

C\(A∪B)=(C\A)∩(C\B),

C\(A∩B)=(C\A)∪(C\B).

An important special case is where all sets under consideration are subsets of a
given universal setX.ForanyA⊆X,wehave

∅∪A=A, ∅∩A=∅,

X∪A=X, X∩A=A.

The setX\Ais said to be thecomplementofA(inX) and may be denoted byAcfor
fixedX. Evidently

∅c=X, Xc=∅,

A∪Ac=X, A∩Ac=∅,

(Ac)c=A.

By takingC=Xin the previous relations for differences, we obtain ‘De Morgan’s

laws’:

(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc.

SinceA∩B=(Ac∪Bc)c, set intersection can be defined in terms of unions and

complements. Alternatively, sinceA∪B=(Ac∩Bc)c, set union can be defined in

terms of intersections and complements.

For any setsA,B,the set of all ordered pairs (a,b) witha∈Aandb∈Bis called

the (Cartesian)productofAbyBand is denoted byA×B.

Similarly one can define the product of more than two sets. We mention only one

special case. For any positive integern, we writeAninstead ofA×···×Afor the set

of all (ordered)n-tuples(a 1 ,...,an) withaj∈A( 1 ≤j≤n). We callajthej-th

coordinateof then-tuple.

Abinary relationon a setAis just a subsetRof the product setA×A.Forany

a,b∈A, we writeaRbif(a,b)∈R. A binary relationRon a setAis said to be