Can someone please give me feedback on my attempted proof that Zorn's Lemma implies the Axiom of Choice? I have a very good idea how to do it, but need help with some small details.   This is my proof so far... major gaps missing, please help!  Let $X$ be a nonempty set. Let $S = \{f : f \text{ is a choice function on } A \subset \mathcal{P}_{0}{X}\}$. Explain why $S$ nonempty. Declare $f_{1} \leq f_{2}$ if $Dom(f_{1}) \subset Dom(f_{2})$ (Why is this a partial ordering?). Let $T$ be a chain in $S$. Let $F$ be the union on the functions in $T$. (Why is $F$ also a choice function?) Therefore, by Zorn's Lemma, there exists a maximal function $m$. (Why is $m$ a choice function on every $A \subset PX$). Suppose not, then there exists an $A \subset \mathcal{P}_{0}{X}$ such that $m$ is not defined on $A$ (Don't know how to finish this!!) Therefore, $f \in S$ and $m &lt; f$, contradicting $m$ being maximal. Thus, $m$ is a choice function for the entire set $\mathcal{P}{X}$.
121305
How can I prove Zorn's lemma is equivalent to Axiom of choice?
39598
Is it possible to prove the following fact without axiom of choice ?  " Every infinite set has a countably infinite subset".  Can it be proved that axiom of choice is necessary here ?
99932
Background:  This question came up in my homework (but was not a homework problem).  The problem was proving one direction of the Heine-Borel theorem. As with all proofs of compactness, one begins with, "Suppose $A$ is closed and bounded, and $\mathcal{U}$ is an open cover ..."  My proof, which I believe is typical, constructed a convergent sequence of points and derived a contradiction.  The problem: to construct a sequence, one needs the cover to be countable.  So I invoked that second-countability implies Lindelöf.  This is not controversial, of course, but I included a little argument along the lines of the answers in this question:  .  In particular, for each $x\in A$ there is some $U$ in $\mathcal{U}$ with $x\in U$; second-countability implies for each $x\in A$ there is some basis element $Q$ with $x\in Q\subset U$; the set of all such $Q$ covers $A$ and each $Q\subset U$ for at least one $U\in\mathcal{U}$, so picking one $U\supset Q$ for each $Q$ gives a countable cover of $A$.  I noticed that the answers in that thread included similar phrases: "Now for each $B\in\mathcal{B}U$ choose some $U(B)\in U$ such that $B\subseteq U$", "for each element $O$ of $\Sigma$ choose an element $U$ of $\Omega$ containing it"  My argument and the arguments suggested in the thread linked both seem to assume the Axiom of Choice.  I'm not sure that I understand the axiom of choice, though.  So, two questions:     1) Are we actually using the axiom of choice in these arguments?      2) Does (second countable) $\Rightarrow$ (Lindelöf) require the axiom of choice?   Thanks!
87882
More specifically, I just want to prove that in a Noetherian (even Dedekind) ring, every ideal in contained in a maximal ideal. Is the axiom oh choice needed here? The usual proofs (for general rings use Zorn's lemma; for Noetherian rings one can build an infinite ascending chain if there is no maximal element) seem to rely on it.  If the axiom of dependent choice can be avoided as well, even better.
65356
I have noticed that the family of non-empty sets referred to in statements of the Axiom of Choice is sometimes required to be mutually disjoint, and sometimes not. Why is that?
42388
A UC Berkeley prelim exam problem asked whether an additive function $f\colon {\mathbb R} \to {\mathbb R}$, i.e. satisfying $f(x + y) = f(x) + f(y)$ must be continuous. The counterexample involved taking a positive-valued Hamel basis $X$ of $\mathbb{R}$ as a vector space over ${\mathbb Q}$, and then letting $f(x_1) =1$ and $f(x_2)=-1$ for two different $x_1,x_2 \in X$, and letting $f(x)$ be arbitrary for other $x \in X$, and then extending the function to all of ${\mathbb R}$ using the property of additivity. Then a sequence $a_n = {p_nx_1 + q_nx_2}$ could be found with rational $p_n,q_n$ such that $a_n \to 0$ but $\lim \limits_{n\to \infty} f(a_n) \neq 0$, showing discontinuity. But is Zorn's Lemma necessary to produce such an example? In other words, is Zorn's Lemma saying we can find a Hamel basis of ${\mathbb R}$ over ${\mathbb Q}$ equivalent to being able to construct a discontinuous additive function $f\colon {\mathbb R} \to {\mathbb R}$?
35828
In terms of purely set theory, the axiom of choice says that for any set $A$, its power set (with empty set removed) has a choice function, i.e. there exists a function $f\colon \mathcal{P}^*(A)\rightarrow A$ such that for any subset $S$ of $A$, $f(S)\in S.$ Is this correct?  My question then is about proving this fact, so that we do not need to put it as an axiom. Now as per the research done on this single object- Axiom of Choice, I believe here that there should be some falsity in my argument. I do not find the mistake.  For any $S\in \mathcal{P}^*(A)$, since $S\neq \emptyset$, $\exists s\in S$. Define $f(S)=s$. Then $f$ is a choice function.  This was showing me that the axiom of choice is proved, but then why it had been put as an axiom? For example, in  book, the author asserts that      It is a metatheorem of mathematical logic that it is impossible to specify the function that assigns to each non-empty subset of $\mathbb{R}$, an element of itself.     There are several notes and books on axiom of choice, but here I am trying to understand through doing some argument for some problem, where problem actually arises.
111309
Having read the classical proof of the existence of an Algebraic Closure (originally due to Artin), I wondered what is wrong with the following simplification (it must be wrong, otherwise why would we bother with the extra complications in Artin's proof?):  Theorem: Let $K$ be a field, then $K$ has an algebraic closure $\bar{K}$ (i.e an algebraic extension that is algebraically closed).   "Proof": Define $A=\{ F \supset K | F \text{ is an algebraic extension of } K\}$ and inherit this with the usual partial order of inclusion. One can check that Zorn's lemma applies (union of a nested chain of algebraic extensions is itself algebraic). Thus take $\overline{K}$ to be a maximal element. It must be algebraically closed for otherwise there is an irreducible polynomial with root in some strictly bigger field.  $\blacksquare$  Now here is what I suspect is false about this proof: The definition of $A$ smells like your usual set theory paradoxes like Russell's paradox. In fact one could just as well use the same technique to prove that there exists a "largest set" which of course there does not. I am however under the impression that "most" working mathematicians ignore set theory foundations and just "do" mathematics, so is there a safe way of doing this (i.e: do "concrete everyday mathematics" by avoiding set theory) without getting burnt?
43278
I have been thinking about the following formulation of the Axiom of Choice.:     For any relation $R$, there is a function $H$, which is a subset of $R$, and such that $\operatorname{dmn}H=\operatorname{dmn}R$.   At first, it seemed surprising to me that this did not follow from Comprehension (i.e., from the schema  $\forall x_1, x_2, ..., x_n \forall C\exists B \forall x ( x \in B \Leftrightarrow x \in C \land \phi )$, where $B$ does not occur free in $\phi$).    I thought that for any relation, it seems that we should be able to define a subset of it with the same domain meeting a "functional condition".  But when I tried to do this, I couldn't.  However, I felt like I was getting close when I let $B$ be free in $\phi$, i.e., when I let myself say that $w$ is in $R$ and also anything in $H$ meets such and such conditions, where $H$ is the set (function) whose existence I'm trying to prove.    But my understanding is that Choice does not even follow from Naive Comprehension.  So, I wondered if someone could explain the following precisely.   Why does the above formulation of Choice does not follow from regular Comprehension? Why does it not even follow from Naive Comprehension (assuming that it does not)?
9958
For sets $A,B$, let $|A|\leq^*|B|$ say that there exists an onto map $f:B\rightarrow A$ or $A=\emptyset$.   My question is, is $$\forall A,B(|A|\leq^*|B|\longrightarrow |A|\leq|B|)$$ equivalent to the axiom of choice?  Thanks
9719
I understand that the axiom of choice, given the axioms of ZF set theory, is equivalent to the statement that "the Cartesian product of any family of nonempty sets is nonempty." I've been unable to find this proof. Could someone sketch it for me? Or provide me with a source at least?
122676
Hi everyone I'd like to know if the following reasoning is correct, any suggestion would be great. Thanks.  Proposition: Let $Y$ be a set and let $f: \mathbb{N}\rightarrow Y$ be a function. Then $f[\mathbb{N}]$ is at most countable.   Proof: If $Y$ is finite the result follows, this is because$f[\mathbb{N}]\subset Y$ and any subset of a finite set  is finite and has at most the size of the set in which is contained.   We may assume  that the set $Y$ is infinite. We set $A:= \{\,n\in\mathbb{N}:f(i)\not=f(n) \,\,\text{ for  any }i&lt; n\, \}$. And we define the function $g:A \rightarrow f[\mathbb{N}]$ as the restriction of $f$ in $A$. We claim that the function $g$ is a bijective map. From the definition of $A$ we already know that the map is $1:1$. We will show that also is onto.   Let $y\in f[\mathbb{N}]$. Suppose for the sake of contradiction that there is no $n\in A$ such that $g(n)=y$. Since $y$ lies in the image of $f$, then there is some $j\in \mathbb{N}$ for which $y=f(j)$. Then either $f(j)\not= f(i)$ for any $i&lt;j$ or there exists some $i&lt;j$ such that $f(j)= f(i)$. For the former, $j$ lies in $A$ (by its definition). For the latter, the set $\{\, n\in \mathbb{N}: f(j)=f(n)\, \text{and }\,n\not=j \}$ is non empty, and hence has a minimum element. Let $m$ be its minimum element. Then $f(m)\not=f(n)$ for any $n&lt;m$ and thus $\,m\in A$ but $g(m)=f(m)= f(j)=y$. Thus any case leads to a contradiction. The result follows by reductio ad absurdum. Hence $f$ is surjective and injective, i.e., a bijective map.   Since there is a bijection between $A$ and the images of the natural numbers under $f$, both have the same cardinality. Also we already know that $A\subset \mathbb{N}$ and any set of the natural numbers is denumerable, thus $f[\mathbb{N}]$ is countable. $\Box$
96329
The statement is:     In a commutative ring with 1, every proper ideal is contained in a maximal ideal.   and we prove it using Zorn's lemma, that is, $I$ is an ideal, $P=\{I\subset  A\mid A\text{ is an ideal}\} $, then by set inclusion, every totally ordered subset has a bound, then $P$ has a maximal element $M$.  My question is why $M$ must contain $I$?
89287
It is well-known (forgive the pun) that the axiom of choice (which states that the product of every non-empty family of non-empty sets is non-empty) implies that the proper class of all cardinal numbers is well-ordered, at least in the presence of the ZF axioms.  Does the converse hold? If not, is the statement that the proper class of all cardinal numbers is well-ordered consistent with axioms like determinacy, which, while interesting, contradict full-blown choice?
9838
In the proof of 'Every open set in $\mathbb{R}^1$ is a countable union of disjoint open intervals', we need to pick one rational representative from each of the intervals hence establish the countability.  This seems to depend on the axiom of choice.  Thus I wonder does this property of $\mathbb{R}$ is equivalent to the axiom of choice, that is, is there any construction such that this property is not true once we abandon the axiom of choice?  Thanks!
73143
Assuming the axiom of choice, show that there exists a sequence of function $\langle f_\alpha\mid\alpha&lt;\omega_1\rangle$ such that: (1) each $f_\alpha:\alpha\rightarrow\omega$ is injective and (2) for all $\alpha&lt;\beta$, the set $\{\gamma&lt;\alpha\mid f_\alpha(\gamma)\not=f_\beta(\gamma)\}$ is finite.   My knee-jerk reaction in trying to solve this problem is to define the sequence by recursion. But I don't see how to actually carry out the construction (in particular, I don't see how I could ensure that (2) remains to be the case once I pass $\omega$). Any help is appreciated.
88618
Let $(X, \leq)$ be an infinite poset. Prove that there is an infinite $X&#39; \subset X$ for which holds one of the following:  1) Induced order on $X&#39;$ is linear.  2) $(X&#39;, \leq_\mathrm{ind})$ is antichain. (Every two elements in $X&#39;$ are incomparable)    My attempt:  Let's start trying to construct a linearly ordered set $(X&#39;, \leq_\mathrm{ind})$ element by element. First we take some element $x_1 \in X$, then we take another $x_2 \in X$ such as $x_1 \leq x_2$ or $x_2 \leq x_1$. Basically, we take an element from $X$, if it is "good" we put it in our chain, otherwise we throw it away. We continue constructing the chain that way. If we do not stop at some finite step, then we are done, we have constructed linearly ordered subset.  If we do stop at some $x_n$ that means that we have finite amount of comparable elements, which means that $X \setminus X&#39;$ is an antichain.    a) I am not sure about the soundness in the last step, could somebody please check it?  b) Can this be proved without a choice function?