Uncountability of the Rationals?
in [Math]
|
Prev: Collatz conjecture
Next: Beginner-ish question
From: Transfer Principle on 18 Jun 2010 19:58 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. 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.
From: Transfer Principle on 18 Jun 2010 21:06 On Jun 18, 5: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: > >> "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. What I'm surprised is that _AP_ hasn't commented on this .sig quote yet, asking for someone to expunge it from Usenet. So far, AP isn't aware of this thread, or at least Hughes's use of AP quotes here. Whatever action AP was going to use to stop Hughes from using his quotes in the .sig randomizer, it obviously hasn't worked yet, since Hughes is still quoting AP in the .sig.
From: Tim Little on 18 Jun 2010 21:08 On 2010-06-18, Jesse F. Hughes <jesse(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
From: Transfer Principle on 18 Jun 2010 21:46 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. > > 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. 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. 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). 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.) 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+. > 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+. > > 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.
From: Transfer Principle on 18 Jun 2010 22:37
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. 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. 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. 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. |