Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been reading the simple parts of Thomas Jech's book on the Axiom of Choice and came across the following proof on page 141. The proof assumes a mathematical model without the axiom of choice.

Lemma. $X$ is D-finite if and only if $X$ does not have a countable subset.

Theorem. There is a set $S$ of real numbers and a real number $a \not \in S$ such that a is in the closure of $S$ but there is no sequence $(x_n)^{\infty}_{n=0} \subset S$ such that $(x_n)^{\infty}_{n=0} \longrightarrow a$.

Proof. Let $D$ be a D-finite infinite set of reals. We claim that the set $D$ must have an accumulation point. To prove this claim suppose that all $d \in D$ are not accumulation points, then let $\{I_n:n=0,1,...\}$ be a fixed enumeration of open intervals with rational endpoints. Assign the least $n$ such that $I_n \cap D={d}$ to each $d \in D$. This makes $D$ countable and by the above lemma gives us our contradiction. So $D$ has an accumulation point $a$. Let $S=D \setminus\{a\}$ and since $S$ is D-finite, every convergent sequence in $S$ is eventually constant.

Could somebody explain this proof? Why is the last sentence true/ Why does this mean every convergent sequence is eventually constant?

I think the following theorem is important

Theorem. There is a model of ZF which has an infinite set of real numbers without a countable subset

share|improve this question
    
I have a hunch this is not even the second time this topic is discussed on the site. –  Asaf Karagila Oct 3 '13 at 10:44
    
Also, the proof verification tag is for questions about your proofs that need to be verified. –  Asaf Karagila Oct 3 '13 at 10:47
1  
The title and first paragraph are a bit misleading, because the hypothesis used in the theorem is "there is a Dedekind-finite infinite set of real numbers," which is stronger than $\neg \mathsf{AC}$. –  Trevor Wilson Oct 3 '13 at 15:49
    
To clear the problem that @Trevor points out, I suggest replacing "there is a set" with "there can be a set" in the title (and while at it, add the missing space). –  Asaf Karagila Oct 3 '13 at 18:15

4 Answers 4

up vote 3 down vote accepted

Of particular importance is that for any D-finite set $F$, every function $\mathbb{N} \to F$ can take on only finitely many values.

If $f: \mathbb{N} \to F$ took only infinitely many different values then one could define $g : \mathbb{N} \to \mathbb{N}$ recursively according to $$g ( n ) = \min \{ k \in \mathbb{N} : f(k) \notin \{ f(g(0)) , \ldots , f(g(n-1)) \}\;\},$$ and then the composition $f \circ g : \mathbb{N} \to F$ would be one-to-one, contradicting that $F$ has no countably infinite subset!

Using this it is fairly straightforward to show that any convergent sequence in a D-finite set of reals is eventually constant.

share|improve this answer

Let $(x_n)$ a sequence in $S$ with $x_n\to x$. If the sequence is not eventually constant, we can define $y_n=x_m$ where $m$ is minimal with $x_m\ne x$ and $|x_m-x|<|y_k-x|$ for all $k<n$. Then $y_n\to x$ as well and $\{\,y_n\mid n\in\mathbb N\,\}$ is a countable subset of $S$. By the lemma $S$ is not D-finite.

share|improve this answer

One point which is somewhat amiss amongst the answers is this:

If $D$ is a Dedekind-finite set and $S\subseteq D$, then $S$ is Dedekind-finite as well. The proof is simple from the lemma cited in your question. If $S$ was Dedekind-infinite, then it would have a countably infinite subset, and so would $D$ -- a contradiction.

Now, since $S$ is Dedekind-finite every countable subset is a finite subset. The range of a sequence is countable, by definition, and therefore finite. The only sequences with finite range which converge are those which are eventually constant.

share|improve this answer
    
This was pretty much the answer I wanted to write, and then I got confused and messed it up. –  Ben Millwood Oct 3 '13 at 18:08
    
@Ben: Well, it happens. Don't forget that I have like 300 answers under my belt on this topic. And over 2300 in general. It takes experience to write concise answers, and I hate seeing my older ones because I find them... crappy (to some extent, anyway). –  Asaf Karagila Oct 3 '13 at 18:13

In this answer I'm going to use "infinite" to mean "not finite" (i.e. does not biject with any finite ordinal) and "countably infinite" to mean "in bijection with $\mathbb N$" (so in particular, $D$-finite sets are not countably infinite, even if they inject into $\mathbb N$). These usages are probably standard, but it's often easy to forget when working without Choice that a few distinctions that didn't matter now do, so the definitions sometimes have to be revisited.

The idea is that if the set of points that the sequence visited were finite, then since the sequence converges it would have to settle down to only one of them, so the sequence is eventually constant. For example, take half the smallest distance between two points in the finite set, and the sequence is eventually within that distance of its limit, so it can't jump between points anymore.

If, on the other hand, the sequence visits infinitely many points, then they form a countable subset of the set $D$, and this violates $D$-finiteness.

The tricky part is arguing "infinite $\implies$ countably infinite", since after all $D$ itself is infinite but not countably so! However, the range of the sequence can be well-ordered by "which element did I visit first", so then it must biject with an ordinal, and the ordinals don't exhibit pathological behaviour like being simultaneously infinite and $D$-finite.

share|improve this answer
    
I don't understand your last paragraph, beginning with "Now, any set that is not finite admits an injection from $\mathbb{N}$." This seems to say that infinite implies D-infinite. Perhaps you meant "any subset of $\mathbb{N}$ that is not finite admits an injection from $\mathbb{N}$"? But then it's easy to see it admits a bijection with $\mathbb{N}$ even without using Cantor-Schröder-Bernstein, just by the recursion theorem. –  Trevor Wilson Oct 3 '13 at 15:57
    
@TrevorWilson: You're right. I edited somewhat half-heartedly because Asaf's answer is so much better anyway :P –  Ben Millwood Oct 3 '13 at 21:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.