0
$\begingroup$

(I do not know whether the definitions below already have names in the literature; apologies in advance.)

Let $R \subseteq \mathcal{X}\times\mathbb{N}$ be a binary relation. We declare that $A \subseteq \mathbb{N}$ covers $R$ when $\forall x \in \mathcal{X} \;\exists y \in A: xRy$. We declare $R$ as infinite-handed if for all $x \in \mathcal{X}$, there exists an infinite number of elements $y \in \mathbb{N}$ such that $xRy$.

Given two infinite-handed binary relations $R_1 \subseteq \mathcal{X_1}\times\mathbb{N}, R_2 \subseteq \mathcal{X_2}\times\mathbb{N}$, and assuming $\left|\mathcal{X_1}\right|, \left|\mathcal{X_2}\right| \le \left|\mathbb{R}\right|$, can we always find disjoint $A_1, A_2 \in \mathbb{N}$ such that $A_1$ covers $R_1$ and $A_2$ covers $R_2$?

If the answer is "depends", is there any further reasonable assumption or change in the problem which would make the answer positive?

I feel that a positive answer would require the Axiom of Choice, but I haven't yet been successful in formulating the problem well enough to use the Cartesian-product statement of AC. I've also tried Zorn's lemma by ordering $(A_1, A_2)$ pairs by inclusion, but I couldn't prove the upper bound criterion for infinite chains. I've also searched and GPT'd, but to no avail.

$\endgroup$
2
  • 1
    $\begingroup$ What if $\mathcal X_1=\mathcal X_2=\{x\subseteq\mathbb N:x\text{ is infinite}\}$ and $R_i=\{\langle x,n\rangle:n\in x\in\mathcal X_i\}$? $\endgroup$ Commented Apr 17 at 18:41
  • $\begingroup$ @bof you're right. Would you write down the rigorous proof as an answer, so that I can mark as accepted? $\endgroup$ Commented Apr 20 at 13:19

1 Answer 1

Reset to default
0
$\begingroup$

bof provided a good counterexample, but, at the time of writing this, they haven't posted it as an answer yet; so I guess I'll just expand the comment into an answer myself.

As suggested, let $\mathcal{X}_1 = \mathcal{X}_2 = \mathcal{X} = \left\{B \subseteq \mathbb{N} \mid B \textrm{ is infinite} \right\}$, and $R_1 = R_2 = \left\{ \left(B, n\right) \mid n \in B \in \mathcal{X} \right\}$. In this counterexample, $|\mathcal{X}| = |\mathbb{R}|$, but it suffices for this question to note that $\mathcal{X} \subseteq \mathcal{P}(\mathbb{N})$ and so $|\mathcal{X}_1| \le |\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$

If $A_1$ is not cofinite, then $A_1^\mathrm{C}$ is, per definition, infinite, and thus $A_1^\mathrm{C} \in \mathcal{X}$. This means $\forall y \in A_1 : y \notin A_1^\mathrm{C}$, rephrasable as $\forall y \in A_1 : \neg R_1\left(A_1^\mathrm{C}, y\right)$; thus, $A_1$ has not covered $R_1$. Therefore, $A_1$ must be cofinite.

Similarly, $A_2$ should also be cofinite; but this leads to a contradiction, since two cofinite subsets of $\mathbb{N}$ cannot be disjoint. $\square$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.