정수론에서 주로 쓰는 논리는 2차논리임?

[기괴공학도(mecheng98)]

"모든 자연수의 집합에는 그 집합에서 가장 작은 원소가 있다"는 걸 써먹으려면 2차 논리가 필요함?

1차 논리로는 안 됨?

[익명(112.149)]

1차논리로 충분히 가능함

[mCC(pumpkin7889)]

어떻게 가능함? 애초에 저 명제자체가 2차논리에서의 sentence 인데

[익명(112.149)]

1차 논리 체계인 ZFC는 페아노 공리계의 extension. 그리고 이 집합론에서는 저 명제 표현가능. 굳이 집합론이 아니어도 되는데 페아노 공리계에서도 저 명제 표현가능함. 페아노 공리계에서는 저 명제에서의 집합이라는 표현 대신에

[익명(112.149)]

모든 자연수 n에 대해서, "모든 x1, ..., xn에 대해서 p(x1) and ... and p(xn)이면 어떤 y가 존재해서 y는 x1, ..., xn중에 하나이며 x1,..., xn보다 작거나 같다"

[익명(112.149)]

"모든 자연수 n에 대해서"에서 n은 메타언어

[익명(112.149)]

내가 위에서 말한 방식대로 번역하면 됨

[mCC(pumpkin7889)]

For all x_1,...,x_n 이라는 표현은 n에 종속되지 않는데? 따라서 (Forall n, Forall x_1,...) 이 아니라 각각의 문장들 (Forall x_1, p(x_1)...),(Forall x_1,x_2, p(x_1),p(x_2),...),(Forall x_1,x_2,x_3, p(x_1)...),(Forall x_1,...,x_n...),... 을 전부 주장해야되고 이 sentence 들의 집합 (theory)이 (1차논리에서, 특히 classical logic상에서) 증명가능하다 뭐 그런소리를 하고싶은거임?

[mCC(pumpkin7889)]

내가 지적한부분은 내가 댓글단 뒤에 메타언어라고 명시해놨네. 뭐 그럼 ㅇㅋ

[기괴공학도(mecheng98)]

저 빡대가리라서 그런데 이렇게 하면 유한집합만 보인 거 아니에요?

[mCC(pumpkin7889)]

ㅇㅇ 유한집합만 보인거네 생각해보니까 네 명제는 well-ordering principle 인데 이거 1차논리에서 증명불가능

[mCC(pumpkin7889)]

증명불가능이라해야되나 1차논리상에서 표현불가능한 명제

[기괴공학도(mecheng98)]

네 저도 "증명 불가능"은 약간 이상한 것 같고 "표현불가능"이 맞는 표현 같다고 생각합니다

[mCC(pumpkin7889)]

이거보셈 :
https://math.stackexchange.com/questions/937348/why-isnt-there-a-first-order-theory-of-well-order

[기괴공학도(mecheng98)]

ㄴ 정말 감사드립니다.

[익명(112.149)]

물론 저 식을 schema가 아닌 식으로 번역하려면 2차논리가 필수겠지만, 꼭 유한집합이 아니어도 "어떤 y가 존재해서 모든 x에 대해( px이면py이고 y는 x보다 작거나 같다)"인 형태로 번역가능.

[기괴공학도(mecheng98)]

아! 알겠습니다. 정말 감사드립니다.

[익명(112.149)]

결론은 1차 논리에서의 페아노 공리계에서도 저 명제 사용가능함. 모든 식 px에 대해서 충분히 증명가능하니까. 물론 위처럼 저 명제의 번역된 식들만 사용가능

[익명(211.36)]

저 명제가 기괴가 말한 명제 말하는 거임? 아님 번역된 명제 말하는 거?

[기괴공학도(mecheng98)]

제가 말한 명제일 것 같아요. "저 명제의 번역된 식"은 제 명제를 공리꼴로 바꾼 명제를 말한 것 같아요.

[익명(112.149)]

내가 말한 '저 명제'는 질문자가 말한 명제. 번역된 스키마는 모든 식에 대해서 증명가능하니까 그냥 뭘 쓰든 결론적으로는 상관없다는 거. 정확하게는 번역된 거 써야되지만