Chapter

Injectivity and Surjectivity

A module on proving injectivity, using surjectivity, cancelling an outside function, and working with preimages in functional equations.
Log in to track solved progress and bookmarks.

Theory

Key Idea

Injectivity and surjectivity in functional equations are often not just assumptions but tools. Injectivity lets us cancel an outside function: from \(f(A)=f(B)\) we get \(A=B\). Surjectivity lets us replace a value \(f(y)\) by an arbitrary variable: if the function is onto, then every \(t\) can be written as \(t=f(y)\).

Basic Facts

To prove injectivity, assume \(f(a)=f(b)\) and insert this equality into the original equation. To prove surjectivity, try to obtain a formula \(f(\text{something})=T\), where \(T\) is arbitrary. If the function is bijective, one may use the unique preimage. On \(\mathbb Q\), additivity immediately gives \(f(x)=cx\); on \(\mathbb R\), this conclusion usually needs continuity, monotonicity, or boundedness.

When to Use This Method

The method is especially useful when the equation contains expressions such as \(f(x+f(y))\), \(f(f(x)+y)\), \(f(f(x))\), or when both sides have the same outside form \(f(\ldots)=f(\ldots)\). If surjectivity is stated, almost always try to replace \(f(y)\) by a new variable.

How to Recognise the Method

Typical signs are: an outside \(f\) has to be removed; two arguments should become equal; a value \(f(y)\) should become an arbitrary \(t\); an inverse function or preimage appears; after substitutions one gets a relation like \(f(x+t)=f(x)+g(t)\).

Typical Mistakes

Do not cancel \(f(A)=f(B)\) before injectivity is proved or given. Do not treat \(f(y)\) as arbitrary before surjectivity is known. Another common mistake is to find a candidate \(f(x)=ax+b\) but not check it in the original equation, where the constant term may create a contradiction.

Mini-checklist

1. Can injectivity be proved from \(f(a)=f(b)\)? 2. Can surjectivity be proved through \(f(\text{expression})=T\)? 3. Is there a place to replace \(f(y)\) by arbitrary \(t\)? 4. What do \(x=0\) and \(y=0\) give? 5. After cancellation, do we get additivity or affinity? 6. Have all found functions been checked?

Examples

Example 1. Cancelling an Injective Function

This example shows that an outside function may be removed only after injectivity is available.

Problem. Let \(f:\mathbb R\to\mathbb R\) be injective and let \(f(f(x)+y)=f(f(y)+x)\) for all \(x,y\). Prove that \(f(x)-x\) is constant.

Solution.

Since \(f\) is injective, from \(f(f(x)+y)=f(f(y)+x)\) we get \(f(x)+y=f(y)+x\). Rearranging gives \(f(x)-x=f(y)-y\) for all \(x,y\). Hence \(f(x)-x\) does not depend on \(x\).

Comment. The key point is not to expand the function, but to remove the outside \(f\).

Example 2. Surjectivity Turns \(f(y)\) into an Arbitrary Number

The whole solution begins by writing \(t=f(y)\).

Problem. Find all surjective \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+f(y)\).

Solution.

Since \(f\) is surjective, the number \(t=f(y)\) is arbitrary. Thus \(f(x+t)=f(x)+t\) for all \(x,t\). Taking \(x=0\), we get \(f(t)=f(0)+t\). Hence \(f(x)=x+c\), where \(c=f(0)\). Checking gives \(f(x+f(y))=x+f(y)+c=f(x)+f(y)\). All such functions work.

Comment. Surjectivity replaces a special value of the function by a free variable.

Example 3. Injectivity from the Equation Itself

Sometimes injectivity is not assumed, but follows from an iteration.

Problem. Let \(f:\mathbb Q\to\mathbb Q\) and \(f(f(x))=x+1\). Prove that \(f\) is bijective.

Solution.

