|
|
|
|
|
|
by codeflo
1738 days ago
|
|
|
I don't doubt that the term is in use, and I understood what you meant. But it's not listed among seven (!) synonyms for computably enumerable on Wikipedia, and more the point, the slides you linked to also don't contain that term. However, that's not the point I wanted to make. I wouldn't like calling it computably countable even if everyone else did, simply because it gives the wrong intuition about subsets. |
|
|
The term "countable" is used in the slides, where it means computably enumerable. The adjective "computably" is used when there's a need to distinguish set-theoretic notions from similarly behaved computability-theoretic notions. Otherwise the meaning of the term "countable" can be context-dependent.
> it gives the wrong intuition about subsets
In constructive logic, a countable set can contain an uncountable subset. The misleading intuition (in the context of non-classical logics) is based on classical logic where countability is a statement about the size of a set. Whether you think constructive logic is a good way of explaining computability theory is another question, but it's certainly a viable way of doing it.
It's like how the term "line" can mean something different in hyperbolic geometry from what it means in Euclidean geometry. You could argue that it might mislead people about the nature of parallel lines, but that's why hyperbolic geometry is not Euclidean geometry. Another example is using "multiplication" to refer to an operation on matrices, which might make people think that AB=BA when that usually isn't true. Mathematics is all about re-using terms and pointing out that there are differences.
[edit]
Admittedly, the slides do use the term "enumerable" as well, so that's another option. When there's a possibility for confusion with set theory, you can say "computably enumerable" as you suggested.
[edit] Made lots of edits. Hopefully, that's it.