My Math Forum Denumerability of a subset of a denumerable subset

 Real Analysis Real Analysis Math Forum

 September 28th, 2015, 08:05 AM #1 Newbie   Joined: Sep 2015 From: São Paulo, Brazil Posts: 2 Thanks: 1 The following is an excerpt from Serge Lang's "Real and Functional Analysis". In the proof, the author defines $\left \{k...k_n \right \}$ as a subset of D. How does he know that D is big enough to contain a set of elements that can be indexed to n? I assume that, by n, the textbook means an index set with the same cardinality as the natural numbers. Thanks from zylo Last edited by skipjack; September 28th, 2015 at 09:55 AM.
 September 28th, 2015, 12:18 PM #2 Senior Member   Joined: Aug 2012 Posts: 1,262 Thanks: 295 n is a finite number used in the induction. Thanks from zylo and bschiavo
 October 4th, 2015, 12:16 PM #3 Newbie   Joined: Sep 2015 From: São Paulo, Brazil Posts: 2 Thanks: 1 @maschke How come $\displaystyle n$ is finite if its being used in a denumeration? To denumerate a sequence means "to trace a function from $\displaystyle Z^+$ to the set of the sequence terms". $\displaystyle n$ should be at least as big as $\displaystyle Z^+$...
 October 4th, 2015, 07:55 PM #4 Senior Member   Joined: Aug 2012 Posts: 1,262 Thanks: 295 It's an induction. Step 1. D is infinite, therefore it's nonempty, therefore by the well-ordering property of the positive integers, it has a smallest element. Call that k1. Note that Lang has left out that level of detail but it's important to realize that you need well-ordering in order to know that the smallest element of D exists. Step 2. D \ {k1} is nonempty (because D is infinite and {k1} is finite) so it has a smallest element. Call it k2. Step 3. D \ {k1, k2} is nonempty (because D is infinite and {k1, k2} is finite) so it has a smallest element. Call it k3. Step 4. D \ {k1, k2, k3} is nonempty (because D is infinite and {k1, k2, k3} is finite) so it has a smallest element. Call it k4. etc. Does that make the structure of the proof more clear? It's an induction on n. You keep picking elements from D and adding them to the k-sequence. At each step of the induction, {k1, k2, ..., kn} is a finite set, and D \ {k1, k2, ..., kn} is nonempty, so you can always pick k_(n+1). Thanks from zylo and bschiavo Last edited by Maschke; October 4th, 2015 at 08:02 PM.
 October 4th, 2015, 08:09 PM #5 Senior Member   Joined: Mar 2015 From: New Jersey Posts: 1,010 Thanks: 83 If D is not denumerable, neither is Z+. Contradiction. Thanks from bschiavo
October 5th, 2015, 08:47 AM   #6
Senior Member

Joined: Aug 2012

Posts: 1,262
Thanks: 295

Quote:
 Originally Posted by zylo If D is not denumerable, neither is Z+. Contradiction.
That is what is to be proven.

 October 5th, 2015, 09:29 AM #7 Senior Member   Joined: Mar 2015 From: New Jersey Posts: 1,010 Thanks: 83 Begin enumerating Z+ by enumerating D.
 October 5th, 2015, 01:01 PM #8 Senior Member   Joined: Mar 2015 From: New Jersey Posts: 1,010 Thanks: 83 An infinite set of anything is countable by definition. How else would you know it's infinite?
October 5th, 2015, 07:38 PM   #9
Senior Member

Joined: Aug 2012

Posts: 1,262
Thanks: 295

Quote:
 Originally Posted by zylo An infinite set of anything is countable by definition. How else would you know it's infinite?
It could be uncountable. It might be the case that there's an infinite subset D of Z+ such that there is no bijection from D to Z+. For all we know. Of course that can't happen. Saying that it can't happen is the content of the theorem. Of course it's obvious; but this is the place where they prove it from first principles.

The theorem is proving the statement that every infinite subset of Z+ is countable. You can't assume the thing you're trying to prove.

By the way I'm not familiar with this text but I know Lang's graduate algebra book. He can be terse. You need to mentally add in all the details he's skipping over. It pays to read Lang slowly.

Last edited by Maschke; October 5th, 2015 at 07:45 PM.

 October 6th, 2015, 11:17 AM #10 Senior Member   Joined: Mar 2015 From: New Jersey Posts: 1,010 Thanks: 83 Induction Maschke, Thanks. You are clear and correct on all counts. But just for fun: Induction Principle: If Pn -> (IMPLIES) Pn+1 and P1=0, all Pn true. A subset of D does not have a lowest member because I removed its lowest member. It's a postulate (well ordering). So the OP is true by postulate. But I really don't believe that. If you accept the postulate, anything you prove after that is a valid theorem. And if b is true whenever a is true, a -> b even though there is no causality. Like I said, just for fun.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post munjo5746 Real Analysis 2 June 7th, 2013 06:20 PM redgirl43 Applied Math 1 April 21st, 2013 06:20 AM fienefie Real Analysis 3 October 9th, 2011 06:11 AM Jimena29 Real Analysis 4 November 10th, 2009 03:09 PM sansar Linear Algebra 1 March 16th, 2009 07:42 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top