Solutions to Sets and Functions Problems

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

Department of Mathematics
University of Wisconsin, Madison
Madison, WI 53706 USA
ram@math.wisc.edu

Last updates: 10 November 2009

Problems

	Let S, T and U be sets and let f:S→T and g:T→U be functions. Show that if f and g are injective then g∘f is injective, if f and g are surjective then g∘f is surjective, and if f and g are bijective then g∘f is bijective.
	Let f:S→T be a function and let U⊆S. The image of U under f is the subset of T given by fU=fu\|u∈U. Let f:S→T be a function. The image of U under f is the subset of T given by imU=fs\|s∈S. Note that imf=fS. Let f:S→T be a function and let V⊆T. The inverse image of V under f is the subset of S given by f-1V=s∈S\|fs∈V. Let f:S→T be a function and let t∈T. The fiber of f over t is the subset of S given by f-1t=s∈S\|fs=t. Let f:S→T be a function. Show that the set F=f-1t\|t∈T of fibers of the map f is a partition of S.
	Let f:S→T be a function. Define f′:S⟶imfs⟼fs. Show that the map f′ is well defined and surjective. Let f:S→T be a function and let F=f-1t\|t∈imf=f-1t\|t∈T\∅ be the set of nonempty fibers of the map f. Define f^:F⟶Tf-1t⟼t. Show that the map f^ is well defined and injective. Let f:S→T be a function and let F=f-1t\|t∈imf=f-1t\|t∈T\∅ be the set of nonempty fibers of the map f. Define f^′:F⟶imTf-1t⟼t. Show that the map f^′ is well defined and bijective.
	Let be a set. The power set of S, 2S, is the set of all subsets of S. Let S be a set and let 01S be the set of all functions f:S→01. Given a subset T⊆S define a function fT:S→01 by fTs=0,if s∉T,1,if s∈T. Show that the map ψ:2S⟶01ST⟼fT is a bijection.
	Let ∘:S×S→S be an associative operation on a set S. An identity for ∘ is an element e∈S such that e∘s=s∘e=s for all s∈S. Let e be an identity for an associative operation ∘ on a set S. Let s∈S. A left inverse for s is an element t∈S such that t∘s=e. A right inverse for s is an element t′∈S such that s∘t′=e. An inverse for s is an element s-1∈S such that s-1∘s=s∘s-1=e. Let ∘ be an operation on a set S. Show that if S contains an identity for ∘ then it is unique. Let e be an identity for an associative operation ∘ on a set S. Let s∈S. Show that if s has an inverse then it is then it is unique.
	Let S and T be sets and let ιS and ιT be the identity maps on S and T respectively. Show that for any function f:S→T, ιT∘f=f,andf∘ιS=f. Let f:S→T be a function. Show that if an inverse function to f exists then it is unique. (Hint: The proof is very similar to the proof in Ex. 5b above.)

