※ 引述《morning3569 (我甘心做一條水草)》之銘言：
: Let f : A -->A be a function from a finite set A to itself. Show that f is inje
: ----------------------------------------
: 是用鴿籠原理去證嗎？
: 我不知道如何用到finite 這個條件
: ----------------------------------
: http://i.imgur.com/qvUnRQe.jpg
: 我這樣證可以嗎？
: 原文書有另外一個問題是用鴿籠原理
: 請問如何用鴿籠原理去證？？
If f:A→A is a function with A is finite.
Show that f is injective if and only if f is surjective.
pf:
(i)若 f 是 injective
Let g:A→f(A) with g(x)=f(x)
則 g 是 bijective
因此 A 與 f(A) 等勢
又 f(A) 是 A 的子集
能夠與自己的真子集等勢的集合必為無限集
(有的人把這當成無限集的定義)
因 A is finite 故 f(A)=A
從而 f:A→A is surjective
(ii)若 f:A→A is surjective.
對 {f^-1(y) | y\in A} 用選擇函數
從每個 f^-1(y) 中取出一個元素，集合成C
則 h:C→A with h(x)=f(x) 是 bijective
因此 C 與 A 等勢
又C為A之子集
能夠與自己的真子集等勢的集合必為無限集
因 A is finite 故 C=A
從而 f:A→A is injective
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.246.101
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1538001240.A.A2B.html