Results 1 to 6 of 6

Math Help - Union of sets

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    Union of sets

    Consider a set S. ( S can be finite or infinite)

    Let I_1,I_2,....I_n,..... be subsets of S , such that
    1. I_i \subseteq I_{i+1}
    2. \bigcup I_i is finite

    Prove that there exits n_0 \in \aleph , such that for any n_1,n_2 \geq n_0, I_{n1}=I_{n2}

    I want to prove this in a rigorous way. Here is my attempt

    1. Claim there exists an n_0, such \bigcup I_i = I_{n_0}. If this claim is true proving above is trivial.
    2. So to prove the claim. Consider any x \in \bigcup I_i. Thus x must belong to some I_n. Let n_1 be minimum such n. Iterate over all the elements of \bigcup I_i (say ' k' elements, as \bigcup I_i is finite). We will have a set A=\{n_1,n_2,....n_k\}. Now claim that n_0=max(A). (This claim is easy to prove)

    I have two questions here:
    1. Is the above proof rigorous enough !
    2. How do I prove that max(A) exists? More generally if A is a finite subset of \aleph, prove that max(A) exits and is unique?

    Please help !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi
    More generally if is a finite subset of , prove that exits and is unique?
    Just apply the "fundamental property" of \mathbb{N} (i.e. the natural order over \mathbb{N} is a well order, i.e. any non-empty subset of \mathbb{N} has a minimum) to the subset \{n\in\mathbb{N}\ ;\ n>_n1,...,n>n_k\}.
    It is non-empty (why?) so it has a minimum; let m be that minimum, what is max(A) ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by clic-clac View Post
    Hi
    Just apply the "fundamental property" of \mathbb{N} (i.e. the natural order over \mathbb{N} is a well order, i.e. any non-empty subset of \mathbb{N} has a minimum) to the subset \{n\in\mathbb{N}\ ;\ n>_n1,...,n>n_k\}.
    It is non-empty (why?) so it has a minimum; let m be that minimum, what is max(A) ?

    Thanks. Sorry I have not followed your argument exactly. Do you mind saying it again plz?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    If you consider \emptyset\neq A=\{n_1,...,n_k\}\subseteq\mathbb{N}, then the subset B of \mathbb{N} of elements greater than all n_i, 1\leq i\leq k is non-empty ( \sum\limits_{i=1}^kn_i +1 belongs to it)
    Therefore it has a minimum, m, and m-1=\max(A).
    Indeed, if m-1\notin A; by definition of m,\ p\geq m\Rightarrow p\notin A, so m-1>n_i,\ 1\leq i\leq n, i.e. m-1\in B, contradiction.
    Hence m-1\in A and forall a\in A, a\leq m-1 by definition of m, i.e. m-1=\max(A).


    There are various ways I guess to show that, we can proceed by induction on k:

    If k=1, nothing to show (n_1=\max(A)). Assume any subset of \mathbb{N} with k elements has a max, consider \{n_0,...,n_k\}, then \{n_1,...,n_k\} has a max, let's say n_j, two cases (because the order is total):
    either n_j<n_0, then n_0=\max(\{n_0,...,n_k\})
    or n_0<n_j, and n_j=\max(\{n_0,...,n_k\})

    Actually the second proof may be better than the first: it only uses the totality of the order, which is a sufficient (and necessary) condition to be able to say that any finite non-empty subset has a maximum.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by clic-clac View Post
    If you consider \emptyset\neq A=\{n_1,...,n_k\}\subseteq\mathbb{N}, then the subset B of \mathbb{N} of elements greater than all n_i, 1\leq i\leq k is non-empty ( \sum\limits_{i=1}^kn_i +1 belongs to it)
    Therefore it has a minimum, m, and m-1=\max(A).
    Indeed, if m-1\notin A; by definition of m,\ p\geq m\Rightarrow p\notin A, so m-1>n_i,\ 1\leq i\leq n, i.e. m-1\in B, contradiction.
    Hence m-1\in A and forall a\in A, a\leq m-1 by definition of m, i.e. m-1=\max(A).


    There are various ways I guess to show that, we can proceed by induction on k:

    If k=1, nothing to show (n_1=\max(A)). Assume any subset of \mathbb{N} with k elements has a max, consider \{n_0,...,n_k\}, then \{n_1,...,n_k\} has a max, let's say n_j, two cases (because the order is total):
    either n_j<n_0, then n_0=\max(\{n_0,...,n_k\})
    or n_0<n_j, and n_j=\max(\{n_0,...,n_k\})

    Actually the second proof may be better than the first: it only uses the totality of the order, which is a sufficient (and necessary) condition to be able to say that any finite non-empty subset has a maximum.
    Thanks very much. I follow it now. I had similar idea but was not sure how to put it. I was trying to repeatedly construct a sub-set by removing the min element (existence of which is guaranteed by well order property) repeatedly till only one element is left and I would then claim that this is the max. But was not able to put it formally. Thanks very much.

    So with this - does my proof to the original problem looks convincing enough?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Well I wouldn't have anything to say against your proof
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Union of sets in R^n
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: January 11th 2012, 04:48 PM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  3. Union of two sets
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: January 29th 2010, 01:23 PM
  4. Union of Connected Sets
    Posted in the Differential Geometry Forum
    Replies: 7
    Last Post: October 17th 2009, 12:28 AM
  5. countable union of sets
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 28th 2008, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum