# How to argue about semi-decidability of a problem?

I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it.

I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a program $\Pi$, such that $\Pi$ takes as input instance $I$ of $\mathcal{P}$, and if we have a positive instance, then $\Pi$ returns true, and on negative instance, $\Pi$ either returns false, or does not terminate.

Now, I tried to write a simple procedure like this:

Then, I tried to argue like this:

We can write a procedure $\Pi'$ that takes as input $(S,n)$, and simulates a run of $\Pi_1$ on $S$, and a run of $\Pi_2$ on $n$. We can show that such procedure $\Pi'$ is a semi-decision procedure, and we can distinguish the following cases:

1. Case 1. Suppose that $(S,n)$ is a positive instance, meaning $\Pi_1$ outputs $I$ on input $S$, and $\Pi_2$ outputs $I$ on input $n$. Then the simulation $\Pi'$ will encounter that $OUT1 = OUT2$, and output return true by its construction.
2. Case 2.1. Suppose that $(S,n)$ is a negative instance and it halts. Then, we have that $\Pi_1$ outputs $I_1$ on input $S$, and $\Pi_2$ outputs $I_2$ on input $n$, such that $I_1 \neq I_2$. Thus, $\Pi'$ does not halt due to its construction.

My problem is that, I cover just two cases, I believe I need one more case, where we have as output false, and terminate. Also, from the definition of semi-decidable program, I believe instead of using the pair $(S,n)$, I need to use the pair $(\Pi_1, \Pi_2)$, which is the actual instance of the problem. But, then how will I choose $S$ and $n$? If someone can help me with those questions, I would be glad.

We know that $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ have the same cardinality, so there exists a bijection $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$. Let $s_n$ be the $n$-th string in some enumeration, like $s_1=\epsilon, s_2=0, s_3=1, s_4=00, s_5=01,\dotsc$ then consider the following semi-decider, where I leave it to you to fill in the missing parts: \begin{align} &\Pi'(\Pi_1, \Pi_2)=\\ &\quad\text{for }n=1,2,3,\dotsc\\ &\quad\quad\text{compute }f(n)=(i,j)\\ &\quad\quad\text{run }\Pi_1(s_i)\\ &\quad\quad\text{run }\Pi_2(j)\\ &\quad\quad\text{... }\\ &\quad\quad\text{... }\\ &\quad\quad\quad\text{return accept} \end{align}
There are lots of bijections between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$, here are a few to get you started.
Your solution doesn't make too much sense. What you want is a procedure that takes $\Pi_1,\Pi_2$ as input, not a string $S$ and an integer $n$. Also, in your proof you don't explain what values of $S$ and $n$ you are going to use.
Try to think how you, as a human, would try to solve the problem. You would probably make two lists, one consisting of outputs of $\Pi_1$, the other consisting of outputs of $\Pi_2$, and constantly compare the two lists to see if there is any intersection. Formalize this method and you have answered your question.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 1, "equation": 0, "x-ck12": 0, "texerror": 0}