If \(f(a)=f(b)\), then \(f(f(a))=f(f(b))\), hence \(a+1=b+1\), so \(a=b\). Thus \(f\) is injective. Now take any \(T\in\mathbb Q\). We have \(f(f(T-1))=T\), so \(T\) is a value of \(f\). Therefore \(f\) is surjective and hence bijective.

Comment. An iteration \(f(f(x))\) often gives both injectivity and surjectivity.

Example 4. An Equation with Two Answers

This example shows the standard chain: injectivity, then \(f(0)=0\), then additivity.

Problem. Find all \(f:\mathbb Q\to\mathbb Q\) satisfying \(f(x+f(y))=f(x)+y\).

Solution.

Putting \(x=0\), we get \(f(f(y))=f(0)+y\). If \(f(a)=f(b)\), then \(f(f(a))=f(f(b))\), hence \(a=b\); so \(f\) is injective. With \(y=0\), \(f(x+f(0))=f(x)\), and injectivity gives \(f(0)=0\). Therefore \(f(f(y))=y\). Put \(y=f(t)\): then \(f(x+t)=f(x)+f(t)\). On \(\mathbb Q\), this gives \(f(x)=cx\). From \(f(f(y))=y\), we get \(c^2=1\). The answers are \(f(x)=x\) and \(f(x)=-x\), and both work.

Comment. On \(\mathbb Q\), additivity immediately becomes linearity.

Example 5. Surjectivity and a Contradiction

Sometimes replacing \(f(y)\) by \(t\) quickly reveals impossibility.

Problem. Prove that there is no surjective \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+f(y)+1\).

Solution.

By surjectivity, \(t=f(y)\) is arbitrary. Hence \(f(x+t)=f(x)+t+1\) for all \(x,t\). At \(x=0\), this gives \(f(t)=f(0)+t+1\). Substituting back, the left-hand side is \(f(0)+x+t+1\), while the right-hand side is \(f(0)+x+1+t+1\). This gives \(0=1\), a contradiction.

Comment. An extra constant often appears only during the final check.

Example 6. Monotonicity Removes Pathological Solutions

First we obtain additivity; then monotonicity turns it into an ordinary linear function.

Problem. Find all increasing \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+2y\).

Solution.

If \(f(a)=f(b)\), comparing the equations with \(y=a\) and \(y=b\) gives \(a=b\), so \(f\) is injective. With \(y=0\): \(f(x+f(0))=f(x)\), hence \(f(0)=0\). With \(x=0\): \(f(f(y))=2y\), so \(f\) is surjective. Let \(t=f(y)\). Then \(f(t)=2y\), and the original equation becomes \(f(x+t)=f(x)+f(t)\). Thus \(f\) is additive. An increasing additive function is linear: \(f(x)=cx\). From \(f(f(y))=2y\), we obtain \(c^2=2\), and increasing gives \(c>0\). Therefore \(f(x)=\sqrt{2}x\).

Comment. Without regularity on \(\mathbb R\), the additive part could be more complicated.

Example 7. An Inverse Hidden in the Equation

This example teaches how to use preimages once the function is bijective.

Problem. Find all continuous \(f:\mathbb R\to\mathbb R\) such that \(f(f(x)+y)=x+f(y)\).

Solution.

With \(y=0\), we get \(f(f(x))=x+f(0)\), which implies injectivity. The same formula also implies surjectivity. With \(x=0\): \(f(f(0)+y)=f(y)\), so \(f(0)=0\). Hence \(f(f(x))=x\). Put \(y=f(t)\): then \(f(f(x)+f(t))=x+t=f(f(x+t))\). By injectivity, \(f(x)+f(t)=f(x+t)\). A continuous additive function has the form \(f(x)=cx\), and \(f(f(x))=x\) gives \(c^2=1\). Therefore \(f(x)=x\) or \(f(x)=-x\).

Comment. Continuity is used only at the end to exclude nonlinear additive functions.

Example 8. Surjectivity in Jensen's Equation

This is olympiad preparation: an image condition turns a partial equality into an equality for every increment.

