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