Expressing binary quantifiers like 'most' and 'finitely many' in second-order logic

270 Views Asked by At

I'm revising for a logic exam and in one of the past papers they have a question about the formalisation of quantifiers in first and second-order logic.

enter image description here [In the question, the notation $\phi^{M,g,\alpha}$ just means the set of objects you can substitute for $\alpha$ to make $\phi$ true under model M and variable assignment g, and (for example), (Finitely many α: φ)ψ just means that finitely many of the $\alpha$ such that φ are such that ψ

The language $\mathcal{L}_=$ is just first-order predicate calculus with identity].

I've done part (a), and clearly the 'at least 2' and 'no' quantifiers can be formalised in first-order logic, so will be expressible in second-order logic too.

I'm pretty sure that the 'finitely many' and 'most' quantifiers should be expressible in second-order logic too, since the compactness arguments you can use to rule out any such first-order formalisations aren't applicable to second-order logic, but I'm not sure how you'd find explicit second-order sentences that express these sentences.

I'd really appreciate if anyone would be able to help tell me how you'd express the two quantifiers in SOL, since it's only a couple of days until my exam and given the current situation I'm not able to ask my professor.

1

There are 1 best solutions below

5
On BEST ANSWER

Hint (for the third part): a set $X$ is finite iff any total ordering of $X$ has a greatest element. This is easy to express in second-order logic by quantifying over two-place relations on $X$.

Hint (for the fourth part): $|X| \ge |Y|$ iff there is a one-to-one (but not necessarily onto) relation between elements of $Y$ and elements of $X$ and again this is easy to express in second-order logic.

I can't make sense of the assertion that the language $\mathcal{L}_=$ is compact. If you need more help with this, then you will need to say some more about the the definitions you are using.

[Aside: I don't believe the claim is is true for monadic second-order logic (i.e., if quantification over predicates is restricted to one-place predicates).]