글쓴이: dpfinger (DoYouLikeToSmell?)
날 짜: Mon Nov 4 11:03:37 1996
제 목: 오늘 marriage problem
음..
재미있군요..
지난번에 set theory 시험을 칠때, 그 책의 문제를 다 풀어 보는데, 저 문제가
나오더군요...
물론, 그 책에서는, set theoretic하게 풀었지만..
근데, 그 문제에서, Y가 infinite일때는 안 될거라고 하는데, 저는 그것이
이해가 안되더군요...
다음의 증명을 보시길....
우선, X는 항상 finite입니다...
이때, X의 사람을 x1,x2,...xn이라고 하고, 각각의 사람이 Y에서 아는 사람들의
집합을 Y1,Y2,...,Yn이라고 하죠....
물론, 이 집합은, 이 문제의 조건, 즉, x1,x2,..,xn의 어떤 subset을 잡아도,
이 subset의 cardinality보다는, 그 subset에 해당하는 Yi들의 union의 cardinality
가 더 크다...를 만족해야 겠지요..
여기서, Yi들에, partial ordering을 줍니다..
Yi의 cardinality에 대해서 주죠...그러면, Yi들의 갯수는 finite(n)이니까,
여기에 대해서, xi도 같이 permute시켜 줍니다..
그러면, 이 rearrage한 것을, xi를 a1,a2,...,an으로 바꾸고, Yi들을,
B1,B2,...,Bn으로, index를 바꿉시다..
그러면, a1에 대한 matching으로, B1에서, arbitrary로 하나 선택합니다..
그런후, 그 선택한 것을, B2,B3,...,Bn에서 모두 뺍니다..
그담엔, a2에 해당하는것을 B2에서, a1의 matching인 것을 뺀 것에서, 임의로
또 선택합니다....이런식으로 하는 것이 항상 가능하지요...
그런데, 여기서, Y가 infinte이라는 조건은 쓰지 않았습니다...
근데, set theory책 에서는, infinite이면, 다른 axiom이 필요해서 그런건지
아니면, 다른 이유가 있는것인지, 그때까지 배운 axiom들만으로는(이때는
axiom of choice를 안 배웠는데, 그것 때문인지..) 증명이 안됨을
보이라는 겁니다...
constructive하게 되는 것 같은데, 왜 안된다고 하는 것인지 이해를 못하겠
군요...
혹시 답을 아시는분은....포스팅을..
==============================================================================
I've got nothing to say right now. -from the most deepest finger
....department of mathematics, undergraduate 95.
