Math 455.1  •  10 February 2009

Sets and functions

Version 7.04

Adapted from a notebook by Ernest G. Manes

Initializations

The special definitions used in this notebook come from two sources:
• the Combinatorica package, which is loaded by the following input cell;
• the definitions in the Definitions section at the end of this notebook; and
• the usage messages in the Glossary section near the end of this notebook.

Like the cell that loads Combinatorica, the cells in the Definitions and Glossary sections are initialization cells.

Needs["Combinatorica`"]

Sets

Prelude: mathematical sets vs. Mathematica lists

The traditional set-builder notation {…} notation from mathematics does not mean the same thing as the built-in list notation {…} from Mathematica!

Indeed, Mathematica does not have any built-in notion of set. The built-in list notation {a,b,…} represents not an unordered set, but rather a set whose elements have been arranged in a specific order, namely, the order in which they are listed—a first element, a second element, etc. For example, as sets, {(Sqrt[3]),π}={π,(Sqrt[3])}; in Mathematica, however:

{(Sqrt[3]),π}=={π,(Sqrt[3])}

In traditional mathematical notation, it doesn't matter whether you duplicate an element among the entries of a set given explicitly using set-builder notation. For example, as sets, {2,5,2,2,8,5}={2,5,8}; in Mathematica, however:

{2,5,2,2,8,5}=={2,5,8}

This should come as no surprise, as the two ordered lists have different lengths:

Length[{2,5,2,2,8,5}]
Length[{2,5,8}]

As a consequence, we will need to define for Mathematicaa what makes something a set. The way we do it is to decree that a set is a Mathematica list that has no duplicate entries.

Sets and membership

As preparation, clear names that you might already have defined but are used below as pure symbols or for special purposes.

Clear[a,b,c,d,e,f,r,t,xx,yy,zz,α]

To check whether something is a set, use SetQ.  We follow the convention that a Mathematica expression which always returns one of the values True, False should end in Q (for "question"). The notation ∅ for the empty set is typed as EscesEsc.

{SetQ[{d}],SetQ[a],SetQ[∅],SetQ[ {a,b,a,c,d }],SetQ[{a,b,d}]}

Notice that a list with a repetition is not considered a set.

To test whether something is a member or element of a set use the built-in Mathematica function MemberQ.  The value returned by MemberQ[X, x] is True when x is a member of X and is False otherwise.  For example:

xx={a,b,c,d,e};
{MemberQ[xx,a],MemberQ[ xx,3]}

Notice that the order of the arguments with MemberQ is exactly the reverse of that in traditional mathematical notation.  In traditional mathematical notation, one would write a ∈ xx when, in Mathematica, one would use MemberQ[xx,a].  Caution:  In Mathematica, the symbol ∈, formed by typing EscelemEsc, is used the same way as in traditional mathematical notation except that it applies only when its right-hand argument is one of several special Mathematica "domains": Primes, Integers, Rationals, Reals, Complexes, Algebraics, and Booleans.  See the section Representing infinite sets, below.

If you prefer, you may use the traditional mathematical notation a ∈ xx for set membership. The element-of symbol ∈ is typed as EscelemEsc.

{a∈xx,3∈xx}

The empty set has no elements. For example:

1∈∅

Subsets

The function SubsetQ tests whether its first argument is a subset of its second argument, that is, whether every member of the first set is a member of the second set.

xx={a,b,c,d,e};
{SubsetQ[{e,c},xx],SubsetQ[{d},xx],SubsetQ[a,xx]}

If you prefer, you may use the traditional mathematical notation x⊂y to mean the same thing as SubsetQ[x,y]. The subset symbol ⊂ is typed as EscsubEsc.

{{e,c}⊂xx,{d}⊂xx,a⊂xx}

Notice that the one-element set {d} is indeed a subset of xx. However, the element a is not a subset of xx, because a is just an abstract symbol, not a set of elements.

The empty set is a subset of every set. For example:

SubsetQ[∅,xx]

