집합, 함수, 논리¶

쪽의 코드가 세 가지를 차례로 보인다. 유한집합에서의 드모르간 법칙, 지시함수의 기댓값이 확률이라는 사실, 그리고 \(\mathbb{N}\) 과 \(\mathbb{Z}\) 를 짝지우는 함수다.

import numpy as np

# === De Morgan's law with finite sets ===
omega = set(range(1, 11))
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}

A_c, B_c = omega - A, omega - B
lhs = omega - (A | B)   # (A ∪ B)^c
rhs = A_c & B_c          # A^c ∩ B^c
print(f"(A ∪ B)^c = {lhs}")
print(f"A^c ∩ B^c = {rhs}")
print(f"Equal: {lhs == rhs}")

# === Indicator function and its connection to probability ===
rng = np.random.default_rng(42)
samples = rng.integers(low=1, high=11, size=10_000)
prob_A = np.mean([s in A for s in samples])
print(f"P(A) estimate: {prob_A:.3f} (true 1/2 since |A|=5 of 10)")

# === Bijection demonstration: N <-> Z ===
def bijection_N_to_Z(n):
    # n=1 -> 0, n=2 -> 1, n=3 -> -1, n=4 -> 2, n=5 -> -2, ...
    return n // 2 if n % 2 == 0 else -(n // 2)

print([bijection_N_to_Z(n) for n in range(1, 11)])

출력:

(A ∪ B)^c = {8, 9, 10}
A^c ∩ B^c = {8, 9, 10}
Equal: True
P(A) estimate: 0.506 (true 1/2 since |A|=5 of 10)
[0, 1, -1, 2, -2, 3, -3, 4, -4, 5]

(1) 손으로 세어 본다. \(A \cup B = \{1,2,3,4,5,6,7\}\)이므로 \((A \cup B)^c = \{8,9,10\}\)이다. 다른 쪽은 \(A^c = \{6,7,8,9,10\}\)과 \(B^c = \{1,2,3,8,9,10\}\)을 교차시켜 \(A^c \cap B^c = \{8,9,10\}\)이다. 출력의 두 줄이 그대로 이것이다.

우연이 아닌 까닭은 이 등식이 집합의 사실이 아니라 논리의 사실이기 때문이다. 원소 하나를 잡고 소속 여부를 명제로 읽으면

이고, 가운데 단계가 바로 \(\lnot(P \lor Q) \iff \lnot P \land \lnot Q\)다. \(\Omega\)가 무엇이든, \(A\)와 \(B\)가 무엇이든 성립한다. 아래 확인 코드는 \(\lvert \Omega \rvert = 5\)에서 부분집합 쌍 \(32^2 = 1024\)개를 전수 검사해 합집합꼴과 교집합꼴이 모두 참임을 보인다.

(2) 추정하는 것은 \(P(A)\)이고 참값은 정확히 \(1/2\)이다. 지시함수의 기댓값이 확률이라는 것이

이고, 균등분포에서는 \(P(A) = \lvert A \rvert / \lvert \Omega \rvert = 5/10 = 1/2\)다. 표본평균은 \(\mathbf{1}_A(X_i)\)들의 평균, 곧 \(\text{Bernoulli}(1/2)\) 표본의 비율이므로 표준오차가

이다. 그러므로 추정값이 \(0.5\)에서 \(\pm 0.005\) 안쪽에 들 확률이 약 \(68\%\), \(\pm 0.01\) 안쪽이 약 \(95\%\)다. \(0.506\)은 정확히 그 예산 안에 있다. 실제로 \(10000\)개 가운데 \(5061\)개가 \(A\)에 들었으니 벗어남은 \(0.0061 = 1.22\,\text{SE}\)다. 어긋난 것이 아니라 예상된 흔들림이며, 참값과 일치하기를 바라는 것이 오히려 잘못된 기대다. 자릿수를 더 얻으려면 \(n\)을 100배로 키워야 \(\text{SE}\)가 10분의 1이 된다.

(3) 두 쪽을 따로 보면 전단사가 보인다. \(n\)이 짝수면 \(f(n) = n/2\), 홀수면 파이썬의 n // 2가 \((n-1)/2\)이므로 \(f(n) = -(n-1)/2\)다. 곧

이고 두 상(image)이 서로 겹치지 않으면서 합이 \(\mathbb{Z}\) 전체다. 각 쪽에서 \(f\)가 단조이므로 단사이고, 두 상이 \(\mathbb{Z}\)를 덮으므로 전사다. 역함수는

이다. \(g(1) = 2\), \(g(0) = 1\), \(g(-1) = 3\), \(g(5) = 10\)이고, 출력의 리스트 [0, 1, -1, 2, -2, ...]가 \(g\)의 값을 \(1\)부터 차례로 되읽은 것이다.

import itertools
import math

import numpy as np

# === 드모르간이 특정 세 집합의 우연이 아님을 전수 확인한다 ===
om = set(range(5))
subs = [set(c) for r in range(6) for c in itertools.combinations(om, r)]
ok_union = all(om - (X | Y) == (om - X) & (om - Y) for X in subs for Y in subs)
ok_inter = all(om - (X & Y) == (om - X) | (om - Y) for X in subs for Y in subs)
print(f"부분집합 쌍 {len(subs) ** 2}개 전수 확인:  합집합꼴 {ok_union}  교집합꼴 {ok_inter}")

# === 지시함수 추정값이 1 표준오차 몇 배만큼 벗어났는가 ===
rng = np.random.default_rng(42)
samples = rng.integers(low=1, high=11, size=10_000)
k = int(np.sum(np.isin(samples, [1, 2, 3, 4, 5])))
se = math.sqrt(0.5 * 0.5 / 10_000)
print(f"A에 든 표본 {k}/10000 = {k / 10_000:.4f},  SE = {se:.4f},  "
      f"벗어남 = {(k / 10_000 - 0.5) / se:.2f} SE")

# === 전단사의 역함수를 적어 양쪽으로 확인한다 ===
def f(n):
    return n // 2 if n % 2 == 0 else -(n // 2)

def g(k):
    return 2 * k if k >= 1 else 1 - 2 * k

print(f"f가 1..4000에서 단사:      {len(set(map(f, range(1, 4001)))) == 4000}")
print(f"f(g(k)) == k  (|k| <= 2000): {all(f(g(k)) == k for k in range(-2000, 2001))}")
print(f"g(f(n)) == n  (n <= 4000):   {all(g(f(n)) == n for n in range(1, 4001))}")

출력:

부분집합 쌍 1024개 전수 확인:  합집합꼴 True  교집합꼴 True
A에 든 표본 5061/10000 = 0.5061,  SE = 0.0050,  벗어남 = 1.22 SE
f가 1..4000에서 단사:      True
f(g(k)) == k  (|k| <= 2000): True
g(f(n)) == n  (n <= 4000):   True

세 가지가 모두 맞는다. 그리고 (3)이 이 쪽에서 가장 쓸모 있는 대목이다. \(\mathbb{N}\) 은 \(\mathbb{Z}\) 의 진부분집합인데도 둘 사이에 전단사가 있으므로 \(\mathbb{Z}\) 는 가산이다. 가산이라는 것은 곧 \(\sigma\)-가법성을 그대로 쓸 수 있다는 뜻이고, 그래서 \(\mathbb{Z}\) 를 값으로 갖는 확률변수는 확률질량함수 하나로 다 기술된다. 반면 \(\mathbb{R}\) 에는 그런 짝짓기가 없고, 거기서부터 밀도와 적분이 필요해진다.

(a) \(\exists\, x \in \mathbb{R} \text{ such that } x^2 < 0\). (b) \(\forall\, \varepsilon > 0,\; \exists\, n \in \mathbb{N} \text{ such that } a_n \leq \varepsilon\). (c) 바깥쪽부터 안쪽으로 차례로 부정한다. 부정은

이며, 이것이 바로 "\(a_n\)이 \(L\)로 수렴하지 않는다"는 진술이다.

(a) \(A \cap B = \{3, 4, 5\}\), \(A \cup B = \{1, 2, 3, 4, 5, 6, 7\}\), \(A \setminus B = \{1, 2\}\), \(A^c = \{6, 7, 8\}\), \(A \triangle B = \{1, 2, 6, 7\}\).

(b) \((A \cup B)^c = \{8\}\)이고 \(A^c \cap B^c = \{6, 7, 8\} \cap \{1, 2, 8\} = \{8\}\)이다. 둘 다 \(\{8\}\)과 같다. \(\square\)

양쪽 포함관계를 보여 집합이 같음을 증명한다.

(\(\subseteq\)): \(x \in (A \cup B)^c\)라 하자. 그러면 \(x \notin A \cup B\)이므로 \(x \notin A\)이고 또한 \(x \notin B\)이다. 따라서 \(x \in A^c\)이고 \(x \in B^c\), 즉 \(x \in A^c \cap B^c\)이다.

