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

2.

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

4. Where's the norm and continuous function come in...? Those are all just absolute value bars... I might need more explaination...

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

6. 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?

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

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

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

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

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

12. What happens to the sign though? If you're just subtracting shouldn't it be

?

From there...

How am I doing?

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

14. ok, so...

Does that do it?

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

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

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

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

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

20. 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!

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

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

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

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

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

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

27. I know you were suggesting it for the other case but I figured I could use it here. How did I show it directly?

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

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

30. 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?

31. 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}

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

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

34. 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?

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

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

37. Well, not how I was planning on attempting it, but that works, and I'm not sure whether or not my idea would.

38. 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?

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

40. That has nothing to do with it. There is no relation to series here at all. They're just plain old sets.

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

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

43. could you give me an example of a countable infinite set?

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

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

46. OK, in that case I have a doozy of a proof sitting on my hard drive. But give it a try first.

47. Stuck, Chemboy?

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

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

50. Well, I decided not to use the cardinality argument, as I felt it would lead us into some deep waters. So I did this:
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

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

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

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

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

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

56. "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.

57. is there any specific way you want to go about proving it?

58. 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?

59. 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?

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

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

62. 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 ?

63. 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?

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

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

66. Originally Posted by Chemboy
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.

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.

67. That's a good one to know how to do.

Oops, looks like DrR already gave away the proof.

68. Well, I put what the book had. Maybe Mr. Shilov could have worded it better.

What does it mean by "pairwise"?

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

70. Yeah...but I don't see how that's significant.

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

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

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

74. ok, that makes sense. thank you.

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

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

77. Originally Posted by DrRocket
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.

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

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

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

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

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

83. So...I was right? Is there anything I could have been more explicit or rigorous about? (just trying to be thorough)

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

85. As an aside, you can prove this straight from a diagonal argument

86. 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 ?

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

88. 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?

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

90. 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?

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

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

93. That's what I thought I might have to do. I'll see if I can do that.

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

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

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

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

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

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

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

101. Originally Posted by salsaonline
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".

Page 1 of 3 123 Last
 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   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement