0
$\begingroup$

Is there a standard (or at least common) symbol in computability theory used to indicate that $x$ enters the c.e. set $W_e$ at stage $s$, i.e., $x \in W_{e,s} - W_{e,s-1}$ (at least for $s \neq 0$)?

I was thinking of using $x \searrow_s W_e$ but I was worried that would be too confusing with its use in the automorphisms of $\mathscr{E}$ (i.e. $X \searrow Y$ are the elements that enter $X$ and then $Y$ (and I vaguely remember that $X \searrow_s Y$ is used for something).

Any suggestions for good notation? I'd consider using just use $x \in W_{e,s} - W_{e,s-1}$ (though a binary relation would be nicer) except for the annoying need to adopt the convention that $s$ can't be zero.

Improve this question
$\endgroup$
6
  • $\begingroup$ What is $W_s{}$? $\endgroup$
    – Wojowu
    Commented Jul 27, 2019 at 21:41
  • 1
    $\begingroup$ It's an r.e. (aka c.e.) set at stage $s$ of the enumeration. I thought it would be clear from context but I'll clarify that W is a c.e. set. Anyone who can answer the question will then know what $W_s$ refers to. $\endgroup$
    – Peter Gerdes
    Commented Jul 27, 2019 at 21:43
  • $\begingroup$ @PeterGerdes To be fair that does clash a bit with the notation for $W_e:=dom(\varphi_e)$. $\endgroup$
    – Noah Schweber
    Commented Jul 27, 2019 at 22:07
  • 1
    $\begingroup$ Ohh yah, well you always use $s$ or $t$ for stages and if you are using indexes you would write $W_{e,s}$. I guess I should have written it that way if I wanted to be really clear..I guess I will change it. I now feel really self-concious about using ellipses for connectives after science friday told me only old people did this. $\endgroup$
    – Peter Gerdes
    Commented Jul 27, 2019 at 22:09
  • $\begingroup$ I would instinctively read $x \searrow_s Y$ as "$x$ enters $Y$ by stage $s$" and not "$x$ enters $Y$ at stage $s$". This is probably from the basic idea that when dealing with c.e. sets, statements should not turn from true to false unless it's very clear or very deliberate. $\endgroup$
    – François G. Dorais
    Commented Jul 28, 2019 at 3:11

1 Answer 1

Reset to default
1
$\begingroup$

(I'm going to write "$V$" for the arbitrary c.e. set, since I'm rather wedded to the convention that "$W_e$" refers to the domain of the $e$th partial computable function.)

The "$\searrow_s$" notationis what I've seen before - I think it's in Soare's old book, although I don't have my copy handy to check. In my opinion the automorphism topic is sufficiently narrow that if you're writing a paper not in that context, you can use the arrow notation freely. And anyways, there's no actual notation ambiguity anyways because of the different types of object (and the lack of subscript in the automorphism usage). So that's what I'd recommend.

If you are writing in that context, though, and don't want to use two $\searrow$s, I don't think there's another notation established so you'll just have to pick something and tell the reader. Luckily, though, I think there are a few good choices here:

  • You could attach the stage to the "$\in$"-relation: "$x\in_s V$" means that $x$ enters $V$ at stage $s$. If I recall correctly I've actually seen this one used before.

  • There's also the "inclusion-arrow" $\hookrightarrow$: you could write "$x\hookrightarrow_s V$," and I think that's actually quite readable. It does clash with the general usage of $\hookrightarrow$ elsewhere, but I actually don't recall seeing that symbol in computability theory (except for category-theory-oriented computability). Disclaimer: this is actually what I wrote in my old notes way back when, I really like how it looks.

  • Finally, you could introduce new notation for the sets $V_s\setminus V_{s-1}$ - something like "$V_s^!$" or "$V_{=s}$," perhaps.

Of course if you go this route you'll have to explain that usage - but honestly it's worth reminding the reader of it anyways.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the suggestion on notation but I’m confused why you think there is tension with it being the domain of the e-th ce function. Computable enumerable sets are the domains of c.e functions. Writing it as a set is just a way of ignoring the value the function takes on (only if it converges). Enumerating an element x into a ce set is just a way of saying your partial function converges at x $\endgroup$
    – Peter Gerdes
    Commented Jul 28, 2019 at 3:44
  • 1
    $\begingroup$ No I’m not doing automorphisms of ce sets anymore, thank god. Anyway I'm just curious above if you think there is some aspect that is lost by using the dual approach of having $W_e$ stand for both the c.e. set and the domain of the partiall function. I remember one weird case where I needed different indexing systems for the two kinds of objects to make my requirements simpler but that was an unusual case. $\endgroup$
    – Peter Gerdes
    Commented Jul 28, 2019 at 3:45
  • $\begingroup$ @PeterGerdes Re: your first comment, yes - my opening was responding to the original edit of the question where "$W_s$" stood for the $s$th stage in the enumeration of the c.e. set $W$. Re: your second comment, I don't think so but I could of course be wrong. $\endgroup$
    – Noah Schweber
    Commented Jul 28, 2019 at 3:52
  • $\begingroup$ Ahh, ok I got confused by the timing. Thanks! Now to actually finish the proof instead of playing online. $\endgroup$
    – Peter Gerdes
    Commented Jul 28, 2019 at 3:54

You must log in to answer this question.

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