Course contentsShow
← Computer Science
Lesson 78 of 2,8722. Discrete Mathematics for CSFree lesson

Function Properties: Surjective (Onto)

Understanding surjective functions where every element in the codomain is mapped to by at least one element.

Function Properties: Surjective (Onto)

What You'll Learn

You'll learn what makes a function surjective (onto) and how to verify that every element in the codomain is "covered" by at least one input.

The Core Idea

Recall that a function maps elements from a domain to a codomain. A function is surjective (or onto) when every single element in the codomain has at least one element from the domain mapping to it. In other words, the range (actual outputs) equals the entire codomain.

Analogy: Imagine assigning students to dorm rooms. The function is surjective if every room has at least one student assigned to it. No rooms sit empty. Some rooms might have multiple students (that's fine), but none are skipped.

Formal Definition

A function f: A → B is surjective if:

  • For every element b in the codomain B, there exists at least one element a in the domain A such that f(a) = b.

Example

Consider f: {1, 2, 3} → {x, y} where:

  • f(1) = x
  • f(2) = y
  • f(3) = x

Is this surjective? Yes! Both x and y in the codomain are hit by at least one element (1 and 3 both map to x; 2 maps to y).

Non-Example

Consider g: {1, 2} → {x, y, z} where:

  • g(1) = x
  • g(2) = y

Is this surjective? No! The element z in the codomain is never reached by any input.

Checking Surjectivity

To verify surjectivity, check each codomain element and confirm at least one domain element maps to it. If even one codomain element is "orphaned," the function is not surjective.

Key Takeaway: A function is surjective if its range equals its entire codomain—every possible output value is actually used by some input.