I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate result. Can someone please dexplain the definitions for each?


All terms describe formal claims that are true. The main difference is in how they are used.

A lemma is mathematical claim that is (generally) true. In textbooks, Lemma's are usually either proven, left as an exercise, or assumed to be prior knowledge. A lemma is distinguished from a theorem in that the lemma is usually a less important or intermediate result.

An assertion is a claim, again supposed to be true. An assertion can be made in a proof, but also by a computer program or algorithm. In the latter case, the assertion is often tested, i.e. a computer program checks if the claim is true.

An invariant is a property of some (mathematical) process that remains true over time. For example, a loop invariant is a property that remains true during the execution of a loop.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.