Show that in 2nd-order logic (2oL) it is possible to express \"P is finite\". L.
ID: 3198119 • Letter: S
Question
Show that in 2nd-order logic (2oL) it is possible to express "P is finite". L.e., give a 20L expression Ep, in which a predicate P(.) appears, with the following properties: (1) In every model of Ep the interpretation of P is a finite subset of the domain; (2) for every finite set S there is a model of Ep in which the interpretation of P is S. Use Dedekind's definition of finiteness: A set S is Dedekind-finite iff every injective function from S into S is surjective. Hint: The expression Ep should say that for every function f that maps S into S, it f is injective then f is surjective.Explanation / Answer
I will describe a translation that takes a computable sentence $phi$ of $L_{omega_1omega}$, in some first-order signature, and turns it into a sentence $phi^*$ in second-order logic with the same signature, so that for any first-order structure $M$, $M$ satisfies $phi$ if and only if $M$ satisfies $phi^*$. This can be done under two extra hypotheses: I need the signature to be finite and I only get a translation that works when $M$ is infinite. I don't see yet how to do the general case, which might use a very different method. But this method is interesting (to me at least), even though it gives a stronger conclusion with stronger hypotheses.
When we have infinite models, second-order logic is able to quantify over isomorphic copies of the standard model of Peano arithmetic. Using these (anonymous) copies, it is able to do the coding of syntax that can be done in Peano arithmetic. It only needs the signature to contain equality for this to work, but it needs the model to be infinite in order to get started.
In any of these copies, second-order logic can define the set $T_1$ of numbers $n$ such that $n$ is the code for a first-order formula $psi$ in the signature of $M$ and $psi$ holds in $M$. $T_1$ is the smallest set that contains the code of every true atomic formula and is closed under the $T$-schema. The former property of a set can be expressed as a formula because the signature is finite; the latter can be expressed because there are only finitely many logical connectives. Thus the property "$X$ contains the code of every true atomic formula and is closed under the $T$-schema" can be expressed as a formula of second-order logic. Then for any $n$, $n$ is in $T_1$ if and only if $n$ is in every set $X$ that has the property quoted in the previous sentence. Thus in general, if $phi$ is first order, we could let $phi^*$ say "$k in T_1$", where $k$ is the code for $phi$. Written more explicitly, $phi^*$ would say "for every model of PA, the term $k$ in this model is in the set $T_1$ defined in this model".
The argument in the last paragraph extends immediately to the computable fragment of $L_{omega_1omega}$. The only change is that we have infinite computable conjunctions; they can be handled as another line in the $T$-schema that is used to define $T_1$. Here we assume that an infinite computable conjunction is syntactically represented by the index of the computable function that enumerates the conjuncts.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.