Suppose $S$ is a k-ary relation on $\mathbb{N}$. Given $1 \leq i \leq k$, define $\pi_i(S)$ in the following way: $$\left \{s_i | (s_1, s_2, \cdots s_i \cdots s_k) \in S \right \}$$.

We call $S$ nice if: for every component $i$, either the projection $\pi_i(S)$ or its complement is finite.

I want to show that if $S$ is nice, then so is $\mathbb{N}^k \setminus S$.

I came across this problem while trying to solve another problem in logic.


Let $k = 2$, $S = \{ (x, y) : (2 \nmid x) \text{ or } y = 0\}$, and $S' = \mathbb{N}^2 \setminus S = \{ (x, y) : (2 \mid x) \text{ and } y \ne 0\}$. Then $\mathbb{N} \times \{0\} \subset S$, $\{1\} \times \mathbb{N} \subset S$, so $\pi_1(S) = \pi_2(S) = \mathbb{N}$, so $S$ is nice. But $\pi_1(S') = \{ x \in \mathbb{N} : (2 \mid x) \}$, and neither this set nor its complement is finite, therefore $S'$ is not nice; so the conjecture is false.

  • $\begingroup$ This was not the definition of niceness. We require the projections to be finite or co-finite, not the relation itself $\endgroup$ – Agnishom Chattopadhyay Dec 2 '17 at 2:29
  • $\begingroup$ Sorry, my bad. Upvoted. $\endgroup$ – Agnishom Chattopadhyay Dec 2 '17 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.