请输入您要查询的字词:

 

单词 ArithmeticalHierarchyIsAProperHierarchy
释义

arithmetical hierarchy is a proper hierarchy


By definition, we have Δn=ΠnΣn. In additionPlanetmathPlanetmath, ΣnΠnΔn+1.

This is proved by vacuous quantification. If R is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to ϕ(n) then R is equivalent to xϕ(n) and xϕ(n), where x is some variable that does not occur free in ϕ.

More significant is the proof that all containments are proper. First, let n1 and U be universalPlanetmathPlanetmath for 2-ary Σn relationsMathworldPlanetmath. Then D(x)U(x,x) is obviously Σn. But suppose DΔn. Then DPin, so ¬DΣn. Since U is universal, ther is some e such that ¬D(x)U(e,x), and therefore ¬D(e)U(e,e)¬U(e,e). This is clearly a contradictionMathworldPlanetmathPlanetmath, so DΣnΔn and ¬DΠnΔn.

In addition the recursive join of D and ¬D, defined by

D¬D(x)(y<x[x=2y]D(x))(¬y<x[x=2y]¬D(x))

Clearly both D and ¬D can be recovered from D¬D, so it is contained in neither Σn nor Πn. However the definition above has only unboundedPlanetmathPlanetmath quantifiers except for those in D and ¬D, so D¬D(x)Δn+1ΣnΠn

随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 7:20:40