(불러오기) (편집 필터 규칙) [[분류:가져온 문서/오메가]] 산술 위계(Arithmetic Hierarchy)란 1차 산술 위의 명제들을 복잡도를 기준으로 나눈 위계를 말한다. == 정의 == 산술 위계는 다음과 같이 귀납적으로 정의된다. * [math(\Sigma^0_0)]과 [math(\Phi^0_0)]은 유계 양화사 (bounded quantifier)만을 갖는 문장들의 집합이다. * [math(\phi)]가 [math(\Sigma^0_n)]이면 [math(\forall x_1\cdots\forall x_n \phi)]는 [math(\Pi^0_{n+1})]이다. * [math(\phi)]가 [math(\Pi^0_n)]이면 [math(\exists x_1\cdots\exists x_n \phi)]는 [math(\Sigma^0_{n+1})]이다. [Include(틀:가져옴,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]], L=[[https://archive.ph/96kNT|링크]])] (임시 저장) (임시 저장 불러오기)기본값모나코 에디터 normalnamumarknamumark_betamacromarkmarkdowncustomraw (↪️) (💎) (🛠️) (추가) [[분류:가져온 문서/오메가]] 산술 위계(Arithmetic Hierarchy)란 1차 산술 위의 명제들을 복잡도를 기준으로 나눈 위계를 말한다. == 정의 == 산술 위계는 다음과 같이 귀납적으로 정의된다. * [math(\Sigma^0_0)]과 [math(\Phi^0_0)]은 유계 양화사 (bounded quantifier)만을 갖는 문장들의 집합이다. * [math(\phi)]가 [math(\Sigma^0_n)]이면 [math(\forall x_1\cdots\forall x_n \phi)]는 [math(\Pi^0_{n+1})]이다. * [math(\phi)]가 [math(\Pi^0_n)]이면 [math(\exists x_1\cdots\exists x_n \phi)]는 [math(\Sigma^0_{n+1})]이다. [Include(틀:가져옴,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]], L=[[https://archive.ph/96kNT|링크]])] 비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다. 편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다. 전송 미리보기
