# Thread: Analysis proof help needed

1. ## Analysis proof help needed

I've been driving myself crazy with the following proof:

Let E be an infinite set, and F be a finite subset of E. Let G = E\F (That is, E minus F). Prove that G is equivalent to E.

If I know that if E is countable, I can prove that G is countable, but what if E is uncountable?? Please help!

2. Originally Posted by stuckinanalysis
I've been driving myself crazy with the following proof:

Let E be an infinite set, and F be a finite subset of E. Let G = E\F (That is, E minus F). Prove that G is equivalent to E.

If I know that if E is countable, I can prove that G is countable, but what if E is uncountable?? Please help!
suppose E is uncountable but G is countable. we have $E=G \cup F.$ clearly G can't be finite. so to get a contradiction, you need to show that the union of an infinite countable set with a finite set is

infinite countable. to show this let $G=\{x_n: \ n \in \mathbb{N} \}, \ F=\{y_1, \cdots, y_m\}.$ define the map $f: G \cup F \longrightarrow \mathbb{N},$ by: $f(y_j)=j, \ f(x_n)=n+m.$ obviously $f$ is bijective and hence $G \cup F$ is countable.

3. You proved that G is uncountable, but does this prove G is equivalent to E? The set of real numbers and the power set of the real numbers are both uncountable, but they are not equivalent.

4. Originally Posted by stuckinanalysis
You proved that G is uncountable, but does this prove G is equivalent to E? The set of real numbers and the power set of the real numbers are both uncountable, but they are not equivalent.
you're right! i didn't see "equivalent"! ok, the problem is now much more interesting! so we have an infinite set $G$ and a finite set $F.$ we want to show that $G$ and $G \cup F$ are equivalent.

since we're dealing with cardinality here, we may assume that $G \cap F = \emptyset.$ now apply Zorn's lemma to find a set $G^*=\bigcup_{i \in I} G_i,$ with $G_i \subseteq G,$ which is maximal with respect to these properties:

1) every $G_i$ is countable,

2) $G_i \cap G_j = \emptyset$ for all $i, j \in I$ with $i \neq j.$

then maximality of $G^*$ implies that $G-G^*=H$ is finite. choose an $i_0 \in I$ and replace $G_{i_0}$ with $G_{i_0} \cup H.$ then: $G = \bigcup_{i \in I} G_i,$ and $G \cup F=(G_{i_0} \cup F) \cup \bigcup_{i \neq i_0}G_i.$ also it's clear that $G_i$ will still satisfy

the properties 1) and 2). thus, since $G_{i_0} \cup F$ and all $G_i$ are countable, they're equaivalent to $\mathbb{N},$ hence both $G$ and $G \cup F$ are equivalent to $I \times \mathbb{N}, \ \color{red}(*)$ and hence they must be equivalent. Q.E.D.

$\color{red}(*)$ the reason is that if $f_i: G_i \longrightarrow \mathbb{N}, \ i \in I,$ is a bijection, then you can define $f: \bigcup_{i \in I}G_i \longrightarrow I \times \mathbb{N}$ by: $f(g_i)=(i,f_i(g_i)).$ since $G_i$ are disjoint, $f$ is well-defined. bijectivity of $f$ is a trivial result

of bijectivity of each $f_i.$

5. Originally Posted by NonCommAlg
... now apply Zorn's lemma
But is that cheating?

There is a known result in ZFC which says if $X$ is an infinite set and $Y$ a subset with $|Y| < |X|$ then $|X - Y| = |X|$. This can be easily proven using axiom of choice and cardinality. However, it still relies on axiom of choice. When I saw this problem I wondered whether it is possible to solve it without any choice.

And if you are using choice then why use Zorn's lemma, simply put a well-ordering on $G$ and start mapping the least elements to the least elements. I think that might work and be a lot simpler.

6. Thanks. That gives me a lot to think about.

Here is a follow up/ similar question. Can it be done the same way?

Let X be an uncountable set, and let Y be a countable subset of X. How can I prove that X is equivalent to X U Y?

7. Originally Posted by stuckinanalysis
Let E be an infinite set, and F be a finite subset of E. Let G = E\F (That is, E minus F). Prove that G is equivalent to E.
I don't think you need the axiom of choice for this. Take a sequence $(x_n)$ of distinct points in E in which the elements of F constitute the first N elements of the sequence. Then define a bijection f from E to E\F by taking $f(x_n)=f(x_{N+n})$, and taking f to be the identity on $E\setminus\{x_n:n\in\mathbb{N}\}$.

8. Originally Posted by stuckinanalysis
Here is a follow up/ similar question. Can it be done the same way?

Let X be an uncountable set, and let Y be a countable subset of X. How can I prove that X is equivalent to X \ Y?
A similar method should work. Let Z be a countable set in X \ Y. Then Z and Z∪Y have the same cardinality, so let f be a bijection from Z to Z∪Y, and extend f to X \ Y by taking it to be the identity on X \ (Z∪Y).

9. Originally Posted by Opalg
Take a sequence $(x_n)$ of distinct points in E in which the elements of F constitute the first N elements of the sequence.
How?
We not supposed to be chosing.

I only see one way of doing this. Let $g$ be a choice function on $\mathcal{P}(E)$ i.e. $g(S) \in S$ for all $S\not = \emptyset$. Since $F$ is finite there is a bijection $f:n\to F$. Define a sequence, by recursion, $x: \mathbb{N} \to E$ by $x_k = f(k)$ for $k and $x_k = g( E - \{ x_i | i < n\})$. Then follow through with your argument.

10. Originally Posted by ThePerfectHacker
Originally Posted by Opalg
Take a sequence $(x_n)$ of distinct points in E in which the elements of F constitute the first N elements of the sequence.
How?
We not supposed to be choosing.
Just because you are making a choice, it doesn't necessarily follow that you require the axiom of choice. You only need to invoke that axiom if you want to make a simultaneous choice of an element from each of an infinite collection of sets. That is not the case here. The elements $x_n$ are chosen one at a time in an inductive fashion. You don't need the axiom of choice for that.

11. Originally Posted by Opalg
Just because you are making a choice, it doesn't necessarily follow that you require the axiom of choice. You only need to invoke that axiom if you want to make a simultaneous choice of an element from each of an infinite collection of sets. That is not the case here. The elements $x_n$ are chosen one at a time in an inductive fashion. You don't need the axiom of choice for that.
Are you sure? What you are doing is this:
$x_{n+1} = \text{ some element of }(E - \{ x_i | i < n\})$

The thing is that this function is not really defined.
That is why we need choice to define such a function.
---
If that (what I just did above) was really okay than we can apply the same argument to transfinite sequences:
As a consequence of which the axiom of choice would be a provable from the other axioms.

12. Originally Posted by ThePerfectHacker
Are you sure? What you are doing is this:
$x_{n+1} = \text{ some element of }(E - \{ x_i | i < n\})$

The thing is that this function is not really defined.
That is why we need choice to define such a function.
No, I'm just using the definition of "nonempty". If a set is nonempty then there exists an element in that set. I'm calling that element $x_{n+1}$.

Almost every proof in analysis starts by saying "Let ε>0." That involves choosing an element from the set of positive real numbers. But it is not true that every such proof requires the axiom of choice.

Originally Posted by ThePerfectHacker
If that (what I just did above) was really okay than we can apply the same argument to transfinite sequences:
As a consequence of which the axiom of choice would be a provable from the other axioms.
No, you could never get beyond a countable set that way, because you are only constructing one element at at time.