Talk:Analytical hierarchy: Difference between revisions

Revision as of 20:35, 7 July 2005

Latest revision as of 14:45, 9 February 2025

(18 intermediate revisions by 12 users not shown)

Line 1:

{{WikiProject banner shell|class=B|1=

{{WikiProject Mathematics|importance=mid}}

}}

== boldface distinction ==

Problem here -- the boldface/lightface distinction is not clearly made --[[User:Trovatore|Trovatore]] 7 July 2005 19:31 (UTC)

The term "analytical" refers exclusively to the lightface concept, whereas "projective" is a boldface notion. Therefore "projective set" should not redirect here. I'm planning a [[pointclass]] page where it might redirect instead. Also "analytic" and "co-analytic", which are boldface notions, should be removed from this page. --[[User:Trovatore|Trovatore]] 7 July 2005 20:35 (UTC)

----

The other major problem with this page is the conflation of formulas and sets. Consider for example the following passage:

: A <math>\Sigma^1_1</math> formula is a formula of the form <math>\exists X \phi</math>, where ''X'' is now a [[Mathematical_relation | predicate]] and <math>\phi \in \Sigma^1_0</math>, while a <math>\Sigma^1_1</math> set is a set of the form

: <math>\{x : (\exists y \in S)\ R(x,y) \}</math>,

: where ''S'' is Borel and ''R'' is a relation.

First, the definition is incorrect, because no restriction is placed on the definability of ''R''. But the problem that more exemplifies the difficulty with the page as a whole is that nothing is said about the underlying Polish space. --[[User:Trovatore|Trovatore]] 7 July 2005 20:48 (UTC)

==major problems seem to be fixed==

Accuracy tag removed (thanks to Ben Standeven). Tech tag removed; subject is inherently technical. --[[User:Trovatore|Trovatore]] 02:18, 20 September 2005 (UTC)

== edit on 2006-6-13 ==

The main changes are:

* Carefully separate the cases of sets of numbers and sets of reals. This is an experiment that may be useful on [[arithmetical hierarchy]] as well.

* Emphasize the fact that this is lightface (maybe more emphasis needed?)

* I rephrased the introduction. The anlytical hierarchy is not really about second order logic; it is about higher type languages such as Z_2 or type theory in first order logic. Every use I know of is in the context of first order ZFC or first order Z_2.

* Add a reference to Rogers' book. I plan to add more references.

==Hyperarithmetical==

I've seen redlinks to 'hyperarithmetical heirachy' many places, and just recently noticed [[hyperarithmetical theory]] so I've created a redirect for now. It's possible that one or the other will need to be renamed in the future, but I figured this was a cheap way to get rid of a lot of dead links at least for now. --- all assuming that 'hyperarithmetical theory' is talking about the same thing... here's hoping!

[[User:Zero sharp|Zero sharp]] 20:46, 30 August 2007 (UTC)

== Removed sentence ==

"Note that it rarely makes sense to speak of a <math>\Delta^1_n</math> ''formula''; the first quantifier of a formula is either existential or universal."

Well, not really, the first quantifier of the normalized form, but not of the formula. As we just demonstrated any formula in <math>\Pi^1_n</math> or <math>\Sigma^1_n</math> is in <math>\Delta^1_m</math> for all m>n. ''[[User:Rich Farmbrough|Rich]]&nbsp;[[User talk:Rich Farmbrough|Farmbrough]]'', 16:23, 14 December 2009 (UTC).

== alternating ==

MAJOR PROBLEM here -- the description of the the abstract levels of the hierarchy do not adequately reflect the alternating nature of the quantifiers. In fact, no where on the page is the word "alternating" found. See the planet math article for a correct description. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/131.107.0.98|131.107.0.98]] ([[User talk:131.107.0.98|talk]]) 18:44, 24 June 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:It is true that the page doesn't use the word "alternating", but I think the definition here is correct. Is there something in particular wrong with it? &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 00:26, 25 June 2010 (UTC)

== "Indicies of Computable ordinals" ==

It is unclear what the indicies of computable ordinals are. See the discussion at http://math.stackexchange.com/questions/72826/complexity-of-the-set-of-computable-ordinals. It may refer to recursive well-orderings of <math>\omega</math> or to Kleene's O notation. If it is Kleene's O, there should be a link to http://en.wikipedia.org/wiki/Kleene%27s_O. Either way (or if it is both and these are equivalent statements), this should be clarified <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/129.67.127.65|129.67.127.65]] ([[User talk:129.67.127.65|talk]]) 20:40, 2 November 2011 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Set parameters in Delta^1_0 ==

Many sources that I've seen say that <math>\Delta^1_0</math> (arithmetical) formulae are allowed to contain set parameters:

* Frittaion, [https://www.jstor.org/stable/27166956?seq=4 A note on fragments of uniform reflection in second-order arithmetic]

* Apt and Marek's [https://www.sciencedirect.com/science/article/pii/0003484374900011 Second Order Arithmetic and Related Topics]

* Jager and Strahm's [https://www.sciencedirect.com/science/article/pii/S0168007298000566 Bar Induction and ω-model Reflection]

* Steven G. Simpson's ''Subsystems of Second-Order Arithmetic''

If this is the consensus (I'm not sure how much disagreement there is about this convention) should it be added? [[User:C7XWiki|C7XWiki]] ([[User talk:C7XWiki|talk]]) 03:44, 10 November 2022 (UTC)