5.7.6번 문제 답을 모르겠습니다.
책은 Ian Chiswell, Wilfrid Hodges의 Mathematical Logic 입니다.
문제 내용을 말씀드리자면, 어떤 임의의 qf(quntifier-free) formula phi가 있을 때, 이 formula phi를 satisfy하는 tuple들의 set이 항상 1) finite 하거나, 2) N - finite set 둘 중 하나가 된다고 함을 증명하라고 합니다.
도와줘요!
- dc official App
문제 설명에서 빼먹은 것이 있네요! 0, +, ×가 있는 arithmetic signature를 갖는 LR(Language of Relation)의 qf formula phi 입니다. - dc App
앗 sigma에서 function S (increment) 도 빼먹었습니다 - dc App
앗 또 빼먹은 것이.. structure N의 tuple입니다. - dc App
일단 "이 formula phi를 satisfy하는 tuple들의 set" 라는 설명을 보니 문제를 약간 오해하고 있는 것 같아서 말하겠음. (아님말고) 문제에서 주어진 phi(x)의 free variable 은 x뿐임. 아마 책 어딘가에 "phi(x) 같은 표기는 이 formula 의 free variable 은 x뿐이라는걸 가정한다" 라는 부분이 있을거임
앗 제가 잘못이해했습니다. 길이가 1 초과인 tuple이 아니라 element 입니다. - dc App
즉, phi(x)를 satisfy하는 set of elements in N을 찾는 문제인 것 같습니당!☆☆ - dc App
아 그걸 찾는 건 아니구.. 그 set이 1) 또는 2) 케이스 중 반드시 하나임을 증명하는 것 가타요잉 - dc App
예를들어 x=y 같은 formula 는 free variable 이 2개인 qf formula 인데 이 formula에 대해, 문제에서 증명할 것을 요구한 명제는 참이 아니게됨
아무튼 증명은 어케하냐면 힌트에서 말한대로 induction on (and, or, not 등의 논리기호) 로 하면 됨
그런데 base case 증명부터 못하겠어요 흐잉.. - dc App
if phi(x) is an atomic formula such that phi(x) is (s=t)(x) where s and t are terms, then ...(모르겠는 clause..) - dc App
일단 base case를 증명해야겠지. base case 가 되는 formula 는 f(x) = g(x) 의 형태임. 여기서 f와 g는 모두 x에 대한 다항식임.
그러면 term에 대해서도 induction on complexity 해서 뭔가 증명해야하눈건가효? 흐잉.. - dc App
"free variable이 x밖에 없는 term은 x에 대한 다항식이다" 이거 자명하다고 생각하긴 했는데 별로 자명하지 않으면 여기서도 스스로 induction 을 써서 증명해볼 수는 있을것같긴함
"free variable이 x밖에 없는 term은 x에 대한 다항식이다" 부분을 좀 모호하게 느낄수도 있을 것 같은데 그냥 덧셈, 곱셈, 상수로만 이루어져있으니 다항식이라고 생각하면 될듯한데
signature 에서 0은 상수고 S는 더하기 1이니까
n차 방정식의 해는 (복소수 해니까 자연수 해를 포함함) 많아야 n개라는 것을 알고있을거임. 따라서 f(x) = g(x) 라는 방정식의 해는 유한함. 혹은 f(x) = g(x) 에서 양변에 더하기 빼기 등등을 잘 해서 x를 모두 정리해버릴경우 0=0의 형타가 되게되는데 이 경우 해집합은 N전체가됨
킹수학의 갓본정리쨩을 써야하눈고에요? - dc App
응 써야함 이거 안쓰는 방법이 있긴하려남
극한 써도 될 것 같은데 아닌가요? - PushItToTheLimit!
1도모루게따.. - dc App
극한 써도 될것같다는말듣고 다시생각해보니 대수학의 기본정리 안쓰고하려면 이렇게하면될듯. monic polynomial (최고차항의 계수가 1인 다항식) f(x) 에 대해여 f(x) = 0의 자연수해가 유한하다는 것을 보이면 충분한데, 적당한 M이 존재하여 x>M 일 경우 f(x) > 0 이 되게 됨. 그러면 f(x) = 0 의 자연수해는 M이하여야하므로 유한개일수밖에없음.
저 M이 존재하는이유는... 엄밀히증명하려면 까다롭겠지만 대충느낌은 컴공이면 big-O notation 을 알텐데 예를들어 O(n^3) = O(n^3 - 1000 n^2) 이잖음? 다항식의 asymptotic growth 는 최고차항이 결정함. 나머지 항에 뭐가 있건 최고차항이 다 dominate 해버림. 그래서 x가 점점 커질때 (결국에는) f(x)도 점점 커질텐데 그러면 f(x) > 0 이게되는거지
그림으로그리면 간단한 직관인데 f(x)를 그래프로그리면 오른쪽으로 갈 때마다 (x-> infty 일때) f(x) -> infty 가됨
x -> infty 일때 f(x) -> infty 라는걸 쓸데없이 길게설명했나
Let f,g be polynomials. Then equation f(x)-g(x)=0 has finitely-many solutions, or N-finite set sol 임을 증명하면 된다는 거죠? f-g가 어떤 점 M부터 increasing or decreasing or constant function임을 증명하면 된다는 거죠? - dc App
ㅇㅇ 대충그러함 (정확히 잘 전해졌는지는 모르겠다)
어떻게 하지 아예 깜깜하고 난감했었는데;; f(x)=g(x) 가 막 무작위의 formula 라는 느낌때문에 어렵게 느껴졌는데 막상 semantic은 방정식이어서.. 깰꼼! - dc App
phi(x), psi(x) 를 formula 라고 하고, 각각의 해집합을 A, B 라고 하자. 그러면 phi(x) and psi(x) 의 해집합은 A n B 가 됨 (교집합기호로 n을 썼음)
마찬가지로 or는 합집합이되고 not 은 여집합이됨
끼요오옷 induction step 아이디어는 얻은 것 가타요. - dc App
걍 그렇게 아이디어 얻어서 풀도록 힌트만줄걸그랬나... 근데 어차피 지금 내 풀이가 알기쉽게 친절하게 잘쓴것도 아니라서 내 댓글 전체를 그냥 힌트라고 할수도있을듯.
이제 (1) => (2) 를 증명하면 충분함. (1) A는 유한하거나 그 여집합이 유한하다. B는 유한하거나 그 여집합이 유한하다. (2) A n B는 유한하거나 그 여집합이 유한하다. A u B는 유한하거나 그 여집합이 유한하다. A의 여집합은 유한하거나 그 여집합이 유한하다.
수잘갤에서왔는데 이런갤도있었네 몰랐음
대충 글살펴보니까 수학보다는 철학에 가까운느낌의 갤인데... 수학과 학부과정에서는 논리를 잘 다루지않고 철학과에서는 그래도 한과목정도는 다뤄서그런가? 컴공도 논리랑 관련있다고 할수있는데 딱히 컴공관련된것도 안보이는듯
근데 님 논리학 공부 왜함? 딱히 학교숙제푸는것같지도않은데
그냥 취미에여 >< - dc App