help with abstract math

Produced by Charles Wells.  Home.   Website Contents     Website Index   
Back to Sets beginning

Posted 27 May 2008



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






Cartesian Product

    cartesian product


     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


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


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


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=.


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}.


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


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.


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.


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


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.


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


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


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).


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.


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).


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


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 ,


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


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


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


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


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

[email protected]      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.


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.

[email protected]      rr 1) 1 1) AB
2) 4 2) A∩B
3) 7 3) A-B
4) -2 4) A-Z
 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.


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.




Answer: Proof of (a):

(b) is false; for example, {1,2}P({1}{2}) but {1,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).


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


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


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


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


he definition of powerset gives two rules of inference:



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


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


How many elements do each of the following sets have?





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


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


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)
g) Z     g) {Z,R}



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.


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'.


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.


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.


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





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:


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


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.


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


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.


<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.


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.


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



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.


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

[email protected]   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 .


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


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


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






<< 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>>)}.


[ 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.


[ 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.


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!).


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


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.


Write each of these functions as tuples.


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


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


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).


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




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=.


Prove Theorem .


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 *).


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>}.


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 .


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>.


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.


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.


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=.


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


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






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.


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


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


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,



{{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}}


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.


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

[email protected]   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


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>,
(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>,
(h) <1,<1,3>>,<1,<1,4>>,<1,<1,5>>,<1,<2,3>>,
(i) <1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,1,2


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}.

[email protected]   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. PA×PB
7. <1,7,7> 7. B2


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