{ localUrl: '../page/standard_provability_predicate.html', arbitalUrl: 'https://arbital.com/p/standard_provability_predicate', rawJsonUrl: '../raw/5gt.json', likeableId: '3136', likeableType: 'page', myLikeValue: '0', likeCount: '2', dislikeCount: '0', likeScore: '2', individualLikes: [ 'EricBruylant', 'PatrickStevens' ], pageId: 'standard_provability_predicate', edit: '7', editSummary: 'adding missing conjunction', prevEdit: '6', currentEdit: '7', wasPublished: 'true', type: 'wiki', title: 'Standard provability predicate', clickbait: 'Encoding provability as a statement of arithmetic', textLength: '2755', alias: 'standard_provability_predicate', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'EricRogstad', editCreatedAt: '2016-07-23 18:04:16', pageCreatorId: 'JaimeSevillaMolina', pageCreatedAt: '2016-07-19 12:12:32', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '5', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '84', text: '[summary: In theories extending [-minimal_arithmetic] there exists a $\\exists_1$-formula $\\square_T$(x) which defines the existence of a proof in an [ axiomatizable theory] $T$. \n\nThe formula satisfies [5j7 some nice propereties], but fails to capture some intuitions about provability due to non-standard weirdness.]\n\nWe know that every theory as [expressiveness_mathematics expressive] as [-minimal_arithmetic] (i.e., [Peano_Arithmetic $PA$]) is capable of talking about [statement_mathematics statements] about itself via [encoding encodings] of [sentence_mathematics sentences] of the language of [-arithmetic] into the [45h natural numbers].\n\nOf particular interest is figuring out whether it is possible to write a formula $Prv(x)$ which is true [-46m] there exists a proof of $x$ from the axioms and rules of inference of our theory.\n\nIf we reflect on what a proof is, we will come to the conclusion that a proof is a sequence of symbols which follows certain rules. Concretely, it is a sequence of strings such that either:\n\n1. The string is an [-axiom] of the system or...\n2. The string is a theorem that can be deduced from previous strings of the system by applying a [ rule of inference].\n\nAnd the last string in the sequence corresponds to the theorem we want to prove.\n\nIf the axioms are a [-computable_set], and the rules of inference are also effectively computable, then checking whether a certain string is a proof of a given theorem is also computable.\n\nSince every computable set can be defined by a [ $\\Delta_1$-formula] in arithmetic %%note:[ Proof]%% then we can define the $\\Delta_1$-formula $Prv(x,y)$ such that $PA\\vdash Prv(n,m)$ iff $m$ encodes a proof of the sentence of arithmetic encoded by $n$.\n\nThen a sentence $S$ is a theorem of $PA$ if $PA\\vdash \\exists y Prv(\\ulcorner S \\urcorner, y)$.\n\nThis formula is the standard provability predicate, which we will abbreviate as $\\square_{PA}(x)$, and has some nice properties which correspond to what one would expect of a [-5j7].\n\nHowever, due to [non_standard_model non-standard models], there are some intuitions about provability that the standard provability predicate fails to capture. For example, it turns out that $\\square_{PA}A\\rightarrow A$ [55w is not always a theorem of $PA$].\n\nThere are non-standard models of $PA$ which contain numbers other than $0,1,2,..$ (called [non_standard_models_of_arithmetic non-standard models of arithmetic]). In those models, the standard predicate $\\square_{PA}x$ can be true even if for no natural number $n$ it is the case that $Prv(x,n)$. %%note:This condition is called [ $\\omega$-inconsistency]%% This means that there is a non-standard number which satisfies the formula, but nonstandard numbers do not encode standard proofs!', metaText: '', isTextLoaded: 'true', isSubscribedToDiscussion: 'false', isSubscribedToUser: 'false', isSubscribedAsMaintainer: 'false', discussionSubscriberCount: '2', maintainerCount: '2', userSubscriberCount: '0', lastVisit: '', 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: [ 'JaimeSevillaMolina', 'EricRogstad', 'EricBruylant' ], childIds: [], parentIds: [ 'modal_logic' ], commentIds: [ '5gz' ], questionIds: [], tagIds: [], relatedIds: [], markIds: [], explanations: [ { id: '6422', parentId: 'standard_provability_predicate', childId: 'intro_modern_logic', type: 'subject', creatorId: 'JaimeSevillaMolina', createdAt: '2016-09-24 21:08:56', level: '1', isStrong: 'true', everPublished: 'true' } ], learnMore: [], requirements: [], subjects: [], lenses: [], 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: '19718', pageId: 'standard_provability_predicate', userId: 'JaimeSevillaMolina', edit: '0', type: 'newTeacher', createdAt: '2016-09-24 21:09:32', auxPageId: 'intro_modern_logic', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3219', likeableType: 'changeLog', myLikeValue: '0', likeCount: '2', dislikeCount: '0', likeScore: '2', individualLikes: [], id: '17421', pageId: 'standard_provability_predicate', userId: 'EricRogstad', edit: '7', type: 'newEdit', createdAt: '2016-07-23 18:04:16', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'adding missing conjunction' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17394', pageId: 'standard_provability_predicate', userId: 'JaimeSevillaMolina', edit: '6', type: 'newEdit', createdAt: '2016-07-23 09:32:51', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17393', pageId: 'standard_provability_predicate', userId: 'JaimeSevillaMolina', edit: '5', type: 'newEdit', createdAt: '2016-07-23 09:31:41', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17167', pageId: 'standard_provability_predicate', userId: 'EricBruylant', edit: '0', type: 'deleteParent', createdAt: '2016-07-19 19:01:22', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17165', pageId: 'standard_provability_predicate', userId: 'EricBruylant', edit: '0', type: 'newParent', createdAt: '2016-07-19 19:01:21', auxPageId: 'modal_logic', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17163', pageId: 'standard_provability_predicate', userId: 'EricBruylant', edit: '0', type: 'newParent', createdAt: '2016-07-19 19:00:44', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3140', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '17161', pageId: 'standard_provability_predicate', userId: 'EricBruylant', edit: '4', type: 'newEdit', createdAt: '2016-07-19 19:00:15', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'adding links, a little rewording and rearranging' }, { likeableId: '3137', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '17159', pageId: 'standard_provability_predicate', userId: 'EricRogstad', edit: '3', type: 'newEdit', createdAt: '2016-07-19 17:18:09', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'small word and punctuation changes' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17158', pageId: 'standard_provability_predicate', userId: 'EricRogstad', edit: '2', type: 'newEdit', createdAt: '2016-07-19 17:09:47', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'capitalize first word of summary' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17157', pageId: 'standard_provability_predicate', userId: 'JaimeSevillaMolina', edit: '1', type: 'newEdit', createdAt: '2016-07-19 12:12:32', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }