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
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
while, when count(C) is natural,
and (in the latter case) any such C is finite (because iso to a natural). It remains to show that:
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.