Tag Info

Hot answers tagged

12

The answer is that we can't write a formula which provably defines a well-ordering of $\Bbb R$ in $\sf ZFC$ (at least assuming that $\sf ZFC$ is consistent), although I don't know whose to credit for it. Suppose that $\varphi(x,y)$ provably defines a bijection of $\Bbb R$ with an ordinal (this is equivalent to the way you state it, just making it easier to ...


10

Forcing with sufficiently homogeneous forcing that adds reals is enough to obtain the negation of $(*)$. The point is that if a formula $\phi$ defines a parameter-free well-ordering of $\mathbb R$, then for any ordinal $\alpha$, the statement "$x$ is the $\alpha$-th real in the well-ordering defined by $\phi$" uniquely characterizes $x$ in terms of $\alpha$. ...


6

In addition to what Noah wrote, Jech "The Axiom of Choice" has a proofs, partial proofs, or problems with hints for the following: In the first Cohen model, the axiom of [countable] choice fails; but the Boolean Prime Ideal theorem holds. Therefore every filter can be extended to an ultrafilter there. There is a model of $\sf ZF$ in which there are no free ...


5

See this mathoverflow question http://mathoverflow.net/questions/59157/reference-request-independence-of-the-ultrafilter-lemma-from-zf, especially the answer by Andreas Blass. Sol Feferman proved that $ZF$ does not prove that there is a nonprincipal ultrafilter on $\omega$, in "Some applications of the notions of forcing and generic sets" ...


5

Yes, it requires the axiom of choice. It was shown by Feferman and Levy, as one of the first uses of forcing, that it is consistent that $\omega_1$ is the countable union of countable sets. This means that there is a countable subset of $\omega_1$ which is unbounded. This is just assuming the consistency of $\sf ZFC$. (The idea is simple, for each $n$ add ...


5

The question is what do you mean by "use". You can show that countable choice does not imply the existence of a non-measurable set; but strengthening it to $\sf DC_{\aleph_1}$ does. Countable choice is not used at all in the proof that a product of compact Hausdorff spaces is compact. This is in fact equivalent to the Ultrafilter Lemma, which is consistent ...


4

No, this is not true. If $D$ is a Dedekind finite set with a Dedekind finite power set, then $\ell_1(D)$ is a Banach space which has a Hamel basis which is also a Schauder basis, and every linear operator from $\ell_1(D)$ to a normed space is continuous. But if $D$ is Dedekind finite, then $|D|^{\aleph_0}>|D|$. So it suffices to assume that an infinite ...


3

Finding a basis for $\Bbb R^\infty$ depends on how you choose to define $\Bbb R^\infty$. Let's expand on @MattSamuel's comment by introducing some terminology. The support of a function $f:X\to\Bbb R$ is the set $$ \DeclareMathOperator{supp}{supp}\supp(f)=\{x\in X:f(x)\neq0\} $$ One reasonable definition of $\Bbb R^\infty$ is $$ \Bbb R^\infty=\left\{\Bbb ...


3

This is certainly possible for a specific point: Suppose there is a infinite, Dedekind-finite set of reals $A$. Then let $f$ be the characteristic function of $A$. Since $A$ cannot be closed (perfect set property), let $a$ be in the closure of $A$ but not in $A$. Then $f$ is sequentially continuous at $a$ (since no $\omega$-sequence of elements of $A$ ...


2

The issue is that $\sf DC$ is not the right tool for constructing measures or ultrafilters. Both, when constructed by transfinite recursion, require recursion much longer than a countable length, which really all that $\sf DC$ can give you. The tool for obtaining such objects is instead the Boolean Prime Ideal theorem, or weaker theorems like the ...


2

Theorem $\mathbf{4.54}$ in Horst Herrlich, Axiom of Choice: Equivalent are: $\Bbb R$ is Fréchet. Each subspace of $\Bbb R$ is sequential. $\Bbb R$ is Lindelöf. Each subspace of $\Bbb R$ is Lindelöf. Each second countable topological space is Lindelöf. Each subspace of $\Bbb R$ is separable. Each second countable ...


2

In general, no. Because your propositional logic could have a "strange" number of propositional variables. If you assume, however, that there are only countably many propositional variables, then you can prove without the aid of the axiom of choice that there are only countably many propositions to write. Then you can enumerate them, and start enlarging ...


2

If $\Omega$ has cardinality larger than that of $F$, then all you need to show is that $F\cup F(\omega)$ as the same cardinality of $F$. Then $\Omega\setminus(F\cup F(\omega)$ has the same size as $\Omega$ itself. If $F$ is finite, then $F(\omega)$ is finite, and $\Omega$ is infinite, so we're good. If $F$ is infinite, then we really just need to check ...


2

The answer is, as Noah suggests, negative. Suppose that $\frak M$ is a model of $\sf ZFCU$ where $U$ is not a set. Consider the model generated by taking all the permutations of $U$ which are sets (namely, permutations of a subset of $U$, and therefore the identity elsewhere). And consider $\cal F$ to be the filter generated by ...


2

If I understand ZFCU correctly, then the answer should be "no": there seems to be nothing ruling out a model $M$ of ZFCU in which the atoms do not form a set, there is a linear order $L$ on the class of atoms with no $L$-greatest element, and there is no infinite set of atoms. In such a case, SDC would fail for the formula $\phi(x, y)\equiv$"$x$ is not an ...


1

HINT: If $A$ can be mapped onto $B$, then there is an injection from $B$ into $\mathcal P(A)$. Now apply Hartogs theorem.


1

This is closely related to König's lemma, which is equivalent in ZF to a choice principle for countable collections of finite sets. The Wikipedia article for König's lemma has a couple references. Quoting Wikipedia, In particular, when the branching at each node is done on a finite subset of an arbitrary set not assumed to be countable, the form of ...


1

Here is a finite version of Scenario 1: * List the rational numbers in $(0,1)$. * Pick a large number $n$ * For each of the first $n$ numbers, associate one of the first $n$ numbers. The probability that one of the first $n$ numbers never appears is $(1-1/n)^n$, which approaches $1/e$ as $n\to\infty$. The chance that it does appear approaches $1-1/e=0.632$


1

Sure. Let $G$ be some undecidable sentence of ZFC, and let $$ \begin{align} \varphi(x) &\equiv x=\{42\} \\ \psi(x) &\equiv G \land x=\langle\{42\},42\rangle \end{align} $$


1

You have two mistakes, as pointed by Andres in the comments. The claim that for an infinite set $A$, the set $B=\{X\subseteq A\mid X\text{ finite}\}$ has the same cardinality as $A$ requires the axiom of choice. For a Dedekind-finite set this is most certainly false in any case (there's an injection from $A$ into $B$, and this injection is not a ...


1

I'm recording my solution here for posterity. The key step is indeed the usage of Cantor normal form, but there are quite a few extra details that were not obvious to me at the start. First, some facts about ordinals, whose proofs are relatively straightforward and so ommitted: If $\alpha<\omega^\gamma\le\beta$, then $\alpha+\beta=\beta$. If ...



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