Sets and functions

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updates: 8 June 2011

Sets

A set is a collection of objects which are called elements. Write sS if s is an element of a set S.

The empty set is the set with no elements.

A subset T of a set S is a set T such that if tT then tS. Write TS if T is a subset of S.

HW: Show that the emptyset is a subset of every set.

Two sets S and T are equal if ST and TS. Write T=S if the set T is equal to the set S.

Let S and T be sets. The union of S and T is the set ST of all u such that uS or uT, ST = {u | uS or uT}.

Let S and T be sets. The intersection of S and T is the set ST of all u such that uS and uT, ST = {u | uS and uT}.

Let S and T be sets. The sets S and T are disjoint if ST=.

Let S and T be sets. The sets The set S is a proper subset of T if ST and ST. Write ST if S is a proper subset of T.

The product of sets S and T is the set S×T of all ordered pairs (s,t) where sS and tT, S×T = {(s,t) | sS, tT} . More generally, given sets S1 ,, Sn, the product i Si is the set of all tuples ( s1,, sn) such that si Si.

The elements of a set S are indexed by the elements of a set I if each element of S is labeled by a unique element of I. In this case si for iI will often be written to denote elements of S so that S= {si | iI}. (CHECK THIS WORDING WITH THE ORIGINAL.)

Notation: = {,-2, -1,0,1, 2,} is the set of integers, 0 = {0,1, 2,} is the set of nonnegative integers, >0 = {1, 2,3,} is the set of positive integers, [1,n] = {1, 2,,n} for each  n >0, is the set of real numbers, and is the set of complex numbers. .

Example. Let S, T, U, and V be the sets S={1,2}, U={1,2}, T={1,2,3} and V={2,3}. Then

(a)   SUT,
(b)   UV,
(c)   UV=T,
(d)   UV= {2}, and
(e)   S×T= { (1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}.

Functions

Let S and T be sets. A function or map f:ST is given by associating to each element sS a unique element f(s)T. Write f:S T s f(s) Often in mathematics one will try to define a function without being explicitly sure if what has been defined is really a function. In order to check tha ta function is well defined one must check that

(a)   If sS then f(s) T, and
(b)   if s1=s2 then f(s1) =f(s2).

Let S and T be sets. Two functions f:ST and g:ST are equal if they satisfy

if sS      then f(s) =g(s).
Write f=g if f and g are equal functions.

Let S and T be sets and let f:ST be a functions. Let RS. The restriction of f to R is the function f|R defined by f|R :S T r f(r).

A function f:ST is injective if f satisfies the condition

If    s1, s2S and f(s1) =f(s2)      then    s1=s2.

A function f:ST is surjective if f satisfies the condition

If    tT      then    there exists sS such that f(s)=t.

A function is bijective if it is both injective and surjective.

Cardinality

Let S and T be sets. The sets S and T are isomorphic, or have the same cardinality, Card(S) = Card(T) if there is a bijective function from S to T.

Notation: Let S be a set. Then Card(S)= { 0, if S=, n if Card(S) =Card({1,2, ,n}), , otherwise.

Note that even in the case where Card(S) = and Card(T)= it may be that Card(S) Card(T).

Let S be a set.

HW: Show that Card()=, that Card()=, and that Card() Card().

Composition of functions

Let f:ST and g:TU be functions. The composition of f and g is the function gf given by gf:S U s g(f(s)).

Let S be a set. The identity map on S is the function given by idS:S S s s.

Let f:ST be a function. The inverse function to f is a function f-1 :TS such that

ff-1= idT     and     f-1f = idS,
where idT and idS are the identity functions on T and S, respectively.

Let f:ST be a function. An inverse function to f exists if and only if f is bijective.

Examples. It is useful to visualise a function f:ST as a graph with edges (s,f(s)) connecting elements sS and f(s)T. With this idea in mind we have the following examples.

Permutation Diagram S T
(a)  a function
Permutation Diagram S T
(b)  not a function
Permutation Diagram S T
(c)  not a function
Permutation Diagram S T
(d)  an injective function
Permutation Diagram S T
(e)  a surjective function
Permutation Diagram S T
(f)  a bijective function
In these pictures the elements of the left column as elements of the set S and the elements of the right column are the elements of the set T. In order to be a function the graph must have exactly one edge adjacent to each point in S. The function is injective if there is at most one edge adjacent to each point in T. The function is surjective if there is at lease one edge adjacent to each point in T.

Representing functions as graphs, the identity function idS looks like

Permutation Diagram S S
(a)  the identity function ι S

In the pictures below, if the left graph is a pictorial representation of a function f:ST then the inverse function to f, f-1: TS, is represented by the graph on the right; the graph for f-1 is the mirror-image of the graph for f.

Permutation Diagram S T
(b)  the function f
Permutation Diagram T S
(c)  the function f -1

Graph (d) below, represents a function g:ST which is not bijective (it is neither injective nor surjective). The inverse function to g does not exist in this case; graph (e) of a possible candidate, is not the graph of a function.

Permutation Diagram S T
(d)  the function g
Permutation Diagram T S
(e)  not a function

Notes and References

Almost everything in mathematics is built from sets and functions. Groups, rings, fields, vector spaces, ... are all sets with specific functions which have special properties. In the society of mathematics, sets and functions are the individuals and the fascination is the way that the individuals, each one different from the others, interact.

The set of subsets of a set S forms a partially ordered set under inclusion . The union and intersection make the set of subsets of S into a Boolean algebra. Functions are the morphisms in the category 𝒮et of sets and products are products in the category 𝒮et.

References

[Bou] N. Bourbaki, Theory of sets, Springer ????, MR?????.

page history