Help Finding the Correct Approach to this Proof (Intro Real Analysis)

  • #1

Summary:

I'm working on this problem and I'm thinking about using contradiction. I'm not sure if this is the correct approach, and if it is, whether I've set it up correctly.
1.3.PNG

Ok, so here is what I have so far:
Suppose ##T_1## is infinite and ##\varphi : T_1 \rightarrow T_2## is a bijection.

Reasoning:
I'm thinking I would then show that there is a bijection, which would be a contradiction since an infinite set couldn't possibly have a one-to-one correspondence with a finite set.

The problem:
This idea makes sense to me logically and I'm pretty sure I can assume bijection since it's the "if" part of an if-then statement. I guess I'm just trying to figure out how to deduce that every element in ##T_1## corresponds with ##T_2## without making any logic jumps. That is if this is even a correct approach at all.

Any help is greatly appreciated, thank you!
 

Answers and Replies

  • #2
Infrared
Science Advisor
Gold Member
788
407
I assume your definition of "finite" is something like "in bijection with ##\{1,\ldots,n\}## for some natural number ##n##".

If so, just think about how to compose bijections appropriately. You don't need to argue by contradiction.
 
  • Like
Likes etotheipi
  • #3
I assume your definition of "finite" is something like "in bijection with ##\{1,\ldots,n\}## for some natural number ##n##".

If so, just think about how to compose bijections appropriately. You don't need to argue by contradiction.
Yes, that is the definition I am using. I'll give this approach some thought. Thanks for the response!
 
  • #4
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,711
6,955
Yes, that is the definition I am using. I'll give this approach some thought. Thanks for the response!
Just a thought. Neither my Real Analysis nor my Intro to Abstract Algebra textbooks go down to questions at that level. I wonder whether you'd be better getting stuck into some genuine analysis or algebra? I did a degree in pure maths and I would take that as more or less the definition of a finite set.

Sure I can see how to prove it rigorously. But, I would say that's because I can (still) do rigorous maths. I never actually started with questions like that.

I just wonder how much good this this material does you? Does it really prepare you for the real stuff?

Have you tried just getting stuck into some "real" mathematics? Like sequences and limits?
 
  • Like
Likes CaptainAmerica17 and Infrared
  • #5
Just a thought. Neither my Real Analysis nor my Intro to Abstract Algebra textbooks go down to questions at that level. I wonder whether you'd be better getting stuck into some genuine analysis or algebra? I did a degree in pure maths and I would take that as more or less the definition of a finite set.

Sure I can see how to prove it rigorously. But, I would say that's because I can (still) do rigorous maths. I never actually started with questions like that.

I just wonder how much good this this material does you? Does it really prepare you for the real stuff?

Have you tried just getting stuck into some "real" mathematics? Like sequences and limits?
No this is like set theory stuff. In the book I'm using, the "real" stuff comes after set theory and properties of the real numbers. Most of the problems are just proofs of definitions similar to this. I've thought about skipping it multiple times but decided against it. I'm starting a degree in math next school year. You really never had to go through this stuff?

(because I honestly feel like skipping it 😕)
 
Last edited:
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,711
6,955
No this is like set theory stuff. In the book I'm using, the "real" stuff comes after set theory and properties of the real numbers. Most of the problems are just proofs of definitions similar to this. I've thought about skipping it multiple times but decided against it. I'm starting a degree in math next school year. You really never had to go through this stuff?

(because I honestly feel like skipping it 😕)
I'd skip it. You can always go back. I'd say that a bijection mapping finite sets to finite sets and infinite sets to infinite sets is in the category of things that are too low level to need to prove. It's very different from, say, proving that the limit of a sequence is unique. That does need to be proved.

Or, what about this proof that there are infinitely many primes:

Let ##p_1, p_2, \dots p_n## be any finite set of primes. Let ##N = p_1 \times p_2 \dots \times p_n + 1##. Note that a number is prime if it not divisible by any other prime. ##N## is not divisible by any prime in the list. Therefore, either ##N## is prime or there is another prime that divides it. Either way, there is another prime and our list is not complete. Hence, no finite list of primes is complete. Hence there are infinitely many primes.

That to me is beautiful and inspiring. That's where I'd start.
 
  • Like
Likes etotheipi
  • #7
