Hot answers tagged

14

Your confusion here reminds me of the old saying "The axiom of choice is clearly true, the well-ordering principle is clearly false, and who can say about Zorn's lemma?" While for any $\alpha$, you can choose an $x_\alpha \in X_\alpha$, you need the axiom of choice to show that this can be stitched together into a full choice function that is simultaneously ...


8

Suppose that a family $X$ has only two elements, $X_1$ and $X_2$. Then, if $X_1$ is nonempty we can use Rule C to obtain some $b_1 \in X_1$. Also, if $X_2$ is nonempty, we can use Rule C to obtain some $b_2 \in X_2$. Then we can explicitly define a choice function $f$ on $X$ by the rule $$ f(x) = y \Leftrightarrow ( x = 1 \land y = b_1) \lor (x = 2 \land y ...


6

This is false without the axiom of choice. Mostowski constructed a model of $\sf ZFA$ (set theory with atoms), and in that model for every $n\in\Bbb N$ there is some $A$ such that: $$|A|<|A|^2<\ldots<|A|^n=|A|^{n+1}$$ So taking a large enough $n$ (e.g. $n=2$) we can take $X=A^{n-1}$ and $Y=A^n$. The Jech-Sochor theorem is enough to transfer this ...


5

No. Suppose that $A$ is a strongly amorphous set. Namely, $A$ is infinite Dedekind-finite set, such that every subset of $A$ is finite or co-finite. Every partition has only finitely many non-singletons. Now every function with domain $A$ induces a partition and only finitely many fibers have nontrivial choices. Of course, it is consistent that there ...


4

König’s inequality in its full form implies the axiom of choice. Let $\{A_i:i\in I\}$ be a set of non-empty sets. Clearly $|\varnothing|<|A_i|$ for each $i\in I$, so by König’s inequality we have $$0<\left|\prod_{i\in I}A_i\right|$$ and hence $$\prod_{i\in I}A_i\ne\varnothing\;.$$ This is one of the many equivalent forms of $\mathsf{AC}$.


4

Sure — this will happen in any model where there is a countable set $X=\{A_i: i\in\mathbb{N}\}$ of countable sets of reals, whose union is not countable. Fix bijections $f_i$ from $\mathbb{R}$ to $(i, i+1)$ for each $i\in\mathbb{N}$, and let $$\hat{S}=\bigcup_{i\in\mathbb N} f_i(A_i).$$ Now to make it dense, just let $S=\hat{S}\cup\mathbb{Q}$. (Lest it seem ...


4

You have a hidden assumption in the proof of your first proposition. If $\beta_{x}\leq d<d'<\beta_{\alpha}$ whenever $x<\alpha ,$ then in order that the map that sends $d$ to $(\alpha,f_{\alpha}(d))$ be 1-to-1, you need each$f_{\alpha}:\beta_{\alpha}\to |\beta_{\alpha}|$ to be 1-to-1. Now for each $\alpha$, such $f_{\alpha}$ exists but it is ...


3

You can do it when the Banach space $E$ is separable (i.e. $\overline {\{x_n\}}=E$ for some sequence). Here a sketch of the way following the "Cours de Theorie de l'Approximation" of Professor P.J.Laurent (Grenoble University). Let $V$ a vectorial subspace of $E$ and $f\in V^*$ with $$||f||=\sup_{||x||\le 1;\space x\in V} |f(x)|$$ We have to show $\exists ...


3

No, we can't quite prove this. Cohen's first model for the failure of the axiom of choice has a set of real numbers which is infinite but Dedekind-finite. This means exactly that this set has cardinality incomparable with that of $\Bbb N$. But we know that $\Bbb R$ and $\mathcal P(\Bbb N)$ have the same cardinality, even without assuming the axiom of ...


3

You can probably find the proof that every successor cardinal is regular in many places, for example, here: A Successor Cardinal is Regular. The discussion of the use of Axiom of Choice in the proof of this result can be found here: The regularity of successor cardinal. I will only write about the part in this particular proof which you singled out as ...


2

The problem with the axiom of choice is that there is no method that can select an element from EVERY set. So, given a set $M$ , we cannot guarantee that the axioms of $ZFC$ allow a selection of an element of $M$, although there must be some, if $M$ is non-empty.


2

Well, "constructively verifable" means different things in different contexts. But I am going to take it here as "true without the axiom of choice". So first of all, the compactness theorem holds for countable languages in $\sf ZF$. So if you add just one constant symbol, compactness still works, and you get a nonstandard model of Peano. In fact, you can ...


2

Yes. Assume $\neg DC$. Then there exists $S$ and a binary relation $R$ on $S$ (that is, $R\subset S\times S$ ) and some $x_0\in S$, such that : $$(1)...\; \forall x\in S\;\exists y\;(\;(x,y)\in R).$$ $$(2)...\; \neg \exists H:\omega \to S\; \;(H(0)=x_0\land \forall n\in \omega \; (\;(H(n),H(n+1)\;)\in R).$$ For $n\in \omega$ let $F_n$ be the set of ...


2

You cannot prove that $\aleph_1\leq2^{\aleph_0}$ without assuming some choice, but there is no need to assume the continuum can be well-ordered. In some models (most famously Solovay's model and the Feferman-Levy model) it is not true that there is an injection from $\omega_1$ into the real numbers. On the other hands if you just destroy the ...


2

Even restricting this to well founded trees is enough to get $\sf DC_\kappa$ for every $\kappa$, which is enough to prove the axiom of choice. So the answer is indeed positive.


1

Yes, and it is easy to see this with the following equivalent of $\sf DC$. $\sf DC$ is equivalent over $\sf ZF$ to the statement "Every tree of height $\omega$ without leaves has a maximal branch". Now, if $\sf DC$ fails, there is a tree of height $\omega$ without leaves, but without a maximal branch. This means that every chain in this tree is finite, ...


1

Your language is countable, your structure is well-orderable. This means that you can prove the existence of Skolem functions without appealing to choice. So the usual proof should work pretty much out of the box.


1

Assume that the ascending chain condition implies the maximum condition. Then we can almost prove Dependent Choice: Let $X$ be a non-empty set and $R$ a binary relation such that for all $x\in X$ there exists $y\in X$ with $xRy$. We want to show that there exists a map $\omega\to X$, $n\mapsto x_n$ such that $x_nRx_{n+1}$ for all $n\in\omega$. Let ...


1

First note that we only need $f(\alpha)\colon \kappa\to X_\alpha$ to be onto (after all the final $F$ is also only needed onto). So I suppose "bijection" is just a typo. We are given for each $\alpha$ that $|X_\alpha|\le\kappa$, i.e., that the set $S_\alpha$ of surjective maps $\kappa\to X_\alpha$ is $\ne\emptyset$. We use AC to pick an element ...


1

We cannot necessarily construct a choice function, but be can show that a choice function exists, i.e., that the set $C$ of choice functions is non-empty (in other words: that the direct product of finitely many non-empty sets is non-empty). Once we know this, we can pick a choice function from this non-empty set and argue with it, e.g., if we have ...



Only top voted, non community-wiki answers of a minimum length are eligible