Motivation
Suppose a program assigns a category to each record. Filtering records and then collecting their categories is different from first collecting all categories and then filtering those labels. Several records may receive the same category, and some declared categories may never occur. These two facts explain many otherwise surprising failures of set formulas involving functions.
This section supplies the set and function foundations used in counting and algorithm specifications. We will read a set identity as a statement about membership, track the domain and codomain of every map, and distinguish pulling a condition back to inputs from sending a collection forward to outputs.
Definitions
Definition 12.4.1
(Sets, subsets and set operations)
Write when belongs to a set . A subset relation means that every member of belongs to ; equality requires both inclusions. The empty set has no members. In particular, for every set , whereas requires the empty set itself to be one of 's objects. The set has one member and is not empty.
Fix a universe whenever taking complements. For , define union by “in at least one,” intersection by “in both,” and difference by “in and not in .” The complement of is . The power set consists of all subsets of , including and itself. A Cartesian product consists of ordered pairs with and ; swapping coordinates generally changes the pair.
Definition 12.4.2
(Functions, domain and codomain)
A function assigns exactly one output in to each input in . Here is its domain and its codomain. Its graph is the subset of . A relation that omits an input, or gives one input two different outputs, is not the graph of a function with that domain. Different inputs may share an output.
Definition 12.4.3
(Image, preimage and fiber)
For and , define
These are the image of and the preimage of . Thus , while . Preimage notation is meaningful for every function, even one without an inverse function. For an output , the set is its fiber. It may be empty or contain several inputs.
Definition 12.4.4
(Composition, injectivity and surjectivity)
If , their composite is , given by : the rightmost map acts first. The identity sends every to itself. A function is injective when equal outputs force equal inputs, and surjective when . It is bijective when both conditions hold. Throughout the inverse-construction discussion below the sets are finite; the set identities themselves do not require finiteness.
Theorem/proposition
Theorem 12.4.5
(Preimages preserve set operations)
For and ,
Also , , and for and ,
Theorem 12.4.6
(Forward images and round trips)
For and ,
The intersection inclusion is equality for every if and only if is injective. Similarly, for every if and only if is injective. The last identity equals for every if and only if is surjective.
Theorem 12.4.7
(Finite inverse constructions, including empty sets)
Let be a function between finite sets. A left inverse is a map with . Such a map exists exactly when is injective and either or . A right inverse is a map with ; one exists exactly when is surjective. A map that is both a left and a right inverse exists exactly when is bijective, and then is unique.
Proof sketch or proof idea
Translate membership before moving symbols
Proof
(Preimages via membership)
For the preimage union identity, take any . Its membership in the left side says . This means or , exactly membership in the right side. Replacing “or” by “and” proves the intersection identity. For the complement, always holds, so is equivalent to within universe . Empty and full preimages follow directly. Finally,
Each line refers to the same input. No inverse function was used.
Concept lensAlgorithmic
Preimages implement a filter on inputs
For finite indexed sets, store the function as an output-index table and a subset as a membership-bit array. To find a preimage, scan the inputs and copy the bit at each input's output index. This costs word operations when table entries and indices fit machine words. To construct an image from an input-membership array, first clear an output array, then scan the inputs and mark the outputs of selected inputs, costing . Repeated marks do not create repeated set members. These procedures explain why pulling back a filter never requires searching for an inverse function, and why an image can forget how many inputs shared an output.
Proof
(Images, witnesses and the intersection inclusion)
For the image union identity, an output has a witness in exactly when it has a witness in at least one of . A witness in is a witness in both, which gives .
Suppose is injective and . Then with and ; injectivity gives , so . Conversely, suppose is not injective, and choose with . For and we get , while , so equality fails.
Proof X-ray
One common witness versus two separate witnesses
The inclusion needs only one witness, and that witness is already common to both sets. The reverse inclusion is where the proof changes character: membership in supplies two inputs, and , that share one output, while membership in needs a single input lying in both sets. The one non-obvious move is therefore from two witnesses to one, and injectivity is used exactly there, to identify with . The hypothesis cannot be weakened: any collision with produces disjoint singletons that break the equality. Surjectivity plays no role, and the argument closes as soon as one input has been found in both sets.
Explain what each round trip forgets
Proof
(What a round trip adds and what it removes)
If , its output lies in , so . More generally, the latter set consists of all inputs sharing an output with some member of . An injective map leaves no additional inputs. Conversely, if all these round trips preserve , apply the equality to : any with must equal . Thus the map is injective.
An output belongs to exactly when it lies in and has some input under . This proves without assuming surjectivity. Equality with for every follows under surjectivity; conversely, taking forces . For one particular , equality merely says that every output in that set occurs. It does not establish surjectivity onto the entire codomain.
Construct inverses rather than just naming them
Proof
(Existence conditions for inverses)
If and , applying gives . Also a map from nonempty into empty cannot exist. These are the two necessary conditions for a left inverse. Conversely, if is injective and is nonempty, choose . Define as the unique input of when , and as otherwise. Then . If is empty, the existence of forces empty too, and the empty map works.
If , every has input , so is surjective. Conversely, for finite list its elements and choose one input for each. The resulting map is a right inverse. If is empty the empty map suffices. A bijection has exactly one input per output, so this construction gives a two-sided inverse. Conversely a two-sided inverse makes both injective and surjective. Uniqueness follows because any inverse must send to that unique input. More generally, if a left inverse and a right inverse both exist, then .
Worked examples
Worked example 12.4.8
(A category map with a collision and an unused output)
Let , and , . For and , , so , whereas . The first round trip sends to . For the preimage is and its image is : green disappears because it never occurs. This one map exhibits the two different sources of information loss.
Worked example 12.4.9
(Proving a set identity with a fixed universe)
For , prove . An element is on the left exactly when it is in neither nor , exactly when it belongs to both complements. The universe must stay fixed: if , , , both sides are . Complementing inside instead would give the empty set and change the claim.
Worked example 12.4.10
(Pulling a filter through a composite)
Let , let , and let return an input's parity. Define by naming the two parity values. The inputs whose composite label is odd form . Pulling the condition back in stages first gives , then . Although is not injective, the preimage formula holds exactly.
Worked example 12.4.11
(One-sided inverses have different obligations)
For the inclusion , the map is a left inverse. No right inverse exists, because output has no input. For , the map is a right inverse; no left inverse exists, because a function cannot recover both inputs from the same output. Finally the unique map is injective but has no left inverse: a left inverse would be a map from into the empty set, and no such map exists.
Common mistakes
Common mistake
(Canceling a preimage against its function)
Do not cancel and as formal symbols. For a preimage of an image, collisions add whole fibers; for an image of a preimage, unused outputs disappear. If happens to be a bijection, its inverse function and the preimage operation are related, but they still act on different types of object: the inverse function acts on elements and the preimage operation on subsets.
Counterexample mode
Images need not preserve complements
A natural guess is . For the category map above and , , but . Red appears on the left because collides with ; green appears on the right because no record has that label, so the two sides fail in different directions. The universally valid complement formula is the preimage formula , with universe on the output side and on the input side.
Common mistake
(Treating one inclusion as an equality)
Showing or proves a bound, not equality. The reverse inclusion is a separate claim, and as the proofs above show it holds for all sets exactly under an injectivity or surjectivity hypothesis.
Common mistake
(Applying an inverse in the wrong order)
Write the type of each map before composing it. A left inverse acts after in , whereas a right inverse acts before in . Test empty sets against these types rather than dismissing them as a notational issue: the empty map is injective but has no left inverse.
Summary
Set identities follow from equivalent membership conditions. A preimage pulls an output condition back to the same input, so it preserves union, intersection and complement. Images require witnesses; collisions can combine different witnesses, and absent outputs limit round trips. Injectivity and surjectivity identify exactly which information can be recovered. Finite inverse constructions expose the corresponding existence and empty-set conditions.
Exercises
Quick check
(Prove by membership. Decide whether and whether .)
Solution · Answer
An element on the left belongs to and belongs to neither nor . Equivalently it is in both and , proving equality. The only subset of the empty set is the empty set, so . Thus the membership assertion is true, and the claimed equality with the empty set is false.
Quick check
(For any and , prove . Give a strict example, and prove equality if is injective.)
Solution · Answer
If , choose with . That cannot belong to , or would belong to . Thus . Strictness occurs for the category map with , : the left side is empty and the right side is . Under injectivity, if with , no input in has output , proving the reverse inclusion.
Quick check
(Prove that for a particular exactly when is a union of whole nonempty fibers. Include the case .)
Solution · Answer
The preimage of the image adds every input sharing an output with a member of . If it adds none, the whole fiber of each member of is contained in , so is the union of those fibers. Conversely a union of fibers already contains every such input, so the round trip adds none. The empty set is the union of an empty family of fibers and satisfies the equality.
Quick check
(For finite sets of sizes and a given injection with , count its left inverses. For a given surjection, count its right inverses in terms of fiber sizes. Explain the empty-bijection case separately.)
Solution · Answer
On the outputs in , a left inverse is forced. Each of the other outputs independently has possible values, giving left inverses. For a surjection, must be one input in the nonempty fiber of , giving right inverses. For the empty bijection there is exactly one inverse, the empty map, agreeing with the empty product one. The left-inverse count was stated with so that no ambiguous value of is needed.