Problem. Let \(f:\mathbb R\to\mathbb R\) be continuous and surjective, and suppose \(f(x+f(y))+f(x-f(y))=2f(x)\). Find all such functions.

Solution.

Since \(f\) is surjective, the value \(t=f(y)\) is arbitrary. Therefore \(f(x+t)+f(x-t)=2f(x)\) for all \(x,t\). This means that the value at the midpoint equals the arithmetic mean of the values at the endpoints: \(f\left(\frac{u+v}{2}\right)=\frac{f(u)+f(v)}{2}\). A continuous function with this property is affine: \(f(x)=ax+b\). Surjectivity requires \(a\ne0\). Checking shows that all \(f(x)=ax+b\), \(a\ne0\), work.

Comment. Surjectivity turns \(f(y)\) into any distance from the midpoint.

Problems

Problems

#4.1
#4.1

Cancelling the Outside Function

Functional Equation Grade 10 Grade 11 ★★☆☆☆

Let \(f:\mathbb R\to\mathbb R\) be injective and suppose that \(f(f(x)+y)=f(f(y)+x)\) for all \(x,y\). Prove that there is a constant \(c\) such that \(f(x)=x+c\) for all \(x\).

Details
Problem: ALG-B3-M04-P001
Difficulty: Level 2 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.2
#4.2

An Arbitrary Image

Functional Equation Grade 10 Grade 11 ★★☆☆☆

Find all surjective functions \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+f(y)\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P002
Difficulty: Level 2 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.3
#4.3

Iteration Gives a Bijection

Bijection Grade 10 Grade 11 ★★☆☆☆

Let \(f:\mathbb Q\to\mathbb Q\) satisfy \(f(f(x))=x+1\) for all \(x\in\mathbb Q\). Prove that \(f\) is bijective.

Details
Problem: ALG-B3-M04-P003
Difficulty: Level 2 of 5
Tag: Bijection
Grade: Grade 10, Grade 11
#4.4
#4.4

Surjectivity Without Extra Substitutions

Functional Equation Grade 10 Grade 11 ★★☆☆☆

Find all surjective \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=x+f(y)+1\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P004
Difficulty: Level 2 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.5
#4.5

A Sum Inside the Function

Functional Equation Grade 10 Grade 11 ★★☆☆☆

Let \(f:\mathbb R\to\mathbb R\) be injective and let \(f(f(x)+f(y))=f(x+y)\) for all \(x,y\). Find \(f\).

Details
Problem: ALG-B3-M04-P005
Difficulty: Level 2 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.6
#4.6

Two Involutions on the Rationals

Additive Grade 10 Grade 11 ★★★☆☆

Find all functions \(f:\mathbb Q\to\mathbb Q\) such that \(f(x+f(y))=f(x)+y\) for all \(x,y\in\mathbb Q\).

Details
Problem: ALG-B3-M04-P006
Difficulty: Level 3 of 5
Tag: Additive
Grade: Grade 10, Grade 11
#4.7
#4.7

A Preimage Inside the Argument

Bijection Grade 10 Grade 11 ★★★☆☆

Find all \(f:\mathbb Q\to\mathbb Q\) satisfying \(f(f(x)+y)=x+f(y)\) for all \(x,y\in\mathbb Q\).

Details
Problem: ALG-B3-M04-P007
Difficulty: Level 3 of 5
Tag: Bijection
Grade: Grade 10, Grade 11
#4.8
#4.8

A Coefficient from the Image

Functional Equation Grade 10 Grade 11 ★★★☆☆

Find all surjective \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+2f(y)\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P008
Difficulty: Level 3 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.9
#4.9

An Impossible Squared Coefficient

No Solution Grade 10 Grade 11 ★★★☆☆

Prove that there is no function \(f:\mathbb Q\to\mathbb Q\) such that \(f(x+f(y))=f(x)+3y\) for all \(x,y\in\mathbb Q\).

Details
Problem: ALG-B3-M04-P009
Difficulty: Level 3 of 5
Tag: No Solution
Grade: Grade 10, Grade 11
#4.10
#4.10

