Jump to content

Talk:Monadic second-order logic

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

monadic restriction on non-quantified predicates

[edit]

Monadic_predicate_calculus#Variants contains the statement: "Monadic second-order logic allows predicates of higher arity in formulas, but restricts second-order quantification to unary predicates, i.e. the only second-order variables allowed are subset variables." This seems to contain an important qualification not present in the MSO article: Allowance of other than unary predicates over which quantification is _not_ allowed. Jim Bowery (talk) 15:15, 26 March 2017 (UTC)[reply]

Agreed, and I added a section to clarify this. Caleb Stanford (talk) 14:38, 13 November 2021 (UTC)[reply]

The use of MSO Büchi-Elgot-Traktenbrot theorem does not allow binary Predicates?

[edit]

The text states that "In the variant considered in automata theory and the Büchi-Elgot-Trakhtenbrot theorem, all predicates, including those in the formula itself, must be monadic". I think this is somewhat misleading since the signature of a word structure contains (depending on which definition you look at) at least the successor relation or its induced linear order as a binary predicate with a fixed semantic. However, unary predicates are the only ones with without a restriction on the semantic. — Preceding unsigned comment added by 185.197.236.16 (talk) 14:48, 18 May 2022 (UTC)[reply]

That's a good point, I will reword. Caleb Stanford (talk) 00:41, 19 May 2022 (UTC)[reply]
Thanks! 185.197.236.16 (talk) 10:46, 20 May 2022 (UTC)[reply]