(A,≤)와 (B,≤')가 정렬집합이고 f : A→B가 증가함수(increasing), g : A→B가 단조증가함수(strictly increasing), f(A)가 B의 하집합(lowerset)이면 모든 x∈A에 대하여 f(x)≤'g(x)임을 보여라.
증명) 각각의 x∈A에 대하여 명제함수 p(x)를 "f(x)≤'g(x)"라 하자. 초한귀납법의 가정을 만족함을 보이기 위해 역을 가정하여 ∀x<a, p(x)가 참인 a∈A가 존재하지만 p(a)는 거짓이라 하자. 즉, ∀x<a, f(x)≤'g(x)이고 g(a)<'f(a)이다. 이때 f는 증가하고 g는 단조증가하므로 y≥a에 대해 다음과 같다.
f(x)≤'g(x)<'g(a)<'f(a)≤'f(y)
g(a)<'f(a)이고 "g(a)∉f(A)이므로 이는 f(A)가 B의 하집합이라는 것에 모순이다."
여기서 따옴표 친 부분이 어케 나온 거임? 그리고 g(a)∉f(A)이면 이게 왜 f(A)가 B의 하집합이라는 거에 모순인 거고?
- dc official App
g(a)∉f(A)이면 모순인 이유는 하집합의 정의상 f(a)∈f(A)니까 그것보다 ≤' 관계상으로 더 작은 것들도 다 f(A)에 들어가야 하는데 g(a)<'f(a)인데도 f(A)에 안들어가니까 모순인건가? 근데 g(a)∉f(A)인 이유는 아직도 모르겠음 - dc App
정렬순서는 선형순서이니까, f(x) = g(a)를 만족하는 A의 원소 x에 대하여 x >= a이어도 모순이고 x < a이어도 모순이니까요.
x≥a이면 처음에 x<a라 가정했으니 모순인데, x<a인 경우에는 뭐땜에 모순이 되나요? - dc App
g(a)가 f(A)의 원소라면 g(a) = f(z)인 A의 원소 z가 존재하겠죠. z < a이거나 z >= a인데 z < a이면 f(z) <' g(a)이고 z >= a이면 g(a) <' f(z)이므로 모순이에요.
정렬순서는 선형순서이고 f(x)≤'g(x)<'g(a)<'f(a)≤'f(y)이니까요.