수학 문제 훈련 3
04 Jul 20265.
유한집합족 $(A_i)_{i \in [n]}$, $A := \bigcup_{i \in [n]} A_i$에 대하여,
$f: [n] \hookrightarrow A$ such that $f(i) \in A_i$가 존재할 필요충분조건은
$I \subseteq [n]$에 대해 $\vert\bigcup_{i\in I} A_i\vert \ge \vert I \vert$
이걸 다시 풀자.
존재한다고 치면, $I \subseteq [n]$에 대하여 $f \vert_I: I \hookrightarrow \bigcup_{i \in I} A_i$ 이므로 참.
약간만 풀어써보면 ${}^{\forall} i \in I, f(i) \in A_i \subseteq \bigcup_{i \in I} A_i$이라 $f(I) \subseteq \bigcup_{i \in I} A_i$이고
$f: [n] \hookrightarrow A$ 이므로 $f \vert_I: I \hookrightarrow \bigcup_{i \in I} A_i$이며 따라서 $\vert\bigcup_{i\in I} A_i\vert \ge \vert I \vert$이다.
역방향은 다음과 같이 보인다.
우선 기본적인 발상은, 어떤 A의 원소를 뽑고, index에서 배정을 잘하는걸 반복하면 된다고 생각했다.
어찌보면 귀납법이다. 일단 n=1일땐 그냥 자명하고, A에서 원소를 잘 뽑고 index를 잘 뺐을때,
모든 A에선 해당 원소를 빼고, [n]에서는 해당 index만 뺄때 조건을 만족시키면 되니까.
사족을 붙이면,
- 절대로 뽑으면 안되는 원소같은게 있다면 집합에 없는 원소나 다름없는데, 손해일거라 생각했다
- 빼도 I에 따라 해당 원소가 아예 없으면 부등호는 보존되겠지만,
작은 케이스로 패턴을 볼때 일괄적으로 처리해도 될것같았다.
우선, fix $e \in A$, $B_i := A_i \setminus \lbrace e \rbrace$
편의를 위해 $U(I) := \bigcup_{i\in I} B_i = \bigcup_{i\in I} A_i \setminus \lbrace e \rbrace $ 라 한다면
조건에 따라 $h(I) := \vert U(I) \vert \ge \vert I \vert - 1$이다.
$Z = \lbrace I \subseteq [n] : h(I) = \vert I \vert - 1 \rbrace$ 라 하면,
우리가 기대하는건 적당한 $k$가 있어 $I \subseteq [n] \setminus \lbrace k \rbrace$에 대하여 $h(I) \ge \vert I \vert$인 것이다. 동치로, $I \notin Z$
다시 써보면, for $\exists k \in [n]$, $k \notin I \Rightarrow I \notin Z$이고, 대우는 $I \in Z \Rightarrow k \in I$.
동치로, $\bigcap Z \neq \varnothing$ (이때, $\bigcap \varnothing = [n]$)
즉, 우리는 $Z$에 대해 이해해야한다.
Lemma.
$h(I \cup J) + h(I \cap J) \le h(I) + h(J)$
증명은 간단하다- $U(I \cup J) = U(I) \cup U(J)$, $U(I \cap J) \subseteq U(I) \cap U(J)$ 이다.
즉, $h(I \cup J) + h(I \cap J) \le \vert U(I) \cup U(J) \vert + \vert U(I) \cap U(J) \vert = h(I) + h(J)$
그리고 여기서 따라오는건, $I, J \in Z$에 대해
\[h(I \cup J) + h(I \cap J) \le h(I) + h(J) = \vert I \vert + \vert J \vert - 2 = (\vert I \cup J \vert - 1) + (\vert I \cap J \vert - 1)\]때문에 놀랍게도 $I \cap J, I \cup J \in Z$ 이다.
즉, $Z$는 binary 교집합, 합집합 연산에 대해 닫혀있다.
Z가 유한집합이기 때문에 원소 전체의 교집합을 binary 교집합 연산들로 나타낼수 있고,
즉 $\bigcap Z \in Z$이다.
그런데 $h(\varnothing) = \vert \varnothing \vert = 0 > -1$이므로, $\varnothing \notin Z$
따라서, $\bigcap Z \neq \varnothing$이다.
알고리즘을 논해보면, 적당히 $e \in A$, $k \in \bigcap Z$를 뽑고,
$A_i, [n]$을 $B_i, [n] \setminus \lbrace k \rbrace$로 대체하면 된다- 귀납법으로 생각해도 좋겠다.
아, 하나 남았다. We should show there is some $k \in \bigcap Z$ such that $e \in A_k$
일단 $Z = \varnothing$이면 $e \in A$라서 자명함
$Z \neq \varnothing$라면 $\bigcap Z \in Z$이며,
$I \in Z$에 대해서 $h(I) = \vert \bigcup_{i\in I} A_i \setminus \lbrace e \rbrace \vert = \vert I \vert - 1$이지만 $\vert\bigcup_{i\in I} A_i\vert \ge \vert I \vert$
따라서 there is some $k in I$ such that $e \in A_K$.
이에 따라, 언제나 그러한 k가 존재한다.
이제 이거 보고 다른 증명 보니까 생각보다 너무 깔끔히 증명해서 좀 벽느껴지네
그냥 부등호가 죄다 > 일때는, 그냥 매칭 하나 빼도 >= 이니까 만족하고
부등호가 = 인게 있으면 그거는 내부적으로 모두 만족할테니 그걸 통째로 들어내버리고,
그 뒤 해당 부분집합 + 걔랑 서로소인 부분집합에 대한 합집합에 대해 부등호 만들고
거기다 딱 빼면 그것도 부등식을 전부 만족해서, 귀납으로 해결
내 증명에서도 내부적으로 귀납처리했어야하는게 좀 있나
아 돌것네
Rado’s theorem이 이거의 일반화라는데,
기존 증명이 너무 깔끔해서 증명 보기 귀찮다해야하나
5.2
[TODO]
필요해보이면 풀지 뭐
6. 윌슨정리, 페르마소정리
p가 소수면 a^p = a mod(p)
2이상의 자연수 p에 대해 p가 소수일 필요충분 조건은 (p-1)! = -1 mod p
생각했던건 Z_p의 곱에 닫힌 애들, 역원 있는 애들은 거기 안의 원소 곱하는게 bijection임.
그래서 걍 1~p-1 곱하면 어차피 p의 배수 아니라 걔도 역원 있고, a 곱한거 싸그리 곱하면 딱 a^(p-1) 곱한셈. 그래서 a가 p의 배수가 아니면 a^(p-1) = 1 mod p
우선 그리고 윌슨은, p가 소수일 필요충분조건은 gcd(p, (p-1)!) = 1 이라는거 정도는 자명하게 따라옴, (p-1)! = -1 mod p면 gcd(p, (p-1)!) = 1 인거니까, 합성수면 -1이 될수 없음은 나오죠.
자 그러면 소수일때 -1이라는걸 보이면 된다.
일단 1~p-1에 대해 죄다 역원이 있고, 그것도 1~p-1로 보내는 map임.
여기서 중요한게, k=1 or p-1인거랑, k^2 = 1 mod p인거랑 동치라는거( 정방향 당연하고, 역방향은 k^2-1 인수분해)
그리고 당연히 값이 다르면 역원이 다름. (p-1)!에서 역원 pair들을 잡는데,
1, p-1 빼고는 자기랑 다른 값이 역원일거고 걔네들은 곱하면 1 됨, (p-1)!은 걔네 곱에 1이랑 p-1 곱한거고, 딱 (p-1)! = p-1 = -1 mod p가 됨,
7. 중간값 정리
Intermediate Value Theorem, IVT
$f:[a, b] \to \mathbb{R}$ 이 연속일때 $min(f(a), f(b)) < y < max(f(a), f(b))$ 에 대해
어느 $c \in (a,b)$가 존재하여 $f(c) = y$ 이다.
$f(a) = f(b)$면 공허하게 참이고, 일반성을 잃지 않고 $f(a) < f(b)$라 하자.
즉 $f(a) < y < f(b)$이며, $b \in f^{-1}((y,\infty))$이며 열린집합에 속하므로
$(b - \epsilon_b, b] \subseteq f^{-1}((y,\infty))$ 인 $\epsilon_b > 0$이 존재함.
즉, $(b - \epsilon_b, b) \subseteq (f^{-1}(y,\infty))$
$A := f^{-1}([y,\infty))$로 잡아보자.
$f$가 연속이고 닫힌집합의 역상이 닫힌집합이 되므로 A는 $[a,b]$에서의 닫힌집합이며,
앞선 논증으로 인해 공집합이 아니라 하한 $c = \text{inf}(A)$가 존재.
또한 앞선 논증으로 $c \le b - \epsilon_b < b$
$c$를 포함하는 임의의 열린집합과 $A$의 교집합을 생각해보자.
열린집합들이 근방들의 합집합이니까 c의 근방 $(c - \epsilon_c, c + \epsilon_c)$에 대해서만보자.($\epsilon_c > 0$)
c는 하한이기 때문에, 정의상 there is some $x \in A$ such that $x < c + \epsilon_c$
즉, $A \cap (c - \epsilon_c, c + \epsilon_c) \neq \varnothing$
따라서 c의 임의의 근방은 A와 교집합이 공집합이 아니고,
A가 $[a,b]$에서 닫힌집합이고 $c \in [a,b]$이니 $c \in A$, 즉, $f(c) \ge y$이다.
$X \setminus A := f^{-1}((-\infty, y))$ 는 반대로 열린집합이고, $a \in X \setminus A$
즉 $[a, a + \epsilon_a) \subseteq X \setminus A$인 $\epsilon_a > 0$이 존재한다.
따라서, 역시 $a < a + \epsilon_a \le c$, 즉 $c \in (a, b)$
하한의 정의상 $x \in (a, c)$면 $f(x) < y$.
f는 연속함수니, $\epsilon > 0$에 대해 there is some $\delta > 0$ such that
$x \in (c - \delta, c + \delta)$ then $\vert f(c) - f(x) \vert = \vert (f(c)-y)+(y - f(x)) \vert < \epsilon$
즉, $x \in (a, c) \cap (c - \delta, c + \delta) = (\text{max}(a, c - \delta), c) \neq \varnothing$ then
두 조건을 합쳐 $\vert f(c) - f(x) \vert = \vert f(c) -y \vert + \vert y - f(x) \vert < \epsilon$
so $\vert f(c) -y \vert < \epsilon$
즉, $f(c) = y$