Coincidence lemma

The coincidence lemma is a set of mathematical logic which makes the obvious statement that the truth value of an interpreted formula depends only on the interpretations of those symbols that actually appear in the formula.

Propositional logic

The coincidence lemma in propositional logic describes the behavior of a given propositional formula with regard to the assignment of its propositional variables. It clearly states that (apart from the structure of the formula itself) the truth value of a formula depends exclusively on the truth values ​​of the propositional variables contained in the formula.

Statements from so-called propositional variables and the Boolean operations and set up, for example . An assignment is a mapping that assigns one of the two truth values true or false to each variable , from which the truth value of the statement can then be determined. Is such a statement, one writes when the assignment becomes true. Formally, the coincidence lemma can now be expressed as follows: ${\displaystyle p_{1},p_{2},\ldots }$ ${\displaystyle \land ,\lor }$ ${\displaystyle \neg }$ ${\displaystyle p_{1}\land (p_{2}\lor \neg p_{3}\lor p_{7})\land \neg p_{2}}$ ${\displaystyle b}$ ${\displaystyle \alpha }$ ${\displaystyle b\vDash \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle b}$

• Let b and b 'be two assignments and be a statement. If for all propositional variables occurring in, the following applies: ${\displaystyle \alpha }$ ${\displaystyle b(p_{i})=b'(p_{i})}$ ${\displaystyle \alpha }$

${\displaystyle b\vDash \alpha }$exactly when . ${\displaystyle b'\vDash \alpha }$

Predicate logic

In predicate logic , formulas are interpreted by models , with each variable being assigned to an element of the model set (universe of the model). In addition, all non-logical symbols of the so-called signature in the model set are interpreted, i.e. an element of the model set is assigned to a constant symbol, a function on the model set is assigned to a function symbol and a relation on the model set is assigned to a relation symbol. A typical signature is used to form formulas in ring or body theory with an arrangement . An example of a typical statement is ${\displaystyle S=\{0,1,+,\cdot ,<\}}$

${\displaystyle \forall b\,\forall c\,(\neg a=0\rightarrow \exists x\,(a\cdot x+b=c))}$,

which asserts the solvability of linear equations, where the variable is free, i.e. not yet fixed. The interpretation of this formula in the ring , i.e. the constant symbols 0 and 1 are interpreted as the integers 0 and 1, the function symbols as addition and multiplication and finally as the usual greater than relation, is known to be wrong, except if through +1 or −1 is interpreted. An analogous interpretation in the body, on the other hand, leads to a true statement with every interpretation of . Obviously the truth content of this statement is independent of the interpretation of the '<' relation, because the symbol <does not appear in the formula. This is exactly the content of the coincidence lemma: ${\displaystyle a}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle +,\cdot }$ ${\displaystyle a}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle a}$

• Let be a formula and be two models over the same set. If the interpretations of the variables occurring in free and the interpretations of all non-logical symbols occurring in match, then the following applies: ${\displaystyle \alpha }$ ${\displaystyle M,M\,'}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

${\displaystyle M\vDash \alpha }$exactly when . ${\displaystyle M\,'\vDash \alpha }$

This technical theorem, the simple proof of which is carried out by means of “induction on the structure of the formula”, is used, for example, for the application of symbol extensions. In doing so, you expand the set of symbols by further symbols that you want to use for any purpose. According to the coincidence lemma, the truth content of the formulas built up using the set of symbols remains unaffected. ${\displaystyle S}$ ${\displaystyle S}$

Individual evidence

1. ↑ Wolfgang Rautenberg: Introduction to Mathematical Logic , Friedr. Vieweg & Sohn 2002, ISBN 3-528-16754-8 , page 8 above
2. ↑ H.-D. Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic , spectrum Akademischer Verlag 1996, ISBN 3-8274-0130-5 , Chapter XI, 4.2
3. ↑ Wolfgang Rautenberg: Introduction to Mathematical Logic , Friedr. Vieweg & Sohn 2002, ISBN 3-528-16754-8 , chapter 2, sentence 3.1