存在一個從X到Y的滿射，那麼一定存在一個從Y到X的單射嗎？

01-05

設 $X$ 和 $Y$ 是非空的集合，設存在一個從 $X$ 到 $Y$ 的滿射 $f:X o Y$ ，那麼一定存在一個從 $Y$ 到 $X$ 的單射嗎？

我在這樣想的，對於每個 $yin Y$ ，集合 $A_{y}=f^{-1}(y):={xin X,f(x)=y}$ 不是空集，於是使用選擇公理，存在一個函數 $(a_y)_{yin Y}$ 它把得每個 $yin Y$ 對應於 $a_yin A_y$ ，考慮集合 $Z:={a_y:yin Y}$ ，根據替代公理， $Z$ 是一個集合，還有 $Zsubseteq X$ .考慮函數 $f$ 限制在 $Z$ 上， $f|_{Z}:Z o Y$ ，那麼 $f|_{Z}$ 是從 $Z$ 到 $Y$ 的雙射，於是它的反函數 $f|_{Z}^{-1}$ 是從 $Y$ 到 $X$ 的單射.
感覺這個證明很奇怪，有沒有別的方法不必用到選擇公理？
還有一個類似的問題

任何一個無限的集合都有一個可數的子集

證明：設 $A$ 是無限集，則 $A$ 不是空集，可取 $a_0in A$ ， $Aackslash{a_0}$ 仍不是空集，又可取 $a_1in Aackslash{a_0}$ ，遞歸地定義 $a_nin Aackslash{a_1,a_2,cdots,a_{n-1}}$ ，這個定義是成功的，因為 $Aackslash{a_1,a_2,cdots,a_{n-1}}$ 不是空集，設 $B:={a_i:iinmathbb{N}}$ ，則 $B$ 是 $A$ 的子集，而且 $B$ 是可數集.
這個證明似乎是非構造性的證明，只斷言 $a_n$ 存在而不實際明白的構造這個對象，這個證明需要用到選擇公理嗎？

題主你說的命題就是選擇公理的等價說法。

axiom of choice in nLab

----------

我就覺得哪裡不對，數學歸納法只是用於證明任意有限而非可數。

在題主的證明中，數學歸納法只能對於任意的n，an存在，但集合B的存在性等同於一個從自然數集出發的映射的存在性，這類映射通常不是自然存在的。

手機打公式不便，如果明天有空再補充。這裡先給出結論：（在ZF下）第二個命題依賴選擇公理，但弱於選擇公理。

--------------------------------------------------------------

Update：2014/8/9

首先明確我理解的「無限集」是指「非有限集」。

1，具體說下用數學歸納法證明

命題1，無限集必然包含勢為任意自然數的子集。

證明：設集合X為一無限集，由於空集是有限集，故X不是空集，故X有勢為1的子集。

若X包含勢為任意小於n的自然數的子集，則不妨設其中之一為A，則X可劃分為A及其補集B。由於A是有限集，故不會等於X，其必是X的真子集，故B非空，故存在 $bin B$ 。於是 $Acup{b}$ 即為X的勢為n的子集。

由數學歸納法，命題得證。

註：

1，數學歸納法只能證明「任意有限」，不能證明「可數」。

2，數學推理的步驟總是有限的，不能是可數無限步。

2，下面給出命題

命題2，無限集必然包含可數子集。

的一個常見證明，並分析其中用到的選擇公理。

證明：設集合X為一無限集，由命題一，X包含以任意自然數為勢的子集，故函數

${ m Card}:{ m Fin}mathcal{P}(X) ightarrowmathbb{N}$ （將X的一個有限子集映到它的勢）

是滿射。

由可數選擇公理，Card具有選擇函數 $S:mathbb{N} ightarrow{ m Fin}mathcal{P}(X)$ 。取並集

$S:=igcup_{ninmathbb{N}}S(n)$

則S即為X的一個可數子集。

當然這樣要用到「可數個有限集的並是可數集」，另一個處理辦法如下：

用可數選擇公理從各 $S(n)$ 中同時選取一個元素組成一個集合，它也是X的一個可數子集。

3，命題2也可以表述為：

命題2"，若X是無限集，則存在單射 $mathbb{N} ightarrow X$ .

稱一個集合為Amorphous set，如果它是無限集但又不能寫成兩個無限集的不相交並集。

命題3，若X是amorphous set，則不存在單射 $mathbb{N} ightarrow X$ .

證明：否則，考慮全體奇數與全體偶數在該單射下的像，它們分屬X的兩個不相交無限子集。

故，由命題2"、3可知，在ZF+可數選擇公理下，不存在amorphous set.

但是

Lévy, A. (1958), "The independence of various definitions of finiteness", Fundamenta Mathematicae46: 1–13

給出了ZF下的具有amorphous set的模型。

可見命題2獨立於ZF，但不強於可數選擇公理。

選擇公理：在任意多個集合中可以從每個集合中選出一個元素。

1. 因為 $f$ 是滿射，所以 ${A_y=f^{-1}(y), yin Y }$ 是 $X$ 的一個劃分，集合 $Y$ 和 ${A_y}$ 之間存在雙射：

$g: g(A_y)=y$

但是這是 $Y$ 中元素和 $X$ 子集之間的映射關係，如果想構造一個 $Y$ 到 $X$ 的單射，關鍵問題是：已知 $X$ 有一個劃分 ${A_y}$ ，是否允許在每一個相互無交的非空子集 $A_y$ 中選出一個代表元。這裡不可避免要使用選擇公理，但是選擇公理在這裡使用是沒有什麼爭議的，因為不會出現怪異的結論。

2. "無限的集合都有一個可數的子集"的證明使用了遞歸定義，歸根結底是使用了數學歸納法，而數學歸納法一般是作為公理被接受的。這個證明裡要求每次可以從一個非空集合里選擇一個元素，先後選擇了可數次，並沒有使用選擇公理，因為選擇公理特指同時在任意多個集合進行選擇。

在數學證明裡隨處可見這樣的論證：如果集合 $A$ 非空，取其中一個元素，記為 $a$ ......

用手機看到的，有個想法不知道對不對：

截取半徑為1的圓方程的上半部分（不包括x軸左右端點），該方程對應X到Y的映射是滿射。對應的Y到X的函數圖像（反函數）即關於y=x對稱的圖形。。。不是映射。

數學不好，請指教^_^