COMP2121 Chap.4 Relations and Functions
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.
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
- 2Prove injectivity from g(x) equal to g(y).
- 2Prove surjectivity by solving for a preimage.
- 1State the classification.
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.
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.
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.