Use induction to prove that any (finite) list is a permutation of itself—in other words, that the permutation relation is reflexive.

Question

I'm having a bit of trouble with starting this proof by induction. I'm given that the definition of a permutation is:

List a is a permutation of list b if any of the following are true:

• list a and list b are both null, otherwise

• a.head=b.head, and a.tail is a permutation of b.tail

• a.head!=b.head, and there exists a list c such that

• a.tail is a permutation of b.head:c, and

• b.tail is a permutation of a.head:c

Could I get some suggestions?

Answer 1

Here's some structure:

Your base case is when the list is null. Assume that the property holds for a list of length $n$, and look at lists of length $n + 1$.

Now we can split the list into head and tail. The tail is a list of length $n$. Apply the above definitions, but keep in mind that $a = b$.

Let me know in the comments if you'd like a hint.