COMP 1002 Unit 6 overview
In this unit we will construct more complex discrete structures such as functions and relations, and discuss their types and properties. We will first define functions, and talk about functions that are one-to-one, onto and bijections, as well as function composition and inverse. Then, we will use the notion of bijection to talk about sizes of infinite sets, showing that a number of sets have the same cardinality as natural numbers (countable sets), yet other sets are uncountable.
Then we will move to talking about binary relations where both elements of the relation come from the same set. These relations are represented by graphs (computer science graphs, which are a different object than graphs of functions plotted in a coordinate system!). We will describe a number of different types of binary relations, their closures (in particular transitive closure) and properties such as what makes a binary relation an order or equivalence.
Readings
Most of the material in this unit is covered in sections 2.3, 2.5, and chapter 9 in the textbook.
Learning objectives
In this unit you will learn a discrete, computer science view of functions and relations. You will learn about their types and operations one can do with them (such as computing an inverse of a function or a transitive closure of a relation). You will also learn about cardinalities of infinite sets: how to compare them, which sets are the same cardinality as natural numbers (countable), which sets are uncountable and how to prove that. Specifically, you will learn to do the following.
- Identify if a given relation is a function, and if so, state what its domain, codomain and range are, and what are the image and preimage of specific elements.
- Identify if a function is total, one-to-one, onto, or a bijection. Give examples of functions with different combinations of these properties, both on a finite domain and on integers.
- Compute composition of functions and inverse of a function.
- Use bijections to compare cardinalities of sets, in particular to prove that sets are countable. Learn that the sets of all integers, all rational numbers and all finite strings over a given finite alphabet are countable, and how to prove that.
- Arrange strings in a string order, as used in proofs of countability.
- Use diagonalization technique to show that some infinite sets are uncountable. Learn that the set of all real numbers, all languages, and in general a power set of a countable sets are uncountable, and how to prove that.
- Give an example of an unsolvable computational problem: the Halting problem.
- Draw directed graphs representing binary relations on a given finite set.
- Identify whether a binary relation is reflexive, anti-reflexive, symmetric, anti-symmetric, transitive, order (total or partial), or equivalence. Give examples of relations with or without each of these properties.
- Compute a reflexive, symmetric and transitive closures of a given binary relation.
- Represent orders using Hasse diagrams, and determine minimal and maximal elements (if they exist).
Vocabulary
You need to know the meaning of the following terminology (and respective notation):
- Function, its domain, codomain, range. Image(x), preimage(y).
- Total vs partial functions, one-to-one, onto, bijection.
- Composition and inverse of functions
- Countable and uncountable sets.
- Halting problem.
- Graph of a binary relation.
- Reflexive, anti-reflexive, symmetric, anti-symmetric, transitive relation, order (total or partial), equivalence.
- Reflexive, symmetric, transitive closure.
- Path and cycle in a graph.
- Equivalence relation, equivalence classes.
- Partial and total order. Hasse diagram of an order.