Talk:Arithmetical set

don't merge, please

Does anyone mind if I merge this into arithmetical hierarchy? CMummert 02:09, 22 July 2006 (UTC)

I have since rewritten arithmetical hierarchy and this page is not redundant with it. This page covers arithmetical sets in general, much like computable set covers computable sets in general. The hierarchy article is all about the subclassification. This page also covers implicitly arithmetical sets, which are not covered by the hierarchy page. So please don't redirect this article to the hierarchy article. CMummert · talk 17:44, 13 February 2007 (UTC)

Not-arithmatical numbers

Are there any real numbers which aren't arithmetical? Or numbers suspected to be them? 83.23.17.49 (talk) 16:47, 7 February 2012 (UTC)

Numbers are not arithmetical or non-arithmetical. Sets are. There are non-arithmetical sets of natural numbers, let alone real numbers. For example, the set of all true arithmetic statements. Stellaathena (talk) 15:03, 20 November 2020 (UTC)

@Stellaathena: Hmm, actually it's pretty clear what is meant by saying a real number is arithmetical or not. You can code real numbers as sets of naturals, for example, by their binary representation, or with Dedekind cuts using natural-number codes for the rationals. Or you can ask whether the map giving the nth decimal digit, for a given n, is arithmetical, or whether its equivalence class of Cauchy sequences has one that's arithmetical.

These all give formally different definitions, but unless I've missed something silly they all give the same answer for any given real, because the translations back and forth are all arithmetically definable.

Anyway, we're not supposed to answer general questions about the subject matter here, but rather talk about how to improve the article. Looking now, I see that the article already says [a] real number is called arithmetical if the set of all smaller rational numbers is arithmetical. A complex number is called arithmetical if its real and imaginary parts are both arithmetical. We could possibly elaborate a bit along the lines I gave above, and/or give a link to definable real number, which I think also discusses the issue. But I don't feel any strong urge to do so. --Trovatore (talk) 18:45, 20 November 2020 (UTC)

link to definable reals

The material here seems closely related to definable real numbers. Perhaps there should be a link connecting these. Tkuvho (talk) 16:35, 22 November 2012 (UTC)

It's such a terrible article that I really hate to link anything to it. I say that as someone who probably wrote most of it, or most of some past version of it. The only thing I'll say in defense is that it was worse before I did that.

I made a proposal in the talk page for a plan to improve it, but somehow that didn't magically result in the article's improvement. --Trovatore (talk) 20:00, 23 November 2012 (UTC)

I see. If definable real number isn't up to par, at least it should link to this arithmetical set page. Of course, ideally it would be best to improve the other article. I haven't checked the traffic statistics but real numbers apriori have wider appeal than sets as far as the general public goes. Tkuvho (talk) 13:48, 25 November 2012 (UTC)

P.S. The definable number page claims that "the truth set of first order arithmetic" is an example of "numbers that are definable but not computable". This seems to be contradicted by a claim on this page, unless of course one talks about different notions of definability. Can someone comment on this? Tkuvho (talk) 14:52, 25 November 2012 (UTC)

The truth set of first-order arithmetic is definable, but not by an arithmetical formula. --Trovatore (talk) 20:28, 25 November 2012 (UTC)

Will this distinction be evident to someone who reads these two pages? Tkuvho (talk) 13:57, 26 November 2012 (UTC)

Use of countable and denumerable side-by-side

In the Properties section. Since some authors define these terms differently from one another, this is poor form. I'm assuming this was done by two different people, but since I don't know enough about the subject, I don't want to edit it myself, for fear of there being an actual distinction. Can someone clarify? Surement (talk) 18:43, 2 May 2014 (UTC)

I think some people use "denumerable" to exclude "finite", but "countable" to include it. However this distinction is not worth bothering about, in my opinion, and "denumerable" is a bit dated. I've changed it to "countable". --Trovatore (talk) 20:41, 2 May 2014 (UTC)

No arithmetically definable sequence that enumerates all arithmetical sets?

The article says "no arithmetically definable sequence that enumerates all arithmetical sets". This seems dubious if we allow the same set to be enumerated more than once, since we may just enumerate all well-formed formulas. Do I miss anything?Dan Gluck (talk) 09:26, 11 June 2016 (UTC)

I think what it means is something like this: There is no arithmetical formula φ(n,m) such that φ(n,·) enumerates all the arithmetical predicates, as n ranges over the natural numbers. That is, certainly, you can have a sequence A_n such that every A_n is an arithmetical set, and you get all of them as n varies over the naturals. But the question "Is m an element of A_n?" cannot be answered by a fixed arithmetical definition taking n and m as parameters.

Does that make sense? If so, can you offer a suggestion as to fix the language so that it's clearer? --Trovatore (talk) 01:29, 12 June 2016 (UTC)

Yeah, thanks. I think you're right. This is a decision problem that belongs to 0^(ω). I'll try rephrasing so that it's clearer and you're welcome to change what I'll write.Dan Gluck (talk) 08:54, 12 June 2016 (UTC)