Is There a Bijection Between Subsets of Countable Sets?

[Rasalhague]

In http://www.proofwiki.org/wiki/Subset_of_Countable_Set that subsets of a countable set are countable, by enumerating the elements of the subset with the labels n_i, hasn't the author implicitly assumed the conclusion, namely that the subset is countable: that its elements can be labeled by the elements of $\mathbb{N}$? However small one writes that i, tucked away in however many embedded levels of subscripts, it still stands for the numbers 1,2,3,..., doesn't it?

 

[SW VandeCarr]

In http://www.proofwiki.org/wiki/Subset_of_Countable_Set that subsets of a countable set are countable, by enumerating the elements of the subset with the labels n_i, hasn't the author implicitly assumed the conclusion, namely that the subset is countable: that its elements can be labeled by the elements of $\mathbb{N}$? However small one writes that i, tucked away in however many embedded levels of subscripts, it still stands for the numbers 1,2,3,..., doesn't it?

I believe it's sufficient to show there is a bijection between the elements of an infinite countable set N and any infinite countable subset of N.

 

[mathwonk]

what is your definition of countable? a surjection exists from N to the set? If so, it is pretty trivial to construct one to any subset of N, isn't it? Just send the omitted integers to the first element of the set, and the included integers to themselves.

 

[Rasalhague]

My definition is: a set is countable if (a) there's a bijection from it to the natural numbers (in which case it's countably infinite), or (b) to the set {1,2,...,n} consisting of the first n natural numbers (in which case, it's finite,), or (c) it's empty.

Of the three cases, (c) is trivial.

One idea for (b): suppose |S| = n. Then there's a bijection f from S to {1,2,...n}. There is a least element, q, in f(A) the image of A under f. Define a function g such that g(q) = 1. There is a least element, w, to f(A)\{q}; let g(w) = 2. Define g thus recursively till all of its values are defined. (These least elements exist by the well-ordering principle.) By construction, g is 1-1. Let the domain of g be its image; then g is also onto. Intuitively it's obvious that image of g is {1,2,...m} for some m less than or equal to n. But how to show this without assuming the conclusion?

For (a), proceed as for (b), again using the well-ordering principle. ... ? (Here the presence of infinity makes a formal proof more important, as intuition is a less sure guide.)

(I see http://planetmath.org/encyclopedia/SubsetsOfCountableSets.html uses an easier definition which bypasses the problem. Is this the definition you had in mine, SW VandeCarr?)

 

[mathwonk]

this stuff doesn't interest me much anymore, but basically one shows that every infinite set admits an injection from the natural numbers. Then for any infinite subset S of a countable set T, it follows that one has both an injection from S to T and an injection from T to S.
"Then one wants to show that if two sets admit injections in both directions, they also admit a bijection. This is a clever standard proof using the idea of "ancestors".

Start from, let's see, I need to regenerate this proof myself. Ok I looked it up in Hungerford.

Consider an element in S and ask whether it came from an element of B via the injection B-->A. If so it has an ancestor in B. Then ask the same about that ancestor, i.e. whether it has an ancestor in S. Continue. Ultimately you divide S into three disjoint subsets, those with a first ancestor in S, those with a first ancestor in T, and those whose ancestry goes back forever.

Do the same for T. Then define a bijection between S and T as follows: Check that the injection S-->T is a bijection from elements of S with a first ancestor in S, to elements of B with a first ancestor in S.
Also S-->T defines a bijection between elements of S with infinite ancestry, and elementsn of T with infinite ancestry.

Then T-->S defines a bijection from elements of T with first ancestor in T, with elements of S with first ancestor in T.

Putting these together gives a bijection between S and T.