Produced by Charles Wells.  Home.   Website Contents     Website Index   

Back to Sets beginning

Posted 27 May 2008

OPERATIONS ON SETS

The unlinked entries have not yet been written.  The links below each one connect you to the relevant sections of Wikipedia.

Subsets and inclusion

      Union and intersection    

     union and intersection

Complement

     complement

     subtraction

Powerset

     powerset

Cartesian Product

    cartesian product

     Diagonal

     Tuples   tuple

Set subtraction

For sets A and B, the notation  refers to the set   the set of elements of A that are not in B. (See sebuilder notation).  Examples: 

¨   

¨   

¨   is the set of nonzero real numbers.

¨  , since . 

¨   is a meaningless expression, since  is not a set.

¨  {1, 3, 5, 6} \ {4, 5, 7} = {1, 3, 6}.

¨  {1, 3, 5, 6} \ {2, 4, 8} = {1, 3, 5, 6}.

Union and intersection

Definition:union

For any sets  A and  B, the union AB of  A and  B is defined by

Definition:intersection

For any sets  A and  B, intersection A∩B is defined by ,

Example

Let A={1,2} and B={2,3,4}. Then AB={1,2,3,4} and A∩ B={2}. If C={3,4,5}, then A∩C=.

Exercise

What are {1,2,3}{2,3,4,5} and {1,2,3}∩{2,3,4,5}? Answer: {1,2,3}{2,3,4,5}={1,2,3,4,5} and {1,2,3}∩{2,3,4,5}={2,3}.

Exercise

What are NZ and N∩Z? Answer: NZ=Z and N∩Z=N.

Remark

Union and intersection mirror the logical connectives ` ∨' and ` ' of section *. The connection is by means of the extensions of the predicates involved. The extension of P∨ Q is the union of the extensions of  P and of  Q, and the extension of , PQ is the intersection of the extensions of  P and of Q.

Example

Let  S be a set of poker chips, each of which is a single color, either red, green or blue. Let R, G, B be respectively the sets of red, green and blue chips. Then RB is the set of chips which are either red or blue; the ` ' symbol mirrors the "or". And R∩B=, since it is false that a chip can be both red and blue.

Warning

Although union corresponds with " ∨", the set RB of the preceding example could also be described as "the set of red chips and blue chips"!

Exercise

Prove that for any sets A and B, A∩ BAB. Answer: By Definition *, we must show that if xA∩B, then xAB. By Definition * (of intersection), xA∩B implies that xA and xB. By Definition * (of union), if xA, then xA B.

Exercise

Prove that for any sets A and B, A∩ BA and AAB.

Definition:disjoint

If A and B are sets and A∩ B= then A and B are said to be disjoint.

Exercise

Name three different subsets of Z that are disjoint from N. Answer: There are of course an infinite number of answers. Some correct answers are: The set of all negative integers, the set of all negative even integers, {-1,-2,-3}, {-42}, and the empty set (which is disjoint from every set).

Exercise

If A and B are disjoint, must P(A) and P(B) be disjoint?

The universal set and complements

Since we cannot talk about the set of all sets, there is no universal way to mirror TRUE as a set. However, in many situations, all elements are of a particular type. For example, all the elements in Example * are chips. The set of all elements of that type constitutes a single set containing as subsets all the sets under consideration. Such a set is called a universal set, and is customarily denoted U .

Given a universal set, we can define an operation corresponding to ` ¬', as in the following defintion.

Definition:complement

If  A is a set, Ac is the set of all elements in U but not in  A. Ac is called the complement of  A (note the spelling).

Usage

Ac may be denoted A ‾ or A' in other texts.

Example

The complement of N in Z is the set of all negative integers.

Definition:set difference

Let  A and  B be any two sets. The set difference A-B is the set defined by ,

Example

Let A={1,2,3} and B={3,4,5}; then A-B={1,2}.

Exercise

