{
  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: '472',
  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'
    }
  }
}