The Extra One

No Solution Grade 10 Grade 11 ★★★☆☆

Prove that there is no surjective function \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+f(y)+1\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P010
Difficulty: Level 3 of 5
Tag: No Solution
Grade: Grade 10, Grade 11
#4.11
#4.11

A Shift After an Involution

Additive Grade 10 Grade 11 ★★★★☆

Find all functions \(f:\mathbb Q\to\mathbb Q\) such that \(f(x+f(y))=f(x)+y+1\) for all \(x,y\in\mathbb Q\).

Details
Problem: ALG-B3-M04-P011
Difficulty: Level 4 of 5
Tag: Additive
Grade: Grade 10, Grade 11
#4.12
#4.12

A Golden Equation Without a Rational Answer

No Solution Grade 10 Grade 11 ★★★★☆

Prove that there is no \(f:\mathbb Q\to\mathbb Q\) such that \(f(x+f(y))=f(x)+f(y)+y\) for all \(x,y\in\mathbb Q\).

Details
Problem: ALG-B3-M04-P012
Difficulty: Level 4 of 5
Tag: No Solution
Grade: Grade 10, Grade 11
#4.13
#4.13

Square Root of Two from Injectivity

Monotonicity Grade 10 Grade 11 ★★★★☆

Find all increasing functions \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+2y\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P013
Difficulty: Level 4 of 5
Tag: Monotonicity
Grade: Grade 10, Grade 11
#4.14
#4.14

Continuous Invertibility

Bijection Grade 10 Grade 11 ★★★★☆

Find all continuous functions \(f:\mathbb R\to\mathbb R\) satisfying \(f(f(x)+y)=x+f(y)\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P014
Difficulty: Level 4 of 5
Tag: Bijection
Grade: Grade 10, Grade 11
#4.15
#4.15

The Golden Ratio in a Functional Equation

Additive Grade 10 Grade 11 ★★★★★

Find all continuous \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+f(y)+y\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P015
Difficulty: Level 5 of 5
Tag: Additive
Grade: Grade 10, Grade 11
#4.16
#4.16

A Surjective Composition

Functional Equation Grade 10 Grade 11 ★★★★★

Find all surjective functions \(f:\mathbb R\to\mathbb R\) such that \(f(f(x)+y)=f(x)+f(y)\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P016
Difficulty: Level 5 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.17
#4.17

Midpoints from the Image

Functional Equation Grade 10 Grade 11 ★★★★★

Let \(f:\mathbb R\to\mathbb R\) be continuous and surjective. Find all \(f\) such that \(f(x+f(y))+f(x-f(y))=2f(x)\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P017
Difficulty: Level 5 of 5
Tag: Functional Equation
Grade: Grade 10, Grade 11
#4.18
#4.18

A Hidden Inverse Function

Bijection Grade 10 Grade 11 ★★★★★

Find all increasing functions \(f:\mathbb R\to\mathbb R\) such that \(f(f(x)+f(y))=x+y\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P018
Difficulty: Level 5 of 5
Tag: Bijection
Grade: Grade 10, Grade 11
#4.19
#4.19

A Condition Killing Both Answers

No Solution Grade 10 Grade 11 ★★★★★

Prove that there is no continuous \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+y\) for all \(x,y\) and \(f(2)=3\).

Details
Problem: ALG-B3-M04-P019
Difficulty: Level 5 of 5
Tag: No Solution
Grade: Grade 10, Grade 11
#4.20
#4.20

The Golden Shift

Additive Grade 10 Grade 11 ★★★★★

Find all continuous functions \(f:\mathbb R\to\mathbb R\) such that \(f(x+f(y))=f(x)+f(y)+y+1\) for all \(x,y\).

Details
Problem: ALG-B3-M04-P020
Difficulty: Level 5 of 5
Tag: Additive
Grade: Grade 10, Grade 11

Ladders

No published ladders were found.
Previous Chapter
Next Chapter