What is Z-N? What is N-Z? Answer: Z-N is the set of all negative integers. N-Z=.

Fact

f there is a universal set U , then Ac =U -A.

Usage

A-B is written A\B in many texts..

Exercise

Let A={1,2,3}, B={2,3,4,5} and C={1,7,8}. Write out the elements of the following sets:

ll@      ll a) AB f) B-C
b) A∩B g) A∩(BC)
c) BC h) B(A∩C)
d) B∩C i) B(A-C)
e) A-B

Answer: (a) 1,2,3,4,5; (b) 2,3; (c) 1,2,3,4,5,7,8; (d) none; (e) 1; (f) 2,3,4,5; (g) 1,2,3; (h) 1,2,3,4,5; (i) 2,3,4,5.

Exercise

State whether each item in the first column is an element of each set in the second column. A={1,3,7}, B={1,2,3,4,5}, and the universal set is Z.

rr@      rr 1) 1 1) AB
2) 4 2) A∩B
3) 7 3) A-B
4) -2 4) A-Z
5)  5) Bc
6) {2,4,5} 6) PA
7) {1,3} 7) P(A∩B)

Answer: 1) 1 and 2. 2) 1. 3) 1, 3 and 5. 4) 5. 5) 6 and 7. 6) None. 7) 6 and 7.

Exercise

Explain why the following statements are true for all sets  A and  B or give examples showing they are false for some  A and  B.

P(A)∩P(B)=P(A∩B)

P(A)P(B)=P(AB)

P(A)-P(B)=P(A-B)

Answer: Proof of (a):

(b) is false; for example, {1,2}P({1}{2}) but {1,2}P{1}P{2}.

(c) is false: for example, the empty set is an element of any powerset, so it is an element of P(A-B). Since it is in both P(A) and P(B), it is not in P(A)-P(B).

Exercise

Show that for any sets A and B included in a universal set U , if AB=U and A∩B=, then B= Ac .

The powerset of a set

Definition:powerset

If  A is any set, the set of all subsets of  A is called the powerset of  A and is denoted PA.

Remark

Using setbuilder notation, PA={X‖XA}.

Example

The powerset of {1,2} is {,{1},{2},{1,2}}, and the powerset of {1} is {,{1}}.

Fact

he definition of powerset gives two rules of inference:

and

Example

The empty set is an element of the powerset of every set, since it is a subset of every set.

Warning

The empty set is not an element of every set; for example, it is not an element of {1,2}.

Exercise

How many elements do each of the following sets have?

{1,2,3,{1,2,3}}

{} 

{,{}}

Answer: a: 4. b: 0. c: 1. d: 2.

Exercise

Write the powerset of {5,6,7}. Answer: {,{5},{6},{7},{5,6},{6,7},{5,7},{5,6,7}}

Exercise

State whether each item in the first column is an element of each set in the second column.

rlcrl a) 1     a) Z
b) 3     b) R
c) π     c) {1,3,7}
d) {1,3}     d) {xR‖x= x2 }
e) {3,π}     e) P(Z)
f)      f)  
g) Z     g) {Z,R}

Answer:

Ordered pairs

In analytic geometry, one specifies points in the plane by ordered pairs of real numbers, for example <3,5>. (Most books use round parentheses instead of pointy ones.) This is not the same as the two-element set {3,5}, because in the ordered pair the order matters: <3,5> is not the same as <5,3>.

In the ordered pair <3,5>, 3 is the first coordinate and 5 is the second coordinate. Sometimes, the two coordinates are the same: for example, <4,4> has first and second coordinates both equal to 4.

An ordered pair in general need not have its first and second coordinates of the same type. For example, one might consider ordered pairs whose first coordinate is an integer and whose second coordinate is a letter of the alphabet, such as <5,`a'> and <-3,`d'>.

The following specification gives the operational properties of ordered pairs:

Specification:ordered pair

An ordered pair <x,y> is a mathematical object distinct from x and y which is completely determined by the fact that its first coordinate is x and its second coordinate is y.

