>>491
つづき

単射だが全射ではない関数 f: S → S が存在するとき、集合 S をデデキント無限集合と呼ぶ。そのような関数は S と S の真部分集合（f の像）との間の全単射を表している。
デデキント無限集合 S の元 x が f の像に属さないとき、x, f(x), f(f(x)), ... のようにして S の異なる元の無限の列を得ることができる。逆に S の元の列 x1, x2, x3, ... があるとき、この列上の元に対しては {\displaystyle f(x_{i})=x_{i+1}}f(x_{i})=x_{{i+1}} となり、それ以外の元については恒等関数として振舞う関数 f を定義できる。
従って、デデキント無限集合には自然数と全単射的に対応する部分集合が含まれる。デデキント有限集合とは、全ての単射自己写像が全射でもある場合を指す。

クラトフスキの有限性の定義は次の通りである。任意の集合 S について、和集合の二項演算は冪集合 P(S) に半束構造を与える。
空集合と単集合から生成した半束を K(S) と記し、S が K(S) に属する場合、S をクラトフスキ有限集合と呼ぶ。直観的に K(S) には S の有限な部分集合が含まれる。
重要なのは、この定義では自然数による帰納も再帰も必要とせず、K(S) は単に空集合と単集合を含む全ての半束構造の積集合として得られる点である。

ZFでは、クラトフスキ有限はデデキント有限を包含するが、逆は真ではない。

つづく