I Missing(?) rigor in proof involving countable union of countable sets

[Uncanny]

TL;DR Summary

I posted earlier regarding a corollary (regarding the rational numbers) of the theorem in question here. Upon reviewing the chapter and putting pen to paper, however, I have come across a deeper question concerning the proof presented of the theorem that a countable union of countable sets is itself countable. A photo of the theorem statement and proof in question is, again, attached below.

My question concerns the portion of the proof stating, “...we set up a correspondence between the elements of U(A_n), for n in N, and a subset of S by making the element a correspond to (m, n) if A_m is the first set in which a appears, and a is the nth element of A_m.”

In particular, I am wondering whether a more precise, or rigorous/symbolic formulation of the quoted portion of the proof above can be made? In other words, how can a statement of the correspondence be formally mathematically expressed (i.e., explicitly in functional form)?

It seems (to me, at least) this would be a function mapping from U(A_n) into a subset of N x N, since, in turn, the correspondence between (m,n) and N is priorly given as a formula in the proof: (1/2)(m+n-2)(m+n-1) + n.

*Update: I’ve done a bit of research into the matter since initially posting, and it seems the solution may involve the axiom of choice (which I should, regardless, brush up on) as well as the particular correspondences denumerating each A_n. I’ll post any tentative solution I reach, should I arrive at one before any helpful or suggestive responses!

 

[PeroK]

Summary: I posted earlier regarding a corollary (regarding the rational numbers) of the theorem in question here. Upon reviewing the chapter and putting pen to paper, however, I have come across a deeper question concerning the proof presented of the theorem that a countable union of countable sets is itself countable. A photo of the theorem statement and proof in question is, again, attached below.

My question concerns the portion of the proof stating, “...we set up a correspondence between the elements of U(A_n), for n in N, and a subset of S by making the element a correspond to (m, n) if A_m is the first set in which a appears, and a is the nth element of A_m.”

In particular, I am wondering whether a more precise, or rigorous/symbolic formulation of the quoted portion of the proof above can be made? In other words, how can a statement of the correspondence be formally mathematically expressed (i.e., explicitly in functional form)?

It seems (to me, at least) this would be a function mapping from U(A_n) into a subset of N x N, since, in turn, the correspondence between (m,n) and N is priorly given as a formula in the proof: (1/2)(m+n-2)(m+n-1) + n.

I'm not sure I understand your question. There's a difference between "rigour" and producing an explicit formula.

 

[Uncanny]

I'm not sure I understand your question. There's a difference between "rigour" and producing an explicit formula.

I’m looking for an explicit formula. Also, check my update, please, incase it elucidates the matter- I may have edited the original post while or after you replied.

 

[PeroK]

I’m looking for an explicit formula. Also, check my update, please, incase it elucidates the matter- I may have edited the original post while or after you replied.

In my opinion it's a good opportunity to get away from the idea that you need an explicit formula. There are many results in mathematics where you can show that something exists without being able to produce a formulaic description of the object.

I can only see that the axiom of choice might be relevant if you want to justify that the countable union of sets is itself a well-defined set. But, that's going in the "opposite" direction towards the foundations of mathematics.

 

[Uncanny]

My tentative solution is such:

By hypothesis, the A_n are denumerable, or countable, so there exist functions, say f_n(a) : A_n —> N which are 1-1 correspondences between the sets A_n and (subsets of) the natural numbers, N. To show that the union of a denumerable number (which is the case here since the A_n are indexed by n in N, hence enumerating them) of denumerable sets (the A_n, again, denumerable by hypothesis) is denumerable, consider the 1-1 correspondences, g_n, from U(A_n) into N x N given by: g_n(a) = (n, f_n(a)).

I still need to figure out a way to account for the potential “overlap” or pairwise (non-empty) intersections between the A_n so that any element(s) is(are) not doubly counted.

 

[stevendaryl]

I still need to figure out a way to account for the potential “overlap” or pairwise (non-empty) intersections between the A_n so that any element(s) is(are) not doubly counted.

So if you have a surjection $f$ from $N$ into $U(A_n)$, then can't you just delete the repeats to get a bijection? (Assuming that $U(A_n)$ is infinite?)

 

[Uncanny]

I got it! Essentially, the modifications and remainder of the proof I have written for the theorem are as follow:

I worked backwards to arrive at this concept, but in presenting the proof it seems more logically appropriate to begin with it; I first show that:

U_n(A_n) = U_n[A_n\U_k=1,k=n-1(A_k)], k ranging the prescribed natural numbers (namely, 1 through n-1, inclusive).

This result turns out fairy simple to prove after first proving a very helpful lemma. That is, {A_n\U_k=1,k=n-1(A_k)}_n are (pairwise) disjoint. This proof, in turn, amounts to considering the intersections of the A_n\U_k=1,k=n-1(A_k) for two exhaustive (and contradictory) cases: j<m and m<j, where j and m are arbitrary (but fixed) natural numbers such that j is not equal to m.

Now, we are naturally left with a family of functions, {g_n: A_n\U_k=1,k=n-1(A_k) —> N x N; g_n(a) = (n, f_n(a))}_n. If we can show that the union of this family of functions is itself a function, then the proof will (at least, to my level of rigor and formality) be complete!

Fortunately here, {A_n\U_k=1,k=n-1(A_k)}_n constitute an exhaustive sequence of sets on their union; that union is equal to U_n(A_n), which was proven above. Furthermore, the restriction of the mapping g_i+1 to A_i\U_k=1,k=i-1(A_k) is equal to g_i. As such, it follows that the union of the set of functions G = {g_n}_n is, indeed, a (well-defined) function.

Thus, a well-formulated proof for the theorem results, with G(a): U_n{A_n\U_k=1,k=n-1(A_k)} = U_n(A_n) —> N x N given by G(a) = g_n(a). The resulting set of ordered pairs, of course, has already been shown to be in 1-1 correspondence with N. Hence, the theorem is proven.

 

[Uncanny]

Also... I felt I should include the demonstration that the functions {g_n} are each well-defined, but the “proof” seems trivial based on the construction of the {g_n}.

 

[Uncanny]

As it turns out, the second-to-last paragraph in my post (#7) isn’t, in general, true (for consider if we simply partition N into two sets: evens and odds; whichever set you call A_1, it is never the case that A_1 is a subset of A_2).

The conclusion of the paragraph, however, remains true by a simpler argument; namely, that for a set of functions, {f_i}_i, where f_i: A_i —> C for each i in N and {A_i}_i are disjoint, f = U_i(f_i) is a function. This is a fairly simple proof usually included in most chapters on functions in set theory (or related) books. The proof for the case i=2 is ordinarily presented therein, but incase it’s of interest to anyone, I wrote my own proof for the generalized case (i.e. for countable unions of functions), and can post it. I doubt this to be the case though.

 

[Uncanny]

I also just realized that most of the work for proving this theorem can be stated compactly by an operation called “disjoint union.” But surely most of these steps are included in proving the underpinnings of that operation?

 

[PeroK]

I also just realized that most of the work for proving this theorem can be stated compactly by an operation called “disjoint union.” But surely most of these steps are included in proving the underpinnings of that operation?

I don't understand why it needs to be made complicated. You have a countable union of countable sets. All the elements of the union can be counted by a diagonal argument; or, by the argument given in the link you posted.