Remark

Specification * implies that ordered pairs are the same if and only if their coordinates are the same:

Thus we have a method:

Method: twoshowTo prove two ordered pairs <x,y> and <x',y'> are the same, prove that x=x' and y=y'.

Exercise

Which of these pairs of ordered pairs are equal to each other?

<2,3>, <3,2>.

<3,4>, <3,2>.

<2,4>, <4,2>.

Answer: The pairs in (a) are different; the pairs in (b) and (c) are equal.

Exercise

discussion In texts on the foundations of mathematics, an ordered pair <a,b> is often defined to be the set {{a,b},{a} }. Prove that at least when a and b are numbers this definition satisfies Specification * (with a suitable definition of "coordinate"). Answer: Let Sa,b = {{a,b},a }. Define the first coordinate of S to be the only number in the set, and the second coordinate to be the same as the first coordinate if the set that is an element of S is a singleton; otherwise the second coordinate is the element of the set in S that is different from the first coordinate. Things get sticky if a can be a set - you have to refer to the "Axiom of Foundation" that in effect forbids infinite chains of the element-of relation. Note: In some texts on foundations, numbers are defined as sets. We do not take that attitude here, so that the clause "at least when a and b are numbers" implies that they are not sets.

Tuples

In order to generalize the idea of ordered pair to allow more than two coordinates, we need some notation.

Definition: n

Let n be an integer, n≥1. Then n is defined to be the set

Example

3={1,2,3}.

Exercise

Let m and n be positive integers. What is m∩n? What is mn? Answer: m∩n is k, where k is the minimum of m and n, and mn is l, where l is the maximum of m and n.

A tuple is a generalization of the concept of ordered pair. A tuple satisfies this specification:

Specification:tuple

A tuple of length n, or n-tuple, is a mathematical object which

T

has an ith entry for each in, and

is distinct from its entries, and

is completely determined by specifying the ith entry for every in.

Example

An ordered pair is the same thing as a 2-tuple.

Usage

A 3-tuple is usually called an ordered triple.

The usual way of denoting a tuple is by listing its entries in order inside angle brackets.

Example

<1,3,3,-2> is a tuple of integers. It has length 4. The integer 3 occurs as an entry in this 4-tuple twice, for i=2 and i=3.

Usage

Tuples and their coordinates are often named according to a subscripting convention, by which one refers to the ith entry by subscripting i to the name of the tuple. For example, let a=<1,3,3,-2>; then a2 =3 and a4 =-2. One often makes this convention clear by saying, "Let a=< ai >in be an n-tuple."

Many authors would use curly brackets here: " { ai }in ." Nevertheless, a is not a set.

Usage

Many computer scientists refer to a tuple as a "vector". Although this usage is widespread, it is not desirable; in mathematics, a vector is a geometric object which can be represented as a tuple, but is not itself a tuple.

It follows from Specification * that two n-tuples are equal if and only if they have the same entries. Formally:

Theorem: tuplteHow to tell if tuples are equalLet a and b be n-tuples. Then

Exercise

Which of these pairs of tuples are equal?

<3,3>, <3,3,3>.

<2,3>, <2,3,3>.

<2,3,2>, <3,2,2>.

Answer: None of them are equal.

Special tuples

For formal completeness, one also has the concept of the null tuple (or empty tuple) <>, which has length 0 and no entries, and a 1-tuple, which has length 1 and one entry.

The index set for the null tuple is the empty set. There is only one null tuple. In the context of formal language theory the unique null tuple is often denoted " Λ" (capital lambda) or sometimes " &epsi;" (small epsilon). We will use the notation Λ here.

Exercise

For each tuple, give the integer n for which it is an n-tuple and also give its second entry.

ll@   ll a) <3,4,0> d) << <2,<1,5>>,7>,9>
b) << 3,4>,<1,5>> e) <3,{1,2}>
c) <3,<5,<2,1>>> f) <N,Z,Q,R>