I'd skip it. You can always go back. I'd say that a bijection mapping finite sets to finite sets and infinite sets to infinite sets is in the category of things that are too low level to need to prove. It's very different from, say, proving that the limit of a sequence is unique. That does need to be proved.

Or, what about this proof that there are infinitely many primes:

Let ##p_1, p_2, \dots p_n## be any finite set of primes. Let ##N = p_1 \times p_2 \dots \times p_n + 1##. Note that a number is prime if it not divisible by any other prime. ##N## is not divisible by any prime in the list. Therefore, either ##N## is prime or there is another prime that divides it. Either way, there is another prime and our list is not complete. Hence, no finite list of primes is complete. Hence there are infinitely many primes.

That to me is beautiful and inspiring. That's where I'd start.
Thanks for the advice! I don't know why I always feel the need to do every single part of a textbook. Just recently, someone told me that they normally only do half of the problems in a textbook. I had spent weeks doing every problem in every section of the books I'm working on and was wondering how anyone could possibly ever get through a self-study. Well, Duh!
 
  • #8
mathwonk
Science Advisor
Homework Helper
11,039
1,230
FWIW, just to keep it confusing, here is the alternate point of view. I suggest you review the exact definition of "finite" given in your book, and then write out the proof. For beginners, even easy arguments are worth making sure of. The fact that you may be a beginner at proofs, (and there is no shame in that), is suggested by the fact that you ask how to do a proof about "finiteness" without first giving us your definition of the word "finite". So you can learn even from this problem that you always begin every proof by giving the definition of the key words in the statement.

And some of us do work every problem in a book we self study. I am currently self studying the book Introduction to algebraic geometry, by David Mumford, and am reading every word, and attempting every problem. I started in summer 2017, and am about 2/3 of the way through.

Oops: my apologies. I seem to have edited the post you found helpful. I didn't realize it had become visible and was afraid it might be unhelpful, but now maybe this version is unhelpful! If so, please forgive me.
 
Last edited:
  • Like
Likes CaptainAmerica17
  • #9
FWIW, just to keep it confusing, here is the alternate point of view. I suggest you review the exact definition of "finite" given in your book, and then write out the proof. For beginners, even easy arguments are worth making sure of. The fact that you may be a beginner at proofs, (and there is no shame in that), is suggested by the fact that you ask how to do a proof about "finiteness" without first giving us your definition of the word "finite". So you can learn even from this problem that you always begin every proof by giving the definition of the key words in the statement.

And some of us do work every problem in a book we self study. I am currently self studying the book Introduction to algebraic geometry, by David Mumford, and am reading every word, and attempting every problem. I started in summer 2017, and am about 2/3 of the way through.

Oops: my apologies. I seem to have edited the post you found helpful. I didn't realize it had become visible and was afraid it might be unhelpful, but now maybe this version is unhelpful!
No worries! All of this is very helpful. I think I just need to stick it out for the simpler stuff, but also not be afraid to move along when necessary. The thing you said about definitions is something that has tripped me up more than once, no one has ever pointed it out to me before now.
 
  • #10
mathwonk
Science Advisor
Homework Helper
11,039
1,230
Wonderful. Thanks for the feedback. I recall my other post involved a different definition of "infinite" sometimes used: a set S is infinite iff there is a bijection from S to some proper subset of S.

It is then some work to prove that the set of the first n positive integers is not infinite. But all these statements involve bijections, and the crux of your exercise seems to be to understand that because a composition of bijections is again a bijection, that the concept of finiteness is invariant under bijection.

But if we let N be the set of the first n positive integers, and define a set T to be finite iff there is a bijection from T to N, then we can ask to prove that a set U is finite iff there is a bijection from U to a known finite set T. This is elementary but fundamental.
 
  • #11
mathwonk
Science Advisor
Homework Helper
11,039
1,230
the remarks about definitions are the reason math has such a high reputation, even if that reputation is misunderstood or undeserved. The only reason math results have a high reliability is that they do not pretend to tell you the difficult determination what is actually true, rather they only show what would be true, if you could be sure of something more basic being true. I.e. we don't claim to prove that X is true, we only claim to prove that X is true in any situation where Y is true. Every proof is dependent on the definitions assumed in the proof.
 
  • #12
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,711
6,955
@CaptainAmerica17

FYI the textbook on Abstract Albegra book I have says (page 2):

A set ##S## is called finite if only finitely many different objects are members of ##S##. Otherwise, ##S## is described as an infinite set.