Solutions

	Assume f and g are injective. To show: If s1s2∈S and g∘fs1=g∘fs2 then s1=s2. Assume s1s2∈S and g∘fs1=g∘fs2. Then gfs1=gfs2. Thus, since g is injective, fs1=fs2 Thus, since f is injective, s1=s2. So g∘f is injective. □ Assume f and g are surjective. To show: If u∈U then there exists s∈S such that g∘fs=u. Assume u∈U. Since g is surjective there exists t∈T such that gt=u. Since f is surjective there exists s∈S such that fs=t. So g∘fs=gfs=gt=u. So there exists s∈S such that g∘fs=u. So g∘f is surjective. □ Assume that f and g are bijective. To Show: g∘f is injective. g∘f is surjective. Proof: Since f and g are bijective, f and g are injective. Thus, by (a), g∘f is injective. Since f and g are bijective, f and g are surjective. Thus, by (b), g∘f is surjective. So g∘f is bijective. □
	To show: If s′∈S then s′∈f-1t for some t∈T. If f-1t1∩f-1t2≠∅ then f-1t1=f-1t2. Proof: Assume s′∈S. Then f-1fs′=s∈S\|fs=fs′. Since fs′=fs′, s′∈f-1fs′. Assume f-1t1∩f-1t2≠∅. Let s∈f-1t1∩f-1t2. So fs=t1 and fs=t2 To show: f-1t1=f-1t2. To show: f-1t1⊆f-1t2. f-1t2⊆f-1t1. Proof: Let k∈f-1t1. Then fk=t1=fs=t2. So k∈f-1t2. So f-1t1⊆f-1t2. Let h∈f-1t2. Then fh=t2=fs=t1. So h∈f-1t1. So f-1t2⊆f-1t1. So f-1t1=f-1t2. So the set F=f-1t\|t∈T of fibres of the map f is a partition of S. □
	To show: f′ is well defined. f′ is surjective. Proof: To Show: If s∈S then f′s∈imf. If s1=s2 then f′s1=f′s2. Proof: Assume s∈S. Then f′s=fs∈imf by definition of f′ and imf. Assume s1=s2. Then, by definition of f′, f′s1=fs1=fs2=f′s2. So f′ is well defined. To show: If t∈imf then there exists s∈S such that f′s=t. Assume t∈imf. Then fs=t for some s∈S. So f′s=fs=t. So f′ is surjective. □ To show: f^ is well defined. f^ is injective. Proof: To show: If f-1t∈F then f^f-1t∈T. If f-1t1=f-1t2 then f^f-1t1=f^f-1t2. Proof: Assume f-1t∈F. Then f^f-1t=t∈T, by definition. Assume f-1t1=f-1t2. Let s∈f-1t1. Then s∈f-1t2 also. So t1=s=t2. Then f^f-1t1=t1=t2=f^f-1t2. So f^ is well defined. To Show: If f^f-1t1=f^f-1t2 then f-1t1=f-1t2. Assume f^f-1t1=f^f-1t2. Then t1=t2. To show: f-1t1=f-1t2. This is clearly true since t1=t2. So f^ is injective. □ By part (b) above, the function f^:F⟶Tf-1t⟼t is well defined and surjective. By part (a) above, the function f^′:F⟶imf^f-1t⟼t is well defined and surjective. To show: imf^=imf. f^′ is injective. Proof: To Show: imf^⊆imf. imf⊆imf^. Proof: Assume t∈imf^. Then f-1t is nonempty. So there exists s∈S such that fs=t. So t∈imf. So imf^⊆imf. Assume t∈imf. Then there exists s∈S such that fs=t. So f-1t≠∅. So t∈imf^. So imf⊆imf^. So imf^=imf. To show: If f^′f-1t1=f^′f-1t2 then f-1t1=f-1t2. Assume f^′f-1t1=f^′f-1t2. So t1=t2. So f-1t1=f-1t2. So f^′ is injective. So f^′ is well defined and bijective. □
	To show: ψ is well defined. ψ is bijective. Proof: To show: If T∈2S then ψT=fT∈01S. If T1 and T2 are subsets of S and T1=T2 then ψT1=ψT2. Proof: It is clear from the definition of fT that ψT=fT is a function from S to 01. Assume T1 and T2 are subsets of S and that T1=T2. To show: ψT1=ψT2. To show: fT1=fT2. To show: If s∈S then fT1s=fT2s. Assume s∈S. Case 1: If s∈T1 then, since T1=T2, s∈T2. So fT1s=1=fT2s. Case 2: If s∉T1 then, since T1=T2, s∉T2. So fT1s=0=fT2s. So fT1s=fT2s for all s∈S. So fT1=fT2. So ψT1=fT1=fT2=ψT2. So ψ is well defined. By virtue of Proposition 2.2.3 [??? - CORRECT?] we would like to show: ψ:2S→01S has an inverse function. Given a function f:s→01 define Tf=s∈S\|fs=1. Define a function ϕ:01S→2S by ϕ:01S⟶2Sf⟼Tf. To Show: ϕ is well defined. ϕ is an inverse function to ψ. Proof: To show: If f∈01S then ϕf=Tf∈2S. If f1f2∈01S and f1=f2 then ϕf1=ϕf2. Proof: By definition Tf=s∈s\|fs=1 is a subset of S. Assume f1f2∈12S and f1=f2. To show: ϕf1=ϕf2. To show: Tf1=Tf2. To Show: Tf1⊆Tf2. Tf1⊆Tf2. Proof: Assume s∈Tf1. Then f1s=1. Since f2s=f1s, f2s=1. Thus s∈Tf2. So, Tf1⊆Tf2 Assume s∈Tf2. Then f2s=1. Since f1s=f2s, f1s=1. Thus s∈Tf1. So, Tf2⊆Tf1 So Tf1=Tf2. So ϕf1=ϕf2. So ϕ is well defined. To Show: If T∈2S then ϕψT=T. If f∈01S then ψϕf=f. Proof: Assume T⊆S. To show: ϕψT=T To show: TfT=T. To Show: TfT⊆T. T⊆TfT. Proof: Assume t∈TfT. Then fTt=1. So t∈T. So TfT⊆T. Assume t∈T. Then fTt=1. So t∈TfT. So T⊆TfT. So TfT=T. So ϕψT=T Assume f∈01S. To show: ϕψf=f. By definition, ψϕf=fTf. To show: If s∈S then fTfs=fs. Assume s∈S. Case 1: fs=1. Then s∈Tf. So fTf=1. So fTf=fs. Case 2: fs=0. Then s∉Tf. So fTf=0. So fTf=fs. So fTfs=fs. So ψϕf=f. So ϕ is an inverse function to ψ. So ψ is bijective. □
	Let ee′∈S be identities for ∘. Then e∘e′=e, since e′ is an identity, and e∘e′=e′, since e is an identity. So, e=e′. Let tu∈S be inverses for s. By associativity of ∘, u=t∘s∘u=t∘s∘u=t. □
	Assume f:S→T is a function. To show: ιT∘f=f. f∘ιT=f. Proof: If s∈S then ιTfs=fs. If s∈S then fιSs=fs. (aa) and (ab) follow immediately from the definitions of ιT and ιS. Assume ϕ and ψ are both inverse functions to f. To show: ϕ=ψ. By the definitions of identity and inverse functions ϕ=ϕ∘f∘ψ=ϕ∘f∘ψ=ψ. So, if an inverse functions exists, then it is unique. □

References [PLACEHOLDER]

[BG] A. Braverman and D. Gaitsgory, Crystals via the affine Grassmanian, Duke Math. J. 107 no. 3, (2001), 561-575; arXiv:math/9909077v2, MR1828302 (2002e:20083)