Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Function Generator for Sequences of Reals
Posted:
Jun 22, 2013 8:43 AM


Brief Introduction
Below are listed steps for purposes of analyzing different Ai. Step 5 is optional and is for testing a cardinality argument. This paper is comprised of 5 steps, a conclusion, and a footnote entitled "Function f and Cantor's Theorem." Steps 1 through 4 are basic definitions and processes. Step 5 is a simple test to check whether function f (defined in step 3) is a surjection or not.
Step 1)
Let D be the set of all dyadic rationals greater than 0 and less than 1 (work in binary). For visually considering results after step 5, also define the sets Fn. Start with a list of countable sets F1, F2, ..., where each Fn is equal to the set of all dyadic rationals containing "n" number of 1's and the union of all Fn would equal D:
F1 = { 0.1, 0.01, 0.001, 0.0001, ...} F2 = { 0.11, 0.101, 0.1001, ..., 0.011, 0.0101, 0.01001, ..., 0.0011, 0.00101, 0.001001, ...} F3 = { 0.111, 0.1101, 0.11001, ...,} . . .
Step 2)
Define the set I:
The set I is analagous to the set of all binary strings with infinitely many ones. The set I is equal to the set of all reals greater than 0 and less than or equal to 1 only if all elements are expressed as infinitely large binary strings, where dyadic rationals and the number one are expressed as:
1 = 0.111... 0.1 = 0.0111... 0.101 = 0.100111...
and the unordered set I would look something like:
I = {0.111..., 0.1010101..., 0.111000111..., i in I}.
Define the set RI:
The set RI follows naturally from the set I and is best illustrated by example as opposed to a rigorous definition. For all elements of RI, there is one and only one element of I that naturally corresponds to it. Define RI by example and then let function 'k' be a bijection going from I to RI and let its inverse function 'h' be a bijection going from RI to I:
0.111... <> { 0.1, 0.11, 0.111, ... }, where k(0.111...) = { 0.1, 0.11, 0.111, ... } 0.10101... <> { 0.1, 0.101, 0.10101, ... }, where k(0.10101...) = { 0.1, 0.101, 0.10101, ... } 0.1101... <> { 0.1, 0.11, 0.1101, ... }, where k(0.1101...) = { 0.1, 0.11, 0.1101, ... } ... i in I <> ri in RI
Step 3)
Define the sequence Ai:
The sequence Ai can be shown as a set and should have a cardinality equal to or less than aleph null (the smallist infinite cardinal). Each element of Ai should be an element of 'I'.
Ai = i1, i2, i3, ... , i_n, where i_n is in I
Define the function g:
Function g goes from D to RI.
Formally: For any dyadic d in D, g(d) is equal to ri in RI such that d is in ri, h(ri) = i_n in Ai, and there does not exist an element i_(x < n) of Ai such that d is in k(i_(x < n))
I will illustrate through three iterations:
If 0.111... is the first iterated real of Ai:
g(0.1) = {0.1, 0.11, 0.111, ...} g(0.11) = {0.1, 0.11, 0.111, ...} g(0.111) = {0.1, 0.11, 0.111, ...} . . .
If 0.10101... is the second iterated real of Ai, and 0.1 has already been related to 0.111... above:
g(0.101) = {0.1, 0.101, 0.10101, ...} g(0.10101) = {0.1, 0.101, 0.10101, ...} . . .
If 0.101101... is the third iterated real of Ai, and 0.1 and 0.101 have already been related above:
g(0.1011) = {0.1, 0.101, 0.1011, ...} g(0.101101) = {0.1, 0.101, 0.1011, ...} . . .
... and so on.
Define Function f: (See Footnote 1 for applicability of Cantor's Theorem)
f = h(g()), where f(d) = i, d is in D, and i is in I
Visually the sets Fn can be "covered." Example, if i1 = 0.111...:
k(0.111...) = {0.1, 0.11, 0.111, ...}, "covering" the sets Fn as follows:
F1 = { [0.1], 0.01, 0.001, 0.0001, ...}, where 0.1 is "covered" by 0.111..., F2 = { [0.11], 0.101, 0.1001, ..., 0.011, 0.0101, 0.01001, ..., 0.0011, 0.00101, 0.001001, ...}, where 0.11 is "covered" by 0.111..., F3 = { [0.111], 0.1101, 0.11001, ...,}, where 0.111 is is "covered" by 0.111..., . . .
Step 4)
Define A = { d : f(d) = i1 } U { d : f(d) = i2 } U { d : f(d) = i3 } U ... U { d : f(d) = i_n }
A will always have a cardinality equal to aleph null so long as Ai contains one element. If Ai contains enough elements, A = D.
Define "Complete"
Step 4 is considered complete if and only if A = D.
Step 5)
This step is the optional cardinality test. It is important to realize, for purposes of our test, what we know, what we don't, and what our test can be expected to achieve. We want to test an arbitrary real to see if it has been included in an Ai. The example uses 0.111... for simplicity. The result is a yes or no answer.
First lets run a full scale example of steps 1 through 4 so we can proceed:
Ai = i1, i2, i3, ... (selected "randomly" for purposes of step 5)
i1 = 0.1011... relates to i1D = { 0.1, 0.101, 0.1011, ...} i2 = 0.0011... relates to i2D = { 0.001, 0.0011, 0.0011..., ...} i3 = 0.1101... relates to i3D = { 0.11, 0.1101, ...} (where 0.1 was related to i1) i4 = 0.11101... relates to i4D = { 0.111, 0.11101, ...} (where 0.1 was related to i1 and 0.11 to i3). . . Assume Step 4 is complete as defined in step 4.
Let A = i1D U i2D U i3D U ...
A) We assume yes, 0.111... is an element of Ai, and there is no contradiction. A = D. For now, the possibility that 0.111... was iterated remains open.
B) We assume no, 0.111... is not an element of Ai, and then see if our assumption results in any contradictions. The answer is yes, a contradiction results. How does the contradiction result? This part is probably the trickiest of the proof:
b1) Check what happened to the dyadics relatable to 0.111...:
0.1 was related to i1, so i1 becomes a: i1 = a 0.11 was related to i3, so i3 becomes b: i3 = b 0.111 was related to i4, so i4 becomes c: i4 = c and so on...
Notice that now b is closer to 0.111... than a, c is closer than b, and so on. The sequence a, b, c, ... is well ordered. Ai must be at most a countably infinite set, so we know that the sequence a, b, c, ... must in turn be a finite sequence with a last term.
b2) We are now free to define sequence (set) Bi and set B:
Bi = Ai U {0.111...} (where Bi has been shown as a set and not a sequence for simplicity)
B = A U {0.1, 0.11, 0.111, ...}
We note that B and Bi are countable, so if Ai is replaced with Bi, there must be dyadic rationals that are related to each element of Bi, and for each element of Bi, there will be at least one (probably an infinitely many) number of dyadic rationals that are related to it and only it, including our test number.
b3) We can now compare Bi to Ai. As an optional step, we can well order Ai and Bi to ensure our tested number is the last element of the set Bi. We know that Bi contains our tested number while Ai may or may not. We necessarily assume Ai does not, so in turn, we must presume that Bi results in at least one dyadic rational having been related to our test number while Ai presumably does not.
b4) Having related at least one dyadic to our test number and to no other real number as a result of iterating Bi, we can now compare A to B. Because we well ordered Ai and Bi for simplicity, we know that 0.111... was the last element of Bi iterated. We know that Ai is a subset of Bi, and that all elements of Ai are related to exactly the same dyadic rationals as Bi, so in turn A is a subset of B. The fact that at least one dyadic is related to our test number when it was the last number iterated is proof that B  A is not empty.
b5) If B  A is not empty, then B contains more elements of D than A does
b6) If B contains more elements of D than A does, we can assume A does not equal D
b7) If A does not equal D, then step 4 was not complete
b8) If step 4 was not complete, then we have a contradiction, as step 4 is necessarily complete before we can assume that our test number was not included in Ai.
C) Conclusion: If we assume 0.111... was an element of Ai and A = D, there is no contradiction. If we assume 0.111... was not an element of Ai, we end up with the contradiction that step 4 is not complete and A does not equal D. We therefore conclude that 0.111... was in fact an element of Ai. The answer is "Yes".
Overall Conclusion
Function f, as defined in step 3, is a surjection from the set D onto the set I if each element of D is related to an element of I and all elements of I are related to one or more elements of D. Step 5 tests whether an element of the set I could be omitted from a set Ai if A = D and step 4 is complete. Step 5 proves by contradiction that no element of I can be omitted from the set Ai if A = D and step 4 is complete. It is concluded that function f is a surjection from the set D onto the set I.
Foot Note 1, Function f and Cantors Theorem
From Step 3: Step 3 defines function f where f(d) = i, d is in D, and i is in I.
Function f has two parts. I will break them into function g and function h so the iteration process can be detailed.
Function g goes from D to RI. It is illustrated again through three iterations:
If 0.111... is the first iterated real of Ai (Ai is defined in part 5):
g(0.1) = {0.1, 0.11, 0.111, ...} g(0.11) = {0.1, 0.11, 0.111, ...} g(0.111) = {0.1, 0.11, 0.111, ...} . . .
If 0.10101... is the second iterated real of Ai, and 0.1 has already been related to 0.111...:
g(0.101) = {0.1, 0.101, 0.10101, ...} g(0.10101) = {0.1, 0.101, 0.10101, ...} . . .
If 0.101101... is the third iterated real of Ai, and 0.1 and 0.101 have already been related above:
g(0.1011) = {0.1, 0.101, 0.1011, ...} g(0.101101) = {0.1, 0.101, 0.1011, ...} . . .
... and so on.
Function h goes from RI to I:
{0.1, 0.11, 0.111, ...} > 0.111... {0.1, 0.101, 0.10101, ...} > 0.10101... {0.1, 0.101, 0.1011, ...} > 0.101101... . . . ri in RI > i in I
Function f can then be defined:
f = h(g()), where f(d) = i, d is in D and i is in I
To directly address Cantor's Theorem:
Let function g go from D to RI.
Define Cantor's A = { d : d is not an element of g(d) }, where d is in D and g(d) is equal to some element ri, ri is in RI.
Cantor's A = {} every time, regardless of the Ai selected. Cantor's Theorem cannot be relied upon to show that function 'g' cannot be a surjection from D onto RI. One must assume that Cantor's diagonal argument then may prevent Ai from being listed so that all elements of the set I are included, but to test that assumption, one should go to step 5.
Message was edited by: Brendon Krause
Message was edited by: Brendon Krause
Message was edited by: Brendon Krause



