# Union of sets

• Nov 30th 2009, 12:25 AM
aman_cc
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?

• Nov 30th 2009, 01:42 AM
clic-clac
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)$ ?
• Nov 30th 2009, 06:04 AM
aman_cc
Quote:

Originally Posted by clic-clac
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?
• Nov 30th 2009, 06:39 AM
clic-clac
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.
• Nov 30th 2009, 06:47 AM
aman_cc
Quote:

Originally Posted by clic-clac
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?
• Nov 30th 2009, 07:39 AM
clic-clac
Well I wouldn't have anything to say against your proof :)