수식 열거 문제

Question

허락하다 $P_0, P_1, P_2, ...$ 하나의 자유 변수가있는 모든 논리 공식의 열거 $n$(셀 수있는 알파벳의 유한 한 문자열이기 때문에 셀 수 있음). 허락하다$Q(n) \iff \lnot P_n(n)$. 어떠한 것도$n$, $Q$ 아니다 $P_n$ 그들은 동의하지 않기 때문에 $n$. 그러나$Q$논리 공식이므로 열거 형에 있어야 합니다 ...

무슨 일이야?

Answer 1

이것은 다음과 같이 귀결됩니다. "논리식"의 정확한 정의는 무엇입니까? 요점은$Q$ 당신은 분명히 "의미"라고 설명했습니다. 어떤 의미에서 어떤 의미에서 더 복잡합니다. $P_i$에스. 우리가 "논리 공식"의 정확한 개념과 그 열거를 찾아 내면, 예를 들어 관련된 기호들에 대한 몇 가지 합리적인 순서를 통해 사전 순으로 정렬 된 "산술 언어의 1 차 공식"에 해당하는$Q$ 특정 의미에서 공식으로 표현할 수없는 것으로 판명 될 것입니다.

이것이 어떻게 작동하는지에 대한 구체적인 예는 Tarski의 정의 불가능 성 정리를 참조하십시오 . 그리고 이것을 유사한 "표현의 역설"과 비교하십시오 : 베리의 역설, 리차드의 역설, 그리고 그 렐링의 역설.

Answer 2

유효한 수식을 나타내는 문자열과 수식 자체를 구별하는 것이 중요합니다.

다음을 참조하십시오.

• 리처드의 역설 (역설과 설명)
• Tarski의 정의 불가능 성 정리 (일관된 논리 시스템에서 공식 문자열의 진실을 인코딩 할 방법이 없음)
• Godel의 불완전 성 정리 (증빙 가능성은 인코딩 될 수 있지만 진실과는 다릅니다)