Jump to content

Talk:Pointclass

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Confusing/wrong statement

[edit]

The article currently states:

(that is, a set is if there is a computable set S of finite sequences of naturals such that the given set is the union of all {x∈ωω|xs} for s in S).

This cannot be right, as written, because if s is a finite sequence of naturals, then s cannot be a member of Baire space (since Baire space consists of all infinite-length sequences of naturals), and so therefore it cannot be the case that xs which invalidates the entire parenthetical remark. So, for now, I am simply removing this sentence, until someone can provide the appropriate clarification. Perhaps cylinder set is what the author was thinking of, when they wrote this? A cylinder set is, among other things, a finite sequence of naturals, followed by an infinite number of *'s (Kleene stars) indicating 'any' value. 84.15.187.18 (talk) 10:05, 17 June 2016 (UTC)[reply]

The article never said that $S$ was a subset of Baire space; the $\subseteq$ relation in the statement refers to $s$ being an initial segment of $x$, as is standard in that context. The statement is correct: each $\Pi^0_1$ class is the collection of paths through a computable tree, and so each $\Sigma^0_1$ class is the collection of paths that go through a node from the complement of the tree of the complementary $\Pi^0_1$ class. — Carl (CBM · talk) 11:17, 17 June 2016 (UTC)[reply]
Thanks, Carl.
I agree that this statement might be hard to work through for someone unused to the context. The use of the ⊇ symbol is literally correct, but that relies on using the standard coding for finite and infinite sequences (a finite sequence being a set {<0,a0>, <1,a1>, ... <n−1,an−1>}, an infinite sequence being similar but infinite). That coding is pretty standard, but is not necessarily the only way you can think of sequences, and people who are used to the context probably aren't thinking of ⊇ in that sense anyway, but rather as "extends as a sequence".
So is there anything to be done about it? I'm afraid that further elaboration may just make it more confusing, rather than less. Maybe an explanatory footnote? --Trovatore (talk) 18:41, 17 June 2016 (UTC)[reply]