In this lab, we’ll be exploring the variety of definitions found in today’s reading that span relations and functions. These definitions test our ability to (a) read definitions made from logical propositions and (b) explore definitions using artificial and real-world examples.
\(\newcommand{\set}[1]{\{\, #1 \,\}}\)
Problem 1: Relatable
Consider the following artificial set:
\[ S = \{\, a, b, c, d, e, f \,\} \]
As well as the following relation \(R\) over \(S\):
\[ R = \{\, (a, b), (a, c), (b, d), (c, c), (d, b), (e, b), (e, f) \,\} \]
Compute the following operations over \(R\):
- \(\mathrm{dom}(R)\).
- \(\mathrm{range}(R)\).
- \(R^{-1}\).
- \(R(a)\).
Instantiation this artificial example to a real-life example. That is, give real-life meaning to the set \(S\) and the relation captured by \(R\). Describe this real-life example in a sentence or two.
For each of the operations from part (a), interpret what the operation is “computing” in terms of your real-life example.
Problem 2: Representatives
Uniqueness and totality are deceptively complex definitions. In this problem, we’ll explore them using artificial and real-world examples.
Give artificial examples of the following relations:
- A partial function.
- An injective function.
- A surjective function.
- A left-unique partial function.
- A bijection.
Your examples should possess exactly the properties implied by the definitions and no more. For example, your injective function should not also be bijection. This way, you can use your artificial example to understand precisely what it means for a function be injective.
The notion of partial and (total) functions is an important concept in computer science! Note that the notion of output in a mathematical function corresponds to the function returning a value. Other kinds of ways that a function can produce some kind of observable behavior, e.g., mutating variables, throwing an exception, or printing to the console, do not count as output.
Give an example of a function in a programming language of your choice (e.g., Racket) that is:
- A partial function.
- A surjective function.
Problem 3: Applications to Programming
Here is a common piece of advice about function design couched in terms of the language of relations:
We should heavily favor designing total rather than partial functions whenever possible.
Keep in mind that when we talk about programming language functions, we only count as output the values that a function returns.
- In a sentence or two, clarify what we mean by total versus partial programming language functions.
- In a few sentences, describe why we might favor total versus partial functions by appealing to the definitions of relations we’ve talked about today.
Problem 4: Compression
Imagine that you are writing a file-compressing program ala zip. We can think of this program as a pair of functions that (a) takes a file as input and produces a (presumably) compressed version of the file as output and (b) takes a compressed version of the file and produces the original file as output.
When viewed as functions, we clearly want these functions to be total, i.e., we want to be able to compress any file. However, what about the other properties of functions?
- First suppose that the functions in question were surjective but not injective. In a few sentences, describe whether such a compression program would be a good compression program.
- Now suppose that the functions are injective but not surjective. In a few sentences, describe whether the resulting compression program would be a good compression program.