Answer: 1. a)  3,4. b)  2,<1,5>. c)  2,<5,<2,1>>. d)  2,9. e)  2,{1,2}. f)  4,Z.

Tuples as functions

[ label: tupasfuncsec] 

Let n be a positive integer, and let

An n-tuple

in An associates to each element i of \n an element ai of A. This determines a function i&Verbar;→ ai with domain \n and codomain A. Conversely, any such function determines an n-tuple in An by setting its coordinate at i to be its value at i.

When \a A1 × A2 ×…× An , so that different components are in different sets, this way of looking at n-tuples is more complicated. Every coordinate ai is an element of the union C= A1  A2 … An , so that \a can be thought of as a function from \n→C. In this case, however, not every such function is a tuple in A1 × A2 ×…× An : we must impose the additional requirement that ai  Ai .

We sum all this up in an alternative definition of tuple:

Definition:tuple as function

[ label: tupfuncdef] A tuple in Πi=1 n Ai is a function

with the property that for each i, a(i) Ai .

Example

The tuple <2,1,3> is the function 1&Verbar;→2, 2&Verbar;→1, 3&Verbar;→ 3 (compare Section  [permexex] ).

Example

The tuple <5,5,5,5> is the constant function C5 :{1,2,3,4}→Z.

Exercise

Write the domain and the graph of these tuples regarded as functions on the index set.

Exercise

<2,5,-1,3,6>.

Exercise

<π,5,π-1,2>.

Exercise

<< 3,5>,<8,-7>,<5,5>>.

Answer: a) Domain: {1,2,3,4,5}.
Graph: ({<1,2>,<2,5>,<3,-1>,<4,3>,<5,6>)}.
b) Domain: {1,2,3,4}.
Graph: ({<1,π>,<2,5>,<3,π-1>, <4,2>)}.
c) Domain: {1,2,3}.
Graph: ({<1,<3,5>>,<2,<8,-7>>,<3,<5,5>>)}.

Example

[ label: reldath]  A simple database might have records each of which consists of the name of a student, the student's student number, and the number of classes the student takes. Such a record would be a triple <w,x,n>, where w is an element of the set A* of strings of English letters and spaces (this notation is introduced formally in Definitions  [listsetdef] and  [stringdef] ), x is an element of the set D* of strings of decimal digits, and nN. This triple corresponds to a function F:{1,2,3}→ A* × D* ×N with the property that F(1) A* , F(2) D* and F(3)N.

Modeling detabases this way is the principle behind relational database theory.

Remark

[ label: notatrem]  In the case that all the Ai are the same, so that \a An , we now have the situation that \fs\nA (the set of functions from \n to A, where \n={1,2,…,n}) and An (the set of n-tuples in A) are essentially the same thing. That is the origin of the notation \fsAB.

Tuples with other index sets

The discussion above suggests that by regarding a tuple as a function set, we can use any set as index set.

Example

In computer science it is often convenient to start a list at 0 instead of at 1, giving a tuple < a0 , a1 ,…, an >. This is then a tuple indexed by the set {0,1,…,n} for some n (so it has n+1 entries!).

Example

[ label: infseqind]  An infinite sequence of integers is indexed by N+ , so it is an element of \fs N+ Z.

Example

This is another look at Example  [reldath] . The point of view that a triple < Jones , 1235551212 ,4> is a function with domain {1,2,3} has an arbitrary nature: it doesn't matter that the name is first, the student number second and the number of classes third. What matters is that Jones is the name, 1235551212 is the student number and 4 is the number of classes. Thus it would be conceptually better to regard the triple as a function whose domain is the set { Name , StudentNumber , NumberOfClasses }, with the property that f( Name ) A* , F( StudentNumber ) D* and F( NumberOfClasses )N. This eliminates the spurious ordering of data imposed by using the set {1,2,3} as domain.

In this context, the elements of a set such as

are called the field names of the database.

Definition:function as tuple

[ label: functupledef] A function T:S→A is is also called an S-tuple or a family of elements of A indexed by S.

Exercise

Write each of these functions as tuples.

Exercise

F:{1,2,3,4,5}→R, Γ(F)=({<2,5>,<1,5>,<3,3>,<5,-1>,<4,17>)}.

Exercise

F:{1,2,3,4,5}→R, F(n)=(n+1)π.

Exercise

x&Verbar;→ x2 :{1,2,3,4,5,6}→R.

Answer: a) <5,5,3,17,-1>. b) <2π,3π,4π,5π,6π>. c)  <1,4,9,16,25,36>.

Cartesian Products

Definition:Cartesian product of two sets

Let A and B be sets. A×B is the set of all ordered pairs whose first coordinate is an element of A and whose second coordinate is an element of B. A×B is called the Cartesian product of A and B (in that order).

Example

if A={1,2} and B={2,3,4}, then

and

Exercise

Write out the elements of {1,2}×{a,b}. Answer: <1,a>,<1,b>,<2,a>,<2,b>.

Fact: emptykillsIf A is any set, then A×=×A=.

Exercise

Prove Theorem .

Example

R×R is often called the "real plane", since it consists of all ordered pairs of real numbers, and each ordered pair represents a point in the plane once a coordinate system is given. Graphs of straight lines and curves are subsets of R×R. For example, the x-axis is {<x,0>&mid;xR } and the parabola y= x2 is {<x,y>&mid;xRy= x2 }, which could be written {<x, x2 >&mid;xR } (recall the discussion in Section *).

Definition:diagonal

For any set A, the subset {<a,a>&mid;aA } of A×A of all pairs whose two coordinates are the same is called the diagonal of A, denoted ΔA .

Worked Exercise

Write out the diagonal of {1,2}×{1,2}. Answer: {<1,1>,<2,2>}.

Example

The diagonal ΔR of R×R is the 45-degree line from lower left to upper right. It is the graph of the equation y=x.

Cartesian products in general

The notion of Cartesian product can be generalized to more than two factors using the idea of tuple.

Definition:Cartesian product

Let A1 , A2 ,…, An be sets - in other words, let < Ai >in be an n-tuple of sets. Then A1 × A2 ×…× An is the set

of all n-tuples whose ith coordinate lies in Ai .

Example

The set R×Z×R has triples as elements; it contains as an element the ordered triple <π,-2,3>, but not, for example, <-2,π,3>.

Warning

Observe that R×N×R, (R×N)×R and R×(N×R) are three different sets; in fact, any two of them are disjoint. Of course, in an obvious sense they all represent the same data.

Example

Consider the set

where m and n are of type integer. Thus <3,6>, <-3,6> and <5,0> are elements of D but not <3,5>. D is not a Cartesian product, although it is a (proper) subset of the cartesian product Z×Z. The point is that a pair in A×B can have any element of A as its first coordinate and any element of B as its second coordinate, regardless of what the first coordinate is. In D what the second coordinate is depends on what the first coordinate is.

A set such as D is a relation, a concept discussed later.

Exercise set

Exercises  through  give "facts" which may or may not be correct for all sets A, B and C. State whether each "fact" is true for all sets A, B and C, or false for some sets A, B or C, and for those that are not true for all sets, give examples of sets for which they are false.

Exercise

A×A=A. Answer: This is false for any nonempty set A because the elements of A×A are pairs of elements of A, and an ordered pair is distinct from its coordinates (see *). (The last statement implies that in fact for nonempty A, A×A and A have no elements in common.) The statement A×A=A is true if A=.

Exercise

A×B=B×A. Answer: False if A and B are both nonempty.

Exercise

A(B×C)=(AB)×(A C). Answer: False for nonempty A (and some other cases as well).

Exercise

A∩(B×C)=(A∩B)×(A∩C).

