Results 1 to 6 of 6

Thread: Union of sets

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    Union of sets

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

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

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

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

    1. Claim there exists an $\displaystyle n_0$, such $\displaystyle \bigcup I_i$ = $\displaystyle I_{n_0}$. If this claim is true proving above is trivial.
    2. So to prove the claim. Consider any $\displaystyle x \in \bigcup I_i$. Thus $\displaystyle x$ must belong to some $\displaystyle I_n$. Let $\displaystyle n_1$ be minimum such $\displaystyle n$. Iterate over all the elements of $\displaystyle \bigcup I_i$ (say '$\displaystyle k$' elements, as $\displaystyle \bigcup I_i$ is finite). We will have a set $\displaystyle A=\{n_1,n_2,....n_k\}$. Now claim that $\displaystyle 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 $\displaystyle max(A)$ exists? More generally if $\displaystyle A$ is a finite subset of $\displaystyle \aleph$, prove that $\displaystyle 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 $\displaystyle \mathbb{N}$ (i.e. the natural order over $\displaystyle \mathbb{N}$ is a well order, i.e. any non-empty subset of $\displaystyle \mathbb{N}$ has a minimum) to the subset $\displaystyle \{n\in\mathbb{N}\ ;\ n>_n1,...,n>n_k\}.$
    It is non-empty (why?) so it has a minimum; let $\displaystyle m$ be that minimum, what is $\displaystyle max(A)$ ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by clic-clac View Post
    Hi
    Just apply the "fundamental property" of $\displaystyle \mathbb{N}$ (i.e. the natural order over $\displaystyle \mathbb{N}$ is a well order, i.e. any non-empty subset of $\displaystyle \mathbb{N}$ has a minimum) to the subset $\displaystyle \{n\in\mathbb{N}\ ;\ n>_n1,...,n>n_k\}.$
    It is non-empty (why?) so it has a minimum; let $\displaystyle m$ be that minimum, what is $\displaystyle 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 $\displaystyle \emptyset\neq A=\{n_1,...,n_k\}\subseteq\mathbb{N},$ then the subset $\displaystyle B$ of $\displaystyle \mathbb{N}$ of elements greater than all $\displaystyle n_i, 1\leq i\leq k$ is non-empty ($\displaystyle \sum\limits_{i=1}^kn_i +1$ belongs to it)
    Therefore it has a minimum, $\displaystyle m,$ and $\displaystyle m-1=\max(A).$
    Indeed, if $\displaystyle m-1\notin A;$ by definition of $\displaystyle m,\ p\geq m\Rightarrow p\notin A,$ so $\displaystyle m-1>n_i,\ 1\leq i\leq n,$ i.e. $\displaystyle m-1\in B,$ contradiction.
    Hence $\displaystyle m-1\in A$ and forall $\displaystyle a\in A, a\leq m-1$ by definition of $\displaystyle m,$ i.e. $\displaystyle m-1=\max(A).$


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

    If $\displaystyle k=1,$ nothing to show $\displaystyle (n_1=\max(A)).$ Assume any subset of $\displaystyle \mathbb{N}$ with $\displaystyle k$ elements has a max, consider $\displaystyle \{n_0,...,n_k\},$ then $\displaystyle \{n_1,...,n_k\}$ has a max, let's say $\displaystyle n_j,$ two cases (because the order is total):
    either $\displaystyle n_j<n_0,$ then $\displaystyle n_0=\max(\{n_0,...,n_k\})$
    or $\displaystyle n_0<n_j,$ and $\displaystyle 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
    678
    Thanks
    1
    Quote Originally Posted by clic-clac View Post
    If you consider $\displaystyle \emptyset\neq A=\{n_1,...,n_k\}\subseteq\mathbb{N},$ then the subset $\displaystyle B$ of $\displaystyle \mathbb{N}$ of elements greater than all $\displaystyle n_i, 1\leq i\leq k$ is non-empty ($\displaystyle \sum\limits_{i=1}^kn_i +1$ belongs to it)
    Therefore it has a minimum, $\displaystyle m,$ and $\displaystyle m-1=\max(A).$
    Indeed, if $\displaystyle m-1\notin A;$ by definition of $\displaystyle m,\ p\geq m\Rightarrow p\notin A,$ so $\displaystyle m-1>n_i,\ 1\leq i\leq n,$ i.e. $\displaystyle m-1\in B,$ contradiction.
    Hence $\displaystyle m-1\in A$ and forall $\displaystyle a\in A, a\leq m-1$ by definition of $\displaystyle m,$ i.e. $\displaystyle m-1=\max(A).$


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

    If $\displaystyle k=1,$ nothing to show $\displaystyle (n_1=\max(A)).$ Assume any subset of $\displaystyle \mathbb{N}$ with $\displaystyle k$ elements has a max, consider $\displaystyle \{n_0,...,n_k\},$ then $\displaystyle \{n_1,...,n_k\}$ has a max, let's say $\displaystyle n_j,$ two cases (because the order is total):
    either $\displaystyle n_j<n_0,$ then $\displaystyle n_0=\max(\{n_0,...,n_k\})$
    or $\displaystyle n_0<n_j,$ and $\displaystyle 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: Jan 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: Oct 8th 2010, 01:59 PM
  3. Union of two sets
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Jan 29th 2010, 01:23 PM
  4. Union of Connected Sets
    Posted in the Differential Geometry Forum
    Replies: 7
    Last Post: Oct 17th 2009, 12:28 AM
  5. countable union of sets
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Sep 28th 2008, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum