I know that you need axiom of choice to prove Banach–Tarski paradox. But what happens with paradox when we remove axiom of choice? Does theorem become false? Or is there just no proof of it without axiom of choice?
123901
Is it possible to prove the infamous Banach-Tarski theorem without using the Axiom of Choice?  I have never seen a proof which refutes this claim.
44273
I don't know much about set theory or foundational mathematics, this question arose just out of curiosity. As far as I know, the widely accepted axioms of set theory is the Zermelo-Fraenkel axioms with the axiom of choice. But the last axiom seems to be the most special out of these axioms. A lot of theorems specifically mention that they depend on the axiom of choice. So, what is so special about this axiom?  I know that a lot of funny results occur when we assume the axiom of choice, such as the Banach-Tarski paradox. However, we are assuming the other ZF axioms at the same time. So why do we blame it to the axiom of choice, not the others? To me, the axiom of regularity is less convincing than the axiom of choice (though it's probably due to my lack of understanding).
34329
The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using the Deduction theorem (and without any hypothesis).  The axioms are:  $A1: B\implies(C\implies B)$  $A2: (B\implies(C\implies D))\implies((B\implies C)\implies(B\implies D))$ $A3: (\lnot C\implies\lnot B)\implies((\lnot C\implies B)\implies C)$  The only inference rule is MP.  I have a proof but it is long. My proof is based on the proof of Lemma 1.11 (d) which proves $(\lnot C\implies\lnot B)\implies(B\implies C)$ but uses the Deduction Theorem (Proposition 1.9). Then, like Mendelson suggests in exercise 1.49, I apply the process used to prove the Deduction Theorem to the steps. To be precise, I assume $(\lnot C\implies\lnot B)$ as a Hypothesis $H$. If $C_1,C_2,\dots,C_n$ is a proof of $(B\implies C)$ that uses $H$ then stepwise I prove $H\implies C_i$ for $i=1,\dots,n$. The last step is $H\implies C_n$ which is what we want to prove.  This way requires around 4 uses of Axiom1, 4 of Axiom2, 1 Axiom3, and 9 uses of Modus Ponens.  Do I miss a shorter proof?
16106
For every vector space $V$ does there exist a linear functional $f$ ( a linear map from $V$ to $F$ the underlying field ) such that for some $ \vec v \in V$ , $f(\vec v) \ne 0$ ? If it does exist , can we prove the existence without the "axiom of choice " ? Is the existence equivalent to axiom of choice ?
70405
$((\neg \alpha \to \alpha) \to \alpha) $  Hi, I am trying to prove this.  Can someone gives me some hints to start the question... My friend told me I might need to use deduction theorem here, but I have no clue to approach it..  Axiom 1: A→(B→A).  Axiom 2: (A→(B→C))→((A→B)→(A→C)).  Axiom 3: (¬B→¬A)→((¬B→A)→B).  To clarify: A, B, C, α, and β are propositions (i.e. assigned True or False). → and ¬ have the standard logical meanings.
51507
Can someone give an argument, if possible using only the axioms of set theory, because I'm very weak there and have virtually no background, except the usual knowledge of the operation with sets one has to have when doing non-set theoretic non-research mathematics, why $\emptyset \in \emptyset$ or $\emptyset \subseteq \emptyset$ should or should not hold?
66090
Yesterday I pose a question where I ask about the correctness of a proof where I shown that the Axiom of Choice implies that for any not empty collection of not empty sets the projection defined on their cartesian product  are surjective funcions, so then I asked to me if from the assertion about the surjectivity of the projections I can argue the Axiom of Choice. Here following the link of the question where I proved the first implication: .   Well could someone help me, please?
71788
Assuming the axiom of choice, it can be shown that every infinite set contains a countable subset. Also, it is my understanding that the proof of this statement requires at least countable choice - i.e., it is consistent with ZF that there exist infinite sets which contain no countable subset.  However, consider the following proof:  Given an infinite (i.e. not equinumerous to any natural number) set $S$, let $A_1$ be a set containing one element in $S$, and construct $A_n$ by adding to $A_{n-1}$ any element from $S$ not already in $A_{n-1}$. This can be done since $S$ is finite, so at no point is $A_{n-1}$ equal to all of $S$. We can construct every $A_n$ using only ZF, since we are only making finitely many choices. Now, define $f: \mathbb{N} \rightarrow S$ by defining $f(n)$ to be the unique element in $A_n \backslash A_{n-1}$. $f$ is injective since $f(n) \notin A_m$ for every $m &lt; n$, so $f(n) \neq f(m)$. Hence, $f$ is an injection from $\mathbb{N}$ to $S$, and the image of $f$ is a countable subset of $S$.  My problem is figuring out where in this proof the axiom of choice is used. It seems the construction of the $A_n$'s can be done without AC, since we are only making a finite number of choices. The construction of $f$ involves choosing an element from $A_n \backslash A_{n-1}$, but since we have a systematic way for choosing (take the unique element in the set) that should be allowed. I know this proof must depend on the axiom of choice, but where is it used?
3648
I recently read a proof that had the following in it: "since $A$ is non-empty, we can find an element $x$ in $A$." This proof did not mention the axiom of choice, but it seems to me that it would be required to make the proof formal. Would I not require a choice function to allow me to find/pick some element $x$ from $A$ after noting that A is non-empty? Thanks
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?
38663
Is there any example of a non-measurable set whose proof of existence doesn't appeal to the Axiom of choice?  What would it imply if there was such an example?  EDIT: For instance, maybe this will help understand the kind of example I had in mind, it is known that an important feature to determine that the AC is needed in the Banach-Tarski case is the non-transitivity of rotations on Euclidean space, one might find an example of a transitive group for some given space keeping the rest equal and make the AC unnecessary?  I guess then it might be said that this transitivity will be in this particular case equivalent to the AC or some amount of it, but I guess that it would be important to show this if it hadn't been realized before.
40258
So I am relatively familiar with the Axiom of Choice and a few of its equivalent forms (Zorn's Lemma, Surjective implies right invertible, etc.) but I have never actually taken a set theory course.  I know there are times when an explicit way of choosing some elements may not be provided, and instead we call upon the Axiom of Choice to do it for us. But one thing has always bothered me.  I have heard that for a finite set we do not need the Axiom of Choice to choose an element. I find this a little confusing. How is choosing an element from a finite set any different than choosing from an infinite set? I have heard before "since the set it finite, there are finitely many orders, so order the set and choose the first element in the order." But how does one choose what order to use? This involves picking an element from a finite set, i.e. it presumes the conclusion.  I'm guessing there is a good reason why everyone keeps insisting that the Axiom of Choice in not needed to choose from finite sets, so could someone please explain it to me?  Edit: There seems to be confusion on what exactly I am asking. I know that we need the Axiom of Choice, sometimes, to make infinitely many choices, from finite or infinite sets. This is not what is confusing me. Allow me to be more precise:     Suppose $S$ is a nonempty finite set. I want to pick one element from $S$. Does choosing one element from $S$ require the Axiom of Choice? If not, how can the choice be made without the Axiom of Choice?   Saying $S$ is not empty, therefore there is an $x \in S$, does not suffice. How do I choose such an $x$? There is one, but how do I describe it without any information about the set, other than the fact that it nonempty and finite?  Another clarification: I am not asking about using "Let ... be given" as a proof technique.
51407
Is there anything wrong with the following proof?  Theorem. Every non-empty subset $B \subset\mathbb{N}$ has a least member.  Proof. Assume not. Then, of necessity, we'd have to have $B=\varnothing$, for if $B$ contained even one $b\in\mathbb{N}$, then that $b$ would satisfy $b=min(B). $ Contradiction, end proof.  I get the sense there is something wrong here, but I can't seem to define exactly what. Also, is there a context where one can simply take this principle as an axiom, and not have to prove it? After all, it is extremely intuitive. Thanks.
105938
This winter I started to study much harder the set theory and especially the axiom of choice. Unfortunately, I have problems with solving the next exercise:  Prove that the 3 statements of the axiom of choice are equivalent :  1) For any non-empty collection $X$ of pairwise disjoint non-empty sets, there exists a choice set.  2) For any non-empty collection $X$ there is a choice function.  3) For any non-empty set $X$, there exists a function $f:P(X)\setminus\{\varnothing\}\to X$ so that for any non-empty set $A\subseteq X$, $f(A) \in A$.
118996
I would like to know if someone can explain in a somehow down to earth (almost logic free) way why is it true that in an axiom system where there is some statement $P$ such that $P$ and its negation $\lnot P$ are true, then every statement in the system is true?  I'm not sure if this can be done, but basically since I don't know any formal logic at all, I'm interested in seeing if at least the argument can be conveyed in an intuitive way, or if the idea can be explained without talking about first or second order logic and using symbols like $\top$, $\bot$, and $\vdash$.  This  is like the formal version (which I don't understand) so maybe my question can be thought of as a version for dummies of that question.   Thanks a lot in advance.
44194
This is the first part of the first half of the a proof in the Axiom of Choice. The proof that the Axiom of Choice is equivalent to the choice function. REsources: Keith Devlin's Joy of Sets: pg. 58. F.R. Drake and Singh Intermediate Set Theory: pg. 110).   I am confused on proving disjointness and will ask further questions of proof once I get this first part v. clear for myself.   AC1: Let $\mathcal F$ be a family of pairwise disjoint, non-empty sets. Then there is a set $\mathcal M$ that consists of precised one element from each member of $\mathcal F$  AC2: For every family $\mathcal F$ of non-empty sets, there is a choice function $\mathcal f$. (I.e. $\mathcal f(X)$ is a member of X, for each X in $\mathcal F$.   Disjointness: Two sets are disjoin if Q $\cap$ R = $\emptyset$. Meaning that they have zero elements in common. These sets do not overlap.   Show: AC1 $\leftrightarrow$ AC2   (1) ($\rightarrow$) Let $\mathcal F$ be a set of nonempty sets.   (2)For each X $\in$ $\mathcal F$, let $X^*$ = (X $\times$ {X}) = {(x, X) | x $\in$ X})  (3) Show Disjointness.  An outline of how book proves  disjointness:  (a) if u = {(X $\times$ {X}) | x $\in$ X} then u is of the form $\lt  z, t \gt$ where z = X and t=x, i.e. x $\in$ X.   (b) then if u $\in$ ({X} $\times$ x) $\cap$ ({Y} $\times$ Y) $\rightarrow$ u = $\lt z, t \gt$ with z = X and z=Y, i.e. X=Y. Which means ({X} $\times$ x) = ({Y} $\times$ y).  Questions: (1) Apparently we cannot prove disjointness in $\mathcal F$ but must prove in a different set. If so, why is that?  (2) why is the case that if u $\in$ ({X} $\times$ X) $\cap$ ({Y} $\times$ Y) then z =X and z=Y? I am not following that step at all.   (3) why does the axiom of choice have to do with ordered pairs? Why are we setting X $\in$ $\mathcal F$, let $X^*$ = (X $\times$ {X})?    Thank you!
42405
As I'm sure many of you do, I read the  webcomic regularly. The  involves a joke about the Axiom of Choice, which I didn't get.     I went to Wikipedia to see what the Axiom of Choice is, but as often happens with things like this, the Wikipedia entry is not in plain, simple, understandable language. Can someone give me a nice simple explanation of what this axiom is, and perhaps explain the XKCD joke as well?