请输入您要查询的字词:

 

单词 EquivalentFormulationOfSubstitutability
释义

equivalent formulation of substitutability


Proposition 1.

Suppose a variable x occurs free in a wff A. A term t is free for x in A iff no variables in t are bound by a quantifierMathworldPlanetmath in A[t/x].

Proof.

We do inductionMathworldPlanetmath on the complexity of A.

  • If A is atomic, then any t is free for x in A, and clearly A[t/x] is just A, which has no bound variables.

  • If A is of the form BC, then t is free for x in A iff t is free for x in both B and C iff no variables in t are bound in either B or C iff no variables in t are bound in A.

  • Finally, suppose A is of the form yB. Since x is free in A, x is not y, and t is free for x in A iff y is not in t and t is free for x in B iff, by induction, y is not in t and no variables of t are bound in B[t/x] iff no variables of t are bound in yB[t/x], which is just A[t/x] (since xy).

If x does not occur free in A (either x occurs bound in A or not at all in A), then t is obviously free for x in A, but A[t/x] is just A, and there is no guarantee that variables in t are bound in A or not.

In the special case where t is a variable y, we see that y is free for x in A iff y is not bound in A[y/x], provided that x occurs free in A. In other words, y is free for x in A iff no free occurrences of x in A are in the scope of Qy, where Q is either or . So if y is not bound in A, y is free for x in A, regardless of whether x is free or bound in A. Also, x is always free for x in A.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:56:58