# Tag Info

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 eachf_{\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