(\(\supseteq\)): \(x \in A^c \cap B^c\)라 하자. 그러면 \(x \notin A\)이고 \(x \notin B\)이므로 \(x\)는 어느 집합에도 속하지 않고 따라서 \(x \notin A \cup B\), 즉 \(x \in (A \cup B)^c\)이다.

양쪽 포함관계가 모두 성립하므로 두 집합은 같다. \(\square\)

(\(\Rightarrow\)) \(f\)가 단사라고 하자. 포함관계 \(f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)\)는 임의의 함수에 대해 성립한다(\(x \in S_1 \cap S_2\)에 대해 \(y = f(x)\)이면 \(y\)는 \(f(S_1)\)과 \(f(S_2)\) 모두에 속한다). 반대 방향으로, \(y \in f(S_1) \cap f(S_2)\)라 하자. 그러면 어떤 \(x_1 \in S_1\), \(x_2 \in S_2\)에 대해 \(y = f(x_1) = f(x_2)\)이다. 단사성에 의해 \(x_1 = x_2\)이므로 \(x_1 \in S_1 \cap S_2\)이고 \(y \in f(S_1 \cap S_2)\)이다.

(\(\Leftarrow\)) 모든 부분집합에 대해 이 항등식이 성립한다고 하자. \(f(x_1) = f(x_2) = y\)인 임의의 \(x_1, x_2 \in A\)를 잡고 \(S_1 = \{x_1\}\), \(S_2 = \{x_2\}\)라 두자. 그러면 \(f(S_1) \cap f(S_2) = \{y\}\)이므로 가정에 의해 \(f(S_1 \cap S_2) = \{y\}\)이다. 이것이 공집합이 아니려면 \(S_1 \cap S_2 \ne \emptyset\)이어야 하므로 \(x_1 = x_2\)가 강제된다. \(\square\)

\(\mathbb{Q}\)에서 \(\mathbb{N}\)으로 가는 단사를 제시하면 충분하다(그러면 \(\mathbb{Q}\)는 많아야 가산이고, 무한집합임은 분명하다). 모든 양의 유리수는 \(p, q \in \mathbb{N}\)인 기약분수 \(p/q\)로 유일하게 쓸 수 있다. 다음과 같이 정의하자.

소인수분해의 유일성에 의해 \(\phi\)는 \(\mathbb{Q}_{>0}\) 위에서 단사다. 여기에 \(\mathbb{Q}\)에서 \(\{0\} \cup \mathbb{Q}_{>0} \cup \mathbb{Q}_{<0}\)으로 가는 전단사(예: 양의 유리수와 음의 유리수를 \(0, q_1, -q_1, q_2, -q_2, \ldots\)처럼 번갈아 배열)를 합성하면 단사 \(\mathbb{Q} \hookrightarrow \mathbb{N}\)을 얻는다. \(\square\)

베이즈 규칙에 의해

이다. 가정 \(P(A \mid B) > P(A)\)는 \(A\)와 \(B\)에 대해 대칭이다. 양변에 \(P(B)/P(A)\)를 곱하면 \(P(B \mid A) > P(B)\)도 성립함을 알 수 있다. 따라서 "\(A\)와 \(B\)가 양의 연관을 갖는다"는 사실은 둘 중 어느 쪽이 (또는 어느 쪽이든) 다른 쪽을 유발하는지에 대해 아무것도 말해주지 않는다. 인과성은 반사실이나 개입에 관한 진술이며 조건부확률 진술만으로는 추론할 수 없다(이것이 "상관관계는 인과관계를 뜻하지 않는다"의 형식적 대응물이다). \(\square\)

귀류법을 쓴다. \((0,1)\)이 가산이라 가정하면 그 원소를 모두 나열할 수 있다.

이제 새로운 수 \(y = 0.e_1e_2e_3\cdots\)를 대각선을 피해서 만든다.

그러면 \(y \in (0,1)\)이지만, 모든 \(k\)에 대해 \(y\)는 \(k\)번째 자리에서 \(x_k\)와 다르므로 \(y \ne x_k\)이다. 즉 \(y\)는 목록에 없다. 이는 목록이 \((0,1)\) 전체를 담는다는 가정에 모순이다. \(\square\)

확률론에서의 귀결. \((0,1)\) 위의 균등분포를 생각하자. 각 점의 확률이 어떤 상수 \(c\)로 같아야 할 것 같지만,

• \(c > 0\)이면 가산개의 점만 모아도 확률의 합이 \(\infty\)가 되어 \(1\)을 넘는다.
• \(c = 0\)이면, 만약 \((0,1)\)이 가산이었을 경우 가산가법성에 의해 전체 확률이 \(0\)이 되어 모순이다.