The function PowerSet returns the power set of its argument—the set of all subsets of that set. (Don't try it for too large a set! ) For example:

xx
PowerSet[xx]

The function Card finds the cardinality of a (finite) set—its number of elements.  For example:

Card[xx]
Card[∅]

To find the number of subsets of xx, use PowerSet and Card together:

Card[PowerSet[xx]]

Like PowerSet, the function Subsets from the Combinatorica package also returns the set of subsets of a set, although the subsets are listed in a different order.

Subsets[xx]

Unlike PowerSet, the function Subsets does not check that its argument is actually a set. Compare, for example, the output from the following two expressions:

PowerSet[{1,2,1}]
Subsets[{1,2,1}]

Union, intersection, and complement

The union of two sets is the set whose members are all those things that are members of one or the other or both of the two sets. The intersection of two sets is the set whose members are those things that are members of both of the two sets. The functions Union and Intersection are built-in to Mathematica:

Union[Range[5],{-3,π}]
Intersection[{a,b,c,d},{d,b}]

You can make Union and Intersection expressions somewhat more readable by using them in infix syntax:

Range[5]~Union~{-3,π}
{a,b,c,d}~Intersection~{d,b}

Even better, you can make Union and Intersection expressions in Mathematica look exactly like ordinary mathematical notation by using  EscunEsc which gives ⋃ and EscinterEsc which gives ⋂.

The complement in one set built-in Mathematica function Complement forms set differences.  For example:

Complement[{a,b,c,d},{d,b}]
Complement[{a,b,c,d},{1,2, d,b}]

Mathematica's infix notation with Complement resembles traditional mathematical notation for set difference.  Thus in traditional mathematical notation one writes {a, b, c, d} - {d, b} or perhaps {a, b, c, d} ∖ {d, b} for what in Mathematica could be written as {a, b, c, d}~Complement~{d, b}.

{a,b,c,d}~Complement~{d,b}

The built-in Mathematica functions Union, Intersection, and Complement do not check whether their arguments are actually sets—lists without duplications—but they do return sets as results.  For example:

Union[{1,2,1},{3,4}]

Cartesian products

The cartesian product of one or more sets is created by SetProduct.  Here are some examples.

SetProduct[{1,2,3},{π,(Sqrt[2])}]

xx = {a,b};∅={};yy={"cat",t};zz={α};
SetProduct[xx]
SetProduct[xx,yy,zz]
SetProduct[∅,yy]

Combinatorica function CartesianProduct

⚠  Caution:  The Combinatorica function CartesianProduct is limited to two arguments, does not check whether these arguments are sets, and returns a somewhat different result than does SetProduct. For example:

SetProduct[{1,2,3,2}, {π,(Sqrt[2])}]
CartesianProduct[{1,2,3,2}, {π,(Sqrt[2])}]

Representing infinite sets

The sets constructed here so far are all necessarily finite, since they are just lists having no repeated entries. In the definitions section of this notebook, we have defined the usual notations for the special sets ℕ, ℤ, ℚ, ℝ, ℂ. Each of these is a "double-struck" letter; to enter ℤ, for example, you type EscdsZEsc.

You may use MemberQ or the elementhood notation ∈ to test for membership in these special sets. For example:

{(Sqrt[2])∈ℚ,(Sqrt[2])∈ℝ}

⚠  Caution:  We have not set up the necessary definitions in this notebook to deal with the subset relation or union, intersection, etc., when one or more of the sets involved is one of these infinite sets. (Doing so would involve making a large number of special definitions.)

The Russell set

Here is a way to handle the "Russell set" in Mathematica:, namely, to ask whether a given set is a member of the Russell set:

RussellQ[x_]:=SetQ[x]&&(!MemberQ[x,x])

We can test various things for belonging to the Russell set. For example:

RussellQ[{a,b,c}]

Since we cannot actually construct infinite sets, in particular we cannot construct the set of all x for which RussellQ[x] has value True. So we cannot construct the paradoxical expression that would test whether the Russell set is a member of itself.

Functions

Representing mathematical functions

A function f from a set X to a set Y is a list of three things:
	• a set X, called the domain of the function;
	• a set Y, called the codomain of the function; and
	• a "relation" from X to Y, called the rule (or functional relation) of the function, that has the property that each x ∈ X is related to at least one y ∈ Y but no x ∈ X is related to more than one y ∈ Y.
Such a function is traditionally denoted in mathematics by f: X -> Y.

Strictly speaking, the rule for a function f: X -> Y should be a set of ordered pairs, each of the form {x,f[x]}. For example, the function
	f: {1, 2, 3, 4} -> {100, 200, 300, 400, 500}
with values
	f(1) =300, f(2) =100, f(3) =500, f(4)= 100
ought to be represented by the list
	{{1,2,3,4},{100,200,300,400,500},{{1,300},{2,100},{3,500},{4,100}}}
whose third entry
	{{1,300},{2,100},{3,500},{4,100}}
is the rule. 
Since, however, we must represent sets in Mathematica as lists, which are intrinsically ordered, it is superfluous to include the element of the domain in each of the pairs {1,300}, etc.  Instead, we merely list the values of the function in the same order in which the corresponding elements of the domain are listed.  Thus this function will be unambiguously represented by the simpler list:
		{{1,2,3,4},{100,200,300,400,500},{300,100,500,100}}

The Mathematica function FunctionQ defined in this notebook tests whether an expression represents a function in this sense.  Thus:

f={{1,2,3},{100,200,300,400},{200,400,200}};
FunctionQ[f]

Here is another example: try to anticipate the result and then explain it:

r = {{a,b,c},{1,2,3},{2,3,0}};
FunctionQ[r]

Composition of functions

To form the composite of functions represented in the form explained here, use the function FunctionCompose defined in this notebook. The expression FunctionCompose[g,f] represents the composite g ∘ f, so that the codomain of f must match the domain of g. For example:

f={{1,2,3},{100,200,300,400},{200,400,200}};
g={{100,200,300,400},{0,π,(Sqrt[2]),(1/3),E},{(1/3),E,(Sqrt[2]),0}};
FunctionCompose[g, f]

Injective, surjective, and bijective functions

Mathematica functions for testing whether a function is injective, surjective, or bijective are defined in the separate notebook Combinatorics.nb. Also defined there are Mathematica functions for forming all functions from one set to another, and for selecting from those only the functions of a specified type, for example, all the injective functions.

Characteristic functions

The basic idea here is to code objects with 1 if they belong to a given set S, and to code them with 0 otherwise. The resulting object is a function—the characteristic function—of the set S. The characteristic function is denoted here by χ, typed as EscchEsc. You may define the characteristic function for a given set S as follows:

(Subscript[χ, S_])[x_]:=If[MemberQ[S,x],(* then*) 1,(* else *) 0]

Note that the larger set S of interest is included as a subscript to χ; you type (Subscript[χ, S])  as EscchEsc_S.

Let's test the definition with the set xx redefined below:

xx={a,b,c};
{(Subscript[χ, xx])[a],(Subscript[χ, xx])[d]}

Mathematica actually can do the work for us by means of its built-in function Boole.

?Boole

Boole[MemberQ[xx,a]]
Boole[MemberQ[xx,d]]

{Boole[2∈Integers],Boole[2∈Rationals]}

{Boole[(Sqrt[2])∈Reals],Boole[(Sqrt[2])∈Rationals]}

Glossary

Names of Mathematica functions about sets, relations, and functions that are defined in this notebook are listed in the next cell.

Off[General::spell1]
Clear[Card,DomainQ,FiniteQ,FunctionCompose,FunctionQ,PowerSet,SetProduct,SetQ,SetsEqualQ,SubsetQ]
On[General::spell1]

Usage messages for those functions are defined in the next several cells.  Reading these usage messages tells you the syntax of the corresponding functions, defined later, and what these functions do.

First, usage messages for functions about sets in general.

∅::usage="The symbol ∅ is an abbreviation for the empty set {}";

Card::usage=
"Card[x] gives the cardinality of x -- the number of elements in x -- if x is a finite set.";

DomainQ::usage="DomainQ[s] is True if s is among a specific list of domains (ℙ,ℕ,ℤ,ℚ,ℝ,ℂ,𝔸,𝔹), False otherwise.";

FiniteQ::usage="FiniteQ[s] is True if s is a finite set, False otherwise.";

PowerSet::usage= "PowerSet[s] (where setQ[s] is True) gives the list of all subsets of s." ;

SetProduct::usage= "SetProduct[x1, ..., xn], where n > 0, gives the cartesian product of all n sets as a list of n-tuples.";

SetQ::usage= "SetQ[x] gives True if x is a set, and False otherwise; {a,b,a} is not a set because a repetition occurs." ;

SetsEqualQ::usage="SetsEqualQ[x,y] gives True if x, y are equal sets, False otherwise.";

SubsetQ::usage= "SubsetQ[ x , y ] gives True if x , y are sets and x is a subset of y, and False otherwise." ;

Next, usage messages for functions about functions.

FunctionCompose::usage= 
"FunctionCompose[g, f] gives the composition of the function g following the function f; the domain of g must equal the codomain of f.";

FunctionQ::usage= 
"FunctionQ[f] gives True if f is a function in the form {domain, codomain, values}, and False otherwise.";

Definitions

Utilities

The next cell contains a technical utility of no direct interest to you.

ds::improper="The expression `1` has been improperly specified. "<>
"For proper syntax type ?`2`.";

Clear[typeCheck]
typeCheck::usage="typeCheck[test,call,stem,expr] evaluates test; if test is True, expr is evaluated; if test is False, message ds::improper is output with call as first argument string and stem as second argument string";
Attributes[typeCheck]={HoldAll};
typeCheck[ test_ , call_String,stem_String,expr_ ]:= If[test,expr,Message[ds::improper,call,stem ]]

Mathematica functions about sets and functions

In order to use the functions defined below, you do not need to understand how they work. In other words, you do not need to understand the Mathematica code that constitutes their definitions—although you can probably decipher some of them). All you need to know is how to use them and what they do. Usage messages were defined in the Glossary section of this notebook.

