Demonstration Exercise 5

Problem: Representatives: Real-World Edition

In lab, you developed a number of artificial examples of different variants of functions. In this problem, you'll develop real-world examples of these variants. In any programming language you'd like, write functions (one per each variant) that are:

• A partial function.
• An injective function.
• A surjective function.
• A left-unique partial function.
• A bijection.

Recall that a mathematical function is defined entirely by the values it takes as input and produce as output. In particular, throwing an error is not "outputting" a value!

Additionally, you may need to specify pre-conditions of the types of the input to your function, e.g., restricting something of type int to be a natural number. If you do so, please mention such pre-conditions in a comment in your code.

Problem: A-mazing

One surprising application of equivalence classes is maze generation. Initially, we might start with a completely walled off maze except for distinguished entry and exit points.

┌─┬─┬─┬─┬─┐
├─┼─┼─┼─┤  
├─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┤
└ ┴─┴─┴─┴─┘

The entry for this maze is in the bottom-left corner and the exit is in the top-right. (Note that this choice was arbitrary; we could have flipped entry and exit!)

We can then punch out walls at random:

┌─┬─┬─┬─┬─┐   ┌─┬─┬─┬─┬─┐   ┌─┬─┬─┬─┬─┐
├─┼─┼─┼─┤     ├─┼─┼─┼ ┤     ├─┼ ┼─┼ ┤  
├─┼─┼─┼─┼─┤   ├─┼─┼─┼─┼─┤   ├─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┤ → ├─┼─┼─┼─┼─┤ → ├─┼─┼─┼─┼─┤ → ⋯
├─┼─┼─┼─┼─┤   ├─┼─┼─┼─┼─┤   ├─┼─┼─┼─┼─┤
└ ┴─┴─┴─┴─┘   └ ┴─┴─┴─┴─┘   └ ┴─┴─┴─┴─┘

Until we have a completed maze:

┌───────┬─┐
├── ┌─┐ │
│ ──┴─┤ │ │
│ ┌── │ └ ┤
├─┴── ┼ ╶─┤
└ ────┴───┘

An algorithm for generating a maze proceeds simply: keep punching out walls until the maze is complete. But what does complete mean? In this problem, we'll use the theory of relations to crystallize the notion of maze completeness.

As a starting point, let's consider labeling each of the rooms induced by the walls of our original maze:

a b c d e
f g h i j
k l m n o
p q r s t

With these labels, we observe that $p$ is the room containing the entrance to the maze and $j$ contains the exit.

1. First, formally define our universe $U$ and a binary relation $R$ that captures the notion of a maze and the connection between rooms in a maze.

2. Prove that $R$ is an equivalence.

3. Use $R$ to give a formal definition for what it means to be a maze to be complete. (Hint: we need to relate the rooms containing the entrance and exit in some fashion!)

4. Argue in a few sentences why the algorithm for generating a maze:

   Keep punching out walls randomly until the maze is complete.

   Always generates a maze. Use your formal definition of completeness in your argument.

Problem: The Cyclotron

A cycle in a relation $R$ is a sequence of $k$ distinct elements $x_1,\dots ,x_k$ that are related in sequence and the sequence ends with $x_k$ and $x_1$ being related, i.e.,

$$(x_1,x_2),(x_2,x_3),\dots ,(x_{k-1},x_k),(x_k,x_1)\in R.$$

A cycle is considered non-trivial if $k\ge 2$.

1. Give an artificial example equivalence relation and a non-trivial cycle in that equivalence relation.

2. Give a real-world example of an equivalence relation and an example of a non-trivial cycle in that relation.

3. Recall from the reading that a partial ordering is a reflexive, anti-symmetric, and transitive relation. We'll show that a partial ordering contains no non-trival cycles. To prove this claim, we'll instead show that for any natural number $k$, there does not exist any cycles of size $k$:

   Claim (Cycles and Partial Orders): Let $R$ be a partial order and $k\ge 2$ be a natural number. Then $R$ possess no non-trivial cycles of size $k$.

   To prove this claim, proceed by strong induction on the length $k$ of the cycle under consideration. Since we are proving the non-existence of an object (cycles in this case), you will need to use a proof by contradiction within each case!

   (Hint: when proving this fact by contradiction, you will assume the existence of a cycle of a certain size. Use the properties of a partial order to infer additional relations between the elements of the cycle until a contradiction arises.)