1
$\begingroup$

Given the number of results that are independent of ZF. It seems that once you've found a proof of a theorem that uses the axiom of choice, the odds are that it will be independent of ZF. So my question is:

-Is there any result that has a solution in ZFC which relies on AC, but has another proof that can be done only in ZF?

I'm especially interested in those results which people thought that were going to be independent of ZF, because only a proof relying on AC was known. And then someone found a proof in ZF.

When I say axiom of choice I'm also including weaker versions like countable choice or DC.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I don't understand your question. 98% of theorems in advanced algebra that are usually proven with the AC don't depend on the AC. $\endgroup$
    – darij grinberg
    Commented Feb 5, 2011 at 14:06
  • $\begingroup$ @darij At least the basic results in algebra need AC: the different definitions of noetherian aren't equivalent without DC. ( (mathoverflow.net/questions/53523/maximal-ideal-and-zorns-lemma). $\endgroup$
    – Gabriel Furstenheim
    Commented Feb 5, 2011 at 14:23
  • 2
    $\begingroup$ Yes, but few of their applications do. If you read some French, try out this: hlombardi.free.fr/liens/constr.html (particularly "Algèbre Commutative"). There are lots of results of the kind "any sufficiently elementary theorem provable in ZFC is provable in ZF or even constructively", where "sufficiently elementary" means things like "1st order formula", "geometric formula" and the likes. Some of these results, ironically, require ZFC themselves, while others don't. Alas, I am not an expert in this field ("program extraction from classical proofs"). $\endgroup$
    – darij grinberg
    Commented Feb 5, 2011 at 14:39
  • 9
    $\begingroup$ The Cantor-Bernstein theorem was first proved using AC but is provable without it as well. $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 5, 2011 at 15:01
  • 4
    $\begingroup$ I don't think the question is well-defined as stated. You can trivially insert "by the Axiom of Choice, ..." into the proof of any statement and then remove it. I think you meant to say "if a result apparently depends on AC, does it necessarily?" and then there are a million counterexamples. $\endgroup$
    – Qiaochu Yuan
    Commented Feb 5, 2011 at 15:34

4 Answers 4

Reset to default
7
$\begingroup$

Construction of the Haar integral for locally compact Hausdorff group $G$ ... as a linear functional on $C_{00}(G)$ ... is often done using the Axiom of Choice. In the Hewitt & Ross textbook ABSTRACT HARMONIC ANALYSIS this is Theorem (15.5), and they do it without AC. They do then have an exercise (15.25) where they outline the much shorter proof using Tihonov's Theorem.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I don't understand this answer. They are using the axiom of choice in the form of a well-known equivalent version. $\endgroup$
    – Andrés E. Caicedo
    Commented Feb 5, 2011 at 19:48
  • 4
    $\begingroup$ I guess (but don't know) that Gerald means they present a proof without AC and then as an exercise suggest a much easier proof that does use AC (via Tichonoff's theorem). $\endgroup$
    – Tom Ellis
    Commented Feb 5, 2011 at 22:05
  • $\begingroup$ Tom is correct, isn't that what I said? $\endgroup$
    – Gerald Edgar
    Commented Feb 6, 2011 at 2:53
  • $\begingroup$ @Gerald: Yes, that is precisely what you said. (I misread and was confused.) It is a nice example. $\endgroup$
    – Andrés E. Caicedo
    Commented Feb 6, 2011 at 2:57
7
$\begingroup$

The paper "Division by Three" by Doyle and Conway (link to PDF) gives a proof of the following result without appeal to the axiom of choice:

Let $A$ and $B$ be sets, and let $3$ denote a three-element set. If there exists a bijection from $3\times A$ to $3\times B$, then there exists a bijection from $A$ to $B$.

(This result is not due to Doyle and Conway -- it was first obtained by Lindenbaum and Tarski in 1926.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This paper is also notable for giving a great conceptual proof of the Schröder-Bernstein theorem, as a warm-up to the main proof. $\endgroup$
    – Jim Conant
    Commented Feb 6, 2011 at 19:30
  • $\begingroup$ To say that it was first obtained by Lindenbaum and Tarski in 1926 is to skip over the actual history of the situation. Certainly it was not published in 1926, and Tarski many years later said he couldn't remember how Lindenbaum's argument for a key lemma went, but found a proof for it himself. The (Conway-)Doyle paper describes all this better than I can in a small comment box (they, or he [Doyle], surmise that they hit upon the argument Lindenbaum must have used, but I'd treat that as just a guess). $\endgroup$
    – Todd Trimble
    Commented Jul 7, 2015 at 13:03
5
$\begingroup$

Tarski proved that, for any set $A$, the set $W(A)$ of well-orderable subsets of $A$ has strictly larger cardinality than $A$. This is trivial with AC, as then $W(A)$ is the whole power set of $A$ and thus Cantor's theorem applies. But Tarski gave a proof that avoids AC.

I don't have my copy of Howard and Rubin's "Consequences of the Axiom of Choice" handy, but if I did then I could probably find lots of examples by looking at the various forms numbered 0A, 0B, etc. I believe all of these are provable without AC (hence the number 0) but there was once a reason to suspect AC was needed.

Improve this answer
$\endgroup$
1
2
$\begingroup$

There are many such proofs which use $AC$, but which are not even close to being independent of $ZF$. The general reason for this is how $AC$ is used. Normally the non-essential use of $AC$ appears when you have a very targeted application in mind, with additional structure in the background.

For example: Given an arbitrary collection of non-empty sets $\{X_\alpha: \alpha \in Y\}$ asserting that the product $Z =\Pi_{\alpha \in Y} X_{\alpha} $ is non-empty requires $AC$ when you have no structure imposed on the $X_\alpha$ and $Y$. However, when we add the assertion that each $X_\alpha$ is a ring, with additive identity $0_\alpha\in X_\alpha$, we then know that $Z$ is always non-empty without $AC$. The reason for this is because we now can define a function which witnesses that $Z$ is non-empty, in fact the function $\varphi:Y \rightarrow \bigcup X_\alpha$, given by $\varphi(\alpha) = 0_\alpha$ is such a witness, because $\varphi \in Z$.

That having been said, as for a specific example of a theorem for which everyone thought relied on $AC$ but was proven to hold in $ZF$, I cannot think of one off-hand that has not already been mentioned. But I think an example of what you are looking for might be contained in a question by Andres Caicedo, Distinct well-orderings of the same set and in his insightful answer to his own question.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .