I don't like the Axiom of Choice
Craig Feinstein
incorrect, but I don't think it is anyone's business to assume claims
about the universe of transfinite sets without actually clearly
demonstrating that the claims are true. After all, lots of crazy stuff
happens when one deals with infinite sets. (My favorite example is
Hilbert's Hotel Infinity. http://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel)
And this is what the Axiom of Choice is doing - making claims without
explicitly demonstrating why the claims must be true.
Throughout most of my mathematics education, the axiom of choice has
been assumed implicitly by my mathematics professors (or explicitly
without making a big deal about it). How much of my mathematics
education should I forget about?
Or more specifically, since I never really took geometry, analysis,
topology seriously because of my natural aversion to infinite sets,
how much of my number theory and discrete mathematics education should
I forget about?
In other words, how much of modern mathematics, particularly number
theory and discrete mathematics, is based on the axiom of choice? (I
understand that Wiles' proof of FLT is based on the Axiom of Choice.
Am I correct? If so, then I guess FLT is still an open problem,
according to my reckoning!)
Craig
Lee Rudolph
Oops. It looks like the Axiom of Choice doesn't like you, either.
Lee Rudolph
Dave L. Renfro
> I don't like the Axiom of Choice. It may be correct or
> it may be incorrect, but I don't think it is anyone's
> business to assume claims about the universe of
> transfinite sets without actually clearly demonstrating
> that the claims are true. After all, lots of crazy stuff
> happens when one deals with infinite sets. (My favorite
> example is Hilbert's Hotel Infinity.
[snip rest]
You may want to look at Brouwer's intuitionism (google it).
The criticisms you raised (not just Hilbert's hotel) don't
have much to do with the axiom of choice. The axiom of choice
is an existence axiom. It is not an axiom that allows or
disallows certain types of mathematical constructability
or mathematical explicitness, which seems to be what
concerns you.
Dave L. Renfro
Mike Kelly
> I don't like the Axiom of Choice. It may be correct or it may be
> incorrect, but I don't think it is anyone's business to assume claims
> about the universe of transfinite sets without actually clearly
> demonstrating that the claims are true. After all, lots of crazy stuff
> happens when one deals with infinite sets. (My favorite example is
> And this is what the Axiom of Choice is doing - making claims without
> explicitly demonstrating why the claims must be true.
>
> Throughout most of my mathematics education, the axiom of choice has
> been assumed implicitly by my mathematics professors (or explicitly
> without making a big deal about it). How much of my mathematics
> education should I forget about?
None of it. Just be aware that some proofs of some theorems require a
choice function to exist but do not demonstrate its existence. And
others use Choice for convenience, when it is not strictly necessary.
> Or more specifically, since I never really took geometry, analysis,
> topology seriously because of my natural aversion to infinite sets,
> how much of my number theory and discrete mathematics education should
> I forget about?
If you don't believe in infinite sets then it makes no sense to
disagree with the axiom of choice. Trivially, all finite sets have a
choice function.
> In other words, how much of modern mathematics, particularly number
> theory and discrete mathematics, is based on the axiom of choice? (I
> understand that Wiles' proof of FLT is based on the Axiom of Choice.
> Am I correct? If so, then I guess FLT is still an open problem,
> according to my reckoning!)
No idea. It's probably worth bearing in mind that many, many proofs
that do rely on Choice can be reformulated in a way such that they do
not. Oftentimes, Choice is just a convenience.
math...@hotmail.com.cut
wrote:
>I don't like the Axiom of Choice. It may be correct or it may be
so don't use it oir believe anything that uses it in a proof
Dave L. Renfro
>> In other words, how much of modern mathematics, particularly
>> number theory and discrete mathematics, is based on the axiom
>> of choice? (I understand that Wiles' proof of FLT is based
>> on the Axiom of Choice. Am I correct? If so, then I guess
>> FLT is still an open problem, according to my reckoning!)
Mike Kelly wrote (in part):
> No idea. It's probably worth bearing in mind that many,
> many proofs that do rely on Choice can be reformulated
> in a way such that they do not. Oftentimes, Choice is
> just a convenience.
Unless you're more careful about exactly which forms
of the axiom of choice you consider suspect, I think
it's silly to even be worrying about the axiom of choice.
Each of the following CAN BE FALSE in the absence
of the axiom of choice:
1. The equivalence of the sequence definition of continuity
at a point with the epsilon-delta definition of continuity
at a point.
2. The reals are not a countable union of countable sets.
3. A countable union of measure zero sets has measure zero.
4. A countable union of first category sets is a first
category set.
5. Every infinite set has a countable subset.
There are many other results which virtually no one would
dispute that could be added to this list. Gregory Moore's
book on the axiom of choice is a great source for
these things. See also the following:
http://www.emis.de/journals/CMUC/pdf/cmuc9703/herrli.pdf
By being "more careful", I mean instead of throwing
out the baby with the bathwater, consider accepting
something weaker such as the axiom of choice for countable
collections of sets. Better yet, the axiom of dependent
choices, an axiom a bit stronger than countable choice
under which each of #1 through 5 above is true.
Incidentally, no form of the axiom of choice is needed
to obtain a choice function for {F, G}, where:
F = { f(0), f(2) }
G = { g(4), g(6) }
f(x) = x if x \in {0, 1, ..., 9} and
the 10^10000th digit of pi is x
f(x) = x+1 otherwise
g(x) = x if pi^e is irrational
g(x) = x+1 otherwise
Just define the choice function to give you the least
element in each of these two sets.
Dave L. Renfro
Jason Pawloski
This post was absolutely fascinating and I'd like to read more about
this. Is this the book you are talking about?
Also I am having a hard time with your link.
Thanks
Jason
Dave L. Renfro
> This post was absolutely fascinating and I'd like to read
> more about this. Is this the book you are talking about?
[long amazon.com URL snipped]
> Also I am having a hard time with your link.
Yes, that's the book. I'm shocked that a book like this,
with such obvious wide-spread appeal throughout mathematics
& logic & philosophy, has gone out of print, and even more
surprised that it hasn't been picked up by Chelsea or Dover.
There must be some reason those two publishers can't
reprint it, because this book is a virtual slam-dunk
compared to much of what they reprint.
As for the journal article I mentioned (just something
I found on the first page of google hits for a search
that included things like "axiom of choice" AND "dependent"
AND "sequence" AND "continuity"), try this URL:
http://www.emis.de/journals/CMUC/
Near the bottom of the page select Volume 38 Number 3,
and then look for the article by Horst Herrlich.
Below is an article by former sci.math poster (off and on)
Eric Schecter that might also be of interest. Note, however,
that it's not really about the axiom of choice, but rather
what I think goes more to the heart of what some people
have in mind when they're arguing against the axiom of
choice.
http://www.math.vanderbilt.edu/~schectex/papers/difficult.pdf
Certainly, many of the uses of the axiom of choice have
a high degree of non-constructability, but so do many
other mathematical procedures that do not involve the
axiom of choice.
By the way, there's a huge number of refinements to
the axiom of choice. Given cardinal numbers d and e,
there's what I'll call AC(d,e), which is the axiom
of choice for collections of d many sets each with
cardinality e. I believe AC(c,2), where c is the
cardinality of the reals, suffices to get a non-measurable
set. In Sierpinski's book "Cardinal and Ordinal Numbers",
there's a section in the chapter on the axiom of choice
where all sorts of relations are proved involving AC(*,n),
that is, the axiom of choice for collections of arbitrarily
many sets each having cardinality n. I seem to recall that
AC(*,4) implies AC(*,2), and more generally, for each pair
of positive integers m & n greater than 1, we have
AC(*,mn) ==> AC(*,n). There are also results where the
hypothesis consists of more than one assertion of the
form "AC(*,n)", but I don't remember any of those statements
now. The axiom of choice variations can also be subdivided
further into situations where all the sets in the collection
are sets of real numbers, or sets chosen from some other
fixed "standard set". Note that all forms of AC(d,e) hold
when the collections consist of sets of positive integers,
since we can always obtain a choice function by taking
the least element. Also, all forms of AC(d,n) for finite n
hold when the collections are sets of real numbers,
since we can again obtain a choice function by taking
the least element from each set.
Herman Rubin is the expert here. I pretty much only know
enough to know that it would be foolish for me to even
begin trying to purge the use of the axiom of choice in
my own pursuits, or to even try identifying where it's
used.
Dave L. Renfro
Craig Feinstein
Thinking about this more, it seems to me that even if Wiles' proof of
FLT requires the Axiom of Choice, this should not matter since the
Axiom of Choice is independent from the ZF axioms - Suppose that FLT
was false. Then this fact would be provable in ZF, since we're talking
about only needing simple arithmetic to verify a counter-example. This
along with Wiles' proof that FLT is provable assuming the AC would
then render the Axiom of Choice to be false, assuming the ZF. But this
would contradict the well-known fact that the AC is independent from
from ZF.
Craig
>
> Craig
MoeBlee
> Thinking about this more, it seems to me that even if Wiles' proof of
> FLT requires the Axiom of Choice, this should not matter since the
> Axiom of Choice is independent from the ZF axioms - Suppose that FLT
> was false. Then this fact would be provable in ZF, since we're talking
> about only needing simple arithmetic to verify a counter-example. This
> along with Wiles' proof that FLT is provable assuming the AC would
> then render the Axiom of Choice to be false, assuming the ZF. But this
> would contradict the well-known fact that the AC is independent from
> from ZF.
I don't know much about Wiles's proof, but I do understand your point
that if FLT is false then ZF proves the negation of FLT. So, accepting
that, let's look at this generally:
Suppose P is a sentence about arithmetic such that (1) if P is false,
then ZF proves ~P and (2) ZFC proves P.
So, if P is false, then ZFC is inconsistent, so ZF is inconsistent, so
ZF proves P.
But under those circumstances, it is trivival that we've shown "ZF
proves P", since, under those circumstances, ZF is inconsistent.
And if ZF is inconsistent, then the axiom of choice is not independent
of ZF and so if P is false, there is no need to worry about
contradicting the independence of the axiom of choice from ZF, since,
if P is false, the axiom of choice is not independent from ZF.
Also, you said "render the Axiom of Choice to be false". To me, it's
not clear what you mean by the truth or falsity of the axiom of choice
unless you say what models or what kind of models the axiom of choice
is true or false in. That is unlike the situation with FLT where I can
take truth or falsehood to be as to the standard model for the
language of, say, PA.
MoeBlee
T.H. Ray
> or it may be
> incorrect, but I don't think it is anyone's business
> to assume claims
> about the universe of transfinite sets without
> actually clearly
> demonstrating that the claims are true. After all,
> lots of crazy stuff
> happens when one deals with infinite sets. (My
> favorite example is
> Hilbert's Hotel Infinity.
> http://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_
> Grand_Hotel)
> And this is what the Axiom of Choice is doing -
> making claims without
> explicitly demonstrating why the claims must be true.
>
Neither does any other axiom demonstrate why the claims
that result from it must be true.
What axioms do you like? Why do you like
them? Why axioms at all?
Tom
Aatu Koskensilta
> Or more specifically, since I never really took geometry, analysis,
> topology seriously because of my natural aversion to infinite sets,
> how much of my number theory and discrete mathematics education should
> I forget about?
The axiom of choice is never necessary to prove any number theoretic
statement. Any appeal to it in a proof of an arithmetical statement can be
removed by relativizing the argument to the constructible hierarchy.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Aatu Koskensilta
> There are many other results which virtually no one would
> dispute that could be added to this list. Gregory Moore's
> book on the axiom of choice is a great source for
> these things.
Indeed it is. My favourite counter-intuitive result that can be true in
absence of choice is that every infinite cardinal may be of cofinality
omega. Now there's a strange image!
MoeBlee
wrote:
> The axiom of choice is never necessary to prove any number theoretic
> statement. Any appeal to it in a proof of an arithmetical statement can be
> removed by relativizing the argument to the constructible hierarchy.
I've seen lists (such as in one of the articles linked to in this
thread) of various theorems of mathematics whose proof uses the axiom
of choice. The question this raises for me is: What are some theorems
of "practical" (for lack of a better word, generally, "applied' or
"scientific") mathematics that rely upon the axiom of choice? In other
words, what are some of the more prominent implications of the axiom
of choice that enable the work of engineers and applied scientists?
The purpose of the question is to address in what way, if any, the
axiom of choice is "needed" not just to facilitate abstract
mathematics but also to prove theorems used for applied mathematics.
Or could we have all of our "applied" mathematics axiomatized without
the axiom of choice?
MoeBlee
Bill Taylor
> Indeed it is. My favourite counter-intuitive result that can be true in
> absence of choice is that every infinite cardinal may be of cofinality
> omega. Now there's a strange image!
Hmmm.
Surely this is only true for a limited view of what is a cardinal,
in the absence of choice? Surely there is more than one way
to define a cardinal, in that context. Your language above
seems to imply that every cardinal is still well-ordered,
but need this be so? Is there any "standard" convention
on this? (Seems unlikely, for such a non-standard matter.)
But surely we would still want to speak of "the cardinality of R"
in such circumstances? So shouldn't a cardinal number be closer
to Russell's definition - the class of all sets equinumerous to one.
Or, if you don't want to go near NGB classes, do the usual trick
and use regularity to pick out the set of all equinumerous sets
at the mimimal level.
-----------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-----------------------------------------------------------------------
Set theory is a shotgun marriage - between well-ordering and power-
set.
The two parties get along OK; but they hardly seem made for each
other.
-----------------------------------------------------------------------
Herman Rubin
Craig Feinstein <cafe...@msn.com> wrote:
>I don't like the Axiom of Choice. It may be correct or it may be
>incorrect, but I don't think it is anyone's business to assume claims
>about the universe of transfinite sets without actually clearly
>demonstrating that the claims are true. After all, lots of crazy stuff
>happens when one deals with infinite sets. (My favorite example is
>Hilbert's Hotel Infinity. http://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel)
>And this is what the Axiom of Choice is doing - making claims without
>explicitly demonstrating why the claims must be true.
These transfinite "crazy items" have nothing to do with
the axiom of choice. The Hilbert Hotel example does not
in any way depend on it.
>Throughout most of my mathematics education, the axiom of choice has
>been assumed implicitly by my mathematics professors (or explicitly
>without making a big deal about it). How much of my mathematics
>education should I forget about?
>Or more specifically, since I never really took geometry, analysis,
>topology seriously because of my natural aversion to infinite sets,
>how much of my number theory and discrete mathematics education should
>I forget about?
Even number theory involves an infinite set, namely,
the set of integers. Euclid includes many results
about infinite sets of integers.
>In other words, how much of modern mathematics, particularly number
>theory and discrete mathematics, is based on the axiom of choice? (I
>understand that Wiles' proof of FLT is based on the Axiom of Choice.
>Am I correct? If so, then I guess FLT is still an open problem,
>according to my reckoning!)
All of analysis involves at least the real numbers.
I am not at all familiar with the proof of FLT, but
I doubt it requires the axiom of choice. It does
use the existence of infinite sets.
>Craig
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Aatu Koskensilta
> I am not at all familiar with the proof of FLT, but
> I doubt it requires the axiom of choice. It does
> use the existence of infinite sets.
Highly infinitary stuff indeed! The use of choice in the proof -- if it is
used in it, about which I know absolutely nothing -- is necessarily
eliminable since FLT is an arithmetical statement.
Mitch
wrote:
> On 2007-05-03, Herman Rubin wrote:
>
> > I am not at all familiar with the proof of FLT, but
> > I doubt it requires the axiom of choice. It does
> > use the existence of infinite sets.
>
> Highly infinitary stuff indeed! The use of choice in the proof -- if it is
> used in it, about which I know absolutely nothing -- is necessarily
> eliminable since FLT is an arithmetical statement.
Really? as usual, not knowing anything, by the extremely weak
metaphor, Desargues' thm, a 2-dimensional statement, requires 3
dimensions. for proof. Is there something about the defintions of
'arithmetical' that precludes A of C (that's not as obvious as your
statement makes it sound).
Mitch
Aatu Koskensilta
> Really? as usual, not knowing anything, by the extremely weak
> metaphor, Desargues' thm, a 2-dimensional statement, requires 3
> dimensions. for proof. Is there something about the defintions of
> 'arithmetical' that precludes A of C (that's not as obvious as your
> statement makes it sound).
Given a proof in which choice is used of a statement P we can transform it
into a proof of "P is true in the constructible hierarchy" in which choice
is not used. For arithmetical statements "P is true in the constructible
hierarchy" is equivalent to P itself. Combining these results yields the
observation that choice is never necessary to prove an arithmetical
statement, which is indeed not obvious.
Aatu Koskensilta
> Surely this is only true for a limited view of what is a cardinal,
> in the absence of choice? Surely there is more than one way
> to define a cardinal, in that context. Your language above
> seems to imply that every cardinal is still well-ordered,
> but need this be so? Is there any "standard" convention
> on this? (Seems unlikely, for such a non-standard matter.)
Using Scott's trick and defining cardinals as sets of equipollent sets of
least possible rank seems pretty standard. However, I had in mind the
possibility, in absence of choice, that there does not exist an ordinal with
cofinality greater than omega. That is a truly sick picture, though it would
be interesting to know whether there's any clear conception of the world of
sets that would justify it or make it plausible -- indeed it would be
interesting to know if there's any clear conception of the world of sets
justifying the usual axioms of set theory and the failure of choice.
mike3
> I don't like the Axiom of Choice. It may be correct or it may be
> incorrect, but I don't think it is anyone's business to assume claims
> about the universe of transfinite sets without actually clearly
> demonstrating that the claims are true. After all, lots of crazy stuff
> happens when one deals with infinite sets. (My favorite example is
> And this is what the Axiom of Choice is doing - making claims without
> explicitly demonstrating why the claims must be true.
>
> Throughout most of my mathematics education, the axiom of choice has
> been assumed implicitly by my mathematics professors (or explicitly
> without making a big deal about it). How much of my mathematics
> education should I forget about?
>
> Or more specifically, since I never really took geometry, analysis,
> topology seriously because of my natural aversion to infinite sets,
> how much of my number theory and discrete mathematics education should
> I forget about?
>
> In other words, how much of modern mathematics, particularly number
> theory and discrete mathematics, is based on the axiom of choice? (I
> understand that Wiles' proof of FLT is based on the Axiom of Choice.
> Am I correct? If so, then I guess FLT is still an open problem,
> according to my reckoning!)
>
> Craig
No, because it's an AXIOM -- a statement taken to be a self-evident
truth, or just accepted to be truth as a foundation point. It cannot
be derived or proved, that is what an AXIOM is. You've got to start
from some sort of basic presumption. Ever heard of what happens
when the child tries to ask his parent "why why why" again and
again? Eventually you run out of justifications and just have to take
something as a fundamental truth. You can't justify everything.
You just have to assume something is true at some point.
Dictionary definition:
from http://www.bartleby.com/61/58/A0555800.html:
axiom
SYLLABICATION: ax·i·om
PRONUNCIATION: ks-m
NOUN: 1. A self-evident or universally recognized truth; a maxim: "It
is an economic axiom as old as the hills that goods and services can
be paid for only with goods and services" (Albert Jay Nock). 2. An
established rule, principle, or law. 3. A self-evident principle or
one that is accepted as true without proof as the basis for argument;
a postulate.
ETYMOLOGY: Middle English, from Old French axiome, from Latin axima,
aximat-, from Greek, from axios, worthy. See ag- in Appendix I.
Bill Taylor
> I had in mind the
> possibility, in absence of choice, that there does not exist an ordinal with
> cofinality greater than omega.
Is this possible within ZF? There is always a set, *the* set, of
countable ordinals. If this had to be of cofinality only omega,
then it would be a countable union of countable sets.
That wouldn't necessarily require for it to be a countable set itself,
for any old sets, but maybe for a well-ordered set of ordinals it
would?
Would it? I can't tell, either way.
> That is a truly sick picture, though it would
Maybe. It's hard to know what "consequences" of non-AC are
pathological,
when (a) we're so used to considering it true and applying it almost
automatically, and (b) there are plenty of pathologies in ZFC anyway.
Including a fair few that come specifically *because of* AC! It is
hard
to know what is more pathological than what else, sometimes.
> be interesting to know whether there's any clear conception of the world of
> sets that would justify it or make it plausible -- indeed it would be
> interesting to know if there's any clear conception of the world of sets
> justifying the usual axioms of set theory and the failure of choice.
Well yes, for the latter, I think so. One can imagine a world of sets
that
include only those that are "definable" in some sense. If any sense
can
be made of this, (and I suspect it can), then all of ZF would apply to
it,
but not AC.
----------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
Robert Maas, see http://tinyurl.com/uh3t
> I don't like the Axiom of Choice.
I don't like it either, but not for the stupid logic you say later.
> It may be correct or it may be incorrect, but I don't think it is
> anyone's business to assume claims about the universe of
> transfinite sets without actually clearly demonstrating that the
> claims are true. After all, lots of crazy stuff happens when one
> deals with infinite sets.
That's true, but what you say next is garbage:
> My favorite example is Hilbert's Hotel Infinity.
There's nothing wrong with the math that yields Hilbert's Hotel.
It comes directly out of the most basic study of automatons.
Consider a program that prints out the number of seconds since midnight.
Consider another program that prints out the number of seconds
since one second after midnight.
The output of the two programs are relatively offset by one (second).
By one logic, they produce corresponding output, parallel streams
of numbers that are numerically offset by one.
But by another logic, looking just at the *set* of numbers
eventually produced by each program, one program produces a number
not produced by the other.
Hence the sequences of numbers are order-isomorphic,
but the sets of numbers have one set larger than the other.
That's really the principle of Hilbert's Hotel.
So what makes you think Hilbert's Hotel is just making up claims
without any evidence they are true? It's pretty obvious to me that
if both programs are allowed to run forever, they produce exactly
the same amount of output, yet produce sets that have a proper
subset relation. Why do you have so much trouble accepting such facts?
Why don't pyramid scams or chainletters really work? Because the
total size of available members is finite. If there were an
unlimited (infinite) number of available members, the scam really
could work. Everyone who joins could achieve an eventual profit.
Think of Ponzi's Hotel! Grok it in fullness!!
Live from New York^H^H^H^H^H^H^H^HLos Angeles, it's the Paris Hilton Hotel!
Aatu Koskensilta
> Aatu Koskensilta wrote:
>
>> I had in mind the
>> possibility, in absence of choice, that there does not exist an ordinal with
>> cofinality greater than omega.
>
> Is this possible within ZF? There is always a set, *the* set, of
> countable ordinals. If this had to be of cofinality only omega,
> then it would be a countable union of countable sets.
It is consistent with ZF that omega_1 has cofinality omega.
>> be interesting to know whether there's any clear conception of the world of
>> sets that would justify it or make it plausible -- indeed it would be
>> interesting to know if there's any clear conception of the world of sets
>> justifying the usual axioms of set theory and the failure of choice.
>
> Well yes, for the latter, I think so. One can imagine a world of sets
> that include only those that are "definable" in some sense. If any sense
> can be made of this, (and I suspect it can), then all of ZF would apply to
> it, but not AC.
Why would the axioms of ZF apply? In particular, why would the axiom of
powersets and the axiom of replacement apply? The most straightforward
interpretation of 'definable' would give us something like L_omega_1^CK in
which not all axioms of set theory hold. Also, while it is clear that the
conception of sets as definable -- in whatever sense -- collections does not
justify choice, it's not clear how it justifies the failure of choice.
Keith Ramsay
On May 3, 9:59 pm, Aatu Koskensilta <aatu.koskensi...@xortec.fi>
wrote:
|Given a proof in which choice is used of a statement P we can
transform it
|into a proof of "P is true in the constructible hierarchy" in which
choice
|is not used. For arithmetical statements "P is true in the
constructible
|hierarchy" is equivalent to P itself. Combining these results yields
the
|observation that choice is never necessary to prove an arithmetical
|statement, which is indeed not obvious.
We can go even further. In "Eliminating the Continuum Hypothesis",
Richard A. Platek, Journal of Symbolic Logic, Vol. 34, No. 2 (1969),
219-225, it shows that a Pi-1-4 sentence provable from ZF+AC+GCH is
provable from ZF. A Pi-1-4 sentence is one of the form (for all S1)
(there exists S2)(for all S3)(there exists S4) P(S1, S2, S3, S4) where
S1, S2, S3, and S4 are sets of integers, and P is formula with only
quantifiers over integers. Here GCH is the generalized continuum
hypothesis, that for each infinite cardinal X, the next cardinality
after X is 2^X. If I remember correctly the result is sharp in the
sense that there's a Sigma-1-4 sentence (like a Pi-1-4 but with the
quantifier alternation starting with a "there exists S1") provable
from
ZFC but not ZF. The original poster may take comfort from this: the
Pi-1-4 theorems of mathematics cover a lot of what we actually
care about. Even in cases where you're dealing with sets of reals,
they can often be encoded as single reals.
The axiom of choice was used in the proof of Fermat's Last Theorem, if
you count the results Wiles built on top of as part of the proof.
There's an extension of the field Q_p of p-adic numbers known as C_p,
and from AC it's possible to prove that C_p is isomorphic as a field
(in a horribly discontinuous way) with the complex numbers C. Once you
assume the axiom of choice, then each of them as a field is just an
algebraically closed field of characteristic 0, and transcendence
degree
the cardinality of the continuum. This isomorphism is used in the
proof
of some result that Wiles used.
I was told, however, that someone had mentioned around that time how
it was possible to avoid using this isomorphism, simply in number
theory
terms, with no reference to mathematical logic. My impression is that
the
isomorphism was used just as a kind of convenience.
Keith Ramsay
Keith Ramsay
On May 5, 10:51 pm, Bill Taylor <w.tay...@math.canterbury.ac.nz>
wrote:
|Well yes, for the latter, I think so. One can imagine a world of
sets
|that
|include only those that are "definable" in some sense. If any sense
|can
|be made of this, (and I suspect it can), then all of ZF would apply
to
|it,
|but not AC.
I'm not sure what the best way to make your idea rigorous is, but
it's not clear that it will fail AC. The minimal transitive model of
ZF, for example, satisfies V=L, and consequently AC. In general,
inside of each model of ZF, there is an internal L which is a model
of ZF+V=L, although it does not "typically" contain all sets definable
in the containing model.
Suppose we take the countable set of elements of a model of ZF
that are first-order definable in it. I don't actually know offhand
whether that's always a countable model of ZF, or if so under
what conditions it satisfies AC. Perhaps if the containing model
satisfies some of the usual assumptions contrary to V=L, the
subset will be a model of ZF violating AC. But I don't find it
at all obvious.
Keith Ramsay
Aatu Koskensilta
> We can go even further. In "Eliminating the Continuum Hypothesis",
> Richard A. Platek, Journal of Symbolic Logic, Vol. 34, No. 2 (1969),
> 219-225, it shows that a Pi-1-4 sentence provable from ZF+AC+GCH is
> provable from ZF. A Pi-1-4 sentence is one of the form (for all S1)
> (there exists S2)(for all S3)(there exists S4) P(S1, S2, S3, S4) where
> S1, S2, S3, and S4 are sets of integers, and P is formula with only
> quantifiers over integers. Here GCH is the generalized continuum
> hypothesis, that for each infinite cardinal X, the next cardinality
> after X is 2^X. If I remember correctly the result is sharp in the
> sense that there's a Sigma-1-4 sentence (like a Pi-1-4 but with the
> quantifier alternation starting with a "there exists S1") provable
> from ZFC but not ZF.
That's right. Thanks for the reference; I was aware of the result
but always had trouble remembering where I saw the proof.
There's one aspect here that might be puzzling to some readers -- though
since it's puzzling only when you know enough of the technical details about
constructibility those puzzled are probably capable of thinking it through
themselves. The proof that the axiom of choice is never necessary in proving
an arithmetical statement outlined by me, i.e. noting that "P is true in the
constructible hierarchy" implies P for arithmetical statements and thus we
can remove choice by relativizing the proof to the constructible hierarchy,
generalizes, by the Shoenfield absoluteness theorem, to Sigma-1-3 statements.
However, this is the best we can do, that is V=L is not conservative for
Pi-1-3 statements or statements of greater logical complexity. Platek's
proof is by a different technique, and shows that ZFC+GCH+AC, instead of
ZFC + V=L, is conservative for Pi-1-4 statements.
Herman Rubin
Aatu Koskensilta <aatu.kos...@xortec.fi> wrote:
>On 2007-05-02, in sci.math, Bill Taylor wrote:
>> Surely this is only true for a limited view of what is a cardinal,
>> in the absence of choice? Surely there is more than one way
>> to define a cardinal, in that context. Your language above
>> seems to imply that every cardinal is still well-ordered,
>> but need this be so? Is there any "standard" convention
>> on this? (Seems unlikely, for such a non-standard matter.)
>Using Scott's trick and defining cardinals as sets of equipollent sets of
>least possible rank seems pretty standard. However, I had in mind the
>possibility, in absence of choice, that there does not exist an ordinal with
>cofinality greater than omega. That is a truly sick picture, though it would
>be interesting to know whether there's any clear conception of the world of
>sets that would justify it or make it plausible -- indeed it would be
>interesting to know if there's any clear conception of the world of sets
>justifying the usual axioms of set theory and the failure of choice.
The Hartogs function of the power set of the integers
has cofinality greater than omega with or without choice.
There are oodles of models not satisfying choice, even
if they satisfy restricted versions. I suggest you
read _Consequences of the Axiom of Choice_ by Paul
Howard and Jean E. Rubin.
At least most of the models start with one satisfying
choice and upon which a group operates; the group
preserves the element relation. One keeps the elements
of the model which, with their elements, and their
elements, etc., are invariant under large subgroups.
For the Cohen models, this can be done because one
cannot compare sets of sets of integers under forcing.
Don Stockbauer
> In article <5xB_h.158259$sH.24...@reader1.news.saunalahti.fi>,
I don't like the Axiom of Choice
I don't like the statement 2 = 2
Dave L. Renfro
> I don't like the Axiom of Choice
>
> I don't like the statement 2 = 2
Well, at least you agree 2 = 2 is a statement.
Some posters seem to disagree about its
status as a statement.
Dave L. Renfro