{
  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: {}
}