Results 1 to 12 of 12

Math Help - Analysis proof help needed

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    3

    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!
    Last edited by stuckinanalysis; October 12th 2008 at 11:53 AM. Reason: left out a word
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by stuckinanalysis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by stuckinanalysis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by NonCommAlg View Post
    ... 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2008
    Posts
    3
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by stuckinanalysis View Post
    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}\}.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by stuckinanalysis View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Opalg View Post
    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.
    Last edited by ThePerfectHacker; October 13th 2008 at 07:06 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ThePerfectHacker View Post
    Quote Originally Posted by Opalg View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Opalg View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ThePerfectHacker View Post
    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.

    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complex Analysis- help needed with proof
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 24th 2011, 08:47 AM
  2. Equation needed for Analysis...
    Posted in the Business Math Forum
    Replies: 2
    Last Post: February 23rd 2010, 05:14 AM
  3. Real Analysis help needed
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 13th 2009, 04:37 PM
  4. Courses needed for biometric analysis
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 14th 2008, 08:05 AM
  5. Real Analysis Proof Help Needed
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 28th 2008, 01:45 PM

Search Tags


/mathhelpforum @mathhelpforum