If ##S## is a finite set, the number of different objects in ##S## is called the order or cardinality of ##S## and is denoted by ##|S|##. E.g. if ##S = \{1, 3, 5, 7 \}##, then ##|S| = 4##.

On the next page he makes a few points that this "simple-minded" concept of a set is a reasonable and useful one and points the reader who wants to know more to Naive Set Theory by Paul Halmos. I studied that book after I graduated and I found it hard going.

My point is that trying to deconstruct "naive" set theory into something more rigorous is in many way quite advanced mathematics. Too much rigour is just as bad as too little, IMHO.
 
  • #13
the remarks about definitions are the reason math has such a high reputation, even if that reputation is misunderstood or undeserved. The only reason math results have a high reliability is that they do not pretend to tell you the difficult determination what is actually true, rather they only show what would be true, if you could be sure of something more basic being true. I.e. we don't claim to prove that X is true, we only claim to prove that X is true in any situation where Y is true. Every proof is dependent on the definitions assumed in the proof.
Honestly thinking about things in this way really helps
@CaptainAmerica17

FYI the textbook on Abstract Albegra book I have says (page 2):

A set ##S## is called finite if only finitely many different objects are members of ##S##. Otherwise, ##S## is described as an infinite set.

If ##S## is a finite set, the number of different objects in ##S## is called the order or cardinality of ##S## and is denoted by ##|S|##. E.g. if ##S = \{1, 3, 5, 7 \}##, then ##|S| = 4##.

On the next page he makes a few points that this "simple-minded" concept of a set is a reasonable and useful one and points the reader who wants to know more to Naive Set Theory by Paul Halmos. I studied that book after I graduated and I found it hard going.

My point is that trying to deconstruct "naive" set theory into something more rigorous is in many way quite advanced mathematics. Too much rigour is just as bad as too little, IMHO.
I can tell the difference. When I do proof problems from my linear algebra book, it normally doesn't take much time at all because everything seems much more straightforward. The thinking for these kinds of proofs just seems different for some reason. The proofs make sense, of course, but my brain just doesn't recognize the process as quickly. I've been sticking it out because I figured it was important to learn and get used to it as mathwonk was saying.
 
  • #14
mathwonk
Science Advisor
Homework Helper
11,039
1,230
you must be kidding; it actually says a set is finite iff it has only a finite set of distinct objects? @@@##$$$%%%!!! what does that mean?!!! that is not a math book!

edit: sorry I lost it here, I was being super impatient. Probably I was tired.
 
Last edited:
  • Sad
Likes Math_QED and PeroK
  • #15
1,024
246
@ Mathwonk. I think the definition a set is finite iff it has only a finite set of distinct objects, comes from Halmos:Naive Set Theory. IRC it ignores Russels Paradox, so it gives that definition. I can be wrong. I read it many years ago when I was still in a remedial trigonometry class. So I don't think I observed much of that book, but it was fun time.

@Op. Here is a link to a free and legal PDF of a book about proofs. Read the section regarding Cardinality. You may need to backtrack a bit and read the section devoted to functions. https://www.math.brown.edu/~res/MFS/handout8.pdf

Sorry the above link was the incorrect version. Here is the source I wanted to link to:
https://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdf

I think this may help you and also has examples of showing sets are countable or non countable. Worked out proofs..
 
Last edited:
  • Like
Likes CaptainAmerica17 and PeroK
  • #16
@ Mathwonk. I think the definition a set is finite iff it has only a finite set of distinct objects, comes from Halmos:Naive Set Theory. IRC it ignores Russels Paradox, so it gives that definition. I can be wrong. I read it many years ago when I was still in a remedial trigonometry class. So I don't think I observed much of that book, but it was fun time.

@Op. Here is a link to a free and legal PDF of a book about proofs. Read the section regarding Cardinality. You may need to backtrack a bit and read the section devoted to functions. https://www.math.brown.edu/~res/MFS/handout8.pdf

Sorry the above link was the incorrect version. Here is the source I wanted to link to:
https://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdf

I think this may help you and also has examples of showing sets are countable or non countable. Worked out proofs..
This is great! I can use this as a reference for future problems as well, thank you!
 
  • #17
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,711
6,955
This is great! Thank you!
Just to complete the picture. If you do want to dig all the way down to the logical bedrock of mathematics. The point where you assume nothing that doesn't ultimately need to be assumed, this is where you end up:

