Analysis proof help needed

**stuckinanalysis** · October 12th 2008, 11:00 AM

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!

**NonCommAlg** · October 12th 2008, 12:22 PM

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.

**stuckinanalysis** · October 12th 2008, 12:50 PM

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.

**NonCommAlg** · October 12th 2008, 03:29 PM

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.$

**ThePerfectHacker** · October 12th 2008, 03:49 PM

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.

**stuckinanalysis** · October 12th 2008, 07:42 PM

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?

**Opalg** · October 13th 2008, 01:13 AM

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}\}$ .

**Opalg** · October 13th 2008, 02:49 AM

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).

**ThePerfectHacker** · October 13th 2008, 06:34 AM

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<n$ and $x_k = g( E - \{ x_i | i < n\})$ . Then follow through with your argument.

**Opalg** · October 13th 2008, 09:22 AM

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.

**ThePerfectHacker** · October 13th 2008, 10:20 AM

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.

**Opalg** · October 13th 2008, 10:59 AM

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.

Thread: Analysis proof help needed

LinkBack

Thread Tools

Display

Analysis proof help needed

Similar Math Help Forum Discussions

Complex Analysis- help needed with proof

Equation needed for Analysis...

Real Analysis help needed

Courses needed for biometric analysis

Real Analysis Proof Help Needed

Search Tags