1
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ So the construction I made may be empty, but could one prove the existence of a subset $S'$ isomorphic to $S$? $\endgroup$
    – Darth Geek
    Commented Apr 12, 2017 at 13:20
  • 1
    $\begingroup$ No. This is exactly the counterexample in my answer. If you could produce such a subset, it would be a de facto choice function. $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 12, 2017 at 13:21
  • $\begingroup$ And could I assert that the cardinality of $\text{Graph}(f)$ is greater or equal to that of $S$? $\endgroup$
    – Darth Geek
    Commented Apr 12, 2017 at 13:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 12, 2017 at 13:26
  • $\begingroup$ Can I at least say that $\text{Graph}(f)$ is infinite? Otherwise its cardinality would be comparable to that of $S$, right? $\endgroup$
    – Darth Geek
    Commented Apr 12, 2017 at 14:33
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)$? $\endgroup$
    – Darth Geek
    Commented Apr 12, 2017 at 13:21
  • $\begingroup$ @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. $\endgroup$
    – hmakholm left over Monica
    Commented Apr 12, 2017 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .