A proposition...

For all x in R, there exists a sequence a_n in Q such that the limit of a_n as n->+inf = x

This seems trivially false to me just from cardinality arguments (e.g. if you assume it's true then the cardinality of Q being less than the cardinality of R immediately implies that there are two different x in R that must have the same limit in Q), but I'll be damned if I can prove it rigorously.  Is there an easier way?

I'm not thinking about it deeply, but it seems to me that your focus on cardinality is dumb.  All that you want is that the sequence of rationals gets arbitrarily close to x (is strictly increasing/decreasing, say), so I don't understand your difficulty.

Well, it's true, so no. Keep in mind that you are identifying SEQUENCES of elements of Q with INDIVIDUAL elements of R. No one ever said the set of sequences of elements of Q was countable.

Cardinality argument only holds if Q is cauchy complete, which it's not.  That's why we need the irrationals in the first place.

A good rule of thumb is that nothing is trivially anything with cardinality arguments, i.e.; cardinality and intuition don't play well with each other.

As 3 said, in fact the power set of Q has the same cardinality as R, which is in a way what you're half proving.

This is stupidly easy if you have even the faintest grasp of limits.

WLOG assume X in [0,1]

Pick a sequence of I_n s/t I_n is either 1 or 0 for all n = 1, 2, 3...

Let your A_n be the sum from 1 to n of I_n / 2^n

It should be totally obvious that
1) A_n is monotone nondecreasing and rational
2) You can always pick I_{n+1} s/t A_{n+1} <= X
3) If A_n =/= X you can find N>n s/t A_n + 1/2^N is still <= X
4) 1-3 imply that you can always find an n' such that X - A_n' < E for all E in R (if A_n doesn't if your bill, find additional N until it does)

Voila.  A sequence of rationals that converges to any X in [0,1] you want.  For X not in [0,1] add the integer part of X, which is rational to the front of your sequence, and take negatives if you need to.

Really I think all you need to do is construct the monotone sequence, bound it by X, and invoke monotone convergence.

>>1
We can't really use cardinality like that, it's not a "size function" in the way you're thinking.

>>3
Surely the set of sequences of elements of Q is countable? Countable union of countable sets etc...

Are we allowed to assume decimal expansion? Even defining it will give the kind of proof >>1 wants.

>>8
It's not a countable union.

Can use the diagonal argument if you wanted

consider a bijection f from the naturals to sequences of rationals....

f(1)=a11,a12,a13.....
f(2)=a21,a22,a23.....
.
.
.
f(i)=ai1,ai2,ai3....
.
.

Now construct a sequence of rationals call this S

s_i = a_ii + 1 mod 10

There doesn't exist any natural number n s.t f(n)=S as s_n !=a_nn

Diagonal argument basically.

>>8
It's a countable product of countable sets, not a countable union of countable sets.

>>10


Countable union < countable product anyway, so the argument would have been true, had the union been countable.

>>9
Yeah, my bad, you're right. I actually realised this last night before I fell asleep and hoped no one would read the thread before I got a chance to correct it.

>>11
Uh, what? IT IS NOT A UNION. It is meaningless to talk about whether or not the "union" is countable.

>>13


Ummm, but a countable union of countable sets is still countable, but that fact is implied by the fact a countable product of countable sets is countable.

>>7
To be pedantic, you can't just WLOG at the top for no reason and explain it at the end of your proof. You should make an assumption and generalize later, or define a lemma and use it in the proof of the theorem. There's also no reason to do it in binary when you could just do it in decimal instead to make it easy to visualize. Like this:


Lemma: For all X in [0,1), there is a sequence a_n in Q which converges to X.

Proof: Suppose X in [0,1) subset R. Define sequence a_n such that a_n = nth digit after the decimal in the decimal expansion of X. Note that a_n in N for all n. Define sequence b_n such that b_n = a_n / 10^n. Note that b_n in Q for all n. Define sequence c_n such that c_n = sum{i=1,n} b_n. For any e > 0 (epsilon), there is f = 10^(-i) < e, so X - c_i < e, therefore c_n is a sequence in Q which converges to X.

Proof of >>1: Suppose X in R. Let Y be the integer part of X, such that Z = X - Y in [0,1). By the above lemma, there is a sequence c_n in Q which converges to Z. Let d_n = Y + c_n, then d_n converges to Y + limit of c_n, so d_n is a sequence in Q which converges to X. Q.E.D.


This is easier to visualize because for example:

X = 3.14159265...
Y = 3
Z = 0.14159265...
a_n = {1, 4, 1, 5, 9, 2, 6, 5, ...}
b_n = {1/10, 4/100, 1/1000, 5/10000, 9/100000, 2/1000000, 6/10000000, 5/100000000, ...}
c_n = {1/10, 14/100, 141/1000, 1415/10000, 14159/100000, 141592/1000000, 1415926/10000000, 14159265/100000000, ...} -> 0.14159265...
d_n = {31/10, 314/100, 3141/1000, 31415/10000, 314159/100000, 3141592/1000000, 31415926/10000000, 314159265/100000000, ...} -> 3.14159265... = X

Voila.

>>14
A countable product of countable sets is not necessarily countable, as exemplified by the very case we are discussing. The proof that a countable union of countable sets is countable is a trivial extension of the fact that N x N is countable.

In general, {sequences of elements of S | cardinality of S > 1} is an uncountable set, by a diagonalization proof:
Suppose it's countable, enumerate the sequences:
x11, x12, x13, ...
x21, x22, x23, ...
x31, x32, x33, ...

Create a sequence y1, y2, y3, ... in which yi != xii. This is obviously possible since each element of the sequence can be any element of S, and there are at least two elements of S.
Clearly y1, y2, y3, ... is not an element of the supposed enumeration of sequences, and therefore our assumption that the set of sequences is countable is invalid.

>>16
Actually there's more than two elements of S

>>17
{0,1} is a set with cardinality greater than 1 and it does not have more than two elements.

I realize my post is poorly written with regards to the specification of S. More precisely, I meant:
S is a set, |S| > 1, {sequences of elements of S} is uncountable.

>>18
Hah, it's obvious to you now you've seen your mistake maybe, I guess it takes a REAL mathematician to spot it in the first place.

>>19
My post, as written, is correct. "Poorly written" does not mean otherwise; it is merely preferable to phrase it differently. In short, if you were a "REAL mathematician" you would not have had trouble understanding the post in the first place.

>>20
Not you, I'm talking to whoever wrote >>16 , it's just a basic misunderstanding of the diagonal argument I think, you can't use the fact that S has 2 elements when it really has a countably infinite amount.

>>21
I'm the person who wrote >>16.
Further, I can't use the fact that S has, to quote and emphasize >>16, "AT LEAST two elements" in the case that it has INFINITELY MANY elements? Are you fucking retarded? If it's infinite, we can choose two elements and call them a and b. We can then use these two elements to describe yi as follows:
If xii = a, yi = b
else yi = a.

Christ.

>>22
Oh good, you're >>16. I've had some other idiot trying to outdo me when he obviously has no idea what he's talking about.

I think I'm taking issue with the fact that S has infinitely many elements, and yet you're trying to pick out some random two of them for no apparent reason. How do you know you're choosing the right ones? How do you know, even more importantly, that you CAN choose some two elements? It might be impossible in some pathological sets.

>>23
There are no "right ones"; any two elements will do. I glossed over this in >>16 since I figured anyone who had graduated from junior high would be able to fill int he details. Since you apparently are still struggling through 7th grade, I clarified it with >>22. With regards to whether or not it is possible to choose two elements, it is painfully trivial with ZFC. Without axiom of choice, it is significantly harder, but still entirely possible. Essentially it is possible to prove that for any non-empty set S, there exists a function f from {S} to S, and f(S) is some element of S. Having chosen one element of S, we remove it from S and repeat the process to get a second element.

I'm not gonna read through this, but I'd like to point out to the original poster that the set {0, 1} is not only countable but finite, and yet the set of sequences of elements of {0, 1} is uncountable, since it obviously contains at least one element for every real number in [0,1]. 

Since the set of sequences of 0s and 1s is uncountable, why would you expect the set of sequences of rationals to be countable?

>>24
Isn't this basically the definition of the axiom of choice for laypeople?  That you can pick an item from an infinite set?

So >>16 is totally obvious that, if S contains exactly 2 elements, it works.  But given that I'm so fucking gunshy of assuming that things that are obvious are also correct (now that I've been raped by analysis), I'm worried that assuming you can proceed from 2 to N to countably infinite to uncountably infinite elements is allowed.  Assume ZFC and all that, for the sake of my battered-child approach to mathematics, how would one show that moving from |S| = 2 to |S|>2 is ok in such a tooth-grindingly pedantic manner that no TA could realistically take issue with it?

>>26
Uh no, axiom of choice states that, given a collection of sets, it is possible to choose one element of each set in the collection. It is trivial to employ axiom of choice to show that it is possible to choose an element from one set, but it is not necessary. Since we can (with ZFC) choose one element from each set in a collection of sets, we let {S} be a collection of sets and choose an element from each set in that collection to get {s} (s being an element of S), at which point you have reduced the problem to choosing an element of a set with one element.

Note, though, that ZFC is only actually necessary for dealing with infinite collections of sets, and then only if the sets aren't "nice" enough. Choosing elements from a finite collection of sets (or, more specifically, from a single set) is possible in ZF.

>>26

Simply put the set of all sequences of two elements is strictly contained in the set of all sequences of three elements. Thus the set has an uncountably infinite subset.

given |S|=2 and |J|>2 then there trivially exists an injection f:J->S, then each sequence of elements of S can be identified with a (not necessarily unique) sequence in J.

>>17
>>19
>>21
>>23

A thorough trolling, good sir.

>>29

same person as >>17 trying to make up for his MASSIVE ERROR

>>30
You genuinely think someone could be that retarded?

>>31
We're on 4chan.

>>32
NO WAY!