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

[CaptainAmerica17]

TL;DR

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.

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!

 

[Infrared]

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.

 

[CaptainAmerica17]

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!

 

[PeroK]

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?

 

[CaptainAmerica17]

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 )

 

[PeroK]

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.

 

[CaptainAmerica17]

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!

 

[mathwonk]

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.

 

[CaptainAmerica17]

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.

 

[mathwonk]

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.

 

[mathwonk]

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.

 

[PeroK]

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

 

[CaptainAmerica17]

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.

 

[mathwonk]

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.

 

[MidgetDwarf]

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

 

[CaptainAmerica17]

@ 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!

 

[PeroK]

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!

 

[FactChecker]

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?

 

[mathwonk]

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.

 

[mathwonk]

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.

 

[MidgetDwarf]

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.

 

[mathwonk]

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

 

[Infrared]

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.

 

[PeroK]

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.

 

[Infrared]

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

 

[mathwonk]

Someone with my mathematicians' dna finds it incomprehensible that anyone could be happy studying a subject in which one did not know what all the words mean. I myself was never content until after sitting through, as a junior or sophomore, a course in which George Mackey laid out the foundations of analysis (for undergraduates), beginning with only the axiom that there exists at least one infinite set, proceeding to the Peano postulates, and definition of the natural numbers as I outlined above, and then the rationals and reals, fundamentals of metric spaces, and the proofs of the basic theorems of calculus. At the end I felt and thought: ahhh..., at last I can be at peace with these previously fuzzy statements! I still wonder how anyone can think they know anything about calculus who cannot define, or at least characterize by axioms, the real numbers. If you don't know what a real number is, why bother to state theorems about them, e.g. what do you mean when you invoke the intermediate value theorem? Of course the student is not at fault, since they have been taught by a teacher who did not bother to explain what was going on. The rubber hits the road with a student who thinks for instance that all real numbers are integers, or at best that they are all finite decimals that can be displayed on their calculator. With such an understanding, of course all the theorems of calculus are actually false!

 

[Infrared]

Someone with my mathematicians' dna finds it incomprehensible that anyone could be happy studying a subject in which one did not know what all the words mean.

I still wonder how anyone can think they know anything about calculus who cannot define, or at least characterize by axioms, the real numbers. If you don't know what a real number is, why bother to state theorems about them, e.g. what do you mean when you invoke the intermediate value theorem?

I agree with this to an extent, but there are some things I'm okay believing. Since you do algebraic geometry, surely you're aware of annoying set theoretical issues of when you need to have (locally) small categories for constructions to be safe, and what to do when you only have proper classes instead of sets, etc. I don't really ever run across this sort of things, but if I did, I think I'd err on the side of not worrying too much about it. I hope that you don't judge me too much for this!

Of course the student is not at fault, since they have been taught by a teacher who did not bother to explain what was going on. The rubber hits the road with a student who thinks for instance that all real numbers are integers, or at best that they are all finite decimals that can be displayed on their calculator. With such an understanding, of course all the theorems of calculus are actually false!

I've wondered a bit about the pedagogical value of constructing $\mathbb{R}$ with decimals, i.e. a real number is a sequence of natural numbers from 0 to 9, with a decimal point somewhere, modulo equivalences coming from trailing sequences of $9$s. It would be a bit more annoying than in the usual constructions to carefully define arithmetic operations, but perhaps it would seem more familiar to students? I'm not sure, it's basically the Cauchy sequence construction, except that you're only working with rationals whose denominators are a power of $10$. Maybe I shouldn't be let in front of an analysis classroom...

Edit: I've realized that you've had Mackey, Bott, and Tate as professors in undergrad. I've also had some well-known professors, but you were spoiled!

 

[mathwonk]

Infrared, I presented exactly the decimal construction of real numbers you describe, from an exercise in the appendix of Spivak's Calculus, "high school real numbers", for a brilliant class of high schoolers some decades ago. It went really well, they composed a rap song about it, and we all learned a lot. One of those students was until recently chair of the math department of Brown, and now heads their data science initiative. That one exercise in Spivak occupied us for several weeks and was written up in a 22 page set of notes I still have in pdf. I attempt to attach the first half of them.

 

[zinq]

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

I think that it's very healthy to prove this at least once. The proof is extremely easy, and it's well worth understanding why it is so easy.

 

[r731]

Hint: by definition, T1 is countable iff there exists an injection from T1 to N. Consequently, T1 is finite iff there is a bijection from T1 to a finite subset of N.