2011/11/01 by Ranald Clouston
Computer Science · #cs.LO
paper · pdf · doi:10.4204/eptcs.71.4
published as EPTCS 71, 2011, pp. 44-57 · In Proceedings LFMTP 2011, arXiv:1110.6685
arxiv created 2011/11/01 · arxiv updated 2011/11/02
Many formal systems, particularly in computer science, may be captured by equations modulated by side conditions asserting the "freshness of names"; these can be reasoned about with Nominal Equational Logic (NEL). Like most logics of this sort NEL employs this notion of freshness as a first class logical connective. However, this can become inconvenient when attempting to translate results from standard equational logic to the nominal setting. This paper presents proof rules for a logic whose only connectives are equations, which we call Nominal Equation-only Logic (NEoL). We prove that NEoL is just as expressive as NEL. We then give a simple description of equality in the empty NEoL-theory, then extend that result to describe freshness in the empty NEL-theory.