mathbase
Learn/sets functions/Constructing Functions in Proofs

Lesson subsection

Constructing Functions in Proofs

Read the explanation, try the on-paper prompts, then explain the idea in your own words. Use AI feedback as a mentor, not a shortcut.

10–20 min focusProof-first mindset

Best flow: read → think on paper → write a short explanation → refine with feedback.

Reading

Core explanation

Sometimes in a proof you must construct a function to show a relationship between sets, especially in counting, cardinality, and equivalence arguments.

Common patterns:

  • To show two sets have the same size (infinite or finite), construct a bijection between them.
  • To prove inequalities about sizes, construct injections or surjections.
  • To prove existence of solutions, define a function whose properties guarantee a solution.

Example: To show there are as many even integers as integers, define: f : ℤ → 2ℤ by f(n) = 2n.

  • f is injective and surjective (a bijection), so the sets have the same cardinality.

In more abstract proofs, constructing the right function is often the main creative step.

TL;DR — key idea

Constructing functions (especially injections, surjections, and bijections) is a central proof technique for comparing sizes of sets and showing structural relationships.

Try these in your notebook

Don’t skip this – writing proofs or explanations on paper is where most of the learning actually happens.

  • 1

    Construct a function f : ℕ → ℕ that is: 1. Injective but not surjective. 2. Surjective but not injective. Describe the rule explicitly and briefly justify its properties.

Once you’ve sketched some ideas, summarize the main insight in the reflection box on the right.

Check your understanding

In 3–6 sentences, explain the core idea of this subsection as if you were teaching a friend who hasn’t seen it. Focus on the logic, not just the final statements.

AI is optional. Use it to spot gaps and sharpen your wording, not to replace your own thinking.