{ localUrl: '../page/arithmetical_hierarchy.html', arbitalUrl: 'https://arbital.com/p/arithmetical_hierarchy', rawJsonUrl: '../raw/1mg.json', likeableId: '578', likeableType: 'page', myLikeValue: '0', likeCount: '5', dislikeCount: '0', likeScore: '5', individualLikes: [ 'EricBruylant', 'LironShapira', 'JaimeSevillaMolina', 'IanPitchford', 'StephanieZolayvar' ], pageId: 'arithmetical_hierarchy', edit: '5', editSummary: '', prevEdit: '4', currentEdit: '5', wasPublished: 'true', type: 'wiki', title: 'Arithmetical hierarchy', clickbait: 'The arithmetical hierarchy is a way of classifying logical statements by the number of clauses saying "for every object" and "there exists an object".', textLength: '6041', alias: 'arithmetical_hierarchy', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'EliezerYudkowsky', editCreatedAt: '2016-01-17 00:51:28', pageCreatorId: 'EliezerYudkowsky', pageCreatedAt: '2016-01-16 23:50:04', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '0', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '592', text: '[summary: The arithmetical hierarchy classifies logical statements by the number of nested clauses saying "for every object" and "there exists an object". Statements with one "for every object" clause belong in $\\Pi_1$, and statements with one "there exists an object" clause belong in $\\Sigma_1$. Saying "There exists an object x such that (some $\\Pi_n$ statement treating x as a constant)" creates a $\\Sigma_{n+1}$ statement. Similarly, adding a "For every x" clause outside a $\\Sigma_n$ statement creates a $\\Pi_{n+1}$ statement. Statements that can be formulated in both $\\Pi_n$ and $\\Sigma_n$ are said to lie in $\\Delta_n$. Some interesting consequences are that $\\Pi_1$ statements are falsifiable by observation, $\\Sigma_1$ statements are verifiable by observation, and statements strictly in higher classes can only be probabilistically verified by observation.]\n\n[summary(Technical): The arithmetical hierarchy classifies statements by the number of nested, unbounded quantifiers they contain. The classes $\\Delta_0$, $\\Pi_0$, and $\\Sigma_0$ are equivalent and include statements containing only bounded quantifiers, e.g. $\\forall x < 10: \\exists y < x: x + y < 10$. If, treating $x, y, z...$ as constants, a statement $\\phi(x, y, z...)$ would be in $\\Sigma_n,$ then adjoining the unbounded universal quantifiers $\\forall x: \\forall y: \\forall z: ... \\phi(x, y, z...)$ creates a $\\Pi_{n+1}$ statement. Similarly, adjoining existential quantifiers to a $\\Pi_n$ statement creates a $\\Sigma_{n+1}$ statement. Statements that can be equivalently formulated to be in both $\\Pi_n$ and $\\Sigma_n$ are said to lie in $\\Delta_n$. Interesting consequences include, e.g., $\\Pi_1$ statements are falsifiable by simple observation, $\\Sigma_1$ statements are verifiable by observation, and statements strictly in higher classes can only be probabilistically verified by observation.]\n\nThe arithmetical hierarchy classifies statements according to the number of unbounded $\\forall x$ and $\\exists y$ quantifiers, treating adjacent quantifiers of the same type as a single quantifier.\n\nThe formula $\\phi(x, y) \\leftrightarrow [(x + y) = (y + x)],$ treating $x$ and $y$ as constants, contains no quantifiers and would occupy the lowest level of the hierarchy, $\\Delta_0 = \\Pi_0 = \\Sigma_0.$ (Assuming that the operators $+$ and $=$ are themselves considered to be in $\\Delta_0$, or from another perspective, that for any particular $c$ and $d$ we can verify whether $c + d = d + c$ in bounded time.)\n\nAdjoining any number of $\\forall x_1: \\forall x_2: ...$ quantifiers to a statement that would be in $\\Sigma_n$ if the $x_i$ were considered as constants, creates a statement in $\\Pi_{n+1}.$ Thus, the statement $\\forall x: (x + 3) = (3 + x)$ is in $\\Pi_1.$\n\nSimilarly, adjoining $\\exists x_1: \\exists x_2: ...$ to a statement in $\\Pi_n$ creates a statement in $\\Sigma_{n+1}.$ Thus, the statement $\\exists y: \\forall x: (x + y) = (y + x)$ is in $\\Sigma_2$, while the statement $\\exists y: \\exists x: (x + y) = (y + x)$ is in $\\Sigma_1.$\n\nStatements in both $\\Pi_n$ and $\\Sigma_n$ (e.g. because they have provably equivalent formulations belonging to both classes) are said to lie in $\\Delta_n.$\n\nQuantifiers that can be bounded by $\\Delta_0$ functions of variables already introduced are ignored by this classification schema: the sentence $\\forall x: \\exists y < x: (x + y) = (y + x)$ is said to lie in $\\Pi_1$, not $\\Pi_2$. We can justify this by observing that for any particular $c,$ the statement $\\forall x < c: \\phi(x)$ can be expanded into the non-quantified statement $\\phi(0) \\wedge \\phi(1) ... \\wedge \\phi(c)$ and similarly $\\exists x < c: \\phi(x)$ expands to $\\phi(0) \\vee \\phi(1) \\vee ...$\n\nThis in turn justifies collapsing adjacent quantifiers of the same type inside the classification schema. Since, e.g., we can uniquely encode every pair (x, y) in a single number $z = 2^x \\cdot 3^y$, to say "there exists a pair (x, y)" or "for every pair (x, y)" it suffices to quantify over z encoding (x, y) with x and y less than z.\n\nWe say that $\\Delta_{n+1}$ includes the entire sets $\\Pi_n$ and $\\Sigma_n$, since from a $\\Pi_{n}$ statement we can produce a $\\Pi_{n+1}$ statement just by adding an inner $\\exists$ quantifier and then ignoring it, and we can obtain a $\\Sigma_{n+1}$ statement from a $\\Pi_{n}$ statement by adding an outer $\\forall$ quantifier and ignoring it, etcetera.\n\nThis means that the arithmetic hierarchy talks about *power sufficient to resolve statements*. To say $\\phi \\in \\Pi_n$ asserts that if you can resolve all $\\Pi_n$ formulas then you can resolve $\\phi$, which might potentially also be doable with less power than $\\Pi_n$, but can definitely not require more power than $\\Pi_n.$\n\n# Consequences for epistemic properties\n\nAll and only statements in $\\Sigma_1$ are *verifiable by observation*. If $\\phi \\in \\Delta_0$ then the sentence $\\exists x: \\phi(x)$ can be positively known by searching for and finding a single example. Conversely, if a statement involves an unbounded universal quantifier, we can never be sure of it through simple observation because we can't observe the truth for every possible number.\n\nAll and only statements in $\\Pi_1$ are *falsifiable by observation*. If $\\phi$ can be tested in bounded time, then we can falsify the whole statement $\\forall x: \\phi(x)$ by presenting some single x of which $\\phi$ is false. Conversely, if a statement involves an unbounded existential quantifier, we can never falsify it directly through a bounded number of observations because there could always be some higher, as-yet untested number that makes the sentence true.\n\nThis doesn't mean we can't get [1ly probabilistic confirmation and disconfirmation] of sentences outside $\\Sigma_1$ and $\\Pi_1.$ E.g. for a $\\Pi_2$ statement, "For every x there is a y", each time we find an example of a y for another x, we might become a little more confident, and if for some x we fail to find a y after long searching, we might become a little less confident in the entire statement.', metaText: '', isTextLoaded: 'true', isSubscribedToDiscussion: 'false', isSubscribedToUser: 'false', isSubscribedAsMaintainer: 'false', discussionSubscriberCount: '2', maintainerCount: '1', userSubscriberCount: '0', lastVisit: '2016-02-24 05:54:44', hasDraft: 'false', votes: [], voteSummary: 'null', muVoteSummary: '0', voteScaling: '0', currentUserVote: '-2', voteCount: '0', lockedVoteType: '', maxEditEver: '0', redLinkCount: '0', lockedBy: '', lockedUntil: '', nextPageId: '', prevPageId: '', usedAsMastery: 'false', proposalEditNum: '0', permissions: { edit: { has: 'false', reason: 'You don't have domain permission to edit this page' }, proposeEdit: { has: 'true', reason: '' }, delete: { has: 'false', reason: 'You don't have domain permission to delete this page' }, comment: { has: 'false', reason: 'You can't comment in this domain because you are not a member' }, proposeComment: { has: 'true', reason: '' } }, summaries: {}, creatorIds: [ 'EliezerYudkowsky' ], childIds: [ '1mj' ], parentIds: [ 'math' ], commentIds: [], questionIds: [], tagIds: [ 'c_class_meta_tag', 'needs_links_meta_tag' ], relatedIds: [], markIds: [], explanations: [], learnMore: [ { id: '1794', parentId: 'arithmetical_hierarchy', childId: '1mj', type: 'subject', creatorId: 'AlexeiAndreev', createdAt: '2016-06-17 21:58:56', level: '1', isStrong: 'false', everPublished: 'true' } ], requirements: [ { id: '1789', parentId: 'reads_algebra', childId: 'arithmetical_hierarchy', type: 'requirement', creatorId: 'AlexeiAndreev', createdAt: '2016-06-17 21:58:56', level: '1', isStrong: 'false', everPublished: 'true' }, { id: '1795', parentId: 'reads_logic', childId: 'arithmetical_hierarchy', type: 'requirement', creatorId: 'AlexeiAndreev', createdAt: '2016-06-17 21:58:56', level: '1', isStrong: 'false', everPublished: 'true' } ], subjects: [], lenses: [ { id: '7', pageId: 'arithmetical_hierarchy', lensId: '1mj', lensIndex: '0', lensName: 'If you don't read logic', lensSubtitle: '', createdBy: '1', createdAt: '2016-06-17 21:58:56', updatedBy: '1', updatedAt: '2016-06-17 21:58:56' } ], lensParentId: '', pathPages: [], learnMoreTaughtMap: {}, learnMoreCoveredMap: {}, learnMoreRequiredMap: {}, editHistory: {}, domainSubmissions: {}, answers: [], answerCount: '0', commentCount: '0', newCommentCount: '0', linkedMarkCount: '0', changeLogs: [ { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18620', pageId: 'arithmetical_hierarchy', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-08 15:16:49', auxPageId: 'c_class_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18619', pageId: 'arithmetical_hierarchy', userId: 'EricBruylant', edit: '0', type: 'deleteTag', createdAt: '2016-08-08 15:16:43', auxPageId: 'b_class_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18617', pageId: 'arithmetical_hierarchy', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-08 15:16:40', auxPageId: 'needs_links_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18609', pageId: 'arithmetical_hierarchy', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-08 15:09:35', auxPageId: 'b_class_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5386', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '5', type: 'newEdit', createdAt: '2016-01-17 00:51:28', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5385', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '4', type: 'newEdit', createdAt: '2016-01-17 00:50:11', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5384', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '3', type: 'newEdit', createdAt: '2016-01-17 00:49:40', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5383', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '2', type: 'newRequirement', createdAt: '2016-01-17 00:02:56', auxPageId: 'reads_logic', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5379', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '2', type: 'newTeacher', createdAt: '2016-01-17 00:01:35', auxPageId: '1mj', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5375', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '2', type: 'newChild', createdAt: '2016-01-17 00:00:58', auxPageId: '1mj', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5374', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '2', type: 'newEdit', createdAt: '2016-01-17 00:00:20', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5367', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '1', type: 'newEdit', createdAt: '2016-01-16 23:50:04', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5366', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '0', type: 'newRequirement', createdAt: '2016-01-16 23:49:18', auxPageId: 'reads_algebra', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5364', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '0', type: 'deleteRequirement', createdAt: '2016-01-16 22:57:21', auxPageId: 'reads_algebra', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5362', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '0', type: 'newRequirement', createdAt: '2016-01-16 22:56:19', auxPageId: 'reads_algebra', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '5360', pageId: 'arithmetical_hierarchy', userId: 'EliezerYudkowsky', edit: '0', type: 'newParent', createdAt: '2016-01-16 22:54:57', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'true', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }