Both surjections
and pigeonholing provide us with relations that have
much of the character of size-orderings among collections. I now turn to the
particular case of collections that are the same size as

some natural number or the whole of {naturals}. The
former shall give us a mapping that tells us how many members a finite
collection has; the latter are the smallest

size of infinite
collection. To this end: define a mapping on collections by

- count = (: unite({natural n: C pigeonholes n}) ←C :{collections})

i.e. count(C) is either the largest natural that C does pigeonhole (any finite union of naturals is the largest natural included in the union) or it's {naturals} itself. Given that each natural subsumes each of its members, i.e. each earlier natural, and C pigeonholes every sub-collection of any collection it pigeonholes, the set united in the definition actually includes every natural in count(n); when count(n) is natural, the set united also includes count(n) itself.

Now, no collection pigeonholes another of which it is a proper sub-collection and every natural subsumes each of the earlier naturals (its members), so no natural pigeonholes any greater natural; and naturals are finite by definition, so pigeonhole themselves and all their members; so (: count :{naturals}) = {naturals}; every natural is a fixed point of count. Thus, at least for naturals, count tells us how many members its input has.

For any collection C, if n = count(C) is natural, then C pigeonholes n and all its members but does not pigeonhole n&unite;{n}, a.k.a. successor(n) or 1+n; consequently, for c not in C, C&unite;{c} pigeonholes n&unite;{n} but not (1+n)&unite;{1+n}, hence count(C&unite;{c}) = 1+n = 1+count(C). When count(C) is {naturals}, of course, C&unite;{c} pigeonholes every natural, so has count(C&unite;{c}) = {naturals} also.

Suppose some natural pigeonholes a collection C; let n be the intersection of all such naturals; hence n pigeonholes C but no member of n does. If n is empty then so is C (as empty only pigeonholes itself) and C pigeonholes n, with count(C) = n; otherwise, let i = unite(n), its maximal member, so n = i&unite;{i} and i does not pigeonhole C, so there exists a mapping (i|f:C) which is not (i:|C). We can define a relation ({i}::C) that relates i to every member of C that isn't a right value of this f; as f is not (:f|C) there is at least one such member of C, so this relation does have i as a left value; as this relation has only one left value, i, it is necessarily a mapping; as it has no right value in common with f, we can unite it with mapping f to get a mapping, g; which is, by construction, (i&unite;{i}| g |C). As this is a mapping (n|g:C) and n pigeonholes C, it's a monic (n:g|C), so maps only one member of C to i; i.e. only one member of C was not a right value of f. In any case, g is now iso (n|g|C) and C is finite, with count(C) = n and C pigeonholes n.

Thus, if any natural pigeonholes a collection, that collection is isomorphic
to its count, with this natural and the collection pigeonholing one
another. Since every finite collection of naturals is subsumed by some natural
(namely: the successor of its union, i.e. of its maximal member), hence
pigeonholed by some natural, we can at least assert that every finite
collection *of naturals* is isomorphic to its count. It remains to show
that *every* finite collection is in fact pigeonholed by some natural;
the rest of this page is unfinished fumbling towards such a result.

For any collection C and any mapping (C|f:N) with N either {naturals} or a natural, we can construct g = (C: c ← intersect({natural i: f(i) = c}) :N), which is monic as well as a mapping, by construction, and has every left value of f so is also (C|g:N). Furthermore, we can construct h = (C| g(i) ← count(g:j←j:i) :), which is necessarily iso (C|h|M) with M either {naturals} or a natural; consequently, whenever a collection C admits a mapping (C|:N) with N either {naturals} or a natural, it in fact admits an iso (C||M) with M either N or in N.

Proof that (C|h:) is iso (C|h|M) with M either {naturals} or a natural, and subsumed by N:

First observe that h is indeed (C|:N), since its typical left value is g(i) and each member of C is indeed g(i) for some i in N; then S(i) = (g:j←j:i) is the collection of g's right values < i, which i subsumes, thus it does not pigeonhole i&unite;{i}, so count(S(i)) is in i&unite;{i}, which N subsumes, hence count(S(i)) is in N – and, in particular, is natural, so finite. Thus every member of C is a left value and the corresponding right value is in N. That h is monic follows from the form of its definition and the fact that g is monic; so we have monic (C|h:N).

The intrinsic ordering on naturals, membership, implies an ordering on the right values of g, so that the least right value i has S(i) = {}, with {i} then being S's value for the next and each subsequent adding its predecessor to S; thus the count of each S(i) in this sequence is simply the successor of the previous count, so that {count(g:j←j:i): i in (g:j←j:)} is either {naturals} or a natural; and it is subsumed by N, by the preceding, so it either is N or is in N. Furthermore, each right value i of g yields a distinct count(g:j←j:i), so h is a mapping. QED.

In particular, if there are no mappings ({naturals}|:C) then there are no monics (C:|{naturals}) so any mapping (C|:{naturals}) implies the existence of an iso (C||n) for some natural n – the alternative n = {naturals} being ruled out by our iso (C||n) being monic (C:|n). So C < {naturals} and C ≤ {naturals}, together, imply count(C) is natural.

A collection C is infinite precisely if it does not pigeonhole itself; so there exists some mapping (C|g:C) which is not (C:|C). If count(C) < C then C pigeonholes {c}&unite;count(C) for any c not in count(C), including c = count(C); and count(C) subsumes every natural that C pigeonholes, but cannot subsume {count(C)}&unite;count(C), so this cannot be a natural; hence count(C) is in fact {naturals}. Otherwise, with C infinite, count(C) ≥ C so consider a mapping (C|:count(C)); as above, it implies an iso (C|f|N) for some N, either {naturals} or a natural, subsumed by count(C), so either N = count(C) or N in count(C). We can compose f and its reverse on either side of g, which isn't (C:|C), to obtain a mapping (N| reverse(f)&on;g&on;f :N). There's at least some c in C that's not a right value of g; and it's f(n) for some n in N; so this n is not a right value of our composite, which is thus a mapping (N|:N) but not (N:|N), hence N is infinite; and count(C) subsumes N. No natural subsumes any infinite collection and the only other possible left value of count is {naturals}, so count(C) = {naturals}. Therefore count maps every infinite collection to {naturals}.

Given a collection C, if count(C) is in some natural m – so C does not pigeonhole m, which is finite – we have C<m and C≤m. In particular, when count(C) = n is natural, with m = n&unite;{n}, {mappings (C|:m)} is non-empty and m pigeonholes C&unite;{c} for any c; cancelling extra members, this last tells us that n pigeonholes C. Now, as C<m, there is no mapping (m|:C), hence no monic (C:|m); but there does exist some mapping (C|:m) hence, by the above, some iso (C|f|i) with i natural and subsumed by m. Since there exist no monic (C:|m), the right values of f cannot be all of m, hence i is not m, so i is in m and, in particular, n is not in i, so f is (C|f:n) and there does exist a mapping (C|:n), so C≤n. Thus, whenever count(C) is natural, C ≤ count(C) and count(C) pigeonholes C.

Whenever a collection C has a natural n in count(C), this last subsumes n&unite;{n} and C pigeonholes count(C) hence also n&unite;{n}, hence n < C; when count(C) is {naturals}, every natural is thus < C; otherwise, count(C) is natural, hence ≥ C, so not < C, nor is any greater natural <C; thus count(C) is simply {naturals < C}.

Suppose some collection C is ≤ some natural; let n be the intersection of all such naturals, hence the least natural ≥ C; hence every natural in n is < C, and n is not, so n = {naturals < C} = count(C) so count(C) is natural. Thus a collection C has count(C) natural precisely if there is some natural ≥ C, in which case one such natural is count(C). Conversely, count(C) is {naturals} precisely if no natural is ≥ C.

When a collection C has count(C) = n natural, hence ≥ C, there exists some mapping (C|f:n); as n is the union of the naturals that C does pigeonhole, C pigeonholes n; so this mapping is monic (C:f|n) and, consequently, iso (C|f|n). As n is finite (by the definition of the naturals), the existence of this iso implies that C is finite. It also implies that every natural which subsumes n pigeonholes C (since each such pigeonholes n, hence everything iso to it).

