An ordering function is a function f:Z→Z which takes the set of integers, and maps them to another order. One very simple example of an ordering function is a swapping function, which swaps the order of two specific values: fi,j(x)= {i when x=j ;j when x=i ; x when x=x} Another simple ordering function is the identiy function, a function which doesn't change the order at all: Id(x)=x. We can use a recursive definition to define the set of all possible ordering functions. Base Case: Id and all fi,j, with i,j∈Z, are ordering functions. Constructor: If f and g are both ordering functions, then f∘g is an ordering function. Use structural induction to prove that all ordering functions have an inverse: that is, if f is an ordering function, then there is another ordering function f−1 such that f−1∘f=Id.
An ordering function is a function f:Z→Z which takes the set of integers, and maps them to another order.
One very simple example of an ordering function is a swapping function, which swaps the order of two specific values:
fi,j(x)= {i when x=j ;j when x=i ; x when x=x}
Another simple ordering function is the identiy function, a function which doesn't change the order at all: Id(x)=x.
We can use a recursive definition to define the set of all possible ordering functions.
Base Case: Id and all fi,j, with i,j∈Z, are ordering functions.
Constructor: If f and g are both ordering functions, then f∘g is an ordering function.
Use structural induction to prove that all ordering functions have an inverse: that is, if f is an ordering function, then there is another ordering function f−1 such that f−1∘f=Id.
Trending now
This is a popular solution!
Step by step
Solved in 5 steps
