Is transfinite induction needed to remove all the elements from an uncountable set?

Question

Given any uncountable set S, would I need to use transfinite induction to prove if I remove single elements recursively, I will be left with the empty set?

It seems like this can be thought of as an arbitrary intersection problem, so just a logical consequence. Could I do with something weaker than transfinite induction?

Answer 1

Yes and no. If you remove single elements recursively, you will eventually remove everything, but you need a wellordering to be able to do that in the first place. To remove single elements recursively, you have to do it in some order; it is a transfinite recursive operation. To show that it eventually removes everything, you would probably still have to use transfinite induction in a more or less veiled way, but you don't need any more “choice” to do that.

On the other hand, if you just remove every single element without caring about the order, you don't need anything like that. $\bigcap_{s\in S} S\setminus \{s\}=\emptyset$, period.

Answer 2

You can't remove a countably infinite number of elements one element at a time. Consider the following family of sets: $A_0 = N$ and $A_{i+1} = A_i - \{i\}$. The empty set can't be a member of this family. Assume $A_{z+1} = \{\}$. Then $A_z = \{z\}$ and $z$ is the largest natural number. I don't see how assuming $A_0$ is uncountable would change anything.

Edit in response to comments.

Tomasz is correct this can be proven using arbitrary intersection. Show there is a collection of sets such that every element of S is missing from some set in the collection. The intersection of this collection will be the empty set. What you can not do is "remove single elements recursively".

The intersection of a collection of sets is a single operation. This is why $\cap_{k<\omega} A_k = \{\}$. Recursively taking the intersection of two sets at a time will never give us the empty set.

$(A_0 \cap A_1) = A_1$

$(A_0 \cap A_1) \cap A_2) = (A_1 \cap A_2) = A_2$

...

$\cap_{k \leq n} A_k = A_n$

Induction does not help either. We can easily prove $\forall A_x \exists y(y \in A_x))$ using induction. The basic problem is the empty set is a finite set. We can never get a finite set by removing one element from an infinite set.