# I Help With Some Short Proofs

1. Dec 12, 2016

### AplanisTophet

I am sure these are wrong given what is 'proven,' I just can't put my finger on it. Any insight into what is wrong is most appreciated. Thank you in advance!:

1) Let $q_1, q_2, q_3,$ … be an enumeration of $A = \mathbb{Q} \cap (0,1)$.

2) Select a real number $r \in (0,1)$ uniformly at random. Note: A common way of doing this cited by mathematicians is the theoretical flipping of a coin infinitely many times followed by some trivial 'clean-up' given that there are two binary expansions of each dyadic rational, e.g. 0.1 = 0.01111111...

3) Let $B = \mathbb{Q} \cap (-r, 1-r)$. Note that $r \in (0,1) \Rightarrow 0 \in B$. Also note that the length of $(-r, 0)$ is completely dependent upon $r$ which was selected uniformly at random, so the length has likewise been selected uniformly at random.

4) Let $f:A \rightarrow B$ be a bijection where a constant $k \in A$ such that $f(a) = a - k$.* This step is to relate some $q_i$ to the element $0 \in B$ in a way that allows any $i \in \mathbb{N}$ a chance of being selected uniformly at random, just as $r$ and the length of $(-r, 0)$ were. There will be one and only one possible constant $k$ for any $r \in \mathbb{R}(0, 1)$ such that $f$ is a bijection given $f(a) = a - k$.

5) Let $C = \{ r + q : q \in B \}$. Note that $0 \in B \Rightarrow r \in C$.

6) Let $g:B \rightarrow C$ be a bijective function: $g(b) = b + r$. Note that $0 \in B \Rightarrow \exists g(0) = r$.

7) $\exists i \in \mathbb{N} : f(q_i) = 0 \Rightarrow g(f(q_i)) = g(0) = r$. Therefore, where $r$ was selected uniformly at random, so was $i$.

* The cardinality of A is equal to the cardinality of B, so a bijection can exist. There is something interesting here, however. Note that $z:\mathbb{R}(0,1) \rightarrow \mathbb{R}(-r, 1-r)$ is a bijection where $z(x) = x - r$, but $q \in A \Rightarrow z(q) \notin B$ if $r \notin \mathbb{Q}$ because any rational less an irrational is not rational. I therefore suggest that $\exists k \in A$ such that $f:A \rightarrow B$ is a bijection where $f(a) = a - k$. This poses the question, what is the result $t$ of the equation: $(1/3 - 0) - (f(1/3) - z(0)) = 1/3 - ((1/3 - k) - (0 - r)) = 1/3 - 1/3 + k - r = k - r = t$? What is unusual is that $k - r = t$ must be all but infinitesimal… It is the smallest difference between two disjoint “shifted copies” of the rational numbers in $\mathbb{R}$ \ $\mathbb{Q}$.

In keeping with the above definitions, we can continue:

1) For each $r \in \mathbb{R}(0,1)$, there will exist a constant $k \in A$ such that $f:A \rightarrow B$ is a bijection where $f(a) = a - k$.

2) A Vitali set $V$ would produce a different $k$ for each $v \in V$. More specifically, the length of $(0, k) = k$ will be unique for any element from each disjoint “shifted copy” of the rationals in the quotient group $\mathbb{R} / \mathbb{Q}$ (where each element of the quotient group is of a form $\mathbb{Q} + r = \{ r + q : q \in \mathbb{Q} \}$ for some $r \in \mathbb{R}$), and there exists one and only one $v \in V$ for each element of $\mathbb{R} / \mathbb{Q}$. Note: Vitali sets are usually restricted to [0, 1], not (0, 1), be we can trivially assume such a restriction to (0,1) here. I use them here for simplicity despite their creation relying on the axiom of choice, noting this proof could also be carried out without the use of Vitali sets and the axiom of choice.

3) For each $v \in V$, let $v \sim k \Rightarrow f(a) = a - k$ is a bijection from $A$ onto $B = \mathbb{Q} \cap (-v, 1-v)$.

4) Where each possible $k \in A$, the set $D = \{ k : \exists v \in V$ where $v \sim k \}$ has a cardinality equal to the cardinality of $\mathbb{N}$.

5) Let $d_1, d_2, d_3,$ … be an enumeration of $D$.