비가산이기 때문에 두 번째 모순이 발생하지 않는다. 가산가법성은 비가산 합집합에는 적용되지 않으므로, 모든 점의 확률이 \(0\)이면서도 전체의 확률이 \(1\)일 수 있다. 연속형 확률변수에서 \(P(X = a) = 0\)인데도 \(P(a < X < b) > 0\)인 것이 이상하지 않은 이유가 바로 이것이다.

기본 항등식. \(\mathbf{1}_{A\cap B}(x) = 1\)일 필요충분조건은 \(x \in A\)이고 \(x \in B\)인 것이며, 이는 \(\mathbf{1}_A(x)\mathbf{1}_B(x) = 1\)과 같다. 두 값이 모두 \(\{0,1\}\)에 있으므로 곱이 곧 논리곱이다. 여집합은 정의에서 바로 나온다.

합집합. \(x\)가 어느 \(A_i\)에도 속하지 않을 필요충분조건은 모든 \(i\)에 대해 \(1 - \mathbf{1}_{A_i}(x) = 1\)인 것이므로

이고, 여집합을 취하면 주어진 식이 된다. 드모르간 법칙을 곱으로 쓴 것이다.

전개. \(n = 3\)일 때 곱을 펼치면

이다. 여기서 \(\mathbb{E}[\mathbf{1}_S] = P(S)\)를 쓰고 곱을 교집합으로 되돌리면

를 얻는다. 일반형의 부호 \((-1)^{k+1}\)은 곱을 전개할 때 나오는 \((-1)^k\)에서 그대로 온다. \(\square\)

import numpy as np

rng = np.random.default_rng(3)
N = 200_000
A = rng.random(N) < 0.5
B = rng.random(N) < 0.3
C = rng.random(N) < 0.2

union = (A | B | C).mean()
incl_excl = (A.mean() + B.mean() + C.mean()
             - (A & B).mean() - (A & C).mean() - (B & C).mean()
             + (A & B & C).mean())
product = (1 - (1 - A) * (1 - B) * (1 - C)).mean()   # 지시함수 곱 형태

print(f"P(A∪B∪C) 직접   = {union:.6f}")
print(f"포함–배제       = {incl_excl:.6f}")
print(f"지시함수 곱     = {product:.6f}")

출력:

P(A∪B∪C) 직접   = 0.718550
포함–배제       = 0.718550
지시함수 곱     = 0.718550

세 값이 부동소수점 오차 안에서 일치한다. 세 번째 계산이 특히 눈여겨볼 만한데, 집합 연산을 산술로 바꾸어 벡터화된 코드 한 줄로 끝냈다.

이 기법은 유도 도구 이상이다. 조합론에서 완전순열의 개수를 세거나 확률에서 본페로니 부등식(전개를 도중에 자르면 상계와 하계가 번갈아 나온다)을 얻을 때도 같은 전개를 쓴다.

(a) 점별 수렴. \(x \in [0,1)\)을 고정하면 \(|x| < 1\)이므로 \(x^n \to 0\)이다. 주어진 \(\varepsilon\)에 대해 \(N = \lceil \ln\varepsilon / \ln x\rceil\)로 두면 된다.

(b) 균등수렴의 실패. 각 \(n\)에 대해

이다(\(x \to 1^-\)일 때 상한에 접근한다. 최댓값은 아니다). 이 상한이 \(n\)과 무관하게 \(1\)이므로 \(0\)으로 가지 않는다.

(c) 한정기호 구조.

차이는 오직 \(\exists N\)과 \(\forall x\)의 순서뿐이다. 점별에서는 \(N\)이 \(x\)에 의존해도 되지만, 균등에서는 하나의 \(N\)이 모든 \(x\)에 동시에 통해야 한다. 여기서는 \(x\)가 \(1\)에 가까워질수록 필요한 \(N\)이 한없이 커지므로 그런 \(N\)이 없다. \(\square\)

import numpy as np

print("고정된 x 에서는 0 으로 간다 (점별 수렴)")
print(f"{'n':>6}{'0.5^n':>12}{'0.9^n':>12}{'0.99^n':>12}{'sup':>8}")
for n in (10, 100, 1000, 10_000):
    print(f"{n:>6}{0.5 ** n:>12.3e}{0.9 ** n:>12.3e}{0.99 ** n:>12.3e}{1.0:>8.1f}")

