{
localUrl: '../page/1mj.html',
arbitalUrl: 'https://arbital.com/p/1mj',
rawJsonUrl: '../raw/1mj.json',
likeableId: '580',
likeableType: 'page',
myLikeValue: '0',
likeCount: '2',
dislikeCount: '0',
likeScore: '2',
individualLikes: [
'EricBruylant',
'AlexAppel'
],
pageId: '1mj',
edit: '9',
editSummary: '',
prevEdit: '8',
currentEdit: '9',
wasPublished: 'true',
type: 'wiki',
title: 'Arithmetical hierarchy: If you don't read logic',
clickbait: '',
textLength: '7021',
alias: '1mj',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'EliezerYudkowsky',
editCreatedAt: '2016-04-04 04:04:32',
pageCreatorId: 'EliezerYudkowsky',
pageCreatedAt: '2016-01-17 00:02:37',
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: '418',
text: 'The arithmetical hierarchy is a way of stratifying statements by how many "for every number" and "there exists a number" clauses they contain.\n\nSuppose we say "2 + 1 = 1 + 2". Since this is only a statement about three specific numbers, this statement would occupy the lowest level of the arithmetical hierarchy, which we can equivalently call $\\Delta_0,$ $\\Pi_0,$ or $\\Sigma_0$ (the reason for using all three terms will soon become clear).\n\nNext, suppose we say, "For all numbers x: (1 + x) = (x + 1)." This generalizes over *all* numbers - a universal quantifier - and then makes a statement about each particular number x, that (1 + x) = (x + 1), that involves no further quantifiers and can be verified immediately. This statement is said to be in $\\Pi_1.$\n\nSuppose we say, "There exists a y such that $y^9 = 9^y.$" This is a single existential quantifier. To verify it by sheer brute force, we'd need to start from 0 and then consider successive integers y, checking for each particular y whether it was true that $y^9 = 9^y.$ Since the statement has a single existential quantifier over y, surrounding a statement that for any particular y is in $\\Delta_0,$ it is said to be in $\\Sigma_1.$\n\nSuppose we say, "For every number x, there exists a prime number y that is greater than x." For any particular $c$ the statement "There is a prime number x that is greater than $c$" lies in $\\Sigma_1.$ Universally quantifying over all $c,$ outside of the $\\Sigma_1$ statement about any particular $c,$ creates a statement in $\\Pi_2.$\n\nSimilarly, the statement "There exists a number x such that, for every number y, $(x + y) > 10^9$ would be in $\\Sigma_2,$ since it adjoins a "there exists a number x..." to a statement that lies in $\\Pi_1$ for any particular $x.$\n\nGeneralizing, putting a "There exists an x..." quantifier outside a $\\Pi_n$ statement creates a $\\Sigma_{n+1}$ statement, and putting a "For all y" quantifier outside a $\\Sigma_n$ statement about y creates a $\\Pi_{n+1}$ statement.\n\nIf there are equivalent ways of formulating a sentence such that it can be seen to occupy both $\\Sigma_n$ and $\\Pi_n$, we say that it belongs to $\\Delta_n.$ \n\n# Consequences for epistemic reasoning\n\nStatements in $\\Sigma_1$ are *verifiable*. Taking "There exists $y$ such that $y^9 = 9^y$" as the example, soon as we find any one particular $y$ such that $y^9 = 9^y,$ we can verify the central formula $y^9 = 9^y$ for that particular $y$ immediately, and then we're done.\n\nStatements in $\\Pi_1$ are *falsifiable*. We can decisively demonstrate them to be wrong by finding a particular example where the core statement is false. \n\nSentences in $\\Delta_1$ are those which are both falsifiable and verifiable in finite time.\n\n$\\Pi_2$ and $\\Sigma_2$ statements are not definitely verifiable or falsifiable by brute force. E.g. for a $\\Pi_2$ statement, "For every x there is a y", even after we've found a y for many particular x, we haven't tested all the x; and even if we've searched some particular x and not yet found any y, we haven't yet searched all possible y. But statements in this class can still be probabilistically supported or countersupported by examples; 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 a long time searching, we might become a little less confident.\n\n# Subtleties\n\n## Bounded quantifiers don't count\n\nThe statement, "For every number $x,$ there exists a prime number $y$ smaller than $x^x$" is said to lie in $\\Pi_1$, not $\\Pi_2$. Since the existence statement is bounded by $x^x$, a function which can itself be computed in bounded time, in principle we could just search through every possible $y$ that is less than $x^x$ and test it in bounded time. For any particular $x,$ such as $x = 2,$ we could indeed replace the statement "There exists a prime number $y$ less than $2^2$" with the statement "Either 0 is a prime number, or 1 is a prime number, or 2 is a prime number, or 3 is a prime number" which contains no quantifiers at all. Thus, in general within the arithmetical hierarchy, bounded quantifiers don't count.\n\nWe similarly observe that the statement "For every number $x,$ there exists a prime number $y$ smaller than $x^x$" is *falsifiable* - we could falsify it by exhibiting some particular constant $c,$ testing all the numbers smaller than $c^c,$ and failing to find any primes. (As would in fact be the case if we tested $c=1.$)\n\n## Similar adjacent quantifiers can be collapsed into a single quantifier\n\nSince bounded quantifiers don't count, it follows more subtly that we can combine adjacent quantifiers of the same type, since there are bounded ways to *encode* multiple numbers in a single number. For example, the numbers x and y can be encoded into a single number $z = 2^x \\cdot 3^y$. So if I want to say, "For every nonzero integers x, y, and z, it is not the case that $x^3 + y^3 = z^3$" I can actually just say, "There's no number $w$ such that there exist nonzero x, y, and z *less than w* with $w = 2^x \\cdot 3^y \\cdot 5^z$ and $x^3 + y^3 = z^3.$" Thus, the three adjacent universal quantifiers over all x, y, and z can be combined. However, if the sentence is "for all x there exists y", there's no way to translate that into a statement about a single number z, so only alike quantifiers can be collapsed in this way.\n\nWith these subtleties in hand, we can see, e.g., that Fermat's Last Theorem belongs in $\\Pi_1,$ since FLT says, "For *every* w greater than 2 and x, y, z greater than 0, it's not the case that $x^w + y^w = z^w.$ This implies that like any other $\\Pi_1$ statement, Fermat's Last Theorem should be falsifiable by brute force but not verifiable by brute force. If a counterexample existed, we could eventually find it by brute force (even if it took longer than the age of the universe) and exhibit that example to decisively disprove FLT; but there's no amount of brute-force verification of particular examples that can prove the larger theorem.\n\n## How implications interact with falsifiability and verifiability\n\nIn general, if the implication $X \\rightarrow Y$ holds, then:\n\n- If $Y$ is falsifiable, $X$ is falsifiable.\n- If $X$ is verifiable, $Y$ is verifiable.\n\nThe converse implications do not hold.\n\nAs an example, consider the $\\Pi_2$ statement "For every prime $x$, there is a larger prime $y$". Ignoring the existence of proofs, this statement is unfalsifiable by direct observation. The falsifiable $\\Pi_1$ statement, "For every prime $x$, there is a larger prime $y = f(x) = 4x+1$ would if true imply the $\\Pi_2$ statement." But this doesn't make the $\\Pi_2$ statement falsifiable. Even if the $\\Pi_1$ assertion about the primeness of $4x+1$ in particular is false, the $\\Pi_2$ statement can still be true (as is indeed the case). [comment: Patrick, is there a particular reason we want this knowledge to be accessible to people who don't natively read logic? I.e. were you making something else rely on it?]',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '2016-02-24 05:54:46',
hasDraft: 'false',
votes: [],
voteSummary: [
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0'
],
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: {
Summary: 'The arithmetical hierarchy is a way of stratifying statements by how many "for every number" and "there exists a number" clauses they contain.'
},
creatorIds: [
'EliezerYudkowsky',
'AlexeiAndreev',
'NoahWalton',
'PatrickLaVictoir'
],
childIds: [],
parentIds: [
'arithmetical_hierarchy'
],
commentIds: [],
questionIds: [],
tagIds: [
'needs_clickbait_meta_tag',
'c_class_meta_tag',
'needs_links_meta_tag'
],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [
{
id: '1793',
parentId: 'reads_algebra',
childId: '1mj',
type: 'requirement',
creatorId: 'AlexeiAndreev',
createdAt: '2016-06-17 21:58:56',
level: '1',
isStrong: 'false',
everPublished: 'true'
}
],
subjects: [
{
id: '1794',
parentId: 'arithmetical_hierarchy',
childId: '1mj',
type: 'subject',
creatorId: 'AlexeiAndreev',
createdAt: '2016-06-17 21:58:56',
level: '1',
isStrong: 'false',
everPublished: 'true'
}
],
lenses: [],
lensParentId: 'arithmetical_hierarchy',
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: '18622',
pageId: '1mj',
userId: 'EricBruylant',
edit: '0',
type: 'newTag',
createdAt: '2016-08-08 15:18:57',
auxPageId: 'c_class_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18624',
pageId: '1mj',
userId: 'EricBruylant',
edit: '0',
type: 'deleteTag',
createdAt: '2016-08-08 15:18:57',
auxPageId: 'b_class_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18621',
pageId: '1mj',
userId: 'EricBruylant',
edit: '0',
type: 'newTag',
createdAt: '2016-08-08 15:18:45',
auxPageId: 'needs_links_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18610',
pageId: '1mj',
userId: 'EricBruylant',
edit: '0',
type: 'newTag',
createdAt: '2016-08-08 15:10:04',
auxPageId: 'b_class_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17131',
pageId: '1mj',
userId: 'EricBruylant',
edit: '0',
type: 'newTag',
createdAt: '2016-07-19 02:09:09',
auxPageId: 'needs_clickbait_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '9215',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '9',
type: 'newEdit',
createdAt: '2016-04-04 04:04:32',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '9214',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '8',
type: 'newEdit',
createdAt: '2016-04-04 04:02:50',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '9213',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '7',
type: 'newEdit',
createdAt: '2016-04-04 04:02:24',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '9212',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '6',
type: 'newEdit',
createdAt: '2016-04-04 04:01:48',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '9205',
pageId: '1mj',
userId: 'PatrickLaVictoir',
edit: '5',
type: 'newEdit',
createdAt: '2016-04-03 20:18:25',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '9204',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '4',
type: 'newEdit',
createdAt: '2016-04-03 18:54:03',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '8670',
pageId: '1mj',
userId: 'NoahWalton',
edit: '3',
type: 'newEdit',
createdAt: '2016-03-18 20:48:31',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '6449',
pageId: '1mj',
userId: 'AlexeiAndreev',
edit: '2',
type: 'newEdit',
createdAt: '2016-02-05 01:50:20',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '5381',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '1',
type: 'newEdit',
createdAt: '2016-01-17 00:02:37',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '5380',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '0',
type: 'newSubject',
createdAt: '2016-01-17 00:01:35',
auxPageId: 'arithmetical_hierarchy',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '5378',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '0',
type: 'newRequirement',
createdAt: '2016-01-17 00:01:26',
auxPageId: 'reads_algebra',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '5376',
pageId: '1mj',
userId: 'EliezerYudkowsky',
edit: '0',
type: 'newParent',
createdAt: '2016-01-17 00:00:58',
auxPageId: 'arithmetical_hierarchy',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {
lessTechnical: {
likeableId: '4082',
likeableType: 'contentRequest',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '198',
pageId: '1mj',
requestType: 'lessTechnical',
createdAt: '2017-10-22 07:24:22'
}
}
}