6) Let $\mathbb{R}(0,1) / \mathbb{Q} = \{ x \cap \mathbb{R}(0, 1) : x \in \mathbb{R} / \mathbb{Q} \}$. The elements of $\mathbb{R}(0,1) / \mathbb{Q}$ therefore partition $\mathbb{R}(0,1)$ by definition (just as $\mathbb{R} / \mathbb{Q}$ is a partition of $\mathbb{R}$) and each element of $\mathbb{R}(0,1) / \mathbb{Q}$ is enumerable because it is merely a shifted copy of $A$ equal to $v + B = C = \{ v + q : q \in B \}$ for some $v \in V$.

7) Let $E = \bigcup_{i = 1}^\infty (C_{d_i})$, where $C_{d_i} = \{ v + q : v \sim d_i \land q \in B = \mathbb{Q} \cap (-v, 1-v) \}$.

8 ) Each $C_{d_i}$ is enumerable by definition so the union $E$ is a countable union of countable sets that is also enumerable.

9) The union $E$ is also equal to $\mathbb{R}(0,1)$ because $\{ C_{d_i} : i \in \mathbb{N} \} = \mathbb{R}(0,1) / \mathbb{Q}$ is a partition of $\mathbb{R}(0,1)$ by definition.

10) The fact that $E$ is enumerable and $E = \mathbb{R}(0,1)$ by definition $\Rightarrow \mathbb{R}(0,1)$ is enumerable.

2. Dec 13, 2016

### andrewkirk

In step 4, $k$ must equal $r$ because if it's less (more) than $r$, the lowest (highest) numbers in $B$ will not be in the image of $f$. Since $k\in A$ we observe that it must be rational. So it is not true that there will be one $k$ for each $r$. When $r$ is irrational there will be no possible $k$.

I didn't read beyond there because I assume that in what follows it somewhere relies on that invalid claim.

To find the flaw in a purported proof like this, it often suffices to just look at every assertion of existence or uniqueness and question whether the proof justifies it. Not only is no justification offered for the claim in the last line of 4, but it is easy to see why the claim is incorrect.

3. Dec 13, 2016

### AplanisTophet

Thank you. How can I show this?

The length of (0, 1) is the same as the length of (-r, 1-r). If you shift the rationals in either of these two sets by any arbitrary constant, they should align with the intersection of an interval of length 1 and some element of the quotient group R/Q (where each element of the quotient group R/Q takes the form of a coset r + Q = { r + q : q is in Q }). We know that constant must be a rational number if going from A to B, so while I'm inclined to agree that this may be what is wrong I don't see how.

Also, we know that there is a bijection between A and B because they are both sets of rationals. Any predefined bijection should suffice for the first proof even if there is no such constant k as you say, so feel free to read on. If correct, you have successfully killed the second proof so that is good. In the unlikely event that you are incorrect, then the second proof should be much, much, much simpler (please read number 3 in its entirety):

1. Let $q_1, q_2, q_3,$ … be an enumeration of $A = \mathbb{Q} \cap \mathbb{R}(0, 1)$.

2. For any $r \in \mathbb{R}(0, 1)$, let $B_r = \mathbb{Q} \cap \mathbb{R}(-r, 1-r)$.

3. (This should be the faulty statement then --->) For each $r \in \mathbb{R}(0,1)$, there exists one and only one $k_r \in A$ such that $f:A \rightarrow B_r$ is a bijection where $f(a) = a - k_r$. Note that $z:\mathbb{R}(0, 1) \rightarrow \mathbb{R}(-r, 1-r)$ is a bijection where $z(x) = x – r$. If $q \in A \land r \notin A$, then $z(q) = q – r \notin B_r$ because the difference between a rational number and an irrational number is not a rational number. Therefore, $f(q) \neq z(q) \Rightarrow k_r – r = t \land t \neq 0$.

4. If $r, s \in \mathbb{R}(0,1)$, then $r \neq s \Rightarrow k_r \neq k_s$.

5. If $r, s \in \mathbb{R}(0,1)$, then $k_r \neq k_s \Rightarrow r \neq s$.

6. Therefore, $r, s \in \mathbb{R}(0,1) \land r \neq s \iff k_r \neq k_s$. Let $g(k_r) = r$ for any $r \in \mathbb{R}(0, 1)$.

7. Let $C = g(q_1), g(q_2), g(q_3),$ … = $\mathbb{R}(0,1)$.

4. Dec 13, 2016

### andrewkirk

If $k<r$ then, because the rational numbers are dense in the reals, there exists a rational number $c$ such that $-r<c<-k$. This $c$ is in $B$ but is not in the image of $f$ because if $f(a)=c$ then $a=c+k\leq -k+k=0$ so $a$ is not in $A$.

The argument for the case $k>r$ is very similar, just changing a few signs and directions.

5. Dec 13, 2016

### andrewkirk

As identified earlier, investigate any claim that is not proven to be true - regardless of how much it may `feel' as if it should be true. This is such a claim. There is no justification for the claim that $k_r\in A$. I doubt it is true. If it leads to a conclusion that Cantor's Theorem is false then we know it is not true, since we have a proof of Cantor's Theorem (Reductio as Absurdam).

6. Dec 13, 2016

### AplanisTophet

Thank you again. Unfortunately, $k_r < c < r \Rightarrow c$ cannot exist because $1 – c > 1 – r \Rightarrow (1 – c) \notin B_r$ despite your ability to assert that if such a $c$ did exist then $a = c + k_r < 0$ when $c$ is negative. Likewise, $r < c < k_r \Rightarrow c$ cannot exist because $-c < -r \Rightarrow c \notin B_r$ despite your ability to assert that if such a $c$ did exist then $a = c + k_r > 1$ when $c$ is positive. The former argument is “shifted” too far to the right while the latter is “shifted” too far to the left but group theory demands that there is a $k_r$ that is just right as I’ll show the proof for below. On the other hand, $k_r > r$ can exist because $f(a) = a - k_r > -r$ and likewise $k_r < r$ can exist because $f(a) = a - k_r < 1 - r$. Therein lies the rub because you are of course correct in that the rationals are dense so if $k_r – r \neq 0$ what is going on?

IMHO, this ‘proof’ is clever if nothing else but appears remarkable in that $k_r – r = t$ literally is defined to be the smallest difference between any two correlating elements of “shifted copies” of the rationals in $\mathbb{R}/\mathbb{Q}$. The number $t$ is the rough equivalent of $dx$ itself (it technically would be in some cases thus allowing for the supposed enumeration of $\mathbb{R}(0, 1)$ assuming it were properly defined, not that I am asserting that at this point).

The proof of the existence of $k_r$ that you assert does not exist follows from the remainder of step 3 that you omitted from your quote above. Namely, $z(q) \notin B_r$ when $q \in A \land r \notin A$ necessitates the existence of $k_r$ based on group theory. Here is why:

1. Let $w, x \in A \land y, z \in B_r$ for an $r \in \mathbb{R}(0, 1)$ such that $w - x = y - z$.

2. Given the above, it is easily proven that $w - y = x - z = k \in \mathbb{Q}$.

3. Because the rationals are dense and the length of $(0, 1) = (-r, 1-r) = 1$, given any $q_a \in A$ there is a corresponding $q_b \in B_r$ such that $X_{q_a} = \{ q_a - z : z \in A \} = X_{q_b} = \{ q_b - z : z \in B_r \}$. Let $q_a \sim q_b \Rightarrow X_{q_a} = X_{q_b}$.

4. If $w \sim y \land x \sim z$ in addition to their above properties from step 1, we can assert from step 2 that $k = k_r$.

Does this help to spell out my hesitation in accepting your logic? I assume we are correct in that something isn't right, but I trust you'll understand if I'm not quite ready to accept what you wrote despite seeing it too. This one is really making me think and I very much appreciate your consideration so far.

7. Dec 14, 2016

### andrewkirk

That 'because' is not correct. Since it was never assumed or asserted that $1-c$ is in $B_r$, no contradiction can be derived from the fact that it isn't. It was $c$ that we assumed was in $B_r$, not $1-c$.

8. Dec 14, 2016

### AplanisTophet

Yes, ok. I’ve thought it through now too. Thank you again. The way I see it is this. If (0, 1) is “shifted” to the left by a constant that is rational, we end up with a set that is (-rational, 1 – rational). The rationals contained on an interval defined by rationals cannot align with an interval defined by irrationals, e.g., (-irrational, 1-irrational). Interesting. :)

As for the first proof, I believe that still works if a proper way of defining a bijection in step 4 is defined. Surely a bijection can exist, but we want one to be 'predefined' so as to preserve the randomness. Just as a Vitali set can exist with one and only one element for each element of R/Q using the axiom of choice, we could use choice to select a bijection for each possible r prior to selecting it that would preserve the proof. What do you think? Does that mean if we accept the axiom of choice we can assert that it is possible to select a natural number uniformly at random? What's wrong there...?

9. Dec 14, 2016

### andrewkirk

That 'if' is the whole problem. Assuming that the remainder of the proof attempt is valid (which I have not checked) we know that no such bijection can exist, because if it did we would have arrived at a contradiction.

Intuition is a great thing, and indispensable in maths. But sometimes it can lead us astray, and we need to be careful of that. That is what seems to be happening here. You have an intuition that, because there is a bijection from A to B, there must also be a bijection of the particular type that you specify, which is $q\mapsto q-k_r$, where $k_r\in\mathbb Q$. That intuition is misleading. There is no bijection of that type if $r$ is not rational..

Consider the sets $\mathbb N$ and $\mathbb N\times \mathbb N$, where $\mathbb N$ is the natural numbers. There are plenty of bijections between these, for example, one ordering of the 2D set is (0,0), (0,1), (1,0), (2,0), (1,1),(0,2), (0,3),(1,2),(2,1),.... This zig-zag diagonal covering of the 2D number quadrant covers all the pairs that add to 0, then all that add to 1, then all that add to 2, and so on. But this bijection does not preserve the dictionary order of the 2D set. One might have an intuition that there must be some order-preserving bijection. But one would be wrong.

Including the axiom of choice in our system will not help. If it did, all it would mean is that ZFC is inconsistent.

10. Dec 14, 2016

### AplanisTophet

That's just it though: the type of bijection doesn't matter for the first proof. It just needs to be a bijection and we can forget all this $k_r$ nonsense (truly, I'm on board and I get it now thanks to you!), so could you please look over the first proof past step 4? More specifically, we know a bijection exists and any one will do, so the only crux for the proof to work is that the bijection must be at the ready prior to picking $r$ because defining the bijection after we pick $r$ kills the whole notion of randomness. That is why I suggested the axiom of choice (because we literally just need to assert the existence of a bijection in step 4 for each possible $B_r$, where any old bijection will do for each, prior to picking $r$).

11. Dec 14, 2016

### AplanisTophet

Here is what I mean (no $k_r$ funny business). Thank you again!

1) Let $q_1, q_2, q_3,$ … be an enumeration of $A = \mathbb{Q} \cap [0,1]$.

2) Let $V$ be a Vitali set, which contains one and only one element $v$ from each coset $\{ r + q : q \in \mathbb{Q} \} \in \mathbb{R}/\mathbb{Q}$ such that $0 \leq v \leq 1$. Note that the creation of a Vitali set requires use of the axiom of choice.

3) Select a real number $r \in [0,1]$ uniformly at random. Note: A common way of doing this cited by mathematicians is the theoretical flipping of a coin infinitely many times followed by some trivial 'clean-up' given that there are two binary expansions of each dyadic rational, e.g. 0.1 = 0.01111111...

4) Let $v_r \in V \Rightarrow v_r, r \in \{ r + q : q \in \mathbb{Q} \}$.

5) Let $B = \mathbb{Q} \cap [-|v_r-r|, 1-|v_r-r|]$. Note that $v, r \in [0,1] \Rightarrow 0 \in B$. Also note that the length of $[-|v-r|, 0]$ is dependent upon $r$, which was selected uniformly at random, so the length has likewise been selected uniformly at random.

6) Let $f:A \rightarrow B$ be a bijection such that $f(a) = a - |v_r-r|$.

7) Let $C = \{ r + q : q \in B \}$. Note that $0 \in B \Rightarrow r \in C$.

8) Let $g:B \rightarrow C$ be a bijective function: $g(b) = b + r$. Note that $0 \in B \Rightarrow \exists g(0) = r$.

9) $\exists i \in \mathbb{N} : f(q_i) = 0 \Rightarrow g(f(q_i)) = g(0) = r$. Therefore, where $r$ was selected uniformly at random, so was $i$.

12. Dec 14, 2016

### zinq

Aplanis Tophet: You wrote

"Let f:A→B be a bijection where a constant k∈A such that f(a)=a−k."

and

"The cardinality of A is equal to the cardinality of B, so a bijection can exist."

But wait: How do you know that a bijection not only exists, but exists of the form f(a) = a - k for some constant k ???

But suppose r is irrational, say r = √(1/2).

Then (-r, 1-r) is the interval (-√(1/2), 1-√(1/2)).

For any constant k, then if the map f(a) of the form f(a) = k-a is going to carry

Q ∩ (0, 1)​

bijectively onto

Q ∩ (-√(1/2), 1-√(1/2))​

then it must clearly have k = 1 - √(1/2).

But why must such a map carry rational numbers to rational numbers? For example, this f applied to a = 1/2 takes the value

f(1/2) = 1 - √(1/2) - 1/2 = 1/2 - √(1/2)​

which is not rational.

This shows to me that your original statement 4) makes a false assumption.

Last edited: Dec 14, 2016
13. Dec 14, 2016

### andrewkirk

I cannot understand (4). It is not clear whether it is a definition, a claim, or something else. It uses a symbol $v_r$ that has not been defined.

14. Dec 14, 2016

### AplanisTophet

4) Where $v \in V \land r \in \mathbb{R}[0, 1]$, if both $v$ and $r$ are also in $\{ r + q : q \in \mathbb{Q} \}$, then let $v = v_r$. Note that by definition of a Vitali set, there is one and only one $v \in V$ such that for any given $r \in \mathbb{R}[0, 1]$, $v \in \{ r + q : q \in \mathbb{Q} \} \Rightarrow v = v_r.$

15. Dec 14, 2016

### andrewkirk

The latest version doesn't seem to touch on Cantor at all. Note that $r-v_r$ is rational since they are both in the coset $r+\mathbb Q$, so we can write $r-v_r$ as $q(r)$. Then we have three sets:
$$A=\mathbb Q\cap[0,1]$$
$$B_r=A-q(r)$$
$$C_r=B_r+r=A+v_r$$
These three sets all have the cardinality of $\mathbb Q$.

How does that say anything about the cardinality of $\mathbb R$?

16. Dec 14, 2016

### AplanisTophet

It doesn't. The point is to select a natural number uniformly at random. This cannot be done in general because there is no uniform probability measure on the naturals where the sum of 0's is 0. Only the second proof dealt with cardinalities and we've debunked that one already. This is the first proof yet to be debunked.

17. Dec 14, 2016

### andrewkirk

What this is doing is, given a random $r\in[0,1]$, finding $h(r)$ which is the index, in an enumeration of $\mathbb Q$, of the rational number $r-v_r$.

Note that the map $h$ may be surjective, but it cannot be injective.

It would be necessary to formalise the statements about 'selected a number at random' in order to make a coherent claim about probability. 'Select at random' is not a well-defined concept. It is not at all clear what is meant by 'a uniform probability measure on the naturals'. I know what a probability measure is, but I don't know what adding the word 'uniform' does, if the sample space is not continuous.

EDIT: It might help to consider a much simpler surjective map from $\mathbb [0,1]$ to $\mathbb Q$. Let $f:\mathbb N\to\mathbb Q$ be a bijection. Define $g:[0,1]\to\mathbb N$ by $g(x)=n$ where $n$ is the largest natural number such that $x\leq 1-2^{-n}$. Then $h=f\circ g$ is a surjection from $[0,1]$ to $\mathbb Q$. If $U$ is a random variable that is uniformly distributed on $[0,1]$ then $X=h(U)$ is a random variable that takes values in $\mathbb Q$, with the probability of each value being $2^{-k}$ for some $k\in\mathbb N$. So every rational number has a nonzero probability of occurring as an outcome of $X$. But there is nothing unusual or contradictory about this.

Last edited: Dec 15, 2016
18. Dec 15, 2016

### AplanisTophet

Yes (well, it finds the index of $|v_r - r|$ in an enumeration of $\mathbb{Q} \cap [0, 1]$ and $r$ is selected uniformly at random, but close enough I suppose).

I think for this purpose, "selecting a number uniformly at random from a set" means that each number in the set has an equal chance of being selected given a method of selecting one and only one number from the set.

That is not going to select a natural uniformly at random given the above definition, no, so you're right, nothing unusual, but then again that is specifically why the proof does not do what you suggest... Make sense? I actually don't think there is anything wrong with the proof at this point. I believe you can in fact select a natural uniformly at random given the above definition of what it means to select a number uniformly at random and the stipulation that you may first select a real in [0, 1] uniformly at random. Maybe I'm wrong though.

19. Dec 15, 2016

### AplanisTophet

It figures that I'd say something wrong and only afterwards realize it, lol. There are only two ways in which $|v_r - r|$ can equal 1, but there are an infinite number of ways that it can be, say, 1/2. The distribution is therefore not uniform. Both proofs are debunked as they were written.

Thank you again for your time. I really respect it. These made me think quite a bit and without your help I'd probably have 'spun my wheels' quite a bit more than I did. Have a great weekend!