HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the Inversion Lemma

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
inversionthelemmawhat

Problem

I am taking a programming languages course, and we have had to use the Inversion Lemma many times in our proofs of preservation. We have been given the Inversion Lemma in each of these examples, but is there a general statement of the inversion lemma that can be applied to any proof of preservation? Can someone write that out for me/explain it a little bit?

Solution

When you have a collection of rules, an inversion lemma lets you prove the premises of a rule from the conclusion. You can't just assume that inversion is true. You have to prove it by rule induction. However, classes will often give it to you because it is often tedious and easy to prove. The reason inversion doesn't always work is that there may be multiple rules which match the conclusion you are trying to use inversion on, and then you only know that the premises of one of those rules is true, but not which rule.

Context

StackExchange Computer Science Q#21825, answer score: 3

Revisions (0)

No revisions yet.