# Tag Info

6

No, there cannot be a formula that always defines a Vitali set whenever one exists. In fact we can say something stronger: There is a model of $\mathsf{ZFC}$ with no definable Vitali set. Assume that $\mathsf{ZF} + \mathsf{DC}$ holds but there is no Vitali set (this follows, for example, from "$\mathsf{ZF} + \mathsf{DC} + {}$every set of reals has the ...

5

If we only reduce to $\Bbb Z$-modules, then we can already identify a very strong connection: The axiom of choice is equivalent to the statement "All divisible abelian groups are injective". Moreover, there is a model where the axiom of choice fails and there are no injective abelian groups, at all, so the above equivalence fails in a very acute way. ...

4

Your function is not really an injection. What you essentially need to show is that there is an injection from $\aleph(X)$ into $\mathcal{P(P(P}(X)))$, which will conclude that its $\aleph$ is larger than that of $X$ itself. Recall that $\aleph(X)$ is the least ordinal $\kappa$ such that there is no injection from $\kappa$ into $X$. Therefore if ...

4

I don't have a proof that the existence of any injection depends on the axiom of choice, but the existence of a right inverse is equivalent to AC, as follows. Let $X$ be a set not containing $\emptyset$ and consider the set $Y = \{(z, A)\ |\ z\in A \in X\}$. Define $f:Y\rightarrow X$ by $f((z,A)) = A$. If $g$ is a right inverse of $f$, then $g^*(A)$ given ...

3

Something much weaker is false: It is consistent with $ZFC$ that every (ordinal) definable collection of sets of reals consists solely of Lebesgue measurable sets of reals or has the same size as the set of all subsets of continuum. This (and a category analogue of it) is due to Harvey Friedman.

3

Note that if $f\colon A\to B$ is onto $B$ (and we can always take $B=\operatorname{rng}(f)$ for that), then $f^{-1}(b)$ is a non-empty set. Using the axiom of choice it is easy to construct an inverse. On the other hand, if you have a family of disjoint sets, $\{A_i\mid i\in I\}$ then there is a function from $\bigcup A_i$ onto $I$, such that its inverse is ...

2

Note that there is a version of Baer's criterion which is true in ZF: If $M$ is some $R$-module with the property that for every ideal $I \subseteq R$ the map $\hom(R,M) \to \hom(I,M)$ is surjective, then for every submodule $A \subseteq B$ such that $B/A$ is finitely generated we have that $\hom(B,M) \to \hom(A,M)$ is surjective. The proof proceeds by ...

2

Suppose we are in a model where the following is true: There are no free ultrafilters on $\Bbb N$. There exists an amorphous set. First of all note that if $A$ is amorphous, then $A$ carries exactly one free ultrafilter, all the cofinite subsets. Then in this model $A\cup\Bbb N$ has only one unique ultrafilter, all those containing a cofinite subset of ...

2

HINT: To show that the axiom of choice holds it suffices to show that for every non-empty $X$, there exists a choice function on $\mathcal P(X)\setminus\{\varnothing\}$. If $(A,\leq)$ is a well-ordered set then there is a choice function for $\mathcal P(A)\setminus\{\varnothing\}$ definable from $\leq$. If $A$ is equipotent with an ordinal then $A$ can be ...

1

Why can't we just let $f(X)=0$ and $f(Y)=1$. Because the function has to be extensional. If $X = Y$ then the quoted definition would not give a function. The proof is using $P∨¬P⟺T$, isn't it? Yes, because equality for natural numbers is decidable: given two natural numbers $n,m$, the constructive systems to which Diaconescu's theorems applies ...

1

Note that using $f$ as an additional symbol, one can write the definition of $g$ as a first-order statement, as well the definition of $G$ (note that $g$ is not really a variable, because $g$ itself is definable from $f$). The statement, if so, about $T(n)$, is all but a first-order statement in the augmented language of the natural numbers. Shoenfield's ...

1

HINT: If you have a choice function for $\wp(X)\setminus\{\varnothing\}$ and a bijection $f:Y\to X$, it’s straightforward to construct a choice function for $\wp(Y)\setminus\{\varnothing\}$. If $\alpha$ is an ordinal, there is a very simple choice function for $\wp(\alpha)\setminus\{\varnothing\}$.

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