동일한 유한 집합 간의 Surjection, 두 개의 다른 입력이 동일한 출력을 생성 할 수 없음을 보여줍니다.
두 개의 서로 다른 입력이 동일한 유한 집합 간의 대립에 대해 동일한 출력을 생성 할 수 없다는 것을 증명할 수 있습니까? 먼저 그러한 예측이 주입이라는 것을 증명하는 것이 가능합니까?
나는이 결과를 사용하여 그러한 추측이 주사라는 것을 증명하려고하기 때문에 이것을 묻는 것입니다.
여기에 주입의 작동 증명이 있습니다.
골: $∀n ∈ ℕ, ∀ f, f: n ⟹ n → injective f$
여기서 "f : n ⟹ n"은 f가 n에서 n까지의 추측임을 나타냅니다.
귀납법으로 증명하면, n = 0은 막연하게 사실입니다.
n = k 인 경우 $∀ f, f: k ⟹ k → injective f$
그래서 우리는 증명해야합니다 $∀ f, f: k⁺ ⟹ k⁺ → injective f$
중간 제외 사용 $∀p ∈ k, f(p) ∈ k$
사례 I : $∀p ∈ k, f(p) ∈ k$
우리는 $f(k) = k$, 또는 $f(k) ∈ k$ k에 매핑되는 것이 없기 때문에 추측과 모순됩니다.
그래서 우리는 $f ↾ k : k ⟹ k$ 여기서 "↾"는 제한을 나타냅니다.
귀납 가설에 의해 $injective (f ↾ k)$
따라서 $f = f ↾ k ∪ \{<k, k>\}$ 주사제입니다.
사례 II : $¬ ∀p ∈ k, f(p) ∈ k$ 즉 $∃p ∈ k，f(p) = k$
증명할 수 있다면 $f(k) ∈ k$， 그런 다음 k와 p의 값을 바꾸어 Case I로 줄일 수 있습니다.
증명하기 위해 $f(k) ∈ k$, 통지 $f(k) ∈ k⁺$
우리는 증명 만하면됩니다 $f(k) ≠ k$ 제목이 요구하는 내용으로 연결됩니다.
답변
동일한 카디널리티의 두 유한 집합 사이의 외래 함수가 주입 적이라는 직접적인 증거를 작성하겠습니다. 그 후 질문 및 증명 시도와 비교하는 방법에 대해 논의 할 것입니다.
당신의 설정에 따라 $n\in\mathbb{N}$유한 서수로; 그래서$n=\{k\in\mathbb{N}:k<n\}$.
정리 : If$g:n\to n$ 주사제, 그럼 $g$추측입니다.
증명 : 하자$X$ 의 이미지 $g$. 그때$g:n\to X$ bijection이므로 $|X|=n$. 그래서$X=n$.
이제 우리는 주요 결과를 증명합니다. 허락하다$f: n\to n$추측 기능입니다. 우리는$f$주사제입니다. 이후$f$ 어느 누구에게나 $k\in n$ 약간있다 $x_k\in n$ 그런 $f(x_k)=k$. 이후$f$ 함수입니다. $k\neq l$ 그때 $x_k\neq x_l$. 그래서$g:n\to n$ 그런 $g(k)=x_k$는 주입 기능이므로 Lemma에 의해 추측됩니다. 마지막으로$x,y\in n$ 과 $f(x)=f(y)$. 이후$g$ 우리는 압니다 $x=x_k$ 과 $y=x_l$ 일부 $k,l\in n$. 그래서$f(x_k)=f(x_l)$즉, $k=l$. 그래서$x=x_k=x_l=y$. 따라서$f$ 주사제입니다.
질문 및 증명 시도에 대한 토론 :
두 가지 다른 입력을 보여줄 수 있는지 묻습니다. $a$ 과 $b$, 함수 $f$ 먼저 표시하지 않고 다른 출력을 생성 $f$주사제입니다. 인젝 티브의 정의는 "어떤 두 개의 서로 다른 입력이 다른 출력을 생성한다"이기 때문에 이것이 가능한 유일한 방법은$f$, $a$, 및 $b$. 실제로 다음과 같은 주장이 있다면$f(a)\neq f(b)$, 특별한 것을 사용하지 않습니다. $f$, $a$, 및 $b$, 그렇다면 당신이 가진 것은 $f$ 주사제입니다.
나는 귀하의 증거에서 귀하가 줄인 문제가 더 쉽다는 결론을 내리기에 충분한 구체적인 정보가 없다고 주장합니다. 귀하의 경우 다음 두 가지 문제를 비교하고 있습니다.
어떠한 것도 $k$ 과 $p\in k$, 만약 $f:k^*\to k^*$ 추측적이고 $f(p)=k$ 그때 $f(k)\neq k$.
어떠한 것도 $k$ 그리고 뚜렷한 $a,b\in k^*$, 만약 $f:k^*\to k^*$ 그렇다면 추측 적이다 $f(a)\neq f(b)$.
따라서 (1)은 증명에서 도달 한 특정 상황이고, (2)는 " $k^*$ ...에 $k^*$ 이것은 일반적인 질문입니다.
(1)이 (2)를 표시하지 않고 보여주기가 더 쉬운 지 묻습니다. 그러나 나는 (1)과 (2)가 본질적으로 동등하다고 주장합니다. 실제로 (1)을 가정한다고 가정합니다. 그런 다음 주어진 surjective$f:k^*\to k^*$ 그리고 뚜렷한 $a,b\in k^*$, 순열 선택 $h$ 의 $k^*$ 보내는 $p$ ...에 $a$ 과 $k$ ...에 $b$. 다른 순열 선택$g$ 의 $k^*$ 보내는 $f(a)$ ...에 $k$. 중히 여기다$f^*=g\circ f \circ h$. 그때$f^*$ 여전히 추측이고 $f^*(p)=k$. 그래서$f^*(k)\neq k$의해 (1). 선택 사항을 풀면 다음과 같이 말합니다.$g(f(a))\neq g(f(b))$, 그래서 $f(a)\neq f(b)$ 이후 $g$주사제입니다. 그래서 우리는 (2)를 보여주었습니다.
요약하면 질문이 더 구체적으로 보이는 외관을 가지고 있지만 적절한 순열로 구성한 후 일반적인 질문과 실제로는 동일합니다. 그러므로 증명을 계속해야하는 유일한 의지는 내가 위에서 준 것과 같은 주입성에 대한 일반적인 유형의 주장입니다.