Off[General::spell1]

First, some special sets.

∅={};

ℝ=Reals;ℤ=Integers;ℂ=Complexes;𝔸=Algebraics;ℙ=Primes;ℚ=Rationals;𝔹=Booleans;ℕ=Naturals;

Next, definitions of functions about sets in genearal.

Card[x_?SetQ]:=Count[x,_]

DomainQ[dom_]:=MemberQ[{ℝ,ℤ,ℂ,𝔸,ℙ,ℚ,𝔹,ℕ},dom]

FiniteQ[x_]:=SetQ[x]&&!DomainQ[x]

PowerSet[set_?SetQ]:=Subsets[set] 

SetProduct[x__?SetQ]:=If[ Length[{x}]==1,Flatten[{x}],
	 Flatten[ Outer[ List,x],Length[{x}]-1 ]]

SetQ[x_]:=(ListQ[x]&&(Length[x]==Length[Union[x]]))~Or~DomainQ[x]

SetsEqualQ[x_,y_]:=SetQ[x]&&SetQ[y]&&(Union[x]===Union[y])

SubsetQ[x_,y_]:=SetQ[x]&&SetQ[y]&&And@@(MemberQ[y,#]&)/@x

Extend definition of Element (∈) from domains to sets (and include additional domains).

Unprotect[Element];
Element[x_,Naturals]:=Element[x,Integers]&&NonNegative[x]
Element[x_,lis_?FiniteQ]:=MemberQ[lis,x]
Protect[Element];

Define notation Subset (⊂) to be synonymous with SubsetQ:

Unprotect[Subset]
Subset[x_,y_]:=SubsetQ[x,y]
Protect[Subset]

Finally, definitions concerning functions .

FunctionCompose[ g_,f_ ]:= typeCheck[FunctionQ[f]&&FunctionQ[g]&&(Union[f[[2]]] ===Union[g[[1]]]), "FunctionCompose[f,g]","FunctionCompose", {f[[1]],g[[2]],Table[ g[[3,Position[g[[1]],f[[3,i]]][[1,1]]]] ,{i,Length[f[[1]]]}]}
	]

FunctionQ[{d_,c_,f_}]:=SetQ[d]&&SetQ[c]&&Head[f]===List&&Length[d]==Length[f]&&SubsetQ[Union[f],c]

On[General::spell1]

Portions of notebook Copyright © 2009 by Murray Eisenberg. All rights reserved.