Can two students have the same seat?
A function is a rule that gives each input exactly one output. A seating plan is one: each student gets one seat.
It matters when you build a system. If two students get the same seat, a plan is not one to one. If a seat is never used, it is not onto. This lesson gives you the words and the tests for both.
By the end of this lesson
Note
I can say whether a mapping is a function, one to one or onto.
Key words
| Word | What it means |
|---|---|
| Domain | the set of inputs a mapping starts from |
| Range | the outputs that actually appear |
| Function | a mapping with exactly one output for each input |
| One to one | no two inputs share an output |
| Onto | every item in the target set is an output |
| Relation | any set of pairs linking two sets |
The cells students fill in are left blank in this preview.
A function gives one output for each input
A mapping links each item in one set to an item in another. The set it starts from is the domain. The set it lands in is called the target. The outputs that really appear are the range.
A mapping is a function when every input has exactly one output. An input with two outputs breaks the rule.
Worked example: which of these are functions?
| Mapping | Pairs (input, output) | A function? |
|---|---|---|
| Seats | (Ana, 1) (Ben, 2) (Cai, 3) | Yes |
| Shared seat | (Ana, 1) (Ben, 1) (Cai, 3) | Yes: two inputs may share an output |
| Two seats | (Ana, 1) (Ana, 2) (Cai, 3) | No: Ana has two outputs |
The cells students fill in are left blank in this preview.
Test whether each input appears once
python3 -c "pairs = [(1, 'a'), (2, 'b'), (2, 'c')]; print(len(set(p[0] for p in pairs)) == len(pairs))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a function cannot send two inputs to the same output. It can. A function needs only one output for each input. "No two inputs share an output" is the extra rule called one to one.
One to one and onto are separate tests
A function is one to one when no two inputs share an output. It is onto when every item in the target is used by some input.
With 3 inputs and a target of 2 items, it cannot be one to one. Some two inputs must share an output.
Worked example: four mappings from {1, 2, 3}
| Mapping | Target | One to one? | Onto? |
|---|---|---|---|
| 1 to a, 2 to b, 3 to c | a, b, c | Yes | Yes |
| 1 to a, 2 to a, 3 to b | a, b, c | No: 1 and 2 share a | No: c is unused |
| 1 to a, 2 to b, 3 to c | a, b, c, d | Yes | No: d is unused |
| 1 to a, 2 to a, 3 to b | a, b | No: 1 and 2 share a | Yes |
The cells students fill in are left blank in this preview.
Check the second mapping by program
python3 -c "m = {1: 'a', 2: 'a', 3: 'b'}; t = ['a', 'b', 'c']; print(len(set(m.values())) == len(m), set(m.values()) == set(t))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Try it: test your own mapping
mapping = {1: "a", 2: "b", 3: "c"}
target = ["a", "b", "c", "d"]
used = []
for key in mapping:
if mapping[key] not in used:
used.append(mapping[key])
print("one to one:", len(used) == len(mapping))
print("onto:", len(used) == len(target))
# Add 4: "d" to the mapping and press Run again.
An equivalence relation sorts things into groups
A relation is any set of pairs. A function is a relation where each input appears once.
Some relations sort things into groups. "Has the same remainder when divided by 3" does. Each number lands in exactly one group, and numbers in a group are all related to each other. We call this an equivalence relation.
Worked example: groups by remainder
| Remainder | Numbers from 0 to 8 |
|---|---|
| 0 | 0, 3, 6 |
| 1 | 1, 4, 7 |
| 2 | 2, 5, 8 |
The cells students fill in are left blank in this preview.
List the remainder of each number
python3 -c "print([n % 3 for n in range(9)])"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.