https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory

The point is that once you start doubting what "a finite number of distinct elements" means, then it's long way down to the bedrock!
 
  • Like
Likes CaptainAmerica17
  • #18
FactChecker
Science Advisor
Gold Member
5,783
2,151
I would NOT skip this proof. It is a good example of a typical proof. If you assume that there is a bijection to a finite set, ##T_2##, then what does the fact that ##T_2## is a finite set tell you? Do you have any properties of the composition of bijections that can help you?
 
  • #19
mathwonk
Science Advisor
Homework Helper
11,039
1,230
I have done some research and those of you who said it is common to define a set as finite if it is in bijection with the first n natural numbers, {1,2,...,n} for some n, are quite correct. However, in those places where this definition is given carefully, such as Halmos's Naive set theory, some 40-50 pages has been used first to give a careful definition of the natural numbers, using successor functions. Halmos also remarks in the same discussion that it follows that a set which is finite by this definition cannot be placed in bijection with a proper subset of itself, which is Dedekind's definition of finite. Although it also seems true that the wikipedia article on the topic seems to actually say in the first sentence, that a set is finite if it consists of a finite number of elements, to a mathematician's ears, this statement is meaningless. The author of the article seems to have meant this as an intuitive statement, not a real definition, and becomes much more detailed and careful later on. It seems to require some version of the axiom of choice to prove that Dedekind's definition implies the one requiring equivalence with some natural number, and possibly for this reason Halmos avoids using it as a definition, although he gives Dedekind's property as one of the aspects distinguishing finite sets from countably infinite ones.

I may have been wrong, but in the present circumstance I assumed the OP was reading a book which had not yet carefully defined natural numbers, and thus it seemed to be inadmissible to me to use them to define finiteness. But I suppose it is fine to do so as long as one has some working properties of the natural numbers that are given. Anyway, not being aware of what had gone before in the book under discussion, I made some assumptions and guesses about what were the likely definitions, but I seem to have been wrong. I would still caution any math student to avoid statements such as "a set is finite if and only if it has a finite number of elements" since this sounds circular. Of course it is ok if the phrase "has a finite number of elements" has been defined carefully, such as in infrared's post #2, but to me, even that would require a prior definition of the set {1,2.,,,n}, such as Halmos gives in the first 50 pages of his book. Other properties I learned today that seem nice include that a finite set is one that can be ordered so that every non empty subset has both a smallest and a largest element, I believe.

Forgive me for unhelpful remarks, my point is just that proofs begin with definitions, and the definitions should be precise and not circular. But you know this. Peace.
 
  • Like
Likes CaptainAmerica17
  • #20
mathwonk
Science Advisor
Homework Helper
11,039
1,230
Wow, thanks midget for the reference to Halmos. He discussed the Dedekind definition of infinite on page 61 and clarifies a point I always kind of sloughed over myself, namely that it is not so clear how to prove that every infinite set contains a subset bijectively equivalent to the set of all natural numbers. One uses the ax of choice it seems, and this enables one to define a bijection of an infinite set with a proper subset, just by mimicking the correspondence for natural numbers of adding one. cool. So I didn't know as much about this "simple" topic as I thought.
 
  • #21
1,024
246
Wow, thanks midget for the reference to Halmos. He discussed the Dedekind definition of infinite on page 61 and clarifies a point I always kind of sloughed over myself, namely that it is not so clear how to prove that every infinite set contains a subset bijectively equivalent to the set of all natural numbers. One uses the ax of choice it seems, and this enables one to define a bijection of an infinite set with a proper subset, just by mimicking the correspondence for natural numbers of adding one. cool. So I didn't know as much about this "simple" topic as I thought.
Thank you. Ill have a more thorough look at it in the upcoming months. At the time, the book went over my head, but I was able to learn a few things from it. Never cared to much about foundational stuff, but my interest has grown seeing some interesting problems on mathstacks.
 
  • #22
mathwonk
Science Advisor
Homework Helper
11,039
1,230
The whole point is just to make some kind of rigorous sense out of the process of counting. So you need a place to start and a way to go to the next number or object. And in set theory we want each "number" to be a set. So in sort of the way the bureau of standards used to have a piece of metal that weighs officially one pound, or ounce, or something, we want to choose once for all a collection of standard sets, where the set representing the number 8 say, has exactly eight elements. Then we can define the number 8 to be that set of 8 elements.

