Which properties survive composition?

Try

Compose two arrow diagrams: f takes X to Y and g takes Y to Z. Only the part of g reached by f participates in the composite. Properties of unused inputs in Y can therefore differ from properties visible in g∘f.

Predict

Predict what a collision in f does to the composite. If f(a)=f(b), applying the same g cannot separate those outputs. Injectivity means equal outputs force equal inputs. Surjectivity means every element of the stated codomain is reached; changing the codomain can change surjectivity.

Experiment

Build X with two inputs and Y with three. Send the two inputs to different elements of Y. Let g send those two to different outputs, but let the unused third Y element collide with one of them. Trace both full-domain g and the composite before classifying either.

Understand

Worked argument: if g∘f is surjective onto Z, then g is surjective onto Z. Take arbitrary z∈Z. Composite surjectivity supplies x∈X with g(f(x))=z. Set y=f(x), which belongs to Y. Then g(y)=z, giving the witness required for surjectivity of g.

An invalid extension claims that f must also be surjective onto Y. Composite coverage of Z never promised coverage of unused Y elements. For example, an inclusion of two elements into a three-element set can miss the third while g still sends the included elements onto Z.

Classify a whole family of integer maps

For f(n)=floor((2n−1)/3), both n=−1 and n=0 give output −1. Floor means the greatest integer no larger than its argument: floor(−1/3)=−1, not zero. These two preimages disprove injectivity. But a collision does not tell us whether every integer is an output.

Prove a fiber is empty, rather than stopping a search

Predict whether changing the numerator scale a or denominator m causes collisions or missing outputs. Compare complete preimage intervals for negative and positive output values.

a 12345 m 12345 b -2-1012 Reset

f(n)=floor((2n + (-1))/3), from integers to integers. The theorem gives: not injective; onto.

Output y	Least possible input	Greatest possible input	All preimages
-4	-5	-5	-5
-3	-4	-3	-4, -3
-2	-2	-2	-2
-1	-1	0	-1, 0
0	1	1	1
1	2	3	2, 3
2	4	4	4
3	5	6	5, 6
4	7	7	7

Each row is a complete fiber by the proved inequalities, not a truncated input search. Only nine output values are displayed; the global classification comes from the proof, not these rows. Temporary state, at most45 listed inputs; no automatic mastery.

Let a and m be positive integers, b any integer, and define f from Z to Z by f(n)=floor((an+b)/m). For an arbitrary integer output y, the floor definition gives my ≤ an+b < m(y+1). Thus the complete fiber consists of the integers from ceil((my−b)/a) through ceil((m(y+1)−b)/a)−1, inclusive. Here ceil is the least integer no smaller than its argument. The upper endpoint subtracts one because the upper inequality is strict, even when its endpoint is an integer. If the lower endpoint exceeds the upper one, the fiber is empty; otherwise every integer in that interval is a preimage. Dividing by a and m preserves inequality signs because both are positive.

Injective exactly when a≥m. If a≥m, increasing n by one increases the unfloored value by at least one, so the floors strictly increase. If a<m, monotonicity places f(0), …, f(m) between f(0) and f(0)+a, because f(n+m)=f(n)+a. There are m+1 inputs but at most a+1 integer outputs in this interval; the pigeonhole principle gives a collision.

Onto exactly when a≤m. If a≤m, the preimage half-open real interval [(my−b)/a, (m(y+1)−b)/a) has length m/a at least one. Its left endpoint rounded upward lies inside: if the interval is [L,U), then L≤ceil(L)<L+1≤U. This constructs a preimage for every y, including negative y. If a>m, the already proved strict increase puts m+1 output values f(0), …, f(m) inside an integer interval containing a+1 values. At least one interior integer is skipped. Inputs below zero produce values below f(0), and inputs above m produce values above f(m), so none can fill that gap.

Consequently the map is bijective exactly when a=m. Then f(n)=n+floor(b/m), a translation with inverse y↦y−floor(b/m). The codomain is part of the claim: restricting any map’s codomain to its image makes it onto that image, but does not remove collisions.

Nonlinear maps require a new image argument

Consider h(n)=n|n| on integers. It equals n² for nonnegative n and −n² for negative n. It is strictly increasing within each side, and negative inputs have negative outputs while nonnegative inputs have nonnegative outputs. Thus it is injective on all integers. Its image is zero together with positive and negative perfect squares, so it is not onto Z; two is missing. It is bijective onto that signed-square image, with the signed square-root inverse. In contrast, n↦n² has collisions n and −n for every nonzero n and misses negative integers. Neither monotonicity of a real formula nor a finite table should replace the required integer image/preimage evidence.

Apply

In a proof, begin from the definition of the desired property. Injectivity starts with two inputs and equal outputs; surjectivity starts with an arbitrary target and constructs an input. In counterexamples, give every function value rather than leaving the problematic part unspecified.

Continue

Depth: show that if f and g are both injective then g∘f is injective, and similarly for surjectivity. Then identify which converses fail. Investigate how an additional surjectivity assumption on f lets composite injectivity imply injectivity of g.