5
$\begingroup$

I have been reading a bit about formal languages to understand exactly what we mean by "first-order" when talking about things such as the transfer principle. If we use the language of set theory $\displaystyle S=\left\langle \in \right\rangle$, then all first-order statements we can create right now consist of logical symbols and our relation $\in$. But suppose we define a new relation:

$\displaystyle a\subseteq b \iff\forall x[( x\in a \implies x\in b)]$

Now we have used our language $S$ to define a new relation. So we could make a statement such as:

$\displaystyle \forall x\forall y[(x\subseteq y)\vee\neg (x\subseteq y)]$

Would this also be considered a first-order statement for some type of number (such as the naturals)? Or would we call this something different entirely?

If so, suppose we now go a step further and talk about real numbers where we have our standard ordered relation $<$. Suppose you make a statement such as:

$\forall x\forall y[(x< y)\vee(y< x)\vee(x=y)]$

Would this be considered "first-order"?

$\endgroup$
15
  • $\begingroup$ First-order means that only individual variables are quantified. $\endgroup$ Feb 29 at 14:13
  • $\begingroup$ And yes, the above examples are both examples of first-order languages: the first one uses the language of (first-order) set theory where there is only one non-logical primitive symbol: the binary predicate $\in$. More specifically, the statement define (using $\in$) the new binary predicaet $\subseteq$. $\endgroup$ Feb 29 at 14:15
  • $\begingroup$ The same for the second one, relative to (first-order) order theory where there is only the nin-logical binary predicate $\lt$. $\endgroup$ Feb 29 at 14:17
  • 1
    $\begingroup$ When you define the subset relation $\subseteq$ you are essentially creating a shorthand for a longer formula. You can rewrite any formula that uses $\subseteq$ by replacing $\subseteq$ with its definition. So yes, the formula remains first-order. $\endgroup$
    – Manlio
    Feb 29 at 14:18
  • 1

2 Answers 2

3
$\begingroup$

Your question is specifically about the transfer principle, more precisely about the meaning of "first-order" when applying the transfer principle to "first-order formulas". The essential point that does not seem to have come out clearly in the comments is that the quantifiers have to be bound for the transfer principle to apply to the formula. Therefore you cannot have expressions like "$(\forall x)$" in your formula, but rather $\forall x\in A$ where $A$ is a set that the variable $x$ ranges through (this formula is itself a shorthand for a more detailed formula, but this technical point can be left out for now).

The theory ZF is a theory in the $\in$-language. Therefore, so long as your formula uses only the relation $\in$ (as opposed to $\subseteq$, for example), the transfer principle could be applied. Note that there is no restriction that transfer should be applied to "individuals" specifically (whatever that means: individual real numbers? etc.), but can apply to any set. For example, a formula incorporating clauses such as $\forall A\in \mathbb P$ where $\mathbb P =\mathcal P(\mathbb R)$ (so that $A$ is a set of real numbers) is perfectly legitimate and transfer can be applied in such a situation. the same applies of course to all sets in, say, a superstructure, or a cumulative hierarchy.

What happens when you apply transfer to such a formula? Roughly, transfer equips every set occurring in the formula with an asterisk. For example, the transfer of the formula above would produce $\forall A\in \mathbb P^\ast$. The meaning is that $A$ now ranges over all internal subsets of $\mathbb R^\ast$.

$\endgroup$
3
  • $\begingroup$ "Therefore, so long as your formula uses only the relation $\in$ (as opposed to $\subseteq$, for example)" Isn't it the case that since $\subseteq$ is simply shorthand notation for a statement that is already first-order itself, a statement where we incorperate $\subseteq$ would also be first-order? So long as we, in our definition of $\subseteq$, specify how our variables are bound? $\endgroup$
    – naytte2
    Mar 1 at 10:10
  • $\begingroup$ And as an example, suppose we make a statement such as: $\sin^2x+\cos^2x=1$, by the transfer principle, could we then also say that $\sin^{\text{*}2}x+\cos^{\text{*}2}x=1$? Or maybe, in terms of first-order logic (does it count as first order?): $\forall x\in\mathbb{R}[\sin^{2}x+\cos^{2}x=1]\implies\forall x\in\mathbb{R}^\text{*}[\sin^{\text{*}2}x+\cos^{\text{*}2}x=1]$ $\endgroup$
    – naytte2
    Mar 1 at 12:13
  • $\begingroup$ "Isn't it the case that since ⊆ is simply shorthand notation for a statement that is already first-order itself, a statement where we incorperate ⊆ would also be first-order? " How would you do that while sticking to bound quantifiers? Trigonometric formulas are certainly part of the package that transfers. @naytte2 $\endgroup$ Mar 3 at 9:05
2
$\begingroup$

Recall that the ordinary definitions of formal languages used in mathematical logic contain functions that yield terms from terms in the form $f(t_{1}, t_{2},\ldots t_{n})$ and relations that yield formulas from terms in the form $R(t_{1}, t_{2},\ldots t_{n})$, where are $t_{1}, t_{2},\ldots t_{n}$ are terms of the language (i.e., individual constants, individual variables and those in functional form).

If the language allows quantification not only a domain of discourse, but also over functions and relations, then we say that it is a second- or higher-order language.

Therefore, for example, Kripke–Platek set theory with urelements is expressed in first-order language, although it posits urelements that build sets.

Returning to the question, then, if the statement included quantification over the ordering relation, such as $\exists R(\ldots)$, where $R$ is a relational variable (that could be instantiated to $<$), it would not be first-order; in the given form, it is.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .