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