$ \newcommand{\N}{\mathbb{N}} \newcommand{\P}{\mathcal{P}(\N \times \N)} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\i}{^{(i)}} \newcommand{\x}{^{[x]}} \newcommand{\y}{^{[y]}} \newcommand{\I}{\mathcal{I}} \newcommand{\J}{\mathcal{J}} $ The Problem: Define $M := \set{A_i}_{i \in \N} \subseteq \P$ to be a countable susbset of $\P$. How would we define some $A \in \P$ such that $A \ne A_i$ for every $i \in \N$?
Context: The context for the problem is this unanswered MSE question from $2018$ that has not been answered yet. I've been trying to answer it for a few days, but I'm not certain of the approach I'm taking. I would like a sort of constructivist approach to the problem, in the sense of an explicit or direct way to define the set $A$ in question (as opposed to, say, just handwaving things away by saying a certain element of $A$ is just in a complement of some $A_i$).
The original problem also specifies the condition $(0,0) \not \in A$, though it's not clear if this is an important restriction in my eyes. (Of course this also means we're adopting the convention $\N := \set{0,1,2,3,\cdots}$.)
My Approach So Far: My goal is sort of in the vein of a diagonalization argument. Since $M$ is countable and $A,A_i$ are at most countable themselves (as $|\N \times \N| = \aleph_0$ per, e.g. here), we may write:
$$M = \set{A_i}_{i=0}^\infty \qquad A = \set{a\i}_{i \in \I} \qquad A_i = \set{a_{i,j}}_{j \in \J}$$
as a means of indexing the members of each set. $\I$ and $\J$ are index sets such that $|\I|,|\J| \le \aleph_0$. We may likewise order the elements of each. Finally, define $a_{i,j} \x$ to be the first coordinate of $a_{i,j}$, and $a_{i,j} \y$ the second. That is,
$$a_{i,j} = \left( a_{i,j} \x \; , \; a_{i,j} \y \right)$$
Then, to ensure $A \ne A_i$, I want to ensure $A$ contains an element different from each $A_i$. We can break this into cases for every possible $A_i$:
- Suppose $A_i = \varnothing$. Then let $a\i := (1,1)$.
- Suppose $A_i$ is finite and nonempty. Then take $$a^{(i)} := \left( 1+ \max_{0 \le j \le |A_i|} a_{i,j} \x \; , \; 1+ \max_{0 \le j \le |A_i|} a_{i,j} \y \right)$$ In short: $a \i$ is $1$ bigger (or more) in each component than any of $A_i$'s elements.
- Suppose $A_i$ is infinite, but not equal to $\N \times \N$. Then ... ?
- Suppose $A_i = \N \times \N$. Then ... ?
I'm pretty confident in my first three cases, but handling the cases of $A_i$ infinite are proving to be sticking points for my approach - in particular the case of $A_i = \N \times \N$, I'm really not sure how to handle that one. I guess we could just say $a\i \in A_i^c$, but that feels a little hand-wavey (especially for, again, $A_i = \N \times \N$), and I'm more interested in defining the elements of $A$ directly in some fashion, if at all possible.
Someone brought up, in the comments of the original question, about using the axiom of choice and ZFC set theory. If strictly necessary, I'm fine with the use of axiom of choice or alternative set theories (e.g. NBG), though the less we have to invoke those, the better in my opinion, since I'm not particularly well-versed in these sorts of decisions and their ramifications.
Anyhow - does anyone have some bright ideas as to how I might be able to finish this approach? And how does the restriction of $(0,0) \not \in A$ affect the original problem?
It’s possible to do something along the lines that you have in mind, but you can also (and much more easily) do it all at once: let
$$A=\{\langle n,n\rangle\in\Bbb N\times\Bbb N:\langle n,n\rangle\notin A_n\}\,.$$
For each $n\in\Bbb N$ the sets $A$ and $A_n$ disagree on $\langle n,n\rangle$: one contains it, and the other doesn’t.
If you want to ensure that $\langle 0,0\rangle\notin A$, change the definition: let
$$A=\{\langle 1,n\rangle\in\Bbb N\times\Bbb N:\langle 1,n\rangle\notin A_n\}\,.$$