Dense Linear Ordering problems.
in [Math]
|
Prev: Is this a valid statement?
Next: lagrange identity
From: David C. Ullrich on 5 Dec 2009 09:23 On Sat, 05 Dec 2009 00:45:15 -0500, David Bernier <david250(a)videotron.ca> wrote: >Aatu Koskensilta wrote: >> David Bernier <david250(a)videotron.ca> writes: >> >>> And I still don't grasp "V = L" . >> >> What's unclear to you about "V = L"? >> > >I had a look at the article: >< http://en.wikipedia.org/wiki/Constructible_universe > . > >Suppose we have the function d: N -> N > >d(n) := n'th digit of pi (with d(0):= 3 ). > >Viewed as a relation on NxN, for each n, (n, d(n)) is in L_omega. > >Then say A = { (n, d(n)) , such that n in N }. > > >Probably A lies in some L_alpha, alpha not a large ordinal. > >I haven't thought much about this. The difficulty for me is in finding >a first-order formula with bounded quantifiers that defines A. Well surely you don't want to try to write down an explicit formula for this in the language of set theory - that would be very long and incomprehensible. There _are_ first-order formulas that "say" the following: N(n): n is a natural number Pair(x,y,z): z = (x,y) Pi(n,m): n, m are natural numbers and m is the n-th digit of pi (seems to me the fact that pi is irrational meams that a formula Pi exists that's simpler than, say, G(n,m), saying that m is the n-th digit of Euler's constant gamma - we have an actual algorithm for computing the n-th digit of pi, while.if it appear that the 20-th digit of gamma is 3 and then there's a large number of 9's it could be that they're actually all 9's from that point, so we never find out that the 20-th digit is really 4. So G(n,m) would involve something like "there exists a sequence of digits such that...", while Pi(n,m), it seems to me, only involves quantifying over natual numbers. This has some relevance to whether A is in L_{w+1} or not...) Then it seems to me that A is the set of z in L_w such that En Em (pair(n,m,z) & pi(n,m)) holds in L_w, hence A is in L_{w+1}. >David Bernier David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.)
From: David Bernier on 5 Dec 2009 10:44 David C. Ullrich wrote: > On Sat, 05 Dec 2009 00:45:15 -0500, David Bernier > <david250(a)videotron.ca> wrote: > >> Aatu Koskensilta wrote: >>> David Bernier <david250(a)videotron.ca> writes: >>> >>>> And I still don't grasp "V = L" . >>> What's unclear to you about "V = L"? >>> >> I had a look at the article: >> < http://en.wikipedia.org/wiki/Constructible_universe > . >> >> Suppose we have the function d: N -> N >> >> d(n) := n'th digit of pi (with d(0):= 3 ). >> >> Viewed as a relation on NxN, for each n, (n, d(n)) is in L_omega. >> >> Then say A = { (n, d(n)) , such that n in N }. >> >> >> Probably A lies in some L_alpha, alpha not a large ordinal. >> >> I haven't thought much about this. The difficulty for me is in finding >> a first-order formula with bounded quantifiers that defines A. > > Well surely you don't want to try to write down an explicit > formula for this in the language of set theory - that would be > very long and incomprehensible. > > There _are_ first-order formulas that "say" the following: > > N(n): n is a natural number > Pair(x,y,z): z = (x,y) > Pi(n,m): n, m are natural numbers and m is the n-th digit of pi > > (seems to me the fact that pi is irrational meams that a > formula Pi exists that's simpler than, say, G(n,m), > saying that m is the n-th digit of Euler's constant gamma - > we have an actual algorithm for computing the n-th digit > of pi, while.if it appear that the 20-th digit of gamma is 3 > and then there's a large number of 9's it could be that they're > actually all 9's from that point, so we never find out that > the 20-th digit is really 4. So G(n,m) would involve > something like "there exists a sequence of digits such > that...", while Pi(n,m), it seems to me, only involves > quantifying over natual numbers. This has some relevance > to whether A is in L_{w+1} or not...) > > Then it seems to me that A is the set of z in L_w such that > > En Em (pair(n,m,z) & pi(n,m)) > > holds in L_w, hence A is in L_{w+1}. [...] Yes. One section in Wikipedia says: "All arithmetical subsets of w and relations on w belong to L{w+1} (because the arithmetic definition gives one in L{w+1})". If we look at L_{w+1}, then there are countably many formulas phi with countably many choices of parameters z_1, ... z_n in L_w . So I think L_{w+1} is countably infinite if we accept ZFC to provide bijections. David Bernier
From: Bill Taylor on 5 Dec 2009 23:52 On Dec 6, 4:44 am, David Bernier <david...(a)videotron.ca> wrote: > So I think L_{w+1} is countably infinite if ... Is this correct? In fact, is it the case that L_alpha is countably infinite for all countable alpha? -- Wondering William
From: David Libert on 6 Dec 2009 03:21 Bill Taylor (w.taylor(a)math.canterbury.ac.nz) writes: > On Dec 6, 4:44 am, David Bernier <david...(a)videotron.ca> wrote: > >> So I think L_{w+1} is countably infinite if ... > > Is this correct? > > In fact, is it the case that L_alpha is countably infinite for all > countable alpha? > > -- Wondering William Yes. Well for all infinite countable alpha. -- David Libert ah170(a)FreeNet.Carleton.CA
From: David C. Ullrich on 6 Dec 2009 08:41
On Sat, 05 Dec 2009 10:44:24 -0500, David Bernier <david250(a)videotron.ca> wrote: >David C. Ullrich wrote: >> On Sat, 05 Dec 2009 00:45:15 -0500, David Bernier >> <david250(a)videotron.ca> wrote: >> >>> Aatu Koskensilta wrote: >>>> David Bernier <david250(a)videotron.ca> writes: >>>> >>>>> And I still don't grasp "V = L" . >>>> What's unclear to you about "V = L"? >>>> >>> I had a look at the article: >>> < http://en.wikipedia.org/wiki/Constructible_universe > . >>> >>> Suppose we have the function d: N -> N >>> >>> d(n) := n'th digit of pi (with d(0):= 3 ). >>> >>> Viewed as a relation on NxN, for each n, (n, d(n)) is in L_omega. >>> >>> Then say A = { (n, d(n)) , such that n in N }. >>> >>> >>> Probably A lies in some L_alpha, alpha not a large ordinal. >>> >>> I haven't thought much about this. The difficulty for me is in finding >>> a first-order formula with bounded quantifiers that defines A. >> >> Well surely you don't want to try to write down an explicit >> formula for this in the language of set theory - that would be >> very long and incomprehensible. >> >> There _are_ first-order formulas that "say" the following: >> >> N(n): n is a natural number >> Pair(x,y,z): z = (x,y) >> Pi(n,m): n, m are natural numbers and m is the n-th digit of pi >> >> (seems to me the fact that pi is irrational meams that a >> formula Pi exists that's simpler than, say, G(n,m), >> saying that m is the n-th digit of Euler's constant gamma - >> we have an actual algorithm for computing the n-th digit >> of pi, while.if it appear that the 20-th digit of gamma is 3 >> and then there's a large number of 9's it could be that they're >> actually all 9's from that point, so we never find out that >> the 20-th digit is really 4. So G(n,m) would involve >> something like "there exists a sequence of digits such >> that...", while Pi(n,m), it seems to me, only involves >> quantifying over natual numbers. This has some relevance >> to whether A is in L_{w+1} or not...) >> >> Then it seems to me that A is the set of z in L_w such that >> >> En Em (pair(n,m,z) & pi(n,m)) >> >> holds in L_w, hence A is in L_{w+1}. >[...] > >Yes. One section in Wikipedia says: > >"All arithmetical subsets of w and relations on w belong to L{w+1} >(because the arithmetic definition gives one in L{w+1})". > >If we look at L_{w+1}, then there are countably many formulas phi >with countably many choices of parameters z_1, ... z_n in L_w . > >So I think L_{w+1} is countably infinite if we accept > >ZFC to provide bijections. Yes. In fact there's no need for AC here. An explicit enumeration of L_w and an explicit enumeration of the first0order formulas give an explicit enumeration of L_{w+1}/ >David Bernier David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.) |