{"id":9293,"date":"2025-10-17T20:26:04","date_gmt":"2025-10-17T11:26:04","guid":{"rendered":"https:\/\/sasamath.com\/blog\/?page_id=9293"},"modified":"2026-09-27T12:38:09","modified_gmt":"2026-09-27T03:38:09","slug":"ch19-incompleteness-theorem","status":"publish","type":"page","link":"https:\/\/sasamath.com\/blog\/invitation-to-mathematical-logic\/ch19-incompleteness-theorem\/","title":{"rendered":"\ubd88\uc644\uc804\uc131 \uc815\ub9ac"},"content":{"rendered":"
<\/p>\n

<\/p>\n

\uad34\ub378\uc758 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \u201c\ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654\ud560 \uc218 \uc788\uc73c\uba74\uc11c \uc790\uc5f0\uc218 \uc0b0\uc220\uc744 \ucda9\ubd84\ud788 \ud45c\ud604\ud558\ub294 \ubb34\ubaa8\uc21c \uc774\ub860\u201d\uc740 \uc644\uc804\ud560 \uc218 \uc5c6\ub2e4\ub294 \uc0ac\uc2e4\uc744 \ubcf4\uc5ec\uc900\ub2e4. \uc5ec\uae30\uc11c \ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654 \uac00\ub2a5<\/span>(effectively axiomatizable)\ud558\ub2e4\ub294 \uac83\uc740 \uacf5\ub9ac\ub4e4\uc744 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucc28\ub840\ub85c \ub098\uc5f4\ud560 \uc218 \uc788\ub2e4\ub294 \ub73b\uc73c\ub85c \uc774\ud574\ud55c\ub2e4.<\/p>\n

\uc774 \uc7a5\uc5d0\uc11c\ub294 \\(\\mathrm{PA}\\)\ub97c \uc911\uc2ec\uc73c\ub85c \ud575\uc2ec \uc544\uc774\ub514\uc5b4\ub97c \uc124\uba85\ud55c\ub2e4.<\/p>\n

1. \uad34\ub378 \uc218\ub9e4\uae40\uacfc \uc0b0\uc220\ud654<\/h3>\n

\uad34\ub378\uc758 \uc544\uc774\ub514\uc5b4\ub294 \ud615\uc2dd\uc5b8\uc5b4\uc758 \uc720\ud55c\ud55c \ubd80\ud638\uc5f4\uacfc \uc99d\uba85\uc744 \uc790\uc5f0\uc218\ub85c \ubd80\ud638\ud654\ud558\ub294 \uac83\uc774\ub2e4. \uc774\ub7ec\ud55c \ubd80\ud638\ud654\ub97c \uad34\ub378 \uc218\ub9e4\uae40<\/span>(G\u00f6del numbering)\uc774\ub77c\uace0 \ubd80\ub978\ub2e4. \uad6c\uccb4\uc801\uc778 \uc218\ub9e4\uae40 \ubc29\uc2dd\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\uc73c\uba70, \uc911\uc694\ud55c \uac83\uc740 \ubd80\ud638\uc5f4\uc758 \uc5f0\uacb0, \uce58\ud658, \u201c\uc62c\ubc14\ub978 \uc99d\uba85\uc778\uac00\u201d\uc640 \uac19\uc740 \uad6c\ubb38\uc801 \uc5f0\uc0b0\uacfc \uad00\uacc4\uac00 \uc790\uc5f0\uc218\uc5d0 \ub300\ud55c \ud6a8\uacfc\uc801\uc778 \uc0b0\uc220 \uc5f0\uc0b0\uacfc \uad00\uacc4\ub85c \ubc14\ub010\ub2e4\ub294 \uc810\uc774\ub2e4.<\/p>\n

\uac04\ub2e8\ud55c \uc608\ub85c \ub2e4\uc74c\uacfc \uac19\uc774 \uae30\ubcf8\uae30\ud638\uc5d0 12\uc9c4 \uc22b\uc790\ub97c \ubc30\uc815\ud558\uc790.<\/p>\n

\"\uad34\ub378<\/a><\/div>\n

<\/p>\n

12\uc9c4 \uc22b\uc790 \\(\\mathrm A\\), \\(\\mathrm B\\)\ub97c \uac01\uac01 \ubcc0\uc218 \ud45c\uc2dc\uc640 \ub17c\ub9ac\uc2dd \uc2dc\uc791 \ud45c\uc2dc\ub85c \uc0ac\uc6a9\ud558\uc790. \ubcc0\uc218 \\(x_n\\)\uc740 \\(\\mathrm A\\), \\(n\\)\uc758 12\uc9c4 \ud45c\uae30, \\(\\mathrm A\\)\ub97c \ucc28\ub840\ub85c \uc801\uc5b4 \ubd80\ud638\ud654\ud558\uace0, \uc644\uc804\ud55c \ub17c\ub9ac\uc2dd\uc758 \ucf54\ub4dc \ub9e8 \uc55e\uc5d0\ub294 \\(\\mathrm B\\)\ub97c \ubd99\uc778\ub2e4. \uc774 \uc2dc\uc791 \ud45c\uc2dc\ub294 \ucf54\ub4dc\uac00 \\(0\\)\uc73c\ub85c \uc2dc\uc791\ud560 \ub54c \uc0dd\uae38 \uc218 \uc788\ub294 \uc120\ub450 \\(0\\)\uc758 \ubaa8\ud638\ud568\uc744 \uc5c6\uc564\ub2e4. \uc608\ub97c \ub4e4\uc5b4
\n\\[
\n(\\forall x_0)(\\neg(s(x_0)=0))
\n\\]
\n\uc758 12\uc9c4 \ucf54\ub4dc\ub294
\n\\[
\n\\mathrm{B43A0A541474A0A56055}_{(12)}
\n\\]
\n\uc774\ub2e4. \uc774 12\uc9c4 \uc815\uc218\uac00 \ud574\ub2f9 \ub17c\ub9ac\uc2dd\uc758 \ud55c \uac00\uc9c0 \uad34\ub378 \uc218<\/span>(G\u00f6del number)\uac00 \ub41c\ub2e4. \ub17c\ub9ac\uc2dd \\(\\phi\\)\uc758 \uad34\ub378 \uc218\uc778 \uc790\uc5f0\uc218\ub97c \\(G(\\phi)\\)\ub85c \ub098\ud0c0\ub0b4\uace0, \uadf8 \uc790\uc5f0\uc218\ub97c \uc0b0\uc220 \uc5b8\uc5b4 \uc548\uc5d0\uc11c \ub098\ud0c0\ub0b4\ub294 \uc218\uc0ac \\(\\overline{G(\\phi)}\\)\ub97c \uac04\ub2e8\ud788 \\(\\ulcorner\\phi\\urcorner\\)\ub85c \uc4f0\uc790.<\/p>\n

\uc99d\uba85\uc740 \ub17c\ub9ac\uc2dd\ub4e4\uc758 \uc720\ud55c\uc5f4\uc774\ubbc0\ub85c \uc720\ud55c\uc5f4\uc5d0 \ub300\ud55c \ud45c\uc900\uc801\uc778 \uc790\uc5f0\uc218 \ubd80\ud638\ud654\ub97c \ud55c \ubc88 \ub354 \uc0ac\uc6a9\ud558\uc5ec \uc790\uc5f0\uc218 \ud558\ub098\ub85c \ubd80\ud638\ud654\ud560 \uc218 \uc788\ub2e4. \uc774\ud6c4 \uc815\ud655\ud55c \uc22b\uc790 \uc790\uccb4\ubcf4\ub2e4 \u201c\uadf8 \ubd80\ud638\uac00 \uc5b4\ub5a4 \uad6c\ubb38\uc801 \ub300\uc0c1\uc744 \ub098\ud0c0\ub0b4\ub294\uac00\u201d\uac00 \uc911\uc694\ud558\ub2e4.<\/p>\n

\uad34\ub378 \uc218\ub9e4\uae40\uc758 \ud575\uc2ec\uc740 \ub2e8\uc21c\ud55c \ubd80\ud638\ud654 \uc790\uccb4\uac00 \uc544\ub2c8\ub77c, \uad6c\ubb38\ub860\uc744 \uc0b0\uc220 \uc548\uc5d0\uc11c \ud45c\ud604\ud560 \uc218 \uc788\ub2e4\ub294 \uc0ac\uc2e4\uc774\ub2e4.<\/p>\n

\n

\uc815\ub9ac 19.1. (\uad6c\ubb38\ub860\uc758 \uc0b0\uc220\ud654)<\/span><\/p>\n

\uc801\uc808\ud55c \uad34\ub378 \uc218\ub9e4\uae40\uc744 \uace0\uc815\uc2dc\ud0a4\uba74 \u201c\\(p\\)\ub294 \\(\\mathrm{PA}\\)\uc758 \uacf5\ub9ac\uc758 \uad34\ub378 \uc218\uc774\ub2e4\u201d, \u201c\\(p\\)\ub294 \uad34\ub378 \uc218\uac00 \\(q\\)\uc778 \ubb38\uc7a5\uc758 \\(\\mathrm{PA}\\)-\uc99d\uba85\uc758 \uad34\ub378 \uc218\uc774\ub2e4\u201d, \u201c\\(q\\)\ub294 \ud55c \ubcc0\uc218 \ub17c\ub9ac\uc2dd\uc5d0 \uc218\uc0ac\ub97c \ub300\uc785\ud558\uc5ec \uc5bb\uc740 \ub17c\ub9ac\uc2dd\uc758 \uad34\ub378 \uc218\uc774\ub2e4\u201d\uc640 \uac19\uc740 \uae30\ubcf8\uc801\uc778 \uad6c\ubb38\uc801 \uad00\uacc4\ub294 \uc6d0\uc2dc\uc7ac\uadc0\uc801(primitive recursive) \uad00\uacc4\ub85c \ub9cc\ub4e4 \uc218 \uc788\uc73c\uba70, \ub530\ub77c\uc11c \\(\\mathrm{PA}\\)\uc758 \ub17c\ub9ac\uc2dd\uc73c\ub85c \ud45c\ud604\ud560 \uc218 \uc788\ub2e4.<\/p>\n

\ub354 \ub098\uc544\uac00 \uc774\ub7ec\ud55c \uc6d0\uc2dc\uc7ac\uadc0\uc801 \uad00\uacc4\ub97c \ud45c\ud604\ud558\ub294 \ub17c\ub9ac\uc2dd\uc740 \ud45c\uc900 \uc790\uc5f0\uc218\uc758 \uc218\uc0ac\uc5d0 \ub300\ud558\uc5ec \uc218\uc0ac\ubcc4\ub85c \uadf8 \ucc38\u00b7\uac70\uc9d3\uc744 \\(\\mathrm{PA}\\) \uc548\uc5d0\uc11c \uc815\ud655\ud788 \ud310\uc815\ud558\ub3c4\ub85d \ud0dd\ud560 \uc218 \uc788\ub2e4. \uc989 \ud45c\uc900 \uc790\uc5f0\uc218\ub4e4\uc744 \ub300\uc785\ud588\uc744 \ub54c \ud574\ub2f9 \uad00\uacc4\uac00 \uc2e4\uc81c\ub85c \uc131\ub9bd\ud558\uba74 \uadf8 \ub17c\ub9ac\uc2dd\uc744 \\(\\mathrm{PA}\\)\uc5d0\uc11c \uc99d\uba85\ud560 \uc218 \uc788\uace0, \uc131\ub9bd\ud558\uc9c0 \uc54a\uc73c\uba74 \uadf8 \ubd80\uc815\uc744 \\(\\mathrm{PA}\\)\uc5d0\uc11c \uc99d\uba85\ud560 \uc218 \uc788\ub2e4.<\/p>\n<\/div>\n

\ud2b9\ud788 \ub450 \ubcc0\uc218 \ub17c\ub9ac\uc2dd
\n\\[
\n\\operatorname{Prf}_{\\mathrm{PA}}(p,q)
\n\\]
\n\ub97c \ud0dd\ud558\uc5ec \ud45c\uc900 \uc790\uc5f0\uc218 \\(m,n\\)\uc5d0 \ub300\ud574
\n\\[
\n\\mathcal N\\models
\n\\operatorname{Prf}_{\\mathrm{PA}}(\\overline m,\\overline n)
\n\\]
\n\uc774 \uc131\ub9bd\ud560 \ud544\uc694\ucda9\ubd84\uc870\uac74\uc774 \\(m\\)\uc774 \uad34\ub378 \uc218 \\(n\\)\uc778 \ubb38\uc7a5\uc758 \uc2e4\uc81c \\(\\mathrm{PA}\\)-\uc99d\uba85 \ucf54\ub4dc\uc774\ub3c4\ub85d \ud560 \uc218 \uc788\ub2e4. \ub610\ud55c \uc815\ub9ac 19.1\uc758 \uc218\uc0ac\ubcc4 \ud310\uc815 \uc131\uc9c8\uc5d0 \uc758\ud574, \uc2e4\uc81c \uc99d\uba85 \ucf54\ub4dc\uc778 \uacbd\uc6b0\uc5d0\ub294
\n\\[
\n\\mathrm{PA}\\vdash
\n\\operatorname{Prf}_{\\mathrm{PA}}(\\overline m,\\overline n),
\n\\]
\n\uc2e4\uc81c \uc99d\uba85 \ucf54\ub4dc\uac00 \uc544\ub2cc \uacbd\uc6b0\uc5d0\ub294
\n\\[
\n\\mathrm{PA}\\vdash
\n\\neg\\operatorname{Prf}_{\\mathrm{PA}}(\\overline m,\\overline n)
\n\\]
\n\uac00 \uc131\ub9bd\ud558\ub3c4\ub85d \\(\\operatorname{Prf}_{\\mathrm{PA}}\\)\ub97c \ud0dd\ud560 \uc218 \uc788\ub2e4. \uc774\ub54c
\n\\[
\n\\operatorname{Prov}_{\\mathrm{PA}}(q)
\n:=(\\exists p)\\operatorname{Prf}_{\\mathrm{PA}}(p,q)
\n\\]
\n\ub97c \\(\\mathrm{PA}\\)\uc758 \uc99d\uba85\uac00\ub2a5\uc131 \uc220\uc5b4<\/span>(provability predicate)\ub77c\uace0 \ubd80\ub978\ub2e4.<\/p>\n

2. \uc81c1 \ubd88\uc644\uc804\uc131 \uc815\ub9ac<\/h3>\n

\ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub97c \uc99d\uba85\ud560 \ub54c \uc0ac\uc6a9\ud558\ub294 \uc790\uae30\ucc38\uc870\uc758 \ud575\uc2ec \ub3c4\uad6c\ub294 \ub2e4\uc74c \uc815\ub9ac\uc774\ub2e4.<\/p>\n

\n

\uc815\ub9ac 19.2. (\ub300\uac01\ud654 \ubcf4\uc870\uc815\ub9ac)<\/span><\/p>\n

\\(\\theta(x)\\)\uac00 \uc790\uc720\ubcc0\uc218\uac00 \\(x\\) \ud558\ub098\uc778 \\(\\mathcal L_{\\mathrm{PA}}\\)-\ub17c\ub9ac\uc2dd\uc774\uba74 \uc5b4\ub5a4 \ubb38\uc7a5 \\(\\sigma\\)\uac00 \uc874\uc7ac\ud558\uc5ec
\n\\[
\n\\mathrm{PA}\\vdash
\n\\sigma\\leftrightarrow
\n\\theta(\\ulcorner\\sigma\\urcorner)
\n\\]
\n\uac00 \uc131\ub9bd\ud55c\ub2e4.<\/p>\n<\/div>\n

\n

\uc99d\uba85 \uac1c\uc694<\/span>
\n\\(d(n)\\)\uc744 \u201c\uad34\ub378 \uc218\uac00 \\(n\\)\uc778 \ud55c \ubcc0\uc218 \ub17c\ub9ac\uc2dd\uc758 \uc790\uc720\ubcc0\uc218\uc5d0 \uc218\uc0ac \\(\\overline n\\)\uc744 \ub300\uc785\ud558\uc5ec \uc5bb\ub294 \ubb38\uc7a5\uc758 \uad34\ub378 \uc218\u201d\ub77c\uace0 \ud558\uc790. \uc815\ub9ac 19.1\uc5d0 \uc758\ud574 \uc774 \ub300\uac01\ud568\uc218 \\(d\\)\ub97c \uc0b0\uc220 \uc548\uc5d0\uc11c \ud45c\ud604\ud560 \uc218 \uc788\ub2e4.<\/p>\n

\\(d(x)=y\\)\ub97c \ud45c\ud604\ud558\ub294 \ub17c\ub9ac\uc2dd\uc744 \\(D(x,y)\\)\ub77c\uace0 \ud558\uace0
\n\\[
\n\\eta(x):=(\\exists y)(D(x,y)\\wedge\\theta(y))
\n\\]
\n\ub85c \ub454\ub2e4. \\(e=G(\\eta)\\)\uc774\uace0 \\(\\sigma=\\eta(\\overline e)\\)\ub77c\uace0 \ud558\uba74, \uc815\uc758\uc0c1
\n\\[
\nd(e)=G(\\sigma).
\n\\]
\n\ub530\ub77c\uc11c \\(D\\)\uac00 \\(d\\)\ub97c \uc62c\ubc14\ub974\uac8c \ud45c\ud604\ud55c\ub2e4\ub294 \uc0ac\uc2e4\uc744 \\(\\mathrm{PA}\\) \uc548\uc5d0\uc11c \uc0ac\uc6a9\ud558\uba74
\n\\[
\n\\mathrm{PA}\\vdash
\n\\sigma\\leftrightarrow
\n\\theta(\\ulcorner\\sigma\\urcorner)
\n\\]
\n\ub97c \uc5bb\ub294\ub2e4.<\/span><\/p>\n<\/div>\n

\ub300\uac01\ud654 \ubcf4\uc870\uc815\ub9ac\ub97c \uc0ac\uc6a9\ud558\uba74 \ub2e4\uc74c \uad34\ub378 \ubb38\uc7a5\uc744 \uc5bb\ub294\ub2e4.<\/p>\n

\n

\uc815\ub9ac 19.3. (\uad34\ub378 \ubb38\uc7a5)<\/span><\/p>\n

\ubb38\uc7a5 \\(G\\)\uac00 \uc874\uc7ac\ud558\uc5ec
\n\\[
\n\\mathrm{PA}\\vdash
\nG\\leftrightarrow
\n\\neg\\operatorname{Prov}_{\\mathrm{PA}}
\n(\\ulcorner G\\urcorner)
\n\\]
\n\uac00 \uc131\ub9bd\ud55c\ub2e4.<\/p>\n

    \n
  1. \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74 \\(\\mathrm{PA}\\nvdash G\\)\uc774\ub2e4.<\/li>\n
  2. \\(\\mathrm{PA}\\)\uac00 \\(\\omega\\)-\ubb34\ubaa8\uc21c\uc774\uba74 \\(\\mathrm{PA}\\nvdash\\neg G\\)\uc774\ub2e4.<\/li>\n<\/ol>\n<\/div>\n
    \n

    \uc99d\uba85<\/span>
    \n(1) \\(\\mathrm{PA}\\vdash G\\)\ub77c\uace0 \ud558\uc790. \uc2e4\uc81c \uc99d\uba85\uc758 \uad34\ub378 \uc218\ub97c \\(n\\)\uc774\ub77c \ud558\uba74 \uad6c\ubb38\ub860\uc758 \uc0b0\uc220\ud654\uc5d0 \uc758\ud574
    \n\\[
    \n\\mathrm{PA}\\vdash
    \n\\operatorname{Prf}_{\\mathrm{PA}}
    \n(\\overline n,\\ulcorner G\\urcorner),
    \n\\]
    \n\ub530\ub77c\uc11c
    \n\\[
    \n\\mathrm{PA}\\vdash
    \n\\operatorname{Prov}_{\\mathrm{PA}}
    \n(\\ulcorner G\\urcorner)
    \n\\]
    \n\uc774\ub2e4. \ud55c\ud3b8 \uad34\ub378 \ubb38\uc7a5\uc758 \uc815\uc758\uc5d0\uc11c \\(\\mathrm{PA}\\vdash G\\)\ub294 \uadf8 \ubd80\uc815\uc744 \ud568\uaed8 \uc8fc\ubbc0\ub85c \ubb34\ubaa8\uc21c\uc131\uc5d0 \ubaa8\uc21c\uc774\ub2e4.<\/p>\n

    (2) \\(\\mathrm{PA}\\vdash\\neg G\\)\ub77c\uace0 \ud558\uc790. \uad34\ub378 \ubb38\uc7a5\uc758 \ub3d9\uce58\uc5d0\uc11c
    \n\\[
    \n\\mathrm{PA}\\vdash
    \n(\\exists p)\\operatorname{Prf}_{\\mathrm{PA}}
    \n(p,\\ulcorner G\\urcorner)
    \n\\]
    \n\ub97c \uc5bb\ub294\ub2e4. \uadf8\ub7ec\ub098 (1)\uc5d0 \uc758\ud574 \uc2e4\uc81c \ud45c\uc900 \uc790\uc5f0\uc218 \\(n\\) \uac00\uc6b4\ub370 \\(G\\)\uc758 \uc99d\uba85 \ucf54\ub4dc\ub294 \ud558\ub098\ub3c4 \uc5c6\ub2e4. \\(\\operatorname{Prf}_{\\mathrm{PA}}\\)\ub294 \uc6d0\uc2dc\uc7ac\uadc0\uc801\uc774\ubbc0\ub85c \uac01 \ud45c\uc900 \\(n\\)\uc5d0 \ub300\ud574
    \n\\[
    \n\\mathrm{PA}\\vdash
    \n\\neg\\operatorname{Prf}_{\\mathrm{PA}}
    \n(\\overline n,\\ulcorner G\\urcorner)
    \n\\]
    \n\uc774\ub2e4. \uc774\ub294 \\(\\omega\\)-\ubb34\ubaa8\uc21c\uc131\uc5d0 \uc5b4\uae0b\ub09c\ub2e4.<\/span><\/p>\n<\/div>\n

    \ud2b9\ud788 \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74 \uc2e4\uc81c \uc790\uc5f0\uc218 \uac00\uc6b4\ub370 \\(G\\)\uc758 \uc99d\uba85 \ucf54\ub4dc\ub294 \uc5c6\uc73c\ubbc0\ub85c \ud45c\uc900\uad6c\uc870 \\(\\mathcal N\\)\uc5d0\uc11c \\(\\neg\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner G\\urcorner)\\)\uac00 \ucc38\uc774\ub2e4. \uad34\ub378 \ubb38\uc7a5\uc758 \ub3d9\uce58\ub3c4 \\(\\mathcal N\\)\uc5d0\uc11c \ucc38\uc774\ubbc0\ub85c \\(\\mathcal N\\models G\\)\uc774\ub2e4. \ub530\ub77c\uc11c \\(G\\)\ub294 \ud45c\uc900 \uc790\uc5f0\uc218\uc5d0\uc11c \ucc38\uc774\uba74\uc11c \\(\\mathrm{PA}\\)\uc5d0\uc11c\ub294 \uc99d\uba85\ud560 \uc218 \uc5c6\ub294 \ubb38\uc7a5\uc774\ub2e4.<\/p>\n

    \uc5ec\uae30\uc11c \uc774\ub860 \\(T\\)\uac00 \\(\\omega\\)-\ubb34\ubaa8\uc21c<\/span>(\\(\\omega\\)-consistent)\uc774\ub77c\ub294 \uac83\uc740 \uc5b4\ub5a4 \ub17c\ub9ac\uc2dd \\(\\phi(x)\\)\uc5d0 \ub300\ud574\uc11c\ub3c4
    \n\\[
    \nT\\vdash(\\exists x)\\phi(x)
    \n\\]
    \n\uc774\uba74\uc11c \ub3d9\uc2dc\uc5d0 \ubaa8\ub4e0 \ud45c\uc900 \uc790\uc5f0\uc218 \\(n\\)\uc5d0 \ub300\ud574
    \n\\[
    \nT\\vdash\\neg\\phi(\\overline n)
    \n\\]
    \n\uc778 \uc77c\uc774 \uc5c6\ub2e4\ub294 \ub73b\uc774\ub2e4. \ub2e8\uc21c\ud55c \ubb34\ubaa8\uc21c\uc131\ubcf4\ub2e4 \uac15\ud55c \uc870\uac74\uc774\ub2e4.<\/p>\n

    \uad34\ub378\uc758 \uc6d0\ub798 \ub17c\uc99d\uc740 \uc704\uc640 \uac19\uc774 \\(G\\)\uc758 \ubc18\uc99d \ubd88\uac00\ub2a5\uc131\uc5d0 \\(\\omega\\)-\ubb34\ubaa8\uc21c\uc131\uacfc \uac19\uc740 \ucd94\uac00 \uc870\uac74\uc744 \uc0ac\uc6a9\ud55c\ub2e4. \ub85c\uc11c\ub294 \ubb38\uc7a5\uc744 \uc870\uae08 \ubc14\uafb8\uc5b4 \uc774 \uc870\uac74\uc744 \uc81c\uac70\ud558\uc600\ub2e4.<\/p>\n

    \n

    \uc815\ub9ac 19.4. (\uad34\ub378-\ub85c\uc11c \uc81c1 \ubd88\uc644\uc804\uc131 \uc815\ub9ac)<\/span><\/p>\n

    \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74 \uc5b4\ub5a4 \uc0b0\uc220 \ubb38\uc7a5 \\(R\\)\uc774 \uc874\uc7ac\ud558\uc5ec
    \n\\[
    \n\\mathrm{PA}\\nvdash R,
    \n\\quad
    \n\\mathrm{PA}\\nvdash\\neg R
    \n\\]
    \n\uc774\ub2e4. \ub354 \uc77c\ubc18\uc801\uc73c\ub85c \\(\\mathrm{PA}\\)\ub97c \ud3ec\ud568\ud558\ub294 \ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654\ub41c \ubb34\ubaa8\uc21c \uc0b0\uc220 \uc774\ub860\ub3c4 \uc644\uc804\ud560 \uc218 \uc5c6\ub2e4.<\/p>\n<\/div>\n

    \n

    \uac1c\uc694<\/span>
    \n\uc5ec\uae30\uc11c\ub294 \ub85c\uc11c \ub17c\uc99d\uc758 \uac1c\uc694\ub97c \uc0b4\ud3b4\ubcf8\ub2e4.<\/p>\n

    \ub300\uac01\ud654 \ubcf4\uc870\uc815\ub9ac\ub97c \uc774\uc6a9\ud558\uc5ec \\(R\\)\uc774 \ub2e4\uc74c \ub0b4\uc6a9\uc744 \ud45c\ud604\ud558\ub3c4\ub85d \ub9cc\ub4e0\ub2e4.<\/p>\n

    \u201c\ub098\uc758 \uc784\uc758\uc758 \uc99d\uba85\ubcf4\ub2e4 \ubc88\ud638\uac00 \uc791\uac70\ub098 \uac19\uc740 \ub0b4 \ubc18\uc99d\uc774 \uc874\uc7ac\ud55c\ub2e4.\u201d<\/p>\n

    \uc880 \ub354 \uc815\ud655\ud788\ub294 \\(R\\)\uc774
    \n\\[
    \n(\\forall p)\\Bigl(
    \n\\operatorname{Prf}_{\\mathrm{PA}}(p,\\ulcorner R\\urcorner)
    \n\\to
    \n(\\exists q\\le p)
    \n\\operatorname{Prf}_{\\mathrm{PA}}(q,\\ulcorner\\neg R\\urcorner)
    \n\\Bigr)
    \n\\]
    \n\uc758 \uace0\uc815\uc810\uc774 \ub418\ub3c4\ub85d \ud55c\ub2e4. \uc5ec\uae30\uc11c \\(q\\le p\\)\ub294 \\((\\exists r)(q+r=p)\\)\ub85c \uc0b0\uc220 \uc548\uc5d0\uc11c \ud45c\ud604\ud560 \uc218 \uc788\ub2e4.<\/p>\n

    \ub9cc\uc57d \\(R\\)\uc758 \uc99d\uba85\uc774 \uc874\uc7ac\ud558\uba74 \uadf8 \uac00\uc6b4\ub370 \uac00\uc7a5 \uc791\uc740 \ucf54\ub4dc\ub97c \\(p\\)\ub77c\uace0 \ud560 \uc218 \uc788\ub2e4. \ubb34\ubaa8\uc21c\uc131 \ub54c\ubb38\uc5d0 \\(\\neg R\\)\uc758 \uc99d\uba85\uc740 \uc874\uc7ac\ud558\uc9c0 \uc54a\ub294\ub2e4. \uadf8\ub7ec\ub098 \\(R\\)\uc758 \ub0b4\uc6a9\uacfc \\(p\\)\uac00 \uc2e4\uc81c \uc99d\uba85 \ucf54\ub4dc\ub77c\ub294 \uc0ac\uc2e4\uc744 \\(\\mathrm{PA}\\) \uc548\uc5d0\uc11c \ud655\uc778\ud558\uba74 \ucf54\ub4dc\uac00 \\(p\\) \uc774\ud558\uc778 \\(\\neg R\\)\uc758 \uc99d\uba85\uc774 \uc788\uc5b4\uc57c \ud55c\ub2e4\ub294 \uacb0\ub860\uc744 \uc5bb\uc5b4 \ubaa8\uc21c\uc774\ub2e4. \ub530\ub77c\uc11c \\(R\\)\uc740 \uc99d\uba85\ub418\uc9c0 \uc54a\ub294\ub2e4.<\/p>\n

    \ubc18\ub300\ub85c \\(\\neg R\\)\uc758 \uac00\uc7a5 \uc791\uc740 \uc99d\uba85 \ucf54\ub4dc\ub97c \\(q\\)\ub77c\uace0 \uac00\uc815\ud558\uc790. \ubb34\ubaa8\uc21c\uc131 \ub54c\ubb38\uc5d0 \\(R\\)\uc758 \uc99d\uba85\uc740 \uc5c6\ub2e4. \\(p<q\\)\uc778 \uc720\ud55c \uac1c\uc758 \ucf54\ub4dc\uac00 \\(R\\)\uc758 \uc99d\uba85\uc774 \uc544\ub2c8\ub77c\ub294 \uc0ac\uc2e4\uacfc \\(q\\) \uc790\uccb4\uac00 \\(\\neg R\\)\uc758 \uc99d\uba85\uc774\ub77c\ub294 \uc0ac\uc2e4\uc740 \ubaa8\ub450 \\(\\mathrm{PA}\\) \uc548\uc5d0\uc11c \ud655\uc778\ud560 \uc218 \uc788\ub2e4. \ub530\ub77c\uc11c \ubaa8\ub4e0 \\(p\\)\uc5d0 \ub300\ud574 \ub85c\uc11c \uc870\uac74\uc774 \uc131\ub9bd\ud568\uc744 \uc99d\uba85\ud558\uc5ec \\(\\mathrm{PA}\\vdash R\\)\uc744 \uc5bb\uac8c \ub418\uace0, \ub2e4\uc2dc \ubb34\ubaa8\uc21c\uc131\uc5d0 \ubaa8\uc21c\uc774\ub2e4. \uadf8\ub7ec\ubbc0\ub85c \\(\\neg R\\)\ub3c4 \uc99d\uba85\ub418\uc9c0 \uc54a\ub294\ub2e4.<\/span><\/p>\n<\/div>\n

    \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \u201c\uc218\ud559 \uc804\uccb4\uac00 \ubd88\uc644\uc804\ud558\ub2e4\u201d\ub77c\ub294 \ub73b\uc774 \uc544\ub2c8\ub2e4. \ud575\uc2ec\uc740 \u201c\ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654\ub41c \ud558\ub098\uc758 \ubb34\ubaa8\uc21c \uccb4\uacc4\uac00 \uc790\uc5f0\uc218 \uc0b0\uc220\uc5d0 \uad00\ud55c \ubaa8\ub4e0 \ubb38\uc7a5\uc744 \uacb0\uc815\ud560 \uc218\ub294 \uc5c6\ub2e4\u201d\ub294 \uac83\uc774\ub2e4. \uc2e4\uc81c\ub85c \\(\\operatorname{Th}(\\mathcal N)\\)\uc740 \uc644\uc804\ud558\uc9c0\ub9cc, \uc81c1 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\uc5d0 \uc758\ud574 \ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654\ub420 \uc218 \uc5c6\ub2e4.<\/p>\n

    3. \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac<\/h3>\n

    \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \u201c\\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\ud558\ub2e4\u201d\ub77c\ub294 \uba54\ud0c0\uc218\ud559\uc801 \uba85\uc81c\ub97c \uc801\uc808\ud788 \uc0b0\uc220\ud654\ud588\uc744 \ub54c \uadf8 \ubb38\uc7a5\uc744 \\(\\mathrm{PA}\\) \uc790\uccb4\uac00 \uc99d\uba85\ud560 \uc218 \uc5c6\ub2e4\ub294 \uacb0\uacfc\uc774\ub2e4. \ud45c\uc900 \uc99d\uba85\uac00\ub2a5\uc131 \uc220\uc5b4\ub97c \uc774\uc6a9\ud558\uc5ec
    \n\\[
    \n\\operatorname{Con}(\\mathrm{PA})
    \n:=
    \n\\neg\\operatorname{Prov}_{\\mathrm{PA}}
    \n(\\ulcorner 0=1\\urcorner)
    \n\\]
    \n\ub85c \ub454\ub2e4.<\/p>\n

    \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\uc5d0\ub294 \uc99d\uba85\uac00\ub2a5\uc131 \uc220\uc5b4\uac00 \ub9cc\uc871\uc2dc\ud0a4\ub294 \uba87 \uac00\uc9c0 \uc0ac\uc2e4\uc774 \ud544\uc694\ud558\ub2e4. \uc5ec\uae30\uc11c\ub294 \ub2e4\uc74c \uc815\ub9ac\ub97c \uc99d\uba85 \uc5c6\uc774 \uc18c\uac1c\ud55c\ub2e4.<\/p>\n

    \n

    \uc815\ub9ac 19.5. (\ud790\ubca0\ub974\ud2b8-\ubca0\ub974\ub098\uc774\uc2a4 \ub3c4\ucd9c\uac00\ub2a5\uc131 \uc870\uac74)<\/span><\/p>\n

    \ubb38\uc7a5 \\(\\phi\\), \\(\\psi\\)\uc5d0 \ub300\ud574 \ud45c\uc900 \uc99d\uba85\uac00\ub2a5\uc131 \uc220\uc5b4\ub294 \ub2e4\uc74c\uc744 \ub9cc\uc871\uc2dc\ud0a8\ub2e4.<\/p>\n

      \n
    1. \\(\\mathrm{PA}\\vdash\\phi\\)\uc774\uba74
      \n\\[
      \n\\mathrm{PA}\\vdash
      \n\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\phi\\urcorner).
      \n\\]<\/li>\n
    2. \\(\\mathrm{PA}\\)\ub294
      \n\\[
      \n\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\phi\\to\\psi\\urcorner)
      \n\\to
      \n\\bigl(
      \n\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\phi\\urcorner)
      \n\\to
      \n\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\psi\\urcorner)
      \n\\bigr)
      \n\\]
      \n\uc758 \uc218\uc0ac\ud654\ub41c \ud615\ud0dc\ub97c \uc99d\uba85\ud55c\ub2e4.<\/li>\n
    3. \\(\\mathrm{PA}\\)\ub294
      \n\\[
      \n\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\phi\\urcorner)
      \n\\to
      \n\\operatorname{Prov}_{\\mathrm{PA}}
      \n(\\ulcorner\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\phi\\urcorner)\\urcorner)
      \n\\]
      \n\uc758 \uc218\uc0ac\ud654\ub41c \ud615\ud0dc\ub97c \uc99d\uba85\ud55c\ub2e4.<\/li>\n<\/ol>\n<\/div>\n
      \n

      \uc815\ub9ac 19.6. (\uad34\ub378\uc758 \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac)<\/span><\/p>\n

      \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74
      \n\\[
      \n\\mathrm{PA}\\nvdash\\operatorname{Con}(\\mathrm{PA}).
      \n\\]<\/p>\n<\/div>\n

      \n

      \uac1c\uc694<\/span>
      \n\uc815\ub9ac 19.3\uc758 \uad34\ub378 \ubb38\uc7a5 \\(G\\)\ub97c \uc0ac\uc6a9\ud55c\ub2e4. \ub3c4\ucd9c\uac00\ub2a5\uc131 \uc870\uac74\ub4e4\uc744 \\(\\mathrm{PA}\\) \uc548\uc5d0\uc11c \ud615\uc2dd\ud654\ud558\uba74
      \n\\[
      \n\\mathrm{PA}\\vdash
      \n\\operatorname{Con}(\\mathrm{PA})\\to G
      \n\\]
      \n\ub97c \uc5bb\ub294\ub2e4. \ud575\uc2ec\uc740 \ub2e4\uc74c\uacfc \uac19\ub2e4. \uad34\ub378 \ubb38\uc7a5\uc758 \uace0\uc815\uc810 \uc131\uc9c8\uc5d0\uc11c \\(\\neg G\\)\ub294 \\(\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner G\\urcorner)\\)\ub97c \ub73b\ud55c\ub2e4. \ud55c\ud3b8 \ub3c4\ucd9c\uac00\ub2a5\uc131 \uc870\uac74\uc740 \\(G\\)\uac00 \uc99d\uba85 \uac00\ub2a5\ud558\ub2e4\ub294 \uac00\uc815\uc73c\ub85c\ubd80\ud130 \u201c\\(G\\)\uac00 \uc99d\uba85 \uac00\ub2a5\ud558\ub2e4\u201d\uc640 \u201c\\(G\\)\uac00 \uc99d\uba85 \uac00\ub2a5\ud558\uc9c0 \uc54a\ub2e4\u201d\uc758 \uc99d\uba85\uac00\ub2a5\uc131\uc744 \ubaa8\ub450 \ub04c\uc5b4\ub0b4\uc5b4 \ubaa8\uc21c\uc758 \uc99d\uba85\uac00\ub2a5\uc131\uc744 \uc5bb\ub3c4\ub85d \ud55c\ub2e4. \ub530\ub77c\uc11c \\(\\neg G\\)\uc774\uba74 \\(\\mathrm{PA}\\)\uac00 \ubaa8\uc21c\uc774\ub77c\ub294 \uacb0\ub860\uc744 \\(\\mathrm{PA}\\) \ub0b4\ubd80\uc5d0\uc11c \uc99d\uba85\ud560 \uc218 \uc788\uace0, \uadf8 \ub300\uc6b0\uac00 \uc704 \uc2dd\uc774\ub2e4.<\/p>\n

      \ub9cc\uc57d \\(\\mathrm{PA}\\vdash\\operatorname{Con}(\\mathrm{PA})\\)\ub77c\uba74 MP\uc5d0 \uc758\ud574 \\(\\mathrm{PA}\\vdash G\\)\uc774\ub2e4. \uadf8\ub7ec\ub098 \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74 \uc815\ub9ac 19.3\uc5d0 \uc758\ud574 \\(G\\)\ub294 \uc99d\uba85 \ubd88\uac00\ub2a5\ud558\ub2e4. \ubaa8\uc21c\uc774\ubbc0\ub85c \\(\\mathrm{PA}\\)\ub294 \uc790\uc2e0\uc758 \ud45c\uc900\uc801\uc778 \ubb34\ubaa8\uc21c\uc131 \ubb38\uc7a5\uc744 \uc99d\uba85\ud560 \uc218 \uc5c6\ub2e4.<\/span><\/p>\n<\/div>\n

      \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \ub354 \uac15\ud55c \uc774\ub860\uc774 \ub354 \uc57d\ud55c \uc774\ub860\uc758 \ubb34\ubaa8\uc21c\uc131\uc744 \uc99d\uba85\ud558\ub294 \uac83\uae4c\uc9c0 \ubd88\uac00\ub2a5\ud558\ub2e4\ub294 \ub73b\uc740 \uc544\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4 ZF\uc5d0\uc11c\ub294 \uc790\uc5f0\uc218\uc758 \ud45c\uc900\uad6c\uc870\ub97c \uad6c\uc131\ud558\uace0 \\(\\mathrm{PA}\\)\uc758 \uacf5\ub9ac\uc640 \ucd94\ub860\uaddc\uce59\uc774 \uadf8 \uad6c\uc870\uc5d0\uc11c \uac74\uc804\ud568\uc744 \ud615\uc2dd\ud654\ud560 \uc218 \uc788\uc73c\ubbc0\ub85c \\(\\operatorname{Con}(\\mathrm{PA})\\)\ub97c \uc99d\uba85\ud560 \uc218 \uc788\ub2e4. \ub2e4\ub9cc ZF \uc790\uccb4\uac00 \uc801\uc808\ud55c \ud6a8\uacfc\uc801 \ud615\uc2dd \uccb4\uacc4\ub85c\uc11c \ubb34\ubaa8\uc21c\ud558\ub2e4\uba74, \uac19\uc740 \uc774\uc720\ub85c ZF\ub294 \uc790\uc2e0\uc758 \ud45c\uc900\uc801\uc778 \ubb34\ubaa8\uc21c\uc131 \ubb38\uc7a5\uc744 \uc99d\uba85\ud560 \uc218 \uc5c6\ub2e4.<\/p>\n

      \n

      \ubb38\uc81c 19.1.<\/span>
      \n\uc704\uc758 \uae30\ud638 \ubcc0\ud658\ud45c\uc758 \uc218\ub9e4\uae40\uc744 \uc0ac\uc6a9\ud558\uc790. \uc0b0\uc220\uc2dd \\(2+2=4\\)\ub97c \\(0\\), \\(s\\), \\(+\\), \\(=\\)\ub9cc\uc744 \uc0ac\uc6a9\ud558\uc5ec \ub098\ud0c0\ub0b4\ub418, \uc644\uc804 \uad04\ud638 \ud45c\uae30\ub294
      \n\\[
      \n((s(s(0))+s(s(0)))=s(s(s(s(0)))))
      \n\\]
      \n\ub85c \ud55c\ub2e4. \uc704\uc758 \uaddc\uce59\uc5d0 \ub530\ub978 \uc774 \ub17c\ub9ac\uc2dd\uc758 12\uc9c4 \ucf54\ub4dc\ub97c \uad6c\ud558\uc2dc\uc624.<\/p>\n<\/div>\n

      \n

      \ubb38\uc81c 19.2.<\/span>
      \n\ubb38\uc7a5 \\(\\phi\\)\uc640 \uc790\uc5f0\uc218 \\(n\\)\uc744 \uc0dd\uac01\ud558\uc790. \ub2e4\uc74c \uac01 \ud45c\ud604\uc774 \uba54\ud0c0\uc218\ud559\uc801\uc73c\ub85c \ubb34\uc5c7\uc744 \ub73b\ud558\ub294\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/p>\n

        \n
      1. \\(\\mathcal N\\models\\operatorname{Prf}_{\\mathrm{PA}}(\\overline n,\\ulcorner\\phi\\urcorner)\\)<\/li>\n
      2. \\(\\mathcal N\\models\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner\\phi\\urcorner)\\)<\/li>\n
      3. \\(\\operatorname{Con}(\\mathrm{PA})=\\neg\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner0=1\\urcorner)\\)<\/li>\n<\/ol>\n

        \ub610\ud55c (2)\ub294 \u201c\\(\\phi\\)\uac00 \ud45c\uc900\uad6c\uc870 \\(\\mathcal N\\)\uc5d0\uc11c \ucc38\uc774\ub2e4\u201d\ub77c\ub294 \ub9d0\uacfc \uc77c\ubc18\uc801\uc73c\ub85c \uac19\uc9c0 \uc54a\uc74c\uc744 \uc124\uba85\ud558\uc2dc\uc624.<\/p>\n<\/div>\n

        \n

        \ubb38\uc81c 19.3.<\/span>
        \n\ub300\uac01\ud654 \ubcf4\uc870\uc815\ub9ac\ub97c
        \n\\[
        \n\\theta(x)=\\neg\\operatorname{Prov}_{\\mathrm{PA}}(x)
        \n\\]
        \n\uc5d0 \uc801\uc6a9\ud558\uc2dc\uc624. \uc5bb\uc5b4\uc9c0\ub294 \ubb38\uc7a5 \\(G\\)\uac00 \uc5b4\ub5a4 \uc758\ubbf8\uc5d0\uc11c \u201c\ub098\ub294 \\(\\mathrm{PA}\\)\uc5d0\uc11c \uc99d\uba85\ub418\uc9c0 \uc54a\ub294\ub2e4\u201d\ub77c\uace0 \ub9d0\ud558\ub294\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/p>\n<\/div>\n

        \n

        \ubb38\uc81c 19.4.<\/span>
        \n\uad34\ub378 \ubb38\uc7a5 \\(G\\)\uac00
        \n\\[
        \n\\mathrm{PA}\\vdash
        \nG\\leftrightarrow
        \n\\neg\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner G\\urcorner)
        \n\\]
        \n\ub97c \ub9cc\uc871\uc2dc\ud0a8\ub2e4\uace0 \ud558\uc790.<\/p>\n

          \n
        1. \\(\\mathrm{PA}\\vdash G\\)\ub77c\uace0 \uac00\uc815\ud558\uba74 \uc65c \uc2e4\uc81c \\(G\\)\uc758 \uc99d\uba85 \ucf54\ub4dc \\(n\\)\uc774 \uc874\uc7ac\ud558\ub294\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n
        2. \uadf8 \ucf54\ub4dc\uc640 \uad6c\ubb38\ub860\uc758 \uc0b0\uc220\ud654\ub97c \uc0ac\uc6a9\ud558\uba74 \uc65c
          \n\\[
          \n\\mathrm{PA}\\vdash\\operatorname{Prov}_{\\mathrm{PA}}(\\ulcorner G\\urcorner)
          \n\\]
          \n\ub97c \uc5bb\ub294\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n
        3. \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74 \\(\\mathrm{PA}\\nvdash G\\)\uc784\uc744 \uacb0\ub860\ub0b4\ub9ac\uc2dc\uc624.<\/li>\n
        4. \uac19\uc740 \ubb34\ubaa8\uc21c\uc131 \uac00\uc815 \uc544\ub798 \ud45c\uc900\uad6c\uc870\uc5d0\uc11c\ub294 \uc65c \\(\\mathcal N\\models G\\)\uc778\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n
          \n

          \ubb38\uc81c 19.5.<\/span>
          \n\uc774\ub860 \\(T\\)\uc640 \ud55c \ubcc0\uc218 \ub17c\ub9ac\uc2dd \\(\\phi(x)\\)\uc5d0 \ub300\ud558\uc5ec \ub2e4\uc74c \uc0c1\ud669\uc744 \uc0dd\uac01\ud558\uc790.<\/p>\n

            \n
          1. \\(T\\vdash(\\exists x)\\phi(x)\\)\uc774\uace0 \ubaa8\ub4e0 \ud45c\uc900 \uc790\uc5f0\uc218 \\(n\\)\uc5d0 \ub300\ud558\uc5ec \\(T\\vdash\\neg\\phi(\\overline n)\\)\uc774\ub2e4.<\/li>\n
          2. \\(T\\vdash(\\exists x)\\phi(x)\\)\uc774\uace0 \\(n=0,1,\\ldots,100\\)\uc5d0 \ub300\ud574\uc11c\ub9cc \\(T\\vdash\\neg\\phi(\\overline n)\\)\uc774\ub2e4.<\/li>\n
          3. \uc5b4\ub5a4 \ud45c\uc900 \uc790\uc5f0\uc218 \\(m\\)\uc5d0 \ub300\ud558\uc5ec \\(T\\vdash\\phi(\\overline m)\\)\uc774\ub2e4.<\/li>\n<\/ol>\n

            \uc5b4\ub290 \uacbd\uc6b0\uac00 \\(\\omega\\)-\ubb34\ubaa8\uc21c\uc131\uc758 \uc815\uc758\uc5d0 \uc9c1\uc811 \uc5b4\uae0b\ub098\ub294\uc9c0 \ub2f5\ud558\uc2dc\uc624. \ub610\ud55c \\(\\omega\\)-\ubb34\ubaa8\uc21c\uc778 \uc774\ub860\uc740 \ubb34\ubaa8\uc21c\uc784\uc744 \uc124\uba85\ud558\uc2dc\uc624.<\/p>\n<\/div>\n

            \n

            \ubb38\uc81c 19.6.<\/span>
            \n\uad34\ub378\uc758 \uc6d0\ub798 \uc81c1 \ubd88\uc644\uc804\uc131 \ub17c\uc99d\uacfc \ub85c\uc11c\uc758 \uac1c\uc120\uc744 \ube44\uad50\ud558\uc5ec \ub2e4\uc74c \ubb3c\uc74c\uc5d0 \ub2f5\ud558\uc2dc\uc624.<\/p>\n

              \n
            1. \uad34\ub378 \ubb38\uc7a5 \\(G\\)\uc758 \ubc18\uc99d \ubd88\uac00\ub2a5\uc131\uc744 \uc704 \ubcf8\ubb38 \ubc29\uc2dd\uc73c\ub85c \uc5bb\uc744 \ub54c \ud544\uc694\ud55c \ucd94\uac00 \uac00\uc815\uc740 \ubb34\uc5c7\uc778\uac00?<\/li>\n
            2. \ub85c\uc11c \ubb38\uc7a5 \\(R\\)\uc5d0\uc11c\ub294 \uc5b4\ub5a4 \uac00\uc815\ub9cc\uc73c\ub85c \\(R\\)\uacfc \\(\\neg R\\)\uc758 \uc99d\uba85 \ubd88\uac00\ub2a5\uc131\uc744 \ubaa8\ub450 \uc5bb\ub294\uac00?<\/li>\n
            3. \\(R\\) \ub610\ub294 \\(\\neg R\\)\uc758 \uc99d\uba85\uc774 \uc2e4\uc81c\ub85c \uc874\uc7ac\ud55c\ub2e4\uace0 \uac00\uc815\ud588\uc744 \ub54c \u201c\uac00\uc7a5 \uc791\uc740 \uc99d\uba85 \ucf54\ub4dc\u201d\ub97c \ud0dd\ud560 \uc218 \uc788\ub294 \uc774\uc720\ub294 \ubb34\uc5c7\uc778\uac00?<\/li>\n
            4. \ub85c\uc11c\uc758 \uac1c\uc120\uc774 \uc81c1 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub97c \u201c\uc644\uc804\ud55c \uc774\ub860\uc744 \uc5bb\ub294 \ubc29\ubc95\u201d\uc73c\ub85c \ubc14\uafb8\ub294 \uac83\uc740 \uc544\ub2cc \uc774\uc720\ub97c \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n
              \n

              \ubb38\uc81c 19.7.<\/span>
              \n\ub2e4\uc74c \uba85\uc81c\uc758 \ucc38\u00b7\uac70\uc9d3\uc744 \ubcf8\ubb38\uc758 \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\uc640 \uadf8 \uc124\uba85\uc5d0 \uadfc\uac70\ud558\uc5ec \ud310\ub2e8\ud558\uace0, \uac04\ub2e8\ud788 \uc774\uc720\ub97c \uc4f0\uc2dc\uc624.<\/p>\n

                \n
              1. \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\uba74 \\(\\mathrm{PA}\\nvdash\\operatorname{Con}(\\mathrm{PA})\\)\uc774\ub2e4.<\/li>\n
              2. \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \uc5b4\ub5a4 \uc774\ub860\ub3c4 \ub2e4\ub978 \uc774\ub860\uc758 \ubb34\ubaa8\uc21c\uc131\uc744 \uc99d\uba85\ud560 \uc218 \uc5c6\ub2e4\uace0 \ub9d0\ud55c\ub2e4.<\/li>\n
              3. \uc608\ub97c \ub4e4\uc5b4 ZF\ub294 \\(\\operatorname{Con}(\\mathrm{PA})\\)\ub97c \uc99d\uba85\ud560 \uc218 \uc788\ub2e4.<\/li>\n
              4. \uc81c2 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \\(\\mathrm{PA}\\)\uac00 \uc2e4\uc81c\ub85c \ubaa8\uc21c\uc778\uc9c0 \ubb34\ubaa8\uc21c\uc778\uc9c0\ub97c \uacb0\uc815\ud574 \uc8fc\ub294 \uc815\ub9ac\uc774\ub2e4.<\/li>\n
              5. \\(\\mathrm{PA}\\)\uac00 \ubb34\ubaa8\uc21c\uc774\ub77c\ub294 \uac00\uc815\uc774 \ube60\uc9c0\uba74 \uc815\ub9ac 19.6\uc758 \uacb0\ub860\uc744 \uadf8\ub300\ub85c \uc8fc\uc7a5\ud560 \uc218 \uc5c6\ub2e4.<\/li>\n<\/ol>\n<\/div>\n
                \n

                \uc9d1\ud569\uacfc \uc218\ub9ac\ub17c\ub9ac \uccab\uac78\uc74c \ubaa9\ucc28 \ubcf4\uae30<\/a><\/p>\n

                \uba85\uc81c\uc640 \ub17c\ub9ac<\/a><\/span>
                \n                \uc9d1\ud569\uc758 \uac1c\ub150<\/a><\/span>
                \n                \ub2e4\uc591\ud55c \uc9d1\ud569\uc758 \uc5f0\uc0b0<\/a><\/span>
                \n                \uad00\uacc4\uc640 \ud568\uc218<\/a><\/span>
                \n                \uc720\ud55c\uc9d1\ud569\uacfc \ubb34\ud55c\uc9d1\ud569<\/a><\/span>
                \n                \uc790\uc5f0\uc218<\/a><\/span>
                \n                \uc9d1\ud569\uc758 \uae30\uc218<\/a><\/span>
                \n                \uc9d1\ud569\uc758 \uc11c\uc218<\/a><\/span>
                \n                \uc9d1\ud569\ub860\uc758 \uacf5\ub9ac<\/a><\/span>
                \n                \uc120\ud0dd \uacf5\ub9ac<\/a><\/span>
                \n                \ud615\uc2dd\ub17c\ub9ac<\/a><\/span>
                \n                \uba85\uc81c\ub17c\ub9ac\uc758 \uac1c\ub150<\/a><\/span>
                \n                \uba85\uc81c\ub17c\ub9ac\uc758 \uac74\uc804\uc131\uacfc \uc644\uc804\uc131<\/a><\/span>
                \n                \uc77c\uacc4\ub17c\ub9ac\uc758 \uad6c\ubb38\ub860<\/a><\/span>
                \n                \uc77c\uacc4\ub17c\ub9ac\uc758 \uc758\ubbf8\ub860<\/a><\/span>
                \n                \uc77c\uacc4\ub17c\ub9ac\uc758 \ucd94\ub860\uaddc\uce59<\/a><\/span>
                \n                \uc77c\uacc4\ub17c\ub9ac\uc758 \ucf64\ud329\ud2b8\uc131<\/a><\/span>
                \n                \ud398\uc544\ub178 \uc0b0\uc220<\/a><\/span>
                \n                \ubd88\uc644\uc804\uc131 \uc815\ub9ac<\/a><\/span>\n<\/div>\n<\/div>\n

                <\/p>\n","protected":false},"excerpt":{"rendered":"

                \uad34\ub378\uc758 \ubd88\uc644\uc804\uc131 \uc815\ub9ac\ub294 \u201c\ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654\ud560 \uc218 \uc788\uc73c\uba74\uc11c \uc790\uc5f0\uc218 \uc0b0\uc220\uc744 \ucda9\ubd84\ud788 \ud45c\ud604\ud558\ub294 \ubb34\ubaa8\uc21c \uc774\ub860\u201d\uc740 \uc644\uc804\ud560 \uc218 \uc5c6\ub2e4\ub294 \uc0ac\uc2e4\uc744 \ubcf4\uc5ec\uc900\ub2e4. \uc5ec\uae30\uc11c \ud6a8\uacfc\uc801\uc73c\ub85c \uacf5\ub9ac\ud654 \uac00\ub2a5(effectively axiomatizable)\ud558\ub2e4\ub294 \uac83\uc740 \uacf5\ub9ac\ub4e4\uc744 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucc28\ub840\ub85c \ub098\uc5f4\ud560 \uc218 \uc788\ub2e4\ub294 \ub73b\uc73c\ub85c \uc774\ud574\ud55c\ub2e4. \uc774 \uc7a5\uc5d0\uc11c\ub294 \\(\\mathrm{PA}\\)\ub97c \uc911\uc2ec\uc73c\ub85c \ud575\uc2ec \uc544\uc774\ub514\uc5b4\ub97c \uc124\uba85\ud55c\ub2e4. 1. \uad34\ub378 \uc218\ub9e4\uae40\uacfc \uc0b0\uc220\ud654 \uad34\ub378\uc758 \uc544\uc774\ub514\uc5b4\ub294 \ud615\uc2dd\uc5b8\uc5b4\uc758 \uc720\ud55c\ud55c \ubd80\ud638\uc5f4\uacfc \uc99d\uba85\uc744 \uc790\uc5f0\uc218\ub85c \ubd80\ud638\ud654\ud558\ub294 \uac83\uc774\ub2e4. \uc774\ub7ec\ud55c \ubd80\ud638\ud654\ub97c \uad34\ub378 \uc218\ub9e4\uae40(G\u00f6del numbering)\uc774\ub77c\uace0 \ubd80\ub978\ub2e4. \uad6c\uccb4\uc801\uc778 \uc218\ub9e4\uae40 \ubc29\uc2dd\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00…<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":9246,"menu_order":119,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_lmt_disableupdate":"no","_lmt_disable":"","footnotes":""},"class_list":["post-9293","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/comments?post=9293"}],"version-history":[{"count":11,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9293\/revisions"}],"predecessor-version":[{"id":10099,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9293\/revisions\/10099"}],"up":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9246"}],"wp:attachment":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/media?parent=9293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}