# Existence of set without the usage of the axiom of choice.

Let $S$ and $R$ be infinite sets and let $FP^*(R)$ be the set of finite non-empty subsets of $R$.

Say that I have a map $f:S\to FP^*(R)$ and let $\text{Graph}(f) = \{(s,r) \in S\times R\mid r\in f(s)\}$.

Using the axiom of choice I can select an element $r_s\in f(s)$ for each $s\in S$ to create a subset $S'$ of $\text{Graph}(f)$ isomorphic to $S$. (Here $S' = \{(s,r_s)\mid s\in S\}$).

Can I assert that such a subset exists without using the axiom of choice?

I think that the fact that the set $$\{g:S\to R \mid \forall s\in S,\, g(s) \in f(s)\} \cong \prod_{s\in S} f(s)$$ is not empty and each $g$ yields a subset $S'$, then it must exist (even if I can't produce a $g$ without the usage of the axiom of choice).

But I'm not convinced that my reasoning is rigorous.

No. Of course not. Exactly because "the fact that the set ... is non-empty" is not a fact, but rather a consequence of the axiom of choice. It is true that it is a set without using choice, but it might as well be empty.

For example, suppose there is a Russell set. Namely, $S$ is the countable union of pairs $\{P_n\mid n\in\Bbb N\}$ such that there is no infinite family of $P_n$'s that admits a choice function.

Now consider the function mapping $n\in\Bbb N$ to the pair $P_n$. If you could have produced a section like you wanted, then you would have had ac choice function from the $P_n$'s.

This can probably be generalized so the principle you suggest will be equivalent to "the axiom of choice from arbitrary families of finite sets".

• So the construction I made may be empty, but could one prove the existence of a subset $S'$ isomorphic to $S$? Commented Apr 12, 2017 at 13:20
• No. This is exactly the counterexample in my answer. If you could produce such a subset, it would be a de facto choice function. Commented Apr 12, 2017 at 13:21
• And could I assert that the cardinality of $\text{Graph}(f)$ is greater or equal to that of $S$? Commented Apr 12, 2017 at 13:24
• Again, no, because in the Russell set example, the graph of $f$ is isomorphic to the Russell set, rather than the domain which is the natural numbers. But the Russell set is not larger (nor smaller) than the natural numbers; it is incomparable. Commented Apr 12, 2017 at 13:26
• Can I at least say that $\text{Graph}(f)$ is infinite? Otherwise its cardinality would be comparable to that of $S$, right? Commented Apr 12, 2017 at 14:33

No -- whithout the axiom of choice you cannot be sure that an $S'$ exists. In a world that doesn't satisfy AC it is entirely possible that the product $\prod_{s\in S}f(s)$ is empty.

This is the case even if you assume that every $f(s)$ has exactly two elements.

• Do you mean that any $S'\subseteq \text{Graph}(f)$ isomorphic to $S$ must be an element of $\displaystyle\prod_{s\in S} f(s)$? Commented Apr 12, 2017 at 13:21
• @DarthGeek: If by "isomorphic to $S$" you mean that each element of $S$ is a first part of exactly one of the pairs in $S'$, then yes. Commented Apr 12, 2017 at 13:27