Exercise

A×(B×C)=(A×B)×C.

Exercise

P(A×B)=P(A)×P(B). Answer: A=B= is an example that makes it false, since P(×) but the only element of P()×P() is <,>.

Exercise set

The statements in problems  through  are true for all sets A, B and C, except that in some cases some of the sets A, B and C have to be nonempty if the statement is to be true for all other sets named. Amend the statement in each case so that it is true.

Exercise

For all sets A, B and C, A×C=B×CA=B. Answer: "For all sets A and B and all nonempty sets C, …"

Exercise

For all sets A and B, A×B=B×AA=B. Answer: "For all nonempty sets A and B…"

Exercise

For all sets A, B and C, AB(A×C)(B×C). Answer: Correct as it stands.

Cartesian product in Mathematica

The dmfuncs.m package contains the command CartesianProduct, which gives the Cartesian product of a sequence of sets. For example,

CartesianProduct[{1,2},{a,b,c},{x,y}]

produces

{{1, a, x}, {1, a, y}, {1, b, x}, {1, b, y}, {1, c, x}, {1, c, y}, {2, a, x}, {2, a, y}, {2, b, x}, {2, b, y}, {2, c, x}, {2, c, y}}

Exercise

Mathematica The command CartesianProduct mentioned in * works on any lists, not just sets (see *, page pageref). Write a precise description of the result given when CartesianProduct is applied to a sequence of lists, some of which contain repeated entries.

Exponential notation

If all the sets in a Cartesian product are the same, exponential notation is also used. Thus A2 =A×A, A3 =A×A×A, and in general

( n times). These are called Cartesian powers of A; in particular, A2 is the Cartesian square of A. This notation is extended to 0 and 1 by setting A0 ={<>} (the singleton set containing the null tuple as an element) and A1 =A.

Exercise

Let A={1,2} and B={3,4,5}. Write all the elements of each set:

ll@   ll a) A0 f) B×A
b) A1 g) A×A×B
c) A2 h) A×(A×B)
d) A3 i) (A×B)A
e) A×B j) (A×B)∩A

Answer:

ll (a) Λ
(b) 1,2
(c) <1,1>,<1,2>,<2,1>,<2,2>
(d) <1,1,1>,<1,1,2>,<1,2,1>,<1,2,2>,
<2,1,1>,<2,1,2>,<2,2,1>,<2,2,2>
(e) <1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>
(f) <3,1>,<3,2>,<4,1>,<4,2>,<5,1>,<5,2>
(g) <1,1,3>,<1,1,4>,<1,1,5>,<1,2,3>,<1,2,4>,<1,2,5>,
<2,1,3>,<2,1,4>,<2,1,5>,<2,2,3>,<2,2,4>,<2,2,5>
(h) <1,<1,3>>,<1,<1,4>>,<1,<1,5>>,<1,<2,3>>,
<1,<2,4>>,<1,<2,5>>,<2,<1,3>>,<2,<1,4>>,
<2,<1,5>>,<2,<2,3>>,<2,<2,4>>,<2,<2,5>>
(i) <1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,1,2
(j)  

Exercise

For each pair of numbers <m,n>{1,2,3,4,5,6,7}×{1,2,3,4,5,6,7}, state whether item m in the first column is an element of the set in item n of the second column. A={1,3,7}, B={1,2,3,4,5}.

ll@   ll 1. <3,5> 1. A×A
2. <3,3> 2. A3
3. <3,3,5> 3. A×B
4. {<3,5>,<7,5> } 4. B×A
5. <{3,7},{3,5}> 5. P(A×B)
6.  6. PA×PB
7. <1,7,7> 7. B2

Answer:

cccccccc 1 2 3 4 5 6 7
1 N N Y N N N Y
2 Y N Y Y N N Y
3 N N N N N N N
4 N N N N Y N N
5 N N N N N Y N
6 N N N N Y N N
7 N Y N N N N N