Somewhat difficult set theory proof

[mbs]

I am trying to prove that two definitions of a finite set are equivalent.

1.) A set ##A## is finite if and only if it is equipollent to a natural number ##n##. ( natural number as the set containing all the previous natural numbers including ##0## )

2.) A set ##A## is finite if and only if every collection of subsets has a minimal element with respect to the ##\subset## relation. ( this means there is at least one element of every collection that contains no others as subsets ).

I have figured out how to prove (1) ##\rightarrow## (2) but am struggling with (2) ##\rightarrow## (1).

Please don't post a full proof. Just a hint or basic sketch would be most appreciated.

Also, I'd like to prove it without using the axiom of choice. Induction on the natural numbers is okay ( that's how I proved (1) ##\rightarrow## (2) ).

 

[mbs]

Okay. I have the basic idea for the proof now. What I'm having trouble with is rigorously justifying it.

I am considering sequences of subsets of ##A##. The sequences are defined inductively such that ##a_0## is ##A## itself, and if ##a_n## is a non-empty set in the sequence then ##a_{n+1}## is ##a_n## with exactly one element removed. If ##a_n## is empty then ##a_{n+1}## is also empty. A sequence is said to terminate if it ends in a string of empty sets. With such sequences defined, I only have to demonstrate that one such sequence exists. If it does, then it must terminate because if it didn't it would violate (2). Then I can create a 1-1 function from some ##n \in \omega## to ##A## by constructing a new finite sequence that picks each of the single elements removed up to the first empty set encountered.

The problem I'm having is formally proving the existence of at least one sequence of the form described in the above paragraph. In analysis there are a lot of proofs that construct a sequence "inductively" by arbitrarily "choosing" something at each step. While it's intuitively obvious that one can "choose" one element to remove from each non-empty set ##a_n## to obtain ##a_{n+1}##, and thus "construct" a sequence, I don't understand how this is formally justified even with the axiom of choice. It obviously can be justified somehow as it's used all the time in analysis. I just don't understand how, or if it requires the axiom of choice. Also, if it does require the axiom of choice, there must be some other way of demonstrating that at least one sequence of the type described above exists.

I hope everything I have written is clear.

 

[mathman]

For an infinite set there is an infinite collection with no minimal element. Your construction (start with A and remove one element at a time) seems to point in that direction.

 

[micromass]

Okay. I have the basic idea for the proof now. What I'm having trouble with is rigorously justifying it.

I am considering sequences of subsets of ##A##. The sequences are defined inductively such that ##a_0## is ##A## itself, and if ##a_n## is a non-empty set in the sequence then ##a_{n+1}## is ##a_n## with exactly one element removed. If ##a_n## is empty then ##a_{n+1}## is also empty. A sequence is said to terminate if it ends in a string of empty sets. With such sequences defined, I only have to demonstrate that one such sequence exists. If it does, then it must terminate because if it didn't it would violate (2). Then I can create a 1-1 function from some ##n \in \omega## to ##A## by constructing a new finite sequence that picks each of the single elements removed up to the first empty set encountered.

The problem I'm having is formally proving the existence of at least one sequence of the form described in the above paragraph. In analysis there are a lot of proofs that construct a sequence "inductively" by arbitrarily "choosing" something at each step. While it's intuitively obvious that one can "choose" one element to remove from each non-empty set ##a_n## to obtain ##a_{n+1}##, and thus "construct" a sequence, I don't understand how this is formally justified even with the axiom of choice. It obviously can be justified somehow as it's used all the time in analysis. I just don't understand how, or if it requires the axiom of choice. Also, if it does require the axiom of choice, there must be some other way of demonstrating that at least one sequence of the type described above exists.

I hope everything I have written is clear.

You are correct, your construction requires the axiom of choice. Most constructions of sequences in analysis require the axiom of choice. What is the clue however, in analysis we need infinite sequences. Here, we don't. You have described it as an infinite sequence, but it's not an infinite sequence since you've proven it to terminate.

The thing is that the axiom of choice can actually be proven from the other ZF axioms if we only make finite choices. That is, if you know beforehand that your sequence is finite. Try to prove a version of the axiom of choice for finite sequences.

The axiom of choice is needed to make a sequence ##\mathbb{N}\rightarrow A##, but not for ##n\rightarrow A##. So you can prove without any problem that there are sequences (obeying your condiction) ##n\rightarrow A## for each ##n\in \mathbb{N}##. These sequences might not be compatible, so be sure not to use those (meaning that the second (eg) element of ##4\rightarrow A## is not necessarily that of ##5\rightarrow A). What you need to show that at least one of these sequences terminate. So you need to find a global bound of termination of the sequence.

 

[micromass]

Here is perhaps a more substantial hint:

DEFINITION: A set ##B\subseteq A## is ##n##-connected to ##A## if ##B\setminus A## has cardinality ##n##.
DEFINITION: Let ##\mathcal{G}_n## be the set of all ##n##-connected subsets of ##A##. Let ##\mathcal{G}= \bigcup_n \mathcal{G}_n##.

Then ##\mathcal{G}## has a minimal element, etc.

 

[mbs]

You are correct, your construction requires the axiom of choice. Most constructions of sequences in analysis require the axiom of choice. What is the clue however, in analysis we need infinite sequences. Here, we don't. You have described it as an infinite sequence, but it's not an infinite sequence since you've proven it to terminate.

The thing is that the axiom of choice can actually be proven from the other ZF axioms if we only make finite choices. That is, if you know beforehand that your sequence is finite. Try to prove a version of the axiom of choice for finite sequences.

The axiom of choice is needed to make a sequence ##\mathbb{N}\rightarrow A##, but not for ##n\rightarrow A##. So you can prove without any problem that there are sequences (obeying your condiction) ##n\rightarrow A## for each ##n\in \mathbb{N}##. These sequences might not be compatible, so be sure not to use those (meaning that the second (eg) element of ##4\rightarrow A## is not necessarily that of ##5\rightarrow A). What you need to show that at least one of these sequences terminate. So you need to find a global bound of termination of the sequence.

Okay. One of my ideas was to construct finite sequences. Then the problem is showing that a finite sequence terminating in an empty set exists. If not, then a sequence of length ##n## must exist for every ##n \in \mathbb{N}##. I need to show that this is incompatible with (2) somehow. I need to think. The existence of finite sequences of arbitrary length doesn't guarantee the existence of an infinite sequence. How do I violate (2) without an infinite sequence?

 

[mbs]

Okay. I figured it out.