Notices
Page 1 of 3 123 LastLast
Results 1 to 100 of 248

Thread: Real analysis problems

  1. #1 Real analysis problems 
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I'm working through a book of real and complex analysis and could use some help with the problems. This is on my own, not homework.

    DrRocket...we were talking about this a while ago...I ended up going with Shilov's book because of cost, so you know...

    Prove that

    for all real ,.

    I have not been exposed to this type of problem/proof before, so it probably won't be easy at first, but hopefully I'll get used to it. Any help is most appreciated.

    It would help me not to see the proof done but to be given general steps on how to go about it, if that's possible.


    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  2.  
     

  3. #2 Re: Real analysis problems 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    I'm working through a book of real and complex analysis and could use some help with the problems. This is on my own, not homework.

    DrRocket...we were talking about this a while ago...I ended up going with Shilov's book because of cost, so you know...

    Prove that

    for all real ,.

    I have not been exposed to this type of problem/proof before, so it probably won't be easy at first, but hopefully I'll get used to it. Any help is most appreciated.

    It would help me not to see the proof done but to be given general steps on how to go about it, if that's possible.
    What you are trying to show is that which proves that the norm is a continuous function. The proof is short, but is a bit of a trick. Take a look at and apply the triangle inequality.


    Reply With Quote  
     

  4. #3  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Where's the norm and continuous function come in...? Those are all just absolute value bars... I might need more explaination...
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  5. #4  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Where's the norm and continuous function come in...? Those are all just absolute value bars... I might need more explaination...
    One upright bar is an absolute value, two upright bars represent the norm. If the bars are around a vector, x or y, there are two of them and it is a norm. Be careful, one expression is the absolute value of a difference of norms. I tried to put in spaces but Tex wouldn't let me.

    I had assumed that you were working in normed spaces, like Banach spaces. Exactly the same proof applies there. If norms are unfamiliar, just replace them with absolute values and replace the vectors with complex numbers. Nothing changes.
    Reply With Quote  
     

  6. #5  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I am nowhere near Banach spaces and these are real numbers, not vectors. In in the second problem in the very first chapter of the book where it establishes the structure of the real numbers.

    There aren't any double bars...



    Maybe I'm wrong, but I just want to make sure we're on the same page.

    And I feel odd questioning you because I know you know what you're talking about...I just don't see how what you're saying connects to what I'm saying so naturally I have to question that. I suppose this is really part of the learning process, clearing up confusion, would you agree?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  7. #6  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    I am nowhere near Banach spaces and these are real numbers, not vectors. In in the second problem in the very first chapter of the book where it establishes the structure of the real numbers.

    There aren't any double bars...



    Maybe I'm wrong, but I just want to make sure we're on the same page.
    There were after I rewrote the inequality. But it doesn't really make any difference. You are not wrong. You can do it as you wrote it for the complex numbers or as I wrote it for a normed space. The proof is the same (the complex numbers with absolute value are a normed space over either the real or complex nuimbers). The only advantage to the formulation with norms is that it is more general and would be useful to you later if you study Banach spaces.

    Sorry if I confused you. When you mentioned Shilov I immediately thought of some of his stuff on functional analysis, and that affected my perspective. I don't own his book on real and complex analysis.
    Reply With Quote  
     

  8. #7  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Ah, ok. I'm trying to apply the triangle inequality like you said...key word being 'trying.' Do we have

    ...? I'm stuck. Very stuck. Please excuse any stupid things I say until I start to get this a little better.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  9. #8  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Ah, ok. I'm trying to apply the triangle inequality like you said...key word being 'trying.' Do we have

    ...? I'm stuck. Very stuck. Please excuse any stupid things I say until I start to get this a little better.

    Try to simplify the expression on the left.
    Reply With Quote  
     

  10. #9  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    oh, duh... So we have...

    ...

    From there I'm tempted to treat the like a and plug that back into the original, , because I think that simplifies down to ... Don't know if I'm allowed to do that though, or if it even gets me anywhere.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  11. #10  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    oh, duh... So we have...

    ...

    From there I'm tempted to treat the like a and plug that back into the original, , because I think that simplifies down to ... Don't know if I'm allowed to do that though, or if it even gets me anywhere.
    That gives you half of it. But not , rather

    Now do it again but switch the roles of x and y.
    Reply With Quote  
     

  12. #11  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    What happens to the sign though? If you're just subtracting shouldn't it be

    ?

    From there...






    How am I doing?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  13. #12  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Quote Originally Posted by Chemboy
    Ah, ok. I'm trying to apply the triangle inequality like you said...key word being 'trying.' Do we have

    ...? I'm stuck. Very stuck. Please excuse any stupid things I say until I start to get this a little better.
    You got a sign wrong. The triangle inequality should be applied like this





    Then you interchange and to get and complete the proof.
    Reply With Quote  
     

  14. #13  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, so...











    Does that do it?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  15. #14  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    ok, so...











    Does that do it?
    I don't quite follow this, but take a look at Jane's post. She has completed the proof.
    Reply With Quote  
     

  16. #15  
    Forum Sophomore Stranger's Avatar
    Join Date
    Sep 2005
    Posts
    148
    If you are just a little bit familiar with complex numbers, you may try this exercise:
    If a,b,c are complex numbers, prove that



    The modulus of a complex number is defined as |a|=sqrt(aa*) where a* is the complex conjugate of a. You may want to prove this using the complex representation: say a=r1exp(i.theta1).

    Here you generalize the triangle inequality to complex numbers. But what's more interesting (and is why I posted that) is to check when the 2 equalities hold. I chose the complex field because, well, when you know the answer you'll see that it's not terribly interesting on real numbers.

    The thing is that you can (in a sense) generalize the conditions on equality on any Hilbert space (but you'll need a totally different proof). What's very useful here is that, when equality holds "too often" in your space, then it cannot be a Hilbert space, only a Banach one. This serves as a method to distinguish a Hilbert space from a Banach one (beside the more popular paralellogram identity).
    Watch what thy eyes can't see... and live it.

    (T.B)
    Reply With Quote  
     

  17. #16  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, back to these...

    The geometric mean of the positive real numbers is defined by



    and the arithmetic mean by

    .

    Prove that unless , in which case .

    Help please? I'd really like hints so I can see things for myself, and not just have things given to me.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  18. #17  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Anyone...? I haven't gotten far with it. The only thought I had was that since such that . That may very well be completely pointless, that's just what I came up with while thinking about it. Please help me...I really really want to become good at this.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  19. #18  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I'm sure I've done this problem before, back when I took real analysis (the course with the single worst abbreviation in the whole catalog), but I can't really remember how to do it anymore. I want to say that you need to either use induction on n, or show how n=2 generalizes (which might be the same thing).
    Reply With Quote  
     

  20. #19  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I can take a guess at that abbreviation...haha. I have the week off and lots of free time so I'll spend some time with it and try what you suggested on it. Thanks!
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  21. #20  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Anyone...? I haven't gotten far with it. The only thought I had was that since such that . That may very well be completely pointless, that's just what I came up with while thinking about it. Please help me...I really really want to become good at this.
    You said you are just looking for hints.

    I would have to think a bit to construct the complete proof, but as I recall there are several ways to skin that cat. I think the most enlightening involves some detailed work with the theory of convex functions, and then application to the logarithm. I don't think there is any short and simple proof. It takes a little work.

    But if you are going to "get good at this" the only way is to do it. The classes that I liked the best were taught using the Moore method -- the students were required to construct all of the proofs with no references and no consultations with anyone. You just buckled down and did your own proofs.
    Reply With Quote  
     

  22. #21  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    if you want, I can prove it for consecutive positive integers, and you can examine that and study and think about how to apply it to all positive real numbers. All I know how to do for sure is consecutive numbers, mostly
    Reply With Quote  
     

  23. #22  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    if you want, I can prove it for consecutive positive integers, and you can examine that and study and think about how to apply it to all positive real numbers. All I know how to do for sure is consecutive numbers, mostly
    Reply With Quote  
     

  24. #23  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Don't worry about it, Arcane, unless you really want to. I've started working on it and I think I'll be ok without that. Thanks for the offer though.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  25. #24  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, first I'm trying to prove the case where . I did it by induction on , as suggested by MagiMaster. Let me know if this works... (and please cut me some slack if I did anything stupid, I'm new at this. the phrase is "constructive criticism.")

    For the case :
    , so for , .

    : Since , we have and , so for .

    so we have

    and so we have so .
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  26. #25  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I think for that case, you don't need induction. It looks like you've shown it directly anyway. I was suggesting induction for the other case.
    Reply With Quote  
     

  27. #26  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I know you were suggesting it for the other case but I figured I could use it here. How did I show it directly?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  28. #27  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, I can't see where you used the inductive hypothesis, so you've not really using induction. Instead, you just show that it's true for any n. In induction, you'd say, if it's true for n, then it must be true for n+1.
    Reply With Quote  
     

  29. #28  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    I thought you were trying to prove that g<a for all cases except when all of {x} is the same

    Edit: this completely peeked my interest, I'm trying to do the proof right now as we type. I tend to err on the side of derivation for figuring this kind of thing out. I don't really know why, I just kind of like it.
    Reply With Quote  
     

  30. #29  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Quote Originally Posted by Chemboy
    ok, first I'm trying to prove the case where . I did it by induction on , as suggested by MagiMaster. Let me know if this works... (and please cut me some slack if I did anything stupid, I'm new at this. the phrase is "constructive criticism.")

    For the case :
    , so for , .

    : Since , we have and , so for .

    so we have

    and so we have so .
    Couple of things...

    1. How come a=b? Where did that come from?

    2. As Arcane pointed out, this seems to be the beginnings of a proof regarding the positive integers. How does this extend to the real numbers?
    Reply With Quote  
     

  31. #30  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    it doesn't work for all real numbers, only all positive numbers. and he took the special case and proved it for all n, now what needs to be done is to figure out how to expand it to a changing factor of {x}
    Reply With Quote  
     

  32. #31  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, since apparently I'm too dumb to do it myself, could someone show the proof by induction? I'd like to see it, if anyone is willing.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  33. #32  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    can you prove it another way? Or are you dead-set to use induction? There are, thankfully, many other ways to prove it than induction and, if I may say so, induction seems as if it would be hard with the large number of variables entailed in the equations. But, if you don't mind, I'd like to take a stab at it and see if I can prove it through the use of gradients and observations on the functions (plus, it would give me one heck of a practice run in using the TeX language.).

    asking out of respect for you to do the proof without help or anyone else doing it for you. Plus, I'm not even sure if I'm right on my proof or not
    Reply With Quote  
     

  34. #33  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I just wanted to prove it, not necessarily by induction. But now that I've attempted it that way (and failed) I'd like to see it. Try what you want though, but maybe start a new thread about this proof so I can move on with more analysis stuff in this one?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  35. #34  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I might can take a shot at it, but I don't have time at the moment, unless someone else decides to try before then.
    Reply With Quote  
     

  36. #35  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    I'm splitting this equation off into another thread so that the real analysis problems of chemboy's can go untainted by a single, overdone proof. :wink:


    oh, and Here is the proof by induction, and a few other methods of proving the inequality, if you are interested.
    Reply With Quote  
     

  37. #36  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, not how I was planning on attempting it, but that works, and I'm not sure whether or not my idea would.
    Reply With Quote  
     

  38. #37  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, back to this stuff...

    Book's question: "Suppose we add the elements of a finite or countable set to an infinite set . Prove that the resulting set is equivalent to the original set ."

    My question: The problem does not state whether is countably or uncountably infinite. Does this make a difference?

    Also, is a "finite or countable set." Does it matter which I treat it as? Would I have to prove it for both cases?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  39. #38  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    I think it means it's a finite set or an infinite set that has a summation limit. Like an infinite geometric series that converges on, say, 8. Where the infinite set would converge on . At least, that's what I think it means.
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  40. #39  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    That has nothing to do with it. There is no relation to series here at all. They're just plain old sets.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  41. #40  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    in that case I think it's just defining 'finite' as 'countable' meaning you can count all of the members of the set, maybe? I have no idea how to approach this one, but I would assume it just means that theres a set, finite amount of members in set and an infinite amount of members in set
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  42. #41  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Quick lesson for you. Finite equals countable. Countable does not necessarily equal finite. Countable can be infinite, and infinite can be countable. Infinite can also be uncountable.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  43. #42  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    could you give me an example of a countable infinite set?
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  44. #43  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,612
    Easy! the natural numbers, the rationals.

    Chemboy: I don't know the context you are operating in, I assume it is set-theoretic? As to your questions, looking your author's terminology, he seems to use "countable" to mean "countably infinite", so you may assume that by is infinite he means uncountable.

    It should make no difference to your argument whether is finite or countably infinite.
    Reply With Quote  
     

  45. #44  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    yes, this is in a set-theoretic context. I'll re-read that section and try to pick out specifically what words he uses to mean what. Thank you.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  46. #45  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,612
    OK, in that case I have a doozy of a proof sitting on my hard drive. But give it a try first.
    Reply With Quote  
     

  47. #46  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,612
    Stuck, Chemboy?
    Reply With Quote  
     

  48. #47  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Well, the only thing that I can figure is that the new set will be infinite and have the same cardinality or order or whatever word is appropriate here as the original infinite set. So, if it's uncountably infinite it's equivalent to the original set (equivalence meaning a one-to-one correspondence can be established between the two sets) by virtue of the fact that the interval [0,1] is equivalent to any subset of the real line... Beats me as to how to come up with a specific one-to-one correspondence if that's what I need to do though. Those are the thoughts that have run through my head so far...
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  49. #48  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    As I understand it, we have an infinite set A and a countable set C, and we want to show that has the same cardinality as .

    It suffices to assume C is disjoint from A. Since is infinite, by definition must contain a countably infinite subset .

    So write

    Now has the same cardinality as since both are countably infinite. Let be a bijection . Then we can construct a bijection between and by letting it be equal to the identity on and letting it equal on .
    Reply With Quote  
     

  50. #49  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,612
    Well, I decided not to use the cardinality argument, as I felt it would lead us into some deep waters. So I did this:
    Quote Originally Posted by Chemboy
    Book's question: "Suppose we add the elements of a finite or countable set to an infinite set . Prove that the resulting set is equivalent to the original set .
    By infinite let's mean uncountable and by countable we mean countably infinite. is uncountable, so the function is surjective but definitely not bijective. Now every infinite set has a non-empty countable subset, say , so we have a bijection given by the restriction . This an isomorphism on sets, so that , since isomorphism is an equivalence relation.

    We may assume, for full generality, that i.e. they are disjoint. We also have that is countable, so that . Now the relation is symmetric, so . then by transitivity, .

    We know that the union of a set with any of its subsets is the set itself, thus . By reflexivity we have that . so that . Thus
    Reply With Quote  
     

  51. #50  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I understand both of those and I really enjoyed them.

    See, the thing is...I definitely understand that once I see it, but I haven't seen enough like that to be able to come up with it myself. Doing those things never would have occured to me. I'm sure it'll just take time...it's just annoying in the meantime.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  52. #51  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,612
    Then just practice! That means, for any problem, trying any avenue that occurs to you. Most will turn out to be blind alleys, but that's normal (for me at least)

    I hope that none of us here is too fearsome. State your exercise, show your attempts, however faltering, and be guided by hints. (Others please note the hints bit).

    When learning, one should never be afraid of making a fool of oneself by asking seemingly dumb questions, here or in class, or by getting attempted proofs wrong. We have all been there and done that; anyone who claims they haven't is glossing the truth.
    Reply With Quote  
     

  53. #52  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    yeah. We can learn by making mistakes and remembering them and correcting ourselves in the future. So the more mistakes you make the more you learn.

    So, here's a mistake.

    Before going to the real problem I'm trying to do I want to ask a general question.

    Say we're given "Prove " or something of the sort. In general can we prove that it's true because ?

    Seems way too simple but it came to me as I was working on a proof and I want to know why it probably doesn't work.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  54. #53  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    yeah. We can learn by making mistakes and remembering them and correcting ourselves in the future. So the more mistakes you make the more you learn.

    So, here's a mistake.

    Before going to the real problem I'm trying to do I want to ask a general question.

    Say we're given "Prove " or something of the sort. In general can we prove that it's true because ?

    Seems way too simple but it came to me as I was working on a proof and I want to know why it probably doesn't work.
    It doesn't work because the limit only applies to sufficiently large values of n and you are trying to prove your assertion for all values of n . But the proof is trivial. Suppose that n>1, the multiplying both sides by n you have QED.
    Reply With Quote  
     

  55. #54  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    yeah, that was just a random example that I could come up with quickly. I figured that's what it would come to, that it only demonstrates it for sufficiently large values of n. thanks.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  56. #55  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    "Prove that "

    Hints, people, as Guitarist said. I want to get it myself in the end even if it requires being pointed in the right direction. I'm going to work on it some more but for now I have school work to do.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  57. #56  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    is there any specific way you want to go about proving it?
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  58. #57  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, think I've got that one. Here's a question leading up to the one I'm working on now...

    Is it safe to say that a set of intervals is countable if its end points are all countable?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  59. #58  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Prove that the set of all intervals with rational end points is countable.

    All I've been able to figure is that since the end points are rational and the rationals are countable, then the intervals are countable... So would it suffice to show that the rationals are countable i.e. establish a bijection between the rationals and the natural numbers? Doesn't seem like that would be enough but it's all I've got right now...

    Ideas?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  60. #59  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Prove that the set of all intervals with rational end points is countable.

    All I've been able to figure is that since the end points are rational and the rationals are countable, then the intervals are countable... So would it suffice to show that the rationals are countable i.e. establish a bijection between the rationals and the natural numbers? Doesn't seem like that would be enough but it's all I've got right now...

    Ideas?
    An interval can be identified with the ordered pair consisting of its end points. So what you need to show is that the cartesion product of the rationals with itself is countable (it is). That actually follows from the proof that the rationals are countable -- which is done by a diagonalization argument showing that the set of ordered pairs of natural numbers (another countable set) is countable.
    Reply With Quote  
     

  61. #60  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I did consider the pairs of rationals at one point but forgot when I made the post. So is it the same idea for this one?

    Prove that the set of all polygonal lines in the plane with finitely many segments and vertices at rational points is countable.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  62. #61  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    I did consider the pairs of rationals at one point but forgot when I made the post. So is it the same idea for this one?

    Prove that the set of all polygonal lines in the plane with finitely many segments and vertices at rational points is countable.
    Yes.

    The set of points in the plain with rational coefficients is countable. A line is just a pair of those points. So there are countably many lines with rational end points. A polygon made from those lines is a finite set of them It is then easy to see that for any fixed number of sides the number of polygons that can be formed is countable. The set of all polygons are just the union of this countable family of countable sets so itis countable also.

    This is a ralatively simply argument using the theory of cardinal numbers. But where are you going with this ?
    Reply With Quote  
     

  63. #62  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    These are just problems from the chapter on sets in Shilov's real analysis book.

    Some of them are about showing that certain things are either countable or uncountable. In general does this really just come down to establishing a one-to-one correspondence with the natural numbers, in the case of countable, or showing that this can't be done, in the case of uncountable?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  64. #63  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    These are just problems from the chapter on sets in Shilov's real analysis book.

    Some of them are about showing that certain things are either countable or uncountable. In general does this really just come down to establishing a one-to-one correspondence with the natural numbers, in the case of countable, or showing that this can't be done, in the case of uncountable?

    That is what it ultimately comes down to, by definition.

    It is often easier to use some of the theorems from cardinal arithmetic rather than develop the correspondence directly and from scratch, but ultimately it comes back to the one-to-one correspondence.

    In most cases the cardinality is either that of the natural numbers or of the real line, and it is usually pretty easy to see which it is. But there are exceptions and the exceptional cases are very difficult to decide. In some cases you cannot decide -- the "continuum hypothesis" for instance has been shown to be formally undecideable and independent of the other axioms of set theory. Fortunately this problem does not often arise, except in formal logic and set theory (as with everything there are some exceptions but I can't think of a specific example at the moment).

    http://en.wikipedia.org/wiki/Continuum_hypothesis
    Reply With Quote  
     

  65. #64  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Quote Originally Posted by DrRocket
    In most cases the cardinality is either that of the natural numbers or of the real line, and it is usually pretty easy to see which it is. But there are exceptions and the exceptional cases are very difficult to decide.
    I'm really curious about the exceptions. Let me know if you happen to think of one or come across one...

    The book had a prove for the countability of the rationals and for the countability of the Cartesian product of the rationals with themself, so I read through those. So, next two questions... Have yet to think on them but I'll put them up so I might have some suggestions when I get on again should I want them.

    Prove that the set of all pairwise nonintersecting intervals on the line is either finite or countable.

    and...

    Prove that the set of all closed self-intersecting "figure eights" in the plane with no points in common is either finite or countable.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  66. #65  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Quote Originally Posted by DrRocket
    In most cases the cardinality is either that of the natural numbers or of the real line, and it is usually pretty easy to see which it is. But there are exceptions and the exceptional cases are very difficult to decide.
    I'm really curious about the exceptions. Let me know if you happen to think of one or come across one...
    You can always cook one up. Let c be the cardinality of the real numbers and consider the set of all cardinals less than or equal to . You can even topologize that set with the order topology if you want to.

    The book had a prove for the countability of the rationals and for the countability of the Cartesian product of the rationals with themself, so I read through those. So, next two questions... Have yet to think on them but I'll put them up so I might have some suggestions when I get on again should I want them.

    Quote Originally Posted by Chemboy
    Prove that the set of all pairwise nonintersecting intervals on the line is either finite or countable.

    and...

    Prove that the set of all closed self-intersecting "figure eights" in the plane with no points in common is either finite or countable.
    I think you mean prove that any set of pairwise nonintersecting intervals on the line is either finite or countable. I don't think that there is such a thing as THE set of all pairwise nonintersecting intervals on the line.

    The proof ought to be be easy. Each such segment contains a rational number. No rational number is a member of more than one of the nonintersecting intervals. So there is a 1-1 correspondence between the intervals and a subset of the ratinals. That set is either countable or finite.

    Exaclty the same argument holds for figure eights in the plane except you use ordered pairs of rational numbers, at least one of which lies in the interior of each figure eight -- the same proof holds for any set of non-intersecting sets with non-empty interior.
    Reply With Quote  
     

  67. #66  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    That's a good one to know how to do.

    Oops, looks like DrR already gave away the proof.
    Reply With Quote  
     

  68. #67  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Well, I put what the book had. Maybe Mr. Shilov could have worded it better.

    What does it mean by "pairwise"?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  69. #68  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Well, I put what the book had. Maybe Mr. Shilov could have worded it better.

    What does it mean by "pairwise"?
    "pairwise" = two at a time.

    It is old and somewhat redundant terminology. But it gets the job done.
    Reply With Quote  
     

  70. #69  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Yeah...but I don't see how that's significant.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  71. #70  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Yeah...but I don't see how that's significant.
    I did not say that it was significant. In many cases people just call it a family of disjoint sets.
    Reply With Quote  
     

  72. #71  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I didn't say that you said it was significant. I just thought it might be since it was in the question. But worded as "family of disjoint sets" I understand it. Thank you.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  73. #72  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    It is possible to have a family of overlapping sets where the intersection of all the sets in the family is empty. However, in the case you are working with, no two sets in the family intersect. Describing the sets as "pairwise disjoint" is the standard way of communicating this point.
    Reply With Quote  
     

  74. #73  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, that makes sense. thank you.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  75. #74  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I'm told that the set of all sequences consisting of a finite number of zeros is countable, but I don't understand how when there are an infinite number with 0 zeros, and infinite number with 1 zero, etc. I can't figure out how you could number them using the natural numbers.

    EDIT: Nevermind, did some more thinking and I think I've got it.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  76. #75  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by salsaonline
    It is possible to have a family of overlapping sets where the intersection of all the sets in the family is empty. However, in the case you are working with, no two sets in the family intersect. Describing the sets as "pairwise disjoint" is the standard way of communicating this point.
    Agreed. But have you ever heard of a family of sets being called "disjoint" simply because the intersection of the family was empty, say a nested chain ? I have not.
    Reply With Quote  
     

  77. #76  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    Quote Originally Posted by DrRocket
    Quote Originally Posted by salsaonline
    It is possible to have a family of overlapping sets where the intersection of all the sets in the family is empty. However, in the case you are working with, no two sets in the family intersect. Describing the sets as "pairwise disjoint" is the standard way of communicating this point.
    Agreed. But have you ever heard of a family of sets being called "disjoint" simply because the intersection of the family was empty, say a nested chain ? I have not.
    It depends on the context. Sometimes the way the question is worded, it could be potentially confusing without the clarification. I can't think of an example off the top of my head though. Remember that not everyone writing mathematics is a native English speaker, so it's good to err on the side of overexplaining things.
    Reply With Quote  
     

  78. #77  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by salsaonline
    It depends on the context. Sometimes the way the question is worded, it could be potentially confusing without the clarification. I can't think of an example off the top of my head though. Remember that not everyone writing mathematics is a native English speaker, so it's good to err on the side of overexplaining things.
    I agree. I just have never seen anything come up in practice where "pairwise disjoint" was distinguishable from "disjoint", and can't cook up any sensible example. "Pairwise disjoint" is so commonly used that I just don't think about it, but it did manage to raise a question in the mind of chemboy, so I guess that it is not clear as most of us thought.

    "Pairwise disjoint" strikes me as reasonable, but a bit of overkill. On the other had there are examples of terminology that has the potential to lead one astray if one is not already reasonably conversant in an area. Consider the use of the term "metric" to describe a non-degenerate quadratic form (or field of such forms) in differential geometry. That need not even lead to a classical notion of a topological metric, yet one often does not see so much as cautionary note when the concept is inntroduced.
    Reply With Quote  
     

  79. #78  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, here it goes... Critique me, please. and keep in mind that I'm new at this.

    "Prove that the set A of all sequences consisting only of zeros and ones has the power of the continuum."

    To show that has the power of the continuum, we will establish a one-to-one correspondence between and . First consider two subsets of , which we will call and . consists of all sequences having a finite number of zeros. consists of all sequences having an infinite number of zeros.

    The subset is countable. Take a countable subset of , say , which we will call . We can form a bijection between this set and , call it .

    Now rewrite every sequence in as a number written in base 2, keeping the number and order of the ones and zeros the same. Clearly there is a one-to-one correspondence between these numbers and .

    Rewrite as and as . Define our bijection as whenever a sequence and as rewriting the terms of as a number in base 2 whenever .

    Since any subset of is equivalent (denoted ) to the interval (that is, it has the power of the continuum), we have that . So, we have and , so by transitivity and has the power of the continuum.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  80. #79  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    ok, here it goes... Critique me, please. and keep in mind that I'm new at this.

    "Prove that the set A of all sequences consisting only of zeros and ones has the power of the continuum."

    To show that has the power of the continuum, we will establish a one-to-one correspondence between and . First consider two subsets of , which we will call and . consists of all sequences having a finite number of zeros. consists of all sequences having an infinite number of zeros.

    The subset is countable. Take a countable subset of , say , which we will call . We can form a bijection between this set and , call it .

    Now rewrite every sequence in as a number written in base 2, keeping the number and order of the ones and zeros the same. Clearly there is a one-to-one correspondence between these numbers and .

    Rewrite as and as . Define our bijection as whenever a sequence and as rewriting the terms of as a number in base 2 whenever .

    Since any subset of is equivalent (denoted ) to the interval (that is, it has the power of the continuum), we have that . So, we have and , so by transitivity and has the power of the continuum.
    There is not need for . If you look at expressions for real numbers in base 2, say on the unit interval, it includes all sequences of 0's and 1's. It does not matter whether or not there are a finite number of 0"s (or equivalently a sequence that is eventually a string of 1's). So the proof boils down to showing that in base 2 any real number in the unit interval can be expressed as a sequence of 0's ad 1's and that the representation is unique except for at most a countable number of cases. (0.11111111...... = 1.00000000....... for instance)
    Reply With Quote  
     

  81. #80  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Am I wrong though, or did I just greatly overdo it?

    In the book it says "Hint: The set A is the union of two sets, the set of all sequences containing only a finite number of zeros and the set of all sequences containing infinitely many zeros. The first set it countable, while the second set has the power of the continuum, being in one-to-one correspondence with the set of points of the unit intervals written in binary notation. Now use Problem 5.

    Problem 5: Suppose we add the elements of a finite or countable set B to an infinite set A. Prove that the resulting set is equivalent to the original set A.

    This is of course the one we did a couple problems or however long ago, and the hint for it says "Let be a countable subset of , and let . Then . Now use the equivalence of the sets and ."

    This is of course along the lines of the way...can't remember who it was...did this one.

    I think it's obvious what I was trying to do. And I went through because I didn't see how it represented everything in the unit interval...I didn't feel right about just throwing decimal places in there...
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  82. #81  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Am I wrong though, or did I just greatly overdo it?

    In the book it says "Hint: The set A is the union of two sets, the set of all sequences containing only a finite number of zeros and the set of all sequences containing infinitely many zeros. The first set it countable, while the second set has the power of the continuum, being in one-to-one correspondence with the set of points of the unit intervals written in binary notation. Now use Problem 5.

    Problem 5: Suppose we add the elements of a finite or countable set B to an infinite set A. Prove that the resulting set is equivalent to the original set A.

    This is of course the one we did a couple problems or however long ago, and the hint for it says "Let be a countable subset of , and let . Then . Now use the equivalence of the sets and ."

    This is of course along the lines of the way...can't remember who it was...did this one.

    I think it's obvious what I was trying to do. And I went through because I didn't see how it represented everything in the unit interval...I didn't feel right about just throwing decimal places in there...
    That proof works. It works because a sequence with only finitely many zeros looks like,

    abcdefg....x0111111111 = abcdefg.......x100000000000000000

    and this takes care of the non-uniqueness in decimal representations base 2.

    So that proof is the same as the proof that I outlined, but a bit more elegant.
    Reply With Quote  
     

  83. #82  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    So...I was right? Is there anything I could have been more explicit or rigorous about? (just trying to be thorough)
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  84. #83  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    So...I was right? Is there anything I could have been more explicit or rigorous about? (just trying to be thorough)
    It pretty much depends on what you assume is already known. Your proof has all of the necessary elements and is valid, if you assume it as known that every real number in [0,1] has a unique representation as a base 2 decimal with an infinite number of zeros (or equivalently a sequence that does not end in a constant infinite string of 1's).

    The gist of the proof can then be put succinctly as.

    is countable

    is in 1-1 correspondence with [0.1] ( we allow 1.0000000 ito be in and hence has cardinality c (c is the cardinality of the continuum).

    as the union of a countable set and a set of cardinality c has cardinality c. Q.E.D.

    The heart of the argument is that is in 1-1 correspondence with [0.1]

    If you don't already have this fact at your disposal then it requires proof. You can prove this fact by working with the series

    where

    and showing how to select the for a given real number to get the desired unique representation.
    Reply With Quote  
     

  85. #84  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    As an aside, you can prove this straight from a diagonal argument
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  86. #85  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by river_rat
    As an aside, you can prove this straight from a diagonal argument
    I don't think so.

    You can prove that the set of sequences of 0's and 1's is not countable that way. But I don't see how a diagonalization argument gets you the cardinality the reals without the continuum hypothesis.

    Am I missing something ?
    Reply With Quote  
     

  87. #86  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Oops, just thought we wanted to show it was uncountable. So lets assume CH

    Suppose you can enumerate the set S of all sequences consisting only of 0s and 1s. so

    Define a sequence as follows. where . Then for all and so S must be uncountable. i.e.

    Define by Its easy to see that f must be an injection so

    So by CH, since
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  88. #87  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, I understand what you have with the series there, to show the one-to-one correspondence between and . However, did I avoid that problem by instead showing that and then using transitivity to show that , since we're not dealing with decimals that way? Or would I still have to show that there's a unique base-2 representation of every non-negative real number?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  89. #88  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    ok, I understand what you have with the series there, to show the one-to-one correspondence between and . However, did I avoid that problem by instead showing that and then using transitivity to show that , since we're not dealing with decimals that way? Or would I still have to show that there's a unique base-2 representation of every non-negative real number?
    I don't t hink you avoided having to show that card()= card(). What you actually showed was that card ()card(). But it depends on what you assume that the audience already knows, since going from the inequality to the equality is not much of a challenge.

    The question is not in passing from [0,1] to but in showing that has the same cardinality as [0,1]. That requires demonstrating the unique representation as decimals with an infinite number of zeros, if the audience does not already know this fact.
    Reply With Quote  
     

  90. #89  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Quote Originally Posted by DrRocket
    What you actually showed was that card ()card().
    And how did I do that? And how do I show that they're equal, then?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  91. #90  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Trying not to get too awfully bogged down with that induction problem, so here's one I did tonight. I had a much more explicit one but think I found an error in it while I was typing it out, so I'll work on it and might post it later.

    "Prove that the set of all subsets of a given set is not equivalent to itself."

    If (where is the power set of ) then we can establish a one-to-one correspondence between the two sets. However, contains more elements than because , which is clearly greater than , so a one-to-one correspondence cannot be established.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  92. #91  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Trying not to get too awfully bogged down with that induction problem, so here's one I did tonight. I had a much more explicit one but think I found an error in it while I was typing it out, so I'll work on it and might post it later.

    "Prove that the set of all subsets of a given set is not equivalent to itself."

    If (where is the power set of ) then we can establish a one-to-one correspondence between the two sets. However, contains more elements than because , which is clearly greater than , so a one-to-one correspondence cannot be established.
    I think that you need to actually prove that since this is merely a restatement of the theorem in different terminology.
    Reply With Quote  
     

  93. #92  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    That's what I thought I might have to do. I'll see if I can do that.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  94. #93  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    Just curious, what is card(A)? The cardinality of A? Just guessing based on the abbreviation, and I still wouldn't have a clue as to what it would be, even if I'm right on the word.
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  95. #94  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Yes, that's what I'm using to denote cardinality. The cardinality of a set is the number of elements it contains.

    The powerset of a set is the set of all subsets of the set, and it's cardinality is always . This is easy to see if you write out the powerset of a set with, say, three elements. The powerset will have elements, all sets themselves. But of course this doesn't prove it, just an example to see.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  96. #95  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Hmm... Trying to think about this. Does this perhaps come down to something combinatorical? I'm thinking about the number of ways a given element of can appear in .
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  97. #96  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Hmm... Trying to think about this. Does this perhaps come down to something combinatorical? I'm thinking about the number of ways a given element of can appear in .
    I wouldn't think so. Combinatirics is gemerally considered to be "finite mathematics". The subject is most definitely infinite mathematics.
    Reply With Quote  
     

  98. #97  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Yeah, wouldn't work, now that I think about it.

    Now, if I need to prove that , is it safe to generalize and prove that in general ? The only sticky spot I see in that is the case where is infinite. Just wanted to throw that idea out there to see if it's kind of the right direction to head in or not.

    Or if the fact that is "obvious," one could just show that is indeed ...

    Just thinking out loud so you can comment on my general thought process if you'd like.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  99. #98  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Yeah, wouldn't work, now that I think about it.

    Now, if I need to prove that , is it safe to generalize and prove that in general ? The only sticky spot I see in that is the case where is infinite. Just wanted to throw that idea out there to see if it's kind of the right direction to head in or not.

    Or if the fact that is "obvious," one could just show that is indeed ...

    Just thinking out loud so you can comment on my general thought process if you'd like.
    It is relatively easy to see that if but that has little to do with the problem since the gist of the issue involves infinite cardinals. Aslo note that in the trivial case, the power set of the empty set is the emnpty set, so you must exclude it.

    What you need to do is show that it is impossible to have a surjective map from any set into its power set. If the set is finite this is simple. The harder part is when the set is infinite. I would attack that problem by showing that if one assumes a surjective map from a set A to its power set, then one can find a contradiction.
    Reply With Quote  
     

  100. #99  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    Quote Originally Posted by Chemboy
    Yeah, wouldn't work, now that I think about it.

    Now, if I need to prove that , is it safe to generalize and prove that in general ? The only sticky spot I see in that is the case where is infinite. Just wanted to throw that idea out there to see if it's kind of the right direction to head in or not.

    Or if the fact that is "obvious," one could just show that is indeed ...

    Just thinking out loud so you can comment on my general thought process if you'd like.
    Asking the obvious question, you do know the definition of if A is a set, right? Just in case you don't, by definition it's the set of all functions



    Strictly speaking, to show that has cardinality you should mention this set somewhere.

    Incidently, when proving things about cardinality, you should know about the Schroeder-Bernstein theorem:

    There is a bijection between sets A and B if and only if there is an injection A--->B and an injection B--->A.
    Reply With Quote  
     

  101. #100  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by salsaonline
    Quote Originally Posted by Chemboy
    Yeah, wouldn't work, now that I think about it.

    Now, if I need to prove that , is it safe to generalize and prove that in general ? The only sticky spot I see in that is the case where is infinite. Just wanted to throw that idea out there to see if it's kind of the right direction to head in or not.

    Or if the fact that is "obvious," one could just show that is indeed ...

    Just thinking out loud so you can comment on my general thought process if you'd like.
    Asking the obvious question, you do know the definition of if A is a set, right? Just in case you don't, by definition it's the set of all functions



    Strictly speaking, to show that has cardinality you should mention this set somewhere.

    Incidently, when proving things about cardinality, you should know about the Schroeder-Bernstein theorem:

    There is a bijection between sets A and B if and only if there is an injection A--->B and an injection B--->A.
    Don't you mean the set of functions ?

    That would be consistent with identifying a set with its "charactistic function".

    While this is correct, I think it is also a bit confusing for someone seeing cardinality and naive set theory for the first time. It is somewhat less intuitive than "the set of all subsets of A".
    Reply With Quote  
     

Page 1 of 3 123 LastLast
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •