Dense Linear Ordering problems.
Bill Taylor
Conjecture 1:
==========
Any countable dense linear ordering with no end-points
is order-isomorphic to any other.
This is easily proved with AC, is that right?
In fact, it only needs DC, is that right?
But CC is not sufficient, is that right? (I'd guess this is hard.)
_________________
Conjecture 2:
===========
Any subset of the reals with the usual ordering,
and continuum many elements in every interval,
is order-isomorphic to any other.
Is this true? Easily proved?
If we merely say they must have uncountably many
elements in every interval, is it still true - and do we need
to assume CH for this?
I presume we still need AC for this set of results - is it so?
-- Baffled Bill
Virgil
<0b7f88ea-b4bf-4b70...@u18g2000pro.googlegroups.com>,
Bill Taylor <w.ta...@math.canterbury.ac.nz> wrote:
> I have two clusters of questions.
>
> Conjecture 1:
> ==========
> Any countable dense linear ordering with no end-points
> is order-isomorphic to any other.
>
> This is easily proved with AC, is that right?
>
> In fact, it only needs DC, is that right?
>
> But CC is not sufficient, is that right? (I'd guess this is hard.)
> _________________
>
> Conjecture 2:
> ===========
> Any subset of the reals with the usual ordering,
> and continuum many elements in every interval,
> is order-isomorphic to any other.
>
> Is this true? Easily proved?
It is false.
Consider the standard reals, R, and the set of non-zero reals, S. Both R
and S satisfy your criteria, BUT:
Note that in R every set which is bounded above has a least upper bound
in R
Note that in S there are many sets which are bounded above but which
have no least upper bound in S.
Since order isomorphisms must carry least upper bounds to least upper
bounds, R and S cannot be order-isomorphic.
Butch Malahide
wrote:
> I have two clusters of questions.
>
> Conjecture 1:
> ==========
> Any countable dense linear ordering with no end-points
> is order-isomorphic to any other.
A theorem of Cantor, the first use of the famous back-and-forth
method.
> This is easily proved with AC, is that right?
>
> In fact, it only needs DC, is that right?
>
> But CC is not sufficient, is that right? (I'd guess this is hard.)
*No* choice is needed, this is a ZF theorem. You don't need the axiom
of choice to choose elements from *countable* sets!
> _________________
>
> Conjecture 2:
> ===========
> Any subset of the reals with the usual ordering,
> and continuum many elements in every interval,
> is order-isomorphic to any other.
>
> Is this true? Easily proved?
Blatantly false. The set of all irrational numbers is not order-
isomorphic to the set of all real numbers.
William Elliot
> On Nov 23, 11:11�pm, Bill Taylor wrote:
>> Any countable dense linear ordering with no end-points
>> is order-isomorphic to any other.
>
> A theorem of Cantor, the first use of the famous back-and-forth
> method.
>
Here's a proof not needing the back and forth method.
Top and bottom elements can be added and removed afterwards.
Let S = { s0, s1, ... } be a countable linear order with
s0 = bottom, s1 = top.
Let D = Z[1/2] /\ [0,1]
Define f:S -> D by induction:
f(s0) = 0, f(s1) = 1
and for k > 1, let
bk = max { sj | j < k, sj < sk }
tk = min { sj | j < k, sk < sj }
f(sk) = (f(bk) + f(tk))/2
It can be show that f is an increasing injection.
Now assume that S is dense. To show f is an injection,
the following intuitively apparent lemma is needed.
If f(sj) = (p-1)/2^m, f(sk) = p/2^m, p,m in N,
and sn = s_n in (sj,sk), then j,k < n.
To simplify the lemma,
let n = min{ n | sn in (sj,sk) } and show j,k < n.
That's possible since sj < sk and (S,<=) is dense linear order.
I dislike proclaiming by construction, j,k < n.
Would you help with proofing the lemma?
----
David C. Ullrich
<fred....@gmail.com> wrote:
>On Nov 23, 11:11�pm, Bill Taylor <w.tay...@math.canterbury.ac.nz>
>wrote:
>> I have two clusters of questions.
>>
>> Conjecture 1:
>> ==========
>> Any countable dense linear ordering with no end-points
>> is order-isomorphic to any other.
>
>A theorem of Cantor, the first use of the famous back-and-forth
>method.
>
>> This is easily proved with AC, is that right?
>>
>> In fact, it only needs DC, is that right?
>>
>> But CC is not sufficient, is that right? �(I'd guess this is hard.)
>
>*No* choice is needed, this is a ZF theorem. You don't need the axiom
>of choice to choose elements from *countable* sets!
That last bit is unfortunately phrased - it can happen that you need
AC to choose elements from finite sets.
What's true is that if S is countable then you don't need AC
to choose elements of subsets of S. (Which of course suffices
to show that no AC is needed above.)
>> _________________
>>
>> Conjecture 2:
>> ===========
>> Any subset of the reals with the usual ordering,
>> and continuum many elements in every interval,
>> is order-isomorphic to any other.
>>
>> Is this true? �Easily proved?
>
>Blatantly false. The set of all irrational numbers is not order-
>isomorphic to the set of all real numbers.
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.)
Butch Malahide
> On Mon, 23 Nov 2009 22:00:20 -0800 (PST), Butch Malahide
>
>
>
>
>
> <fred.gal...@gmail.com> wrote:
> >On Nov 23, 11:11 pm, Bill Taylor <w.tay...@math.canterbury.ac.nz>
> >wrote:
> >> I have two clusters of questions.
>
> >> Conjecture 1:
> >> ==========
> >> Any countable dense linear ordering with no end-points
> >> is order-isomorphic to any other.
>
> >A theorem of Cantor, the first use of the famous back-and-forth
> >method.
>
> >> This is easily proved with AC, is that right?
>
> >> In fact, it only needs DC, is that right?
>
> >> But CC is not sufficient, is that right? (I'd guess this is hard.)
>
> >*No* choice is needed, this is a ZF theorem. You don't need the axiom
> >of choice to choose elements from *countable* sets!
>
> That last bit is unfortunately phrased - it can happen that you need
> AC to choose elements from finite sets.
>
> What's true is that if S is countable then you don't need AC
> to choose elements of subsets of S. (Which of course suffices
> to show that no AC is needed above.)
Good point. Thanks for the correction.
Bill Taylor
Butch Malahide <fred.gal...@gmail.com> wrote:
> > Any countable dense linear ordering with no end-points
> > is order-isomorphic to any other.
>
> A theorem of Cantor, the first use of the famous back-and-forth
> method. *No* choice is needed,
Of course! Silly me, I should have seen that myself.
......................
> > Any subset of the reals with the usual ordering,
> > and continuum many elements in every interval,
> > is order-isomorphic to any other.
> Blatantly false.
Of course; now let me update it with the question I *meant* to ask!
Consider subsets of the reals such that both the subset and
its complement are continuum many in every interval.
Are any two such subsets order-iromorphic?
I know that one can produce set-pairs like that which are of
zero/full measure, or which are full/sparse category; but I'm
not sure if that necessarily prevents them from being
order-isomorphic.
-- Wondering William
Butch Malahide
wrote:
>
> Consider subsets of the reals such that both the subset and
> its complement are continuum many in every interval.
>
No, but the counterexample won't impress you, because it uses AC.
Since you're not going to accept the example anyway, I'll just sketch
the argument.
Recall that a subset of R is "totally imperfect" if it contains no
perfect set (and therefore no uncountable Borel set of any type.) Use
AC to obtain a so-called Bernstein decomposition of R, i.e., a totally
imperfect set A whose complement B = R\A is also totally imperfect.
(Needless to say, they are nonmeasurable sets.) Of course each of the
sets A and B contains continuum many points in every interval. As far
as I know, A and B may be order-isomorphic. Now, let C be the Cantor
set, and consider the set X = A union C and its complement Y = B\C.
The modified sets X and Y still contain continuum many points in each
interval. I claim that X and Y are not isomorphic. To see this,
observe that X contains a subset which is order-isomorphic to R (in
fact C contains such a subset), while Y, being totally imperfect,
contains no subset order-isomorphic to R.
David C. Ullrich
<fred....@gmail.com> wrote:
>On Nov 25, 10:05�pm, Bill Taylor <w.tay...@math.canterbury.ac.nz>
>wrote:
>>
>> Consider subsets of the reals such that both the subset and
>> its complement are continuum many in every interval.
>>
>> Are any two such subsets order-isomorphic? [Spelling typo corrected.]
>
>No, but the counterexample won't impress you, because it uses AC.
A counterexample that depends on AC _should_ be of interest
even to people who don't "accept" AC! If AC implies that
there is no gazebo then it follows, whether one accepts
AC or not, that the existence of a gazebo cannot be proved
in ZF.
>Since you're not going to accept the example anyway, I'll just sketch
>the argument.
>
>Recall that a subset of R is "totally imperfect" if it contains no
>perfect set (and therefore no uncountable Borel set of any type.) Use
>AC to obtain a so-called Bernstein decomposition of R, i.e., a totally
>imperfect set A whose complement B = R\A is also totally imperfect.
>(Needless to say, they are nonmeasurable sets.) Of course each of the
>sets A and B contains continuum many points in every interval. As far
>as I know, A and B may be order-isomorphic. Now, let C be the Cantor
>set, and consider the set X = A union C and its complement Y = B\C.
>The modified sets X and Y still contain continuum many points in each
>interval. I claim that X and Y are not isomorphic. To see this,
>observe that X contains a subset which is order-isomorphic to R (in
>fact C contains such a subset), while Y, being totally imperfect,
>contains no subset order-isomorphic to R.
David C. Ullrich
Virgil
David C. Ullrich <dull...@sprynet.com> wrote:
> On Thu, 26 Nov 2009 01:27:20 -0800 (PST), Butch Malahide
> <fred....@gmail.com> wrote:
>
> >On Nov 25, 10:05�pm, Bill Taylor <w.tay...@math.canterbury.ac.nz>
> >wrote:
> >>
> >> Consider subsets of the reals such that both the subset and
> >> its complement are continuum many in every interval.
> >>
> >> Are any two such subsets order-isomorphic? [Spelling typo corrected.]
> >
> >No, but the counterexample won't impress you, because it uses AC.
>
> A counterexample that depends on AC _should_ be of interest
> even to people who don't "accept" AC! If AC implies that
> there is no gazebo then it follows, whether one accepts
> AC or not, that the existence of a gazebo cannot be proved
> in ZF.
Nice! And nicely sneaky!!
David Bernier
> In article<m9atg5h0jvcun23n7...@4ax.com>,
> David C. Ullrich<dull...@sprynet.com> wrote:
>
>> On Thu, 26 Nov 2009 01:27:20 -0800 (PST), Butch Malahide
>> <fred....@gmail.com> wrote:
>>
>>> On Nov 25, 10:05 pm, Bill Taylor<w.tay...@math.canterbury.ac.nz>
>>> wrote:
>>>>
>>>> Consider subsets of the reals such that both the subset and
>>>> its complement are continuum many in every interval.
>>>>
>>>> Are any two such subsets order-isomorphic? [Spelling typo corrected.]
>>>
>>> No, but the counterexample won't impress you, because it uses AC.
>>
>> A counterexample that depends on AC _should_ be of interest
>> even to people who don't "accept" AC! If AC implies that
>> there is no gazebo then it follows, whether one accepts
>> AC or not, that the existence of a gazebo cannot be proved
>> in ZF.
>
> Nice! And nicely sneaky!!
I'm not sure what the gazebo-property is here...
Under ZF + AC something was shown to exist.
So one reading is that what I'll call the gazebo* property for a set X
is this:
gazebo*(X):
X = (A, B) , A union B is Reals, A and B are disjoint,
A \intersect [a, b] has cardinality 2^(aleph_0) , any a< b Reals,
B \intersect [a, b] has cardinality 2^(aleph_0) , any a< b Reals,
and
[ Exists f: A -> B a bijection, and f order-preserving
under canonical '<' .]
Then, in ZFC, there is an X with the gazebo* property, or ? ...
David Bernier
Bill Taylor
> > even to people who don't "accept" AC! If AC implies that
> > there is no gazebo then it follows, whether one accepts
> > AC or not, that the existence of a gazebo cannot be proved
> > in ZF.
This is OC the contrapositive case of the usual thing.
The earlier proof shows that an alleged example is provably
a true example, therefore no proof of non-existence can exist in ZF.
A direct example would be a proof that gazebos exist, using
ZF + indpt-hypothesis. Thus making it is useless to look for one.
> Nice! And nicely sneaky!!
Yes, I have long been advocating prople continue to use AC
(and CH, and Suslin etc - anything now proved independent
of ZF), in order to circumscribe the limits of what ZF can do.
It's nice, though I wouldn't necessarily call it sneaky.
An example of the direct form, would be that ~CH proves
that there exists a non-continuum uncountable subset of Z;
but as the hypothesis is independent, it is useless to look
for and hope to find any such actual set! (Strictly speaking,
it is only useless to come up with a set AND a proof that it
is unctble-cntuum, but the philosophical or practical
difference is minuscule.)
-- Wriggling William
David C. Ullrich
<davi...@videotron.ca> wrote:
>Virgil wrote:
>> In article<m9atg5h0jvcun23n7...@4ax.com>,
>> David C. Ullrich<dull...@sprynet.com> wrote:
>>
>>> On Thu, 26 Nov 2009 01:27:20 -0800 (PST), Butch Malahide
>>> <fred....@gmail.com> wrote:
>>>
>>>> On Nov 25, 10:05 pm, Bill Taylor<w.tay...@math.canterbury.ac.nz>
>>>> wrote:
>>>>>
>>>>> Consider subsets of the reals such that both the subset and
>>>>> its complement are continuum many in every interval.
>>>>>
>>>>> Are any two such subsets order-isomorphic? [Spelling typo corrected.]
>>>>
>>>> No, but the counterexample won't impress you, because it uses AC.
>>>
>>> A counterexample that depends on AC _should_ be of interest
>>> even to people who don't "accept" AC! If AC implies that
>>> there is no gazebo then it follows, whether one accepts
>>> AC or not, that the existence of a gazebo cannot be proved
>>> in ZF.
>>
>> Nice! And nicely sneaky!!
>
>I'm not sure what the gazebo-property is here...
>Under ZF + AC something was shown to exist.
I'm not sure whether what's below is a comment or a
question, nor what the question is.
But note in any case I wasn't paying any attention to
the specific question dealt with in this thread - I was
commenting on the statement
"No, but the counterexample won't impress you, because it uses AC.
Since you're not going to accept the example anyway, I'll just sketch
the argument."
pointing out that examples "constructed" using AC are
nonetheless far from irrelevant to a hypothetical
being who does not "accept" AC.
David Bernier
> On Thu, 26 Nov 2009 16:34:58 -0500, David Bernier
> <davi...@videotron.ca> wrote:
>
>> Virgil wrote:
>>> In article<m9atg5h0jvcun23n7...@4ax.com>,
>>> David C. Ullrich<dull...@sprynet.com> wrote:
>>>
>>>> On Thu, 26 Nov 2009 01:27:20 -0800 (PST), Butch Malahide
>>>> <fred....@gmail.com> wrote:
>>>>
>>>>> On Nov 25, 10:05 pm, Bill Taylor<w.tay...@math.canterbury.ac.nz>
>>>>> wrote:
>>>>>>
>>>>>> Consider subsets of the reals such that both the subset and
>>>>>> its complement are continuum many in every interval.
>>>>>>
>>>>>> Are any two such subsets order-isomorphic? [Spelling typo corrected.]
>>>>>
>>>>> No, but the counterexample won't impress you, because it uses AC.
>>>>
>>>> A counterexample that depends on AC _should_ be of interest
>>>> even to people who don't "accept" AC! If AC implies that
>>>> there is no gazebo then it follows, whether one accepts
>>>> AC or not, that the existence of a gazebo cannot be proved
>>>> in ZF.
>>>
>>> Nice! And nicely sneaky!!
>>
>> I'm not sure what the gazebo-property is here...
>> Under ZF + AC something was shown to exist.
>
> I'm not sure whether what's below is a comment or a
> question, nor what the question is.
I think I understand your point now. So I've
snipped out the part you refer to above.
> But note in any case I wasn't paying any attention to
> the specific question dealt with in this thread - I was
> commenting on the statement
>
> "No, but the counterexample won't impress you, because it uses AC.
> Since you're not going to accept the example anyway, I'll just sketch
> the argument."
>
> pointing out that examples "constructed" using AC are
> nonetheless far from irrelevant to a hypothetical
> being who does not "accept" AC.
[...]
If there is a proof in ZFC of a sentence T, then
there is no proof in ZF of the negation of T.
Proof by contradiction:
Suppose there is a proof in ZF of the negation of T.
Then there is a proof in ZFC of the negation of T.
By hypothesis, there is a proof in ZFC of
T. So there is a proof in ZFC of (T and not(T)).
But ZFC is consistent, so it can't be
that ZFC has a proof of (T and not(T)).
So we conclude that "there is a proof in ZF of the negation of T"
is false. So there is _no_ proof in ZF of the negation of T. QED
In my proof above, I used as an assumption that
ZFC is consistent. I read somewhere:
"In 1963, Paul Cohen showed that AC couldn't
be proved with the ZF axioms."
And also:
"In 1940, Goedel proved that AC couldn't be
disproved with the ZF axioms."
Recently, I've been wondering in which formal
systems the Independence proofs of Goedel and
Cohen can be carried out ...
If a doubter accepts ZF but no more, would the
doubter accept as proved that AC is
independent of ZF ?
David Bernier
[rest of earlier post of mine snipped]
Frederick Williams
>
> ...
>
> In my proof above, I used as an assumption that
> ZFC is consistent. I read somewhere:
> "In 1963, Paul Cohen showed that AC couldn't
> be proved with the ZF axioms."
>
> And also:
> "In 1940, Goedel proved that AC couldn't be
> disproved with the ZF axioms."
>
> Recently, I've been wondering in which formal
> systems the Independence proofs of Goedel and
> Cohen can be carried out ...
>
> If a doubter accepts ZF but no more, would the
> doubter accept as proved that AC is
> independent of ZF ?
Cohen's proof was carried out within ZFC, G\"odel's was carried out
within NBG.
--
Which of the seven heavens / Was responsible her smile /
Wouldn't be sure but attested / That, whoever it was, a god /
Worth kneeling-to for a while / Had tabernacled and rested.
David C. Ullrich
<davi...@videotron.ca> wrote:
That's most of my point, but an important bit is missing.
You only need to assume that ZF is consistent, because
the consistency of ZFC _follows_, by the result of
Godel you mention below. (It's not clear to me whether
that was clear to you or not...)
That's "important" in regard to "(assuming of course
that ZF is consistent) if you can prove something in
ZFC then you can't disprove the same thing in ZF" -
a person who doesn't "accept" AC would a priori
be more willing to assume the constency of ZF than
of ZFC, but in fact that two are equivalent.
>I read somewhere:
>"In 1963, Paul Cohen showed that AC couldn't
> be proved with the ZF axioms."
>
>And also:
>"In 1940, Goedel proved that AC couldn't be
> disproved with the ZF axioms."
>
>Recently, I've been wondering in which formal
>systems the Independence proofs of Goedel and
>Cohen can be carried out ...
>
>If a doubter accepts ZF but no more, would the
>doubter accept as proved that AC is
>independent of ZF ?
Yes.
(Well, people can "doubt" anything...)
>David Bernier
>
>[rest of earlier post of mine snipped]
David C. Ullrich
Aatu Koskensilta
> Cohen's proof was carried out within ZFC, G\"odel's was carried out
> within NBG.
I see you persist in your perversion. Being a very tolerant person when
it comes to such matters I'll let your typographic deviance pass without
further comment this time. As to the question at hand, both Cohen's and
G�del's proofs, taken as a proof of a result of the form "if ZF is
consistent, so is ...", can be proved purely finitistically, and
formalized in e.g. primitive recursive arithmetic.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon man nicht sprechan kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
David Bernier
> On Fri, 27 Nov 2009 08:53:56 -0500, David Bernier
> <davi...@videotron.ca> wrote:
[...]
>> If there is a proof in ZFC of a sentence T, then
>> there is no proof in ZF of the negation of T.
>>
>> Proof by contradiction:
>>
>> Suppose there is a proof in ZF of the negation of T.
>> Then there is a proof in ZFC of the negation of T.
>> By hypothesis, there is a proof in ZFC of
>> T. So there is a proof in ZFC of (T and not(T)).
>> But ZFC is consistent, so it can't be
>> that ZFC has a proof of (T and not(T)).
>> So we conclude that "there is a proof in ZF of the negation of T"
>> is false. So there is _no_ proof in ZF of the negation of T. QED
>>
>> In my proof above, I used as an assumption that
>> ZFC is consistent.
>
> That's most of my point, but an important bit is missing.
> You only need to assume that ZF is consistent, because
> the consistency of ZFC _follows_, by the result of
> Godel you mention below. (It's not clear to me whether
> that was clear to you or not...)
No, it wasn't clear to me. And I still don't
grasp "V = L" .
David Bernier
Aatu Koskensilta
> And I still don't grasp "V = L" .
What's unclear to you about "V = L"?
David Bernier
> David Bernier <davi...@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.
David Bernier
David C. Ullrich
<davi...@videotron.ca> wrote:
What I meant was it wasn't clear to me whether or not
you were aware that Godel _had_ in fact proved that the
consistency of ZF implies that of ZFC, not whether
the proof was clear.
Regarding V and L,
http://en.wikipedia.org/wiki/Constructible_universe
seems somewhat clear to me.
>David Bernier
>
>
>
>> That's "important" in regard to "(assuming of course
>> that ZF is consistent) if you can prove something in
>> ZFC then you can't disprove the same thing in ZF" -
>> a person who doesn't "accept" AC would a priori
>> be more willing to assume the constency of ZF than
>> of ZFC, but in fact that two are equivalent.
>>
>>> I read somewhere:
>>> "In 1963, Paul Cohen showed that AC couldn't
>>> be proved with the ZF axioms."
>>>
>>> And also:
>>> "In 1940, Goedel proved that AC couldn't be
>>> disproved with the ZF axioms."
>>>
>>> Recently, I've been wondering in which formal
>>> systems the Independence proofs of Goedel and
>>> Cohen can be carried out ...
>>>
>>> If a doubter accepts ZF but no more, would the
>>> doubter accept as proved that AC is
>>> independent of ZF ?
>>
>> Yes.
>>
>> (Well, people can "doubt" anything...)
>>
>>> David Bernier
>>>
>>> [rest of earlier post of mine snipped]
>>
>> David C. Ullrich
David C. Ullrich
David C. Ullrich
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 Bernier
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
Bill Taylor
> 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
David Libert
David C. Ullrich
<davi...@videotron.ca> wrote:
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
That's a nice argument. In ZF, obviously we can still form the
power set of N ( another name for omega), to get P(omega).
Under the V=L condition/hypothesis, for some ordinal alpha,
P(omega) is an element of L_{alpha}.
The Wikipedia article states that each L_alpha is transitive, i.e.
if A is in L_alpha, and x is an element of A, then x is an element
of L_alpha. I think I understand that now. There's a least
alpha such that P(omega) e L_alpha. Either alpha is a limit ordinal
or not. It's easy to see that the minimal alpha can't be a limit
ordinal, so it must be a successor alpha = beta+1.
Then P(omega) is in L_{beta+1} and there is a formula
defining P(omega) which allows P(omega) to be in L_{beta+1}.
Then, by that formula, P(omega) has its elements in L_beta.
So, under V=L, P(omega) is in some L_alpha and since L_alpha
is transitive, P(omega) is a subset of L_alpha.
I don't have any question for now, but I'm contemplating
the least ordinal alpha such that P(omega) is an element of L_alpha,
under V=L.
David Bernier