Whenever there exists an iso (C|f|n) between some collection C and a natural n, we can construe it as a mapping (C|f:m) for any natural m of which n is a member (hence m also subsumes n); it is not (C:|m) for any such m (n, in m, is not a right value of f) so C does not pigeonhole any such m; thus n subsumes count(C). However, n is natural, hence finite and f is iso; every mapping (C|g:n) yields (n| reverse(f)&on;g :n), a mapping (n|:n), hence monic (n:|n), so g = (C:f|n)&on;(n: reverse(f)&on;g |n) is (C:|n) and a composite of monics hence monic; thus C pigeonholes n (and, thus, all of its members), so count(C) subsumes n. Thus the existence of an iso (C|f|n) implies that n = count(C). So a collection C is iso to some natural precisely if count(C) is natural.

Thus, for natural n and any collection C

- n ≥ C ⇔ n subsumes count(C) ⇔ n pigeonholes C

while, when count(C) is natural,

- C ≥ n ⇔ count(C) subsumes n ⇔ C pigeonholes n

and (in the latter case) any such C is finite (because iso to a natural). It remains to show that:

- any finite collection has natural count;
- every collection whose count is {naturals} also pigeonholes {naturals} and is infinite;
- if there are no mappings ({naturals}|:C), then C is finite (for this it suffices to show that C<{naturals} implies C≤{naturals}, from results above.

any one of which likely makes the others easier to prove.

Consider a collection C which pigeonholes every natural; hence count(C) is {naturals} and C > every natural, so there is no mapping (C|:n) for any natural n. Let N = {naturals n: C≥n}; since every collection ≥empty, this is not empty. Furthermore, for any n in N and i in n, C≥n implies some mapping (n|:C) and its (i::) restriction is inevitably (i|:C), as n subsumes i, so i is also in N; so N subsumes each of its members. It is thus either {naturals} or a natural. Given n in N, let (n|f:C) be a witness to C≥n; if f is monic, its reverse is (C::n) and there is no (C|:n) so there is some c in C that is not a right value of f, so the union of f with ({n}:n←c:{c}) is a mapping (n&unite;{n}|:C); otherwise, f is not monic so there is some i in n which is both f(a) and f(b) for some distinct a, b in C; restricting f to {c in C: c is not b} and uniting the result with ({n}:n←b:{b}) we again obtain a mapping (n&unite;{n}|:C); either way, C ≥ n&unite;{n}. Thus n in N implies n&unite;{n} in N and, by induction, N = {naturals}. Thus a collection which pigeonholes every natural is also ≥ every natural.

Conversely, if a collection C ≥ every natural then no natural pigeonholes any collection, except possibly C, that subsumes C; in particular, no natural's successor pigeonholes C&unite;{c} for any c not in C so no natural pigeonholes C and no natural ≥ C, so every natural < C and count(C) = {naturals}, so C pigeonholes every natural. So a collection pigeonholes every natural precisely if it is ≥ every natural; in particular, a collection is ≥ every natural precisely if it is > every natural.

If C > {naturals} then it pigeonholes {naturals} fatuously; otherwise, C ≤ {naturals} so there exists some (C|g:{naturals}) – RTP: C pigeonholes {naturals}

Now consider any collection C; if there are no mappings (C|:{naturals}), then C pigeonholes {naturals} fatuously and thus pigeonholes every natural, so has count(C) = {naturals}. Otherwise, there exists some mapping (C| f :{naturals}); I then define an iso ({naturals}: h :{naturals}) as follows. Given iso ({naturals}:h:n) for some natural n in count(C) – e.g., initially, n = 0 –

Given collections A, B, C for which A pigeonholes B and B pigeonholes C, consider a mapping (A|f:C). If it can be factored as a composite of mappings f = (A:e:B)&on;(B:g:C) then, as f is (A|:), so must e be, which makes it a mapping (A|e:B) so we know it's a monic (A:e|B). As this is monic, no member of a is related to more than one member of B, g must be (B|:) in order to supply every member of B to e, so as to obtain every member of A in (|f:). As g is thus a mapping (B|:C), it is monic (B:|C) and f is a composite of monics (A:|B)&on;(B:|C) hence a monic (A:|C). So, if every mapping (A::C) can be factored as a composite of mappings (A::B)&on;(B::C), A shall pigeonhole C and pigeonholing shall be transitive. It remains, then, to determine whether such factoring is necessarily possible; if so, pigeonholing is transitive.

TODO: show {lists ({naturals}: |n)} countable for each natural n, add section in there being countably many ratios yet infinitely many of them between any two of them.

Written by Eddy.