Talk:Arithmetical set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Foundations, logic, and set theory

don't merge, please[edit]

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[edit]

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

link to definable reals[edit]

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[edit]

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?[edit]

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 An such that every An is an arithmetical set, and you get all of them as n varies over the naturals. But the question "Is m an element of An?" 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)