Uncountability of the Rationals?
in [Math]
|
Prev: Collatz conjecture
Next: Beginner-ish question
From: Tony Orlow on 20 Jun 2010 07:12 On Jun 18, 8:52 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Tony Orlow <t...(a)lightlink.com> writes: > > On Jun 16, 11:00 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> Transfer Principle <lwal...(a)lausd.net> writes: > >> > On Jun 16, 8:08 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> >> Tony Orlow <t...(a)lightlink.com> writes: > >> >> > Actually, I meant a general formulaic relation, not necessarily > >> >> > algebraic, but with an inverse function that can be determined through > >> >> > algebra, not necessarily restricted to polynomials, but also including > >> >> > exponents and logs, etc. > >> >> That's not very explicit. > > >> > How about this: > > >> > An algebraic function is a real-valued function which is the > >> > composition of finitely many real-valued polynomial, radical, > >> > rational, exponential, and logarithmic functions, and whose > >> > inverse (or at least the real-valued branches thereof) is > >> > also the composition of finitely many polynomial, radical, > >> > rational, exponential, and logarithmic functions. > > >> Yes, that's explicit. > > >> And, who knows, it might be what Tony meant. Perhaps he'll say so. > > > That list probably covers the gamut, at least for now. So, I guess I > > didn't misuse "algebraic" after all. > > Yes, you did misuse "algebraic". In my experience, an algebraic > function is one which preserves certain algebraic structure. > > But no matter. We'll assume that Walker's definition of "algebraic > bijection" is what you "probably" (probably?) meant. > > I guess it will follow that the set P of primes has no size, since there > is no algebraic bijections between P and N+? http://primes.utm.edu/howmany.shtml "The Prime Number Theorem: The number of primes not exceeding x is asymptotic to x/log x." So, let's say tav/log(tav). > > >> "Am I am [sic] misanthrope? I would say no, for honestly I never heard > >> of this word until about 1994 or thereabouts on the Internet reading a > >> post from someone who called someone a misanthrope." > >> -- Archimedes Plutonium > > I don't know the meaning of the word "crank". Therefore I cannot be > > one. QED. ;) > > You're not really required to comment on every .sig quote. Feel free, I > suppose, but don't feel compelled. > It's a free country, or newsgroup, or whatever. > -- > Jesse F. Hughes > > "I guess it's a passable day to die." > -- Lt. Dwarf, /Star Wreck:In the Pirkinning"- Hide quoted text - Tony
From: Tony Orlow on 20 Jun 2010 07:55 On Jun 18, 7:58 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > On Jun 18, 5:12 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > > > Tim Little <t...(a)little-possums.net> writes: > > > Such a sequence can be obtained by taking successive logarithms of > > > absolute values, noting the signs at each step. For example, 3 is > > > approximated to eight decimal digits by > > > 2^2^2^-2^-2^-2^-2^2^-2^2^-2^2^-2^-2^2^2^-2^2^-2^2^2^-2^2^-2^2^-2^2^-2^-2^2^0 > > Ah yes, I mentioned something like this much earlier in this thread. > > But here's the problem that I mentioned earlier. To find on the TO > tree this number that Little has found, we must read this number > from right to left. So we begin at the 0, then take the 2 path to > reach 2^0 = 1. Then we take the -2 path to read -2^1 = -2. Then we > take the -2 path again to reach -2^-2 = -1/4. Then we take the 2 > path to reach 2^-1/4 = 1/sqrt(sqrt(2)). Then we take the -2 path > to reach -2^(1/sqrt(sqrt(2)), and so on. > > But let's say we wanted to obtain 3 to nine digits of accuracy > rather than eight. Taking a few more lg's, we obtain: > > 2^2^2^-2^-2^-2^-2^2^-2^2^-2^2^-2^-2^2^2^-2^2^-2^2^2^-2^2^-2^2^-2^2^-2^-2^2^-2^2^2^-2^0 > > But this defines a completely different path on the tree. Now, we > must start at 0 and take the -2 path to -2^0 = -1. (Recall that > for eight digits, we started on the 2 path to 2^0 = 1). Then we > take the 2 path to reach 2^-1 = 1/2. Then we take the 2 path again > to reach 2^(1/2) = sqrt(2). Then we take the -2 path to reach > -2^sqrt(2), and so on. > > And now we can see what the problem is. Taking lg's gives us the > signs in the power tower from left to right, but we determine > which path to take from right to left. So if we were to find the > complete infinite sequence of signs: > > 2^2^2^-2^-2^-2^-2^2^-2^2^-2^2^-2^-2^2^2^-2^2^-2^2^2^-2^2^-2^2^... > > there is no rightmost sign, so we can't even tell which part of > the tree to start with from zero. Okay. I think I see from your objection here what Tim and you are talking about as far as approximating a value like 3. There is sort of a way to get arbitrarily close to 3 as far as some finite sequence is concerned, but it involves "moving" the root node relative to the "final" node, so the beginning of any such infinite sequence remains elusive. On the other hand, the parent node of every H-riffic h (second definition, including negatives) can be calculated as log_2(|h|). The bit (0 denoting child=2^parent, and 1 denoting child=-2^parent) can be determined by whether h is negative, in which case the parent of h is log_2(-h) and the bit is a 1. Otherwise it's a 0 and the parent is log_2(h). Clearly, all positives end in a 0 and all negatives in a 1, but how they begin is another matter, and I have my doubts as to whether following the parents back and reverse-calculating the bit string really converges on anything. Oh, well. They're interesting, but perhaps intractable in ways. We'll see. > > This doesn't happen when we try to locate 1/3 on WM's binary tree, > because the infinite paths of WM's tree are _Cauchy_sequences_ > whose value can be defined to be the limit of that sequence. The > paths of TO's tree go something like: > > {0, 1, -2, -1/4, 1/sqrt(sqrt(2)), -2^(1/sqrt(sqrt(2)), ...} > > which is decidedly _not_ a C-sequence. So if this were the start > of an infinite path, there's no way to determine its value. > > > > It is fairly easy to prove that a slightly modified lexicographic > > > order on distinct sign sequences agrees with the usual ordering on the > > > reals. Proving that distinct reals yield distinct sign sequences > > > requires somewhat more, but can be done by analysing stability under > > > iteration of log_2|x|. > > It's still not at all obvious to me, even with your example of 3 to > > eight digits, nor do I see easily how to modify lexicographic ordering > > to make it work out in the tree, but I am not quite curious enough to > > dig in and see. > > If you say that finite and infinite paths in Tony's tree correspond in > > a natural way to reals, and every real is thus represented, then I'll > > accept it. > > I agree with Hughes's skepticism that infinite paths in TO's tree > correspond to reals. Well, I am skeptical that any such path can be exactly determined, but it's an interesting question. 3 might be some sort of Hr-ffic "irrational", but it's interesting that, *if* there is an infinite path from 2 to 3, then this path can be further extended after that, to include 8, 1/8, etc. Thanks, anyway, Tim. Please feel free to correct us all, but I think they're right. Peace, Tony
From: Tony Orlow on 20 Jun 2010 08:00 On Jun 18, 9:08 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-18, Jesse F. Hughes <je...(a)phiwumbda.org> wrote: > > > It's still not at all obvious to me, even with your example of 3 to > > eight digits, nor do I see easily how to modify lexicographic ordering > > to make it work out in the tree, but I am not quite curious enough to > > dig in and see. > > Heh, fair enough. I must admit I had misgivings about spending more > than ten minutes on this. There did appear to be a slightly > interesting analogy between these sequences and something a little > like continued fractions. > > In both cases, you can form the sequence from a real by repeatedly > "splitting off" some information into the sequence and applying a > function at each step. In the case of continued fractions, it is the > integer part and 1/x. In the H-riffic case, it is the sign and > log_2(x). > > The only question in my mind was whether the iterated log_2|x| > function was able to provide distinct sequences for all reals. As it > happens, it can. It might be interesting to see if Tony can himself > provide support for this property or even explain why it is important. > > - Tim Are you sure it can? You didn't generate a unique sequence for 3, but produced a sequence, perhaps, that gets arbitrarily close to 3. Does your method produce the same string as would be reverse-calculated from the sign of the value at each point? Definitely, the countable end of any real H-riffic can be generated. The beginning of the bit string becomes the problem. Thanks, TOny
From: Tony Orlow on 20 Jun 2010 08:29 On Jun 18, 9:46 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > On Jun 18, 7:45 am, Tony Orlow <t...(a)lightlink.com> wrote: > > > > > > > On Jun 16, 11:31 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > > > So we drop the Axiom of Infinity from ZF. Why? It's > > > because TO wants all infinite sets in his theory to > > > adhere to his rules, yet Infinity proves the existence > > > of a set, namely standard omega, that doesn't adhere > > > to TO's rules. So we must drop Infinity. > > Well, wait a minute. I don't object to the set N or N+ or omega, as a > > construction. So, as far as I am concerned, the axiom of infinity can > > stay. I just wouldn't pretend that the set transitively closed under > > membership is necessarily the greatest model of the natural numbers. > > My rules don't say such a set doesn't exist - all countably infinite > > sets are measured with respect to N+ in my theory. What I object to is > > assigning this set some absolute size. What we need, really, is a > > primitive pertaining to |S|, the size of a set. Defining axioms would > > dictate how such a size works, and would differ between cardinality > > and Bigulosity. In Bigulosity, tav=|N+| is only a "virtual" or > > "relative" number, and not an absolute quantity in any sense, because > > of the following logic, which doesn't appear to violate any of ZFC > > that I have heard. > > Thank you. So in that case, we can start with full ZF (or even > ZFC) as the base theory. The set omega still exists and is the > cardinality (or ordinality, with aleph_0 being the corresponding > cardinality) of N+, but now we can assign Bigulosities to sets > as well. Two sets with the same cardinality can have different > Bigulosities, but two sets with the same Bigulosities must have > the same cardinality. > My pleasure. First, I should say, I am not partial to Choice, so I would like to say, at least tentatively, that Bigulosity should work with ZF, anyway. Othwerwise, we're good. :) > > > > But how can we state the ICI Schema in a manner that's > > > rigorous enough for Chandler and others? We notice > > > that the schemata labeled TA1 and TA2 are stated in > > > terms of real numbers, leading posters like MoeBlee > > > to ask for the definition of "<" and other symbols. For > > > after all, in standard theory, we start with omega and > > > define (rational numbers, then) real numbers, but here > > > there is no omega, so there aren't any reals yet. > > The definition of '<' is not at all difficult. It is an operation that > > follows the following rules: > > (a<b ^ b<c) -> a<c > > ~(a<b ^ b<a) ...or... (a<b) -> ~(b<a) > > ~(a<b v b<a) <-> (a=b) > > Likewise we can define the field axioms for the behavior of +, -, > > *, /, ^, and log to determine the behavior of such operators when > > applied in formulas. > > We can define ICI as: > > (Ea>0 : AneN+ f(n)-g(n)>a) -> ((AneN+ tav>n) -> (f(tav)>g(tav))) > > That is, "If there exists an 'a' greater than 0 such that for all > > positive naturals n, f(n)-g(n)>a, then if tav is greater than any > > finite, f(tav)>g(tav)". Here, really "tav" can be any ifinite set, > > countable or uncountable. > > OK. What I was hoping was that we could write the schema > in terms of the set theoretic primitive "e" (which stands > for membership), since this was related to some of the > objections expressed by MoeBlee, Chandler, and others. Well, I have to admit, I think Bigulosity is not strictly a "set" theory. I really think geometrical justifications for arithmetic operations have taken too much of a back seat, and that set-theoretic notions alone don't always lead to the richest results. The use of f and g are rather necessary here. Sorry. > > But, as we saw during the "phi" discussion, is that trying > to generalize leads to inconsistency. TO intends his ICI > schema to apply only to the "algebraic" formulas f and g, > and so this is what we will do for now. There seems to be a little friction over the use of the term "algebraic". We can just say a monotonically increasing or decreasing bijection with N+. > > TO states that "tav" could represent any set, which would > presumably include omega, but the problem is that ICI > would prove that 1+omega > omega, even though 1+omega is > equal to omega (regardless of whether "+" denotes cardinal > or ordinal addition). I would defined 'tav' as a primitive constant, the Bigulosity of N+. "Zillion" is also a primitive constant, the number of points in the unit line segment. > > There are two ways out of this dilemma. One way is to > restrict "tav" to the actual "tav," and not any arbitrary > set (so that "tav" is a primitive _constant_, not any sort > of _variable_). But what if we wanted to apply ICI to the > other infinity, "zillion" (as TO often desires)? We know > that TO considers "zillion" to be uncountable, but is > "zillion" related to "tav," perhaps by zillion = 2^tav or > some other relation? If so, then we can include "2^" as > part of the algebraic functions f and g (since to TO, > "algebraic" includes exponentiation) and keep "tav" as > the only infinity to which ICI applies. (For example, we > prove 1+zillion > zillion by letting f(x) = 1+2^x and > g(x) = 2^x in the ICI schema.) No, zillion=2^tav (or any finite relationship between tav and zillion) is inconsistent with Bigulosity. Each has to be declared separately. Sorry again. > > The other way is to consider the algebraic symbols "+", > "*", "<", etc., as primitives, with axioms defining these > to have their standard meanings in N+. Then we apply the > ICI to any infinite set, including omega, to prove that > 1+omega > omega -- so that therefore, the primitive "+" > corresponds to neither cardinal nor ordinal addition. But > nowhere in the axioms does it state that "+" must be > equivalent to either addition, only that they agree with > standard addition on N+. > Right. That's an important part of the approach, to extend the normal algebraic operators as consistently as possible to the infinite case. By preserving the field axioms as much as possible (if not entirely) I think we arrive at more intuitive conclusions. If, for instance, "x>0 <-> x+y>y" and "x+y = y+x" are considered axiomatic, they are inconsistent with cardinal and ordinal arithmetic, and no theory can preserve these axioms and entertain such a construction at the same time. > > > IFR can be stated, in terms of well formed formula g: > > |{x: x<=a ^ x>=b ^ g(x)eN+ ^ g(x+1)>g(x)}| = floor(g(b))-ceiling(g(a)) > > +1 > > (monotonically increasing) > > and > > |{x: x<=a ^ x>=b ^ g(x)eN+ ^ g(x+1)<g(x)}| = floor(g(a))-ceiling(g(b)) > > +1 > > (monotonically decreasing) > > Then, we can define IFR *with* ICI, and state that: > > |{x: g(x)eN+ ^ g(x+1)>g(x)}| = floor(g(tav))-ceiling(g(1))+1 (the > > floor() here is superfluous) > > and > > |{x: g(x)eN+ ^ g(x+1)<g(x)}| = floor(g(1))-ceiling(g(tav))+1 (now > > ceiling() is superfluous) > > Doesn't tht sound like a relatively valid outline? If we take the > > field axioms to be inviolable, then we have to discard certain > > conclusions of transfinite set theory as a result of ensuing > > contradictions, no? > > OK, so IFR gives us the Bigulosities of certain subsets of N+. No, more generally, ANY countably infinite set bijected with N+, not just subsets of N+. > > > > So somehow tav is finite, yet for every natural number m > > > we can prove that tav has m as an element? At first this > > > sounds like a contradiction, but it was mentioned in earlier > > > threads that: > > > For every natural number n, it is provable that tav contains n. > > > and > > > It is provable that for every natural number n, tav contains n. > > Is it true that AneN+ neN+? > > Of course. > > > > are distinct (in first-order logic at least -- I'm not sure about > > > second-order logic). But even so, this would make tav a > > > really strange set to contain every natural number as an > > > element, yet still somehow be "finite" -- and it certainly > > > doesn't describe tav as intended by TO. > > It sort of does, actually, but if you could please state your two > > English sentences there in FOL it might be illuminating. > > I believe that someone else can explain this better than I can, > but I remember someone mentioning that even if we have the > following infinitely many lines: > > |- phi(1) > |- phi(2) > |- phi(3) > |- phi(4) > |- phi(5) > ... > > where the turnstile denotes "is provable," and we have a line > > |- phi(n) > > for _every_ natural n, we still can't conclude: > > |- AneN+ phi(n) > > since the provability of the statement "AneN+ phi(n)" has > nothing to do with the provability of the statements "phi(n)" > for any, or even all, natural numbers n. > > I gathered this from a different thread a fairly long time > ago (at least a year). I don't recall an explicit example of > a theory T and a formula phi with one free variable n such > that T proves "phi(n)" for every natural number n, but not > the statement "AneN+ phi(n)". > > Of course "phi" is no longer relevant to TO's schema, so > this discussion doesn't really matter any more.- Hide quoted text - > Well, if you don't get it, Transfer, it's likely that it doesn't make sense. :) TOny
From: Tony Orlow on 20 Jun 2010 08:51
On Jun 18, 10:37 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > On Jun 17, 12:31 pm, Virgil <Vir...(a)home.esc> wrote: > > > > > David R Tribble wrote: > > > > >> So the question becomes, what axiom justifies your logical > > > > >> leap, applying a property of finite sets to infinite sets without > > > > >> largest members? > > > > Tony Orlow wrote: > > > > > There is no leap. > > Then there can be no difference between finite sets and infinite sets, > > thus everything true of finite sets must be true of infinite sets, thus > > all infinite sets must be finite since that is true of finite sets. > > At least following TO's logic. > > This is, incidentally, a problem that occurs with many posters > who want the properties of all finite sets to extend to all > infinite sets. In general, such posters want more properties > to extend from finite sets to infinite sets than standard > theory allows, but they certainly don't want the property of > _finiteness_ to extend to infinite sets! > > So we see how any schema of the form: > > (Ax (x finite -> phi(x)) -> Ax phi(x) > > fails if we let phi(x) be "x finite" (and, of course, at least > one infinite set exists). > > TO attempts to prevent this by preventing phi from being just > any function, but instead limiting the schema to _algebraic_ > functions using a few chosen operations. Hi Transfer - Actually, I avoid this conundrum by resticting my properties to statements of inequality among formulaically expressed quantities. By focusing on inequalities I am establishing quantitative order among different expressions, and by extending those expressions to the infinite case, I am concocting a method of distinguishing among different countable infinities. Whether they are technically algebraic or not is of little consequence. For the purposes of IFR it is only required that they be monotonic bijections between N+ and any set. N.B. In order to avoid contradiction with standard finite mathematics, it is further stipulated that the difference upon which the inequality is based not have a limit of 0 in the infinite case. If f(x)>g(x) for neN+, but lim(x->oo: f(x)-g(x))=0, ICI does not imply that f(tav)>g(tav), at least for standard purposes. If there exists some a>0 such that f(x)-g(x)>a for all xeN+, then ICI applies. > > Another way of preventing this problem is to come up with a > new primitive, "finite," a one-place predicate symbol. Then > we add axioms that correspond to properties that we expect > finite sets to have, such as: > > Axy ((x subset y & finite(y)) -> finite(x)) > > and, depending on what we are trying to accomplish, axioms > stating that the union or Cartesian product of finitely many > finite sets is finite, that singletons are finite, or > whatever we need. We may also add: > > ~finite(tav) (if this is based on TO's theory) > > Then we write the schema as, if phi doesn't contain the > symbol "finite," then all closures of: > > (Ax (finite(x) -> phi(x)) -> Ax phi(x) > > are axioms. > > What this tells us is that there is no formula phi without > the symbol "finite" such that phi(x) <-> finite(x), not > even if phi(x) is "x is finite" (for some standard > definition of finite such as Dedekind's). The axioms can > prescribe that finite(x) agrees with standard finiteness > for many common sets of ZFC, but not all of them without > leading to a contradiction. Right. We explored that a few years ago, and including the predicate "is finite" doesn't avoid all problems. > > If we try to write the schema that I've written earlier as: if > phi doesn't contain "finite" or "tav," then all closures of: > > (EneN+ (phi(n)) & Ax (phi(x) -> phi(xu{x}))) -> phi(tav) > > are axioms. > > Notice that according to this schema, we can prove that > tav is (standard/Dedekind) "finite," but that it contains > all natural numbers, and that ~finite(tav) as well. Well, I don't think that the argument regarding tav's ability to be finite or infinite requires any such schema. By elementary logic, no element of N+ will suffice for all of N+, so tav can't be finite. However, any such set must include an element equal to its size, if any such size exists, and the set has only finite numbers. Therefore the size tav also cannot be infinite. > > Keep in mind that TO prefers that we drop all this > discussion about "phi" and just stick to "algebraic" > formulas (as defined elsewhere in this thread). But then > I see the following: > > > > > By your logic, you state that all sets of the form {1,2,3,...,k} > > > > have a largest member, therefore sets of the form {1,2,3,...} > > > > also have a largest member. I assume you have an axiom > > > > or theorem in mind to help you reach this conclusion. > > But {1,2,3,...,k} with a largest member has nothing to do > with algebraic formulas at all. Indeed, it deals with > _sets_ of naturals, not naturals themselves. > > On the other hand, using the von Neumann definition of > naturals, each natural is the set of all of its > predecessors (including 0). The schema that I've written > above proves that since all naturals (starting from 1) > contain a largest element, tav also contains a largest > element -- and we can call that element "tav-1." > > Should we continue to use this schema, or should we use > the ICI schema as stated by TO? This schema contains > fewer primitives than TO's (if we require all the algebraic > symbols to be primitives, as I explain in another post), > but if this schema turns out to be inconsistent, then we > will need to use TO's and stick to algebraic functions. I'm not sure what was wrong with my statements of IFR and ICI and the combination thereof. TOny |