The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Chap.4 Relations and Functions

- one subject, every graph, every model, every mark
6 Chapters3-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 4 of 11 · COMP2121

Relations and Functions

Relations and equivalence

A relation on a set is a set of ordered pairs, drawn as a table or a directed graph. The chapter tests three properties, reflexive, symmetric and transitive, each written as a quantified statement.

A relation with all three is an equivalence relation, and its classes split the set into disjoint parts.

Functions and their properties

A function assigns exactly one output in the codomain to each input in the domain, and its range is the set of outputs actually produced.

Injective functions keep distinct inputs apart, surjective ones reach every element of the codomain, and bijections do both, which makes them a counting tool.

Checking relation properties one at a time

The model solutions verify reflexive, symmetric and transitive separately, each written first as a quantified sentence.

A failure needs only one witness: a single element not related to itself, one pair related one way but not the other, or a triple that breaks transitivity.

When a relation is defined by a divisibility condition, rewrite the condition with a stated multiple before testing it, and use the earlier conditions as tools in the transitive step.

Equivalence classes and partitions

The classes of an equivalence relation never overlap and together cover the whole set, so they form a partition.

Conversely, any partition defines an equivalence relation, with two elements related exactly when they share a part. For relations defined by congruence, the classes are the residue classes, and the number of classes equals the modulus. Writing out the classes explicitly is a short and convincing way to finish any classification question.

In this chapter

What this chapter covers

  • 01

    Relations as ordered pairs

  • 02

    Reflexive, symmetric and transitive

  • 03

    Equivalence relations and classes

  • 04

    Domain, codomain and range

  • 05

    Injective and surjective functions

  • 06

    Bijections for counting

Worked example · free

Read one-to-one and onto from arrow diagrams

Q [5 marks]. This practice weighting was set for revision and is not an official University marking scheme. Decide whether g from the integers to the integers, g(x) equal to x plus 4, is injective, surjective or both, with proof.
Two arrow diagrams separate the two function properties.Two arrow diagrams separate the two function properties. On the left each element of A has its own target, so the map is one-to-one, but one element of B receives nothing; on the right every element of B is hit, so the map is onto, but two inputs share an output.one-to-oneone target missedontotwo inputs shareABAB
Two arrow diagrams separate the two function properties. On the left each element of A has its own target, so the map is one-to-one, but one element of B receives nothing; on the right every element of B is hit, so the map is onto, but two inputs share an output.
  • 2Prove injectivity from g(x) equal to g(y).
  • 2Prove surjectivity by solving for a preimage.
  • 1State the classification.
If x plus 4 equals y plus 4 then x equals y, so g is injective. For any integer y, the integer y minus 4 is mapped to y, so every element of the codomain is reached and g is surjective. Being both, g is a bijection, and its inverse subtracts 4.
Sia tip — Prove properties for an arbitrary element; a few checked values are not a proof.
Glossary

Key terms

Equivalence relation
A relation that is reflexive, symmetric and transitive.
Equivalence class
The set of all elements related to a given element under an equivalence relation.
Codomain
The set a function maps into, which may be larger than its range.
Bijection
A function that is both injective and surjective.
FAQ

Relations and Functions FAQ

What is the difference between codomain and range?

The codomain is the set named as the target of the function. The range is the subset of outputs actually produced. Squaring on the integers has the integers as codomain but no negative numbers in its range.

How do I show a relation is not transitive?

Exhibit three elements a, b and c with a related to b and b related to c, but a not related to c. One such triple is a complete counterexample.

Why are bijections useful for counting?

For finite sets, a bijection exists exactly when the sets have the same size. To count a set, match it one to one with a set whose size is already known.

Can a function be onto but not one-to-one?

Yes, when the domain is larger than the codomain or the rule repeats values. Mapping each integer to its value divided by two and rounded down reaches every integer, but sends two inputs to each output, so it is onto without being one-to-one.

How do I show a function is not injective?

Find two different inputs that give the same output. For squaring on the integers, two and minus two both map to four, which settles the question in one line. When the domain is restricted to non-negative integers the same rule becomes injective, so always check the stated domain.

Study strategy

Exam move

Write the three relation properties and the two function properties as quantified sentences and keep them visible while practising. For every yes, write a general argument; for every no, find the smallest counterexample. Change the domain or codomain of a familiar function and reclassify it, because the same formula can change its properties.

When a counterexample is needed, try the smallest possible set first, often with two or three elements. Draw small relations as directed graphs, where loops show reflexivity and paired arrows show symmetry at a glance.

Working through Relations and Functions in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Relations and Functions question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 3-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works