print("\n|x^N| < 0.01 을 만들려면 N 이 얼마나 커야 하는가")
for x in (0.5, 0.9, 0.99, 0.999):
    N = int(np.ceil(np.log(0.01) / np.log(x)))
    print(f"  x = {x:<6}: N = {N:>5}")

출력:

고정된 x 에서는 0 으로 간다 (점별 수렴)
     n       0.5^n       0.9^n      0.99^n     sup
    10   9.766e-04   3.487e-01   9.044e-01     1.0
   100   7.889e-31   2.656e-05   3.660e-01     1.0
  1000  9.333e-302   1.748e-46   4.317e-05     1.0
 10000   0.000e+00   0.000e+00   2.249e-44     1.0

|x^N| < 0.01 을 만들려면 N 이 얼마나 커야 하는가
  x = 0.5   : N =     7
  x = 0.9   : N =    44
  x = 0.99  : N =   459
  x = 0.999 : N =  4603

표의 마지막 열이 핵심이다. 각 열은 \(0\)으로 내려가지만 상한은 \(n\)이 아무리 커도 \(1\)에 붙박여 있다. 그리고 필요한 \(N\)은 \(x \to 1^-\)에서 발산한다.

통계에서 왜 중요한가. 글리벤코–칸텔리 정리는 경험분포함수가 참 분포함수로 균등하게 수렴한다고 말한다(\(\sup_x |F_n(x) - F(x)| \to 0\), 거의 확실하게). 점별 수렴만으로는 부족한데, 콜모고로프–스미르노프 검정 같은 방법이 바로 그 상한을 검정통계량으로 쓰기 때문이다.

전단사. \(y = 1/(1+e^{-x})\)를 \(x\)에 대해 푼다.

각 \(y \in (0,1)\)에 대해 이 \(x\)가 유일하게 존재하므로 \(\sigma\)는 전단사이고, 역함수는 로짓 \(\operatorname{logit}(y) = \ln\frac{y}{1-y}\)이다. 이것이 로지스틱 회귀에서 확률을 실직선으로 옮겨 선형모형을 세울 수 있게 해 주는 다리다.

도함수. 몫의 미분 또는 연쇄법칙으로

이다. 마지막 등호는 \(\dfrac{e^{-x}}{1+e^{-x}} = 1 - \dfrac{1}{1+e^{-x}}\)에서 나온다.

대칭성. \(\sigma(-x) = \dfrac{1}{1+e^{x}} = \dfrac{e^{-x}}{e^{-x}+1} = 1-\sigma(x)\)이다. \(\square\)

import numpy as np
from scipy.special import expit

x = np.array([-3., -1., 0., 1., 3.])
p = expit(x)

print("sigma(x)        :", p.round(6))
print("sigma(x)+sigma(-x):", (p + expit(-x)).round(12))
print("logit(sigma(x)) :", np.log(p / (1 - p)).round(10))

h = 1e-6
print("\n수치 도함수 :", ((expit(x + h) - expit(x - h)) / (2 * h)).round(8))
print("sigma(1-sigma):", (p * (1 - p)).round(8))

출력:

sigma(x)        : [0.047426 0.268941 0.5      0.731059 0.952574]
sigma(x)+sigma(-x): [1. 1. 1. 1. 1.]
logit(sigma(x)) : [-3. -1.  0.  1.  3.]

수치 도함수 : [0.04517666 0.19661193 0.25       0.19661193 0.04517666]
sigma(1-sigma): [0.04517666 0.19661193 0.25       0.19661193 0.04517666]

두 가지 실무적 함의.

도함수가 \(\sigma(1-\sigma)\)라는 것은 최댓값이 \(x = 0\)에서 \(0.25\)이고 양쪽 꼬리에서 \(0\)으로 죽는다는 뜻이다. \(|x|\)가 크면 기울기가 사실상 사라지므로, 신경망에서 시그모이드를 은닉층 활성함수로 쓸 때 기울기 소실 문제가 생긴다. 로지스틱 회귀의 피셔 정보에도 같은 인자가 나타나며, 이는 \(\hat{p}\)이 \(0\)이나 \(1\)에 가까울 때 계수 추정이 불안정해지는 이유다.

\(x = -800\)처럼 큰 음수에서 \(1/(1+e^{-x})\)를 그대로 계산하면 exp 가 넘쳐 경고가 난다. scipy.special.expit 은 부호에 따라 \(e^{x}/(1+e^{x})\) 형태로 갈아타 이를 피한다. 로그가능도를 직접 구현할 때는 이런 수치적으로 안정한 형태를 쓰라.