4.3. Functions 71
The elements of a set are required to be distinct, but terms in a sequence can
be the same. Thus,.a;b;a/is a valid sequence of length three, butfa;b;ag
is a set with two elements —not three.
The terms in a sequence have a specified order, but the elements of a set do
not. For example,.a;b;c/and.a;c;b/are different sequences, butfa;b;cg
andfa;c;bgare the same set.
Texts differ on notation for theempty sequence; we usefor the empty
sequence.
The product operation is one link between sets and sequences. Aproduct of sets,
S 1 S 2 Sn, is a new set consisting of all sequences where the first component
is drawn fromS 1 , the second fromS 2 , and so forth. For example,Nfa;bgis
the set of all pairs whose first element is a nonnegative integer and whose second
element is anaor ab:
Nfa;bgDf.0;a/;.0;b/;.1;a/;.1;b/;.2;a/;.2;b/;:::g
A product ofncopies of a setSis denotedSn. For example,f0;1g^3 is the set of
all 3 -bit sequences:
f0;1g^3 Df.0;0;0/;.0;0;1/;.0;1;0/;.0;1;1/;.1;0;0/;.1;0;1/;.1;1;0/;.1;1;1/g
4.3 Functions
Afunctionassigns an element of one set, called thedomain, to an element of an-
other set, called thecodomain. The notation
f WA!B
indicates thatf is a function with domain,A, and codomain,B. The familiar
notation “f.a/D b” indicates thatf assigns the elementb 2 Btoa. Hereb
would be called thevalueoffatargumenta.
Functions are often defined by formulas as in:
f 1 .x/WWD
1
x^2
wherexis a real-valued variable, or
f 2 .y;z/WWDy 10 yz