As to where to begin, zero is a natural start, and besides there is a natural choice of a set with zero elements, namely the empty set. So we define the number zero to be the empty set. Then we have to decide how to move from zero to one, and then from one to two and so on. The brilliant solution, is to choose the set representing one to be the set whose one element is the number zero! I.e. the set containing zero, namely the set whose only element is the empty set, is not the same as the empty set itself, since the empty set has no elements, and the set with the empty set as its only element, has one element.

This same trick then works to get us from each previously defined number to the next one. I.e. to find the "next" number, we need a way to add one new element to our given set, and we choose as the new element, the set itself. So given any set S, this takes us to the set consisting of the elements of S plus the one new element S itself, namely S union {S}. So 1 = {0}, 2 = {0,1} = {0,{0}}, 3 = {0,1,2} = {0,{0}, {0,{0}}}. Ok, it is simpler theoretically than actually, but it seems to work.

The process of making a set with one extra element, namely that set itself, is called forming the "successor", or "next" set. Then it gets a little abstract, at least for me. To try to define the collection of all natural numbers, you consider sets which are closed under the process of taking successors. You need an axiom, the axiom of infinity, to guarantee some non empty such set exists, i.e. that there is at least one "infinite" set. Then you intersect them all, to get the smallest such "infinite" set. That smallest set. closed under taking successors, is the natural numbers, (starting with zero). Or if you want to start with 1, you could restrict to just those elements which are themselves successors.

Then you can actually define addition and so on with these numbers.....
 
Last edited:
  • Like
Likes CaptainAmerica17
  • #23
Infrared
Science Advisor
Gold Member
788
407
To try to define the collection of all natural numbers, you consider sets which are closed under the process of taking successors. You need an axiom, the axiom of infinity, to guarantee some non empty such set exists, i.e. that there is at least one "infinite" set. Then you intersect them all, to get the smallest such "infinite" set.
Just a little quibble, mostly because I haven't thought much about this before either: The collection of sets satisfying this property doesn't itself form a set, so I don't think you can safely take an intersection. But maybe this is okay, because I think a simple remedy is to fix one such set, and then intersect over its subsets that satisfy this property.
 
Last edited:
  • Like
Likes mathwonk and CaptainAmerica17
  • #24
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,711
6,955
My first quibble would be that none of this is a prerequisite to studying pure mathematics. We could, for example, say that the equation ##x^2 = 1## has two real solutions and that ##\{-1, 1 \}## is the finite set of solutions. We don't have to put this notion on a more fundamental basis as prerequisite to undergraduate mathematics.

The second quibble is that with this level of rigour it becomes difficult to make progress beyond a basic level, so it must eventually be abandoned in any case. You couldn't complete a course in real analysis with this level of rigour. That would be more like a graduate project.

I suspect it would take a considerable effort to deconstruct something as simple as "let ##p## be an odd prime". A typical undergraduate course in number theory can progress without deconstructing such a notion into set theoretic language.
 
  • Like
Likes CaptainAmerica17
  • #25
Infrared
Science Advisor
Gold Member
788
407
You couldn't complete a course in real analysis with this level of rigour. That would be more like a graduate project.
I think this depends on what you mean by 'rigour'. A first course in analysis might take the existence of ##\mathbb{N}## or ##\mathbb{Q}## (or maybe even ##\mathbb{R}##) for granted, but after accepting some basic notions like that as granted, I think a first analysis course should be close to 100% rigorous.

I suspect it would take a considerable effort to deconstruct something as simple as "let ##p## be an odd prime". A typical undergraduate course in number theory can progress without deconstructing such a notion into set theoretic language.
Right, once ##\mathbb{N}## (or whatever) has been constructed, there shouldn't be a need to refer back to the gory details of the construction, and you can abstract it all away. You'd never say ##1\in 1/2## in a real problem, even if that's literally true according to your construction of ##\mathbb{Q},## say. But I think one should still care that ##\mathbb{Q}## can be rigorously defined in the first place! Of course you're right you don't need to take it as prerequisite to studying mathematics built on top of it..
 
  • Like
Likes CaptainAmerica17

Related Threads on Help Finding the Correct Approach to this Proof (Intro Real Analysis)

Replies
5
Views
3K
Replies
19
Views
5K
Replies
5
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
4
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
Replies
1
Views
2K
Top