Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Somewhat difficult set theory proof

  1. Mar 29, 2016 #1

    mbs

    User Avatar

    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) ).
     
    Last edited: Mar 29, 2016
  2. jcsd
  3. Mar 29, 2016 #2

    mbs

    User Avatar

    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.
     
  4. Mar 29, 2016 #3

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  5. Mar 29, 2016 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  6. Mar 29, 2016 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  7. Mar 29, 2016 #6

    mbs

    User Avatar

    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?
     
    Last edited: Mar 29, 2016
  8. Mar 30, 2016 #7

    mbs

    User Avatar

    Okay. I figured it out.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Somewhat difficult set theory proof
  1. Set Theory Proof Help (Replies: 6)

  2. Set theory proof (Replies: 2)

Loading...