AB之间互有满射，是否一定有双射？

abababa

下面说的映射，规定可以多对一，但不能一对多。

给定两个集合$A,B$，且已知$A$到$B$存在满射$f$，已知$B$到$A$存在满射$g$，问$A,B$之间是否存在双射？

这里是否需要限定$A,B$都是有限集？

现在已知如果互相都存在单射，是一定存在双射的。

hbghlyj

就是著名的施罗德-伯恩斯坦(Schroeder-Bernstein)定理
参阅《Naive Set Theory(Halmos)》Section22

abababa

回复 2# hbghlyj

我不明白，那定理要求两个都是单射，我这里说的是两个都是满射。

hbghlyj

回复 3# abababa
好像是这样：
A到B存在满射f，对B中任意元素b，任取它的一个原像a，定义h(b)=a，则h是单射

abababa

回复 4# hbghlyj

这样的话，那对于元素$a,a'\in A$满足$f(a)=f(a')=b\in B$，如果定义了$h(b)=a$，那得证明$a'$也必须要由同样的映射$h$对应才行，如果是由$b\in B$对应，$h$就不是映射了。但这时必须证明存在元素$b'\neq b,b'\in B$使得$h(b')=a'$才行。

hbghlyj

回复 5# abababa
为何还得证明a′也必须要由同样的映射h对应呢？
已经说明B到A有单射了，不需要A中每个元素都有h的原像啊

abababa

回复 6# hbghlyj

因为得证明它是映射啊，在这个规则下，$h(b)$为什么只能等于$a$而不能等于$a'$。

我觉得主楼那个可能不存在双射。我在想能不能把不可数集满射到一个可数集，然后可数集也满射到不可数集，这样就不存在双射了。

hbghlyj

回复 7# abababa
不是这个意思
对B中任意元素b，只要任取它的一个原像a(只需要任取一个，不需要取多个)，定义h(b)=a，这样h是映射，而且是单射(单射允许值域中有的元素没有原像)

abababa

刚才网友给讲了一大堆，基本没听懂。什么集合基数幂集之类的，不过最终取决于是否承认选择公理，如果承认选择公理它就是对的，否则就是不对的。

hbghlyj

如果承认选择公理就可以从b的原像中选出一个a来,就能构造h了吧

hbghlyj

Supplementary notes on countability by HA Priestley
Some suggestions for reading (mathematically rather than philosophically oriented)
1. T.M. Apostol, Mathematical Analysis, 2nd edition.
2. P.J. Cameron, Sets, Logic and Categories, parts of Ch. 1.
3. D. Goldrei, Classic Set Theory, parts of Ch. 6.
4. A.G. Hamilton, Numbers, Sets and Axioms, Ch.2.
Apostol gives an account geared to applications in analysis. The other books include not-
too-formal accounts of set theory. The one by Cameron is particularly suitable for contextual
reading and contains a lot of interestng material in an accessible form.

...


C.5 The Schröder–Bernstein Theorem.
Let $A$ and $B$ be sets and assume there exist injective maps $g : A → B$ and $h : B → A$. Then $A ≈ B$.
Proof. This does not need any fancy set-theoretic machinery. The most elegant proof makes use of a result known as the Tarski Fixed Point Theorem. This proof is given for example in [2], pp. 18–19.
SBT is particularly useful because it is often much harder explicitly to construct a bijection than to construct an injection.

Czhang271828

姑且简单写一下, 之后会补充一些.

Thm. (Schröder–Bernstein) $X$ 与 $Y$ 等势若且仅若 $|X|\leq |Y|$ 且 $|Y|\leq |X|$.

Proof.  取 $f:X\to Y$ 与 $g:Y\to X$ 为单射.不妨设 $g$ 为自然嵌入, 则
\[
\cdots f(f(Y))\subset  f(f(X))\subset f(Y)\subset f(X)\subset Y\subset X.\]
记 $X$ ($Y$) 在 $f$ 的 $k$ 次复合下的像为 $X_k$ 与 $Y_k$, 则
\[
\phi:X\to Y,x\mapsto
\left\{\begin{align*}
&f(x)&& x\in \cup_{n\geq 1} (X_n\setminus Y_n),\\
&x&&\text{else}.
\end{align*}\right.\]
为良定义的双射.

hbghlyj

math.stackexchange.com/questions/3323133

hbghlyj

abababa 发表于 2020-9-4 11:02
下面说的映射，规定可以多对一，但不能一对多。

给定两个集合$A,B$，且已知$A$到$B$存在满射$f$，已知$B$到$A$存在满射$g$，问$A,B$之间是否存在双射？

en.wikipedia.org/wiki/Eilenberg%E2%80%93Mazur_swindle#Other_examples

如果存在从 X 到 Y 和从 Y 到 X 的集合单射，这意味着形式上我们有 X = Y + A 和 Y = X + B，对于某些集合 A 和 B，其中 + 表示不相交并，用 = 表示两个集合之间存在双射。用后者扩展前者，

X = X + A + B。
在这个双射中，让 Z 由左侧对应于右侧 X 元素的那些元素组成。这个双射然后扩展为双射

X = A + B + A + B + ⋯ + Z。
将 X 替换为 Y = B + X 右侧的 X 得到双射

Y = B + A + B + A + ⋯ + Z。
交换每一对相邻的 B + A 得到

Y = A + B + A + B + ⋯ + Z。
将 X 的双射与 Y 的双射的逆复合得到

X = Y。
这个论证依赖于双射 A + B = B + A 和 A + (B + C) = (A + B) + C 以及无限不相交并集的定义良好性。