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

Question

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.

Answer 1

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".

Answer 2

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.