Timeline for Can one define second-order equinumerosity in MSO via first-order cardinality quantifiers?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9 at 17:38 | vote | accept | Alexander Pruss | ||
| Dec 3 at 14:09 | comment | added | Alexander Pruss | @Emil Jeřábek: My bad: I did mean monadic second-order. | |
| Dec 3 at 14:07 | history | edited | Alexander Pruss | CC BY-SA 4.0 |
rephrase to make clear that interest is in *monadic* second-order
|
| Dec 3 at 14:06 | answer | added | Emil Jeřábek | timeline score: 7 | |
| Dec 3 at 7:42 | comment | added | Emil Jeřábek | I could try to write something later if I find the time. But frankly, I don’t see the point: if you “know very little about complexity theory”, to the extent that you are even oblivious of the basic correspondence of SO to PH, you will not understand the answer anyway. The expressive power of fragments of second- and higher-order logic on finite structures is complexity theory in thin disguise, and you won’t get anywhere with the subject unless you learn some complexity theory. | |
| Dec 3 at 7:37 | comment | added | Emil Jeřábek | On second thought, since the interpretations of $F$ and $G$ can be arbitrary, this really means $\mathrm{C_=P}^A\subseteq\mathrm{PH}^A/\mathrm{poly}$ for all oracles $A$ (whence $\mathrm{CH}^A=\mathrm{PH}^A$). This is actually known to be false, as there are oracles $A$ such that the polynomial hierarchy does not colapse. | |
| Dec 2 at 22:06 | comment | added | Alexander Pruss | One approach might be to look at graphs and compare the expressive power of MSO$_1$+all cardinality predicates vs. MSO$_2$+all cardinality predicates. But I don't know much about graphs. | |
| Dec 2 at 16:00 | comment | added | Alexander Pruss | @Emil Jeřábek: Is there a chance you could try to do the translation rigorously and write it up as an answer? I know very little about computational complexity, and my own thinking was that there is no obvious computational complexity reduction implied by an affirmative answer. (To naively check if $F$ and $G$ have equal numbers of satisfiers is to go through all $2^{|A|}$ subsets of $A$. If there is a $\phi$ as in the question, then instead we have to check if $\phi$ is true, but naively that also requires going through all $2^{|A|}$ subsets of $A$ for each universal quantifier.) | |
| Dec 2 at 15:05 | comment | added | Emil Jeřábek | I’m not sure whether I translated it correctly from descriptive complexity to computational complexity, but since you allow arbitrary numerical predicates, doesn’t your question amount to asking whether $\mathrm{C_=P}$ (no direct relation to your $C_=$ notation) is included in PH/poly (which is actually equivalent to: is PH = CH)? Then it’s almost certainly false, but you won’t be able to prove that with current technology. | |
| Dec 2 at 14:13 | history | edited | Alexander Pruss | CC BY-SA 4.0 |
added a first-order formulation
|
| Dec 2 at 2:32 | history | edited | Alexander Pruss | CC BY-SA 4.0 |
clarify in response to Noah Schweber's comment
|
| Dec 2 at 2:26 | comment | added | Alexander Pruss | 1st-order variables (written with lower-case letters) range over "objects" and 2nd-order variables (upper-case letters) range over sets of objects. 2nd-order predicates take 2nd-order variables as arguments. Since, $C_=$ is a 2nd-order predicate, it takes 2nd-order variables: $C_=(X,Y)$. But $F$ and $G$ are 2nd-order predicates ($F(X)$ and $G(X)$ only make sense for $X$ a 2nd-order variable), and would only be possible values for a 3rd-order variable, but the logic here is 2nd-order, so there are no 3rd-order variables. So $C_=(F,G)$ is not in $L$. | |
| Dec 2 at 2:11 | comment | added | Noah Schweber | What exactly can $L$ quantify over? You say $L$ is second-order, but then expressing $\vert F\vert=\vert G\vert$ is trivial. Separately, why doesn't the sentence $$C_{=}(F,G)$$ do the job? | |
| Dec 2 at 2:03 | history | asked | Alexander Pruss | CC BY-SA 4.0 |