2
$\begingroup$

Are those statements first order or second order: $\{X\in 2^{A}:|X|=2\} \\ \{X \subset 2^{A}:|X|=2\} \\ \{X \subset A:|X|=2\}$ why?

  • 0
    I have found a [good lecture](http://videolectures.net/ssll09_tiu_intlo) which briefly explains those king of things.2012-03-18

2 Answers 2

5

For a statement to be first or second (or higher) order you will have to first specify the language.

In the language of set theory we only have the binary relation $\in$, from the axioms of ZFC we can define $=$, $\subseteq$, $P(x)$ and $\bigcup x$. We can define more things, like when is $x$ a set of the form $\{a,b\}$.

We can define all those from ZFC, in first order. This is because we define a pair to be something in bijection with $P(P(\varnothing))$. Therefore given a set $A$ the set $[A]^2$ which is the collection of all subsets of $A$ with two elements there exists a first order formula defining this collection.

However, in different languages and different theories, it might not be possible to express within the theory what does it mean for a set to have exactly two elements, and to express what does it mean to be a subset of another set. In such theories, the collection of all pairs of a certain set is not definable in first order, and the expressions become second order.

  • 0
    @Trismegistos: Don't worry about unclear things. It took me years before I fully understood this concept properly.2012-02-24
5

As Asaf Karagila says, there is something strange about determining whether a statement is "first-order" or "second-order". In fact the problem is quite severe.

A single statement such as $(\forall X)(0 \in X \lor 0 \not\in X)$ can appear both as a statement in second-order logic (for example, the second order theory of the natural numbers) and first-order logic (for example, in "second-order arithmetic" which is a theory in first-order logic). There is nothing in the syntax of the statement itself that can tell you whether it is being read in first-order or second-order logic.

The truly germane difference between "first-order" and "second-order" is in the choice of semantics. There are two main semantics that can be used for statements such as the one above:

  • "Full second-order semantics", where the set quantifiers range over all subsets of the domain. This is full-blooded second-order logic.

  • "Henkin semantics", which are really a first-order semantics, in which there is a separate domain for the set quantifiers to range over. This is really just first-order logic going by a different name.

Unfortunately, this distinction about the semantics was not well understood until Henkin's work in the 1950's (or later), and so there is historical terminology in which "second-order" is used for any statement that quantifies over subsets of the domain. For example "second-order arithmetic" is really a first-order theory as it is usually formalized (it is my area of research) despite the name. Thus people still use phrases such as "second-order statement" even though a statement, on its own, cannot know whether it is being interpreted in first-order or second-order logic.

There is some more information at the SEP article on second-order logic, and much more in Shapiro's book Foundations without foundationalism which is entirely about second-order logic.

Separately, as has been pointed out, the expressions in the question are not statements, because they are not the sort of expressions that are either true or false. The expressions are just terms denoting sets using set-builder notation.

  • 0
    These domains are just part of each model, they are not specified. However, the theory may have axioms that imply that various sets exist. For example, we could include an axiom scheme so that every definable subset of $I$ must exist. But in FOL we cannot ensure that *every* subset of $I$ appears in every model, while this is precisely what full second-order semantics ensure. In either case, whether we use first-order or second-order semantics, we can indeed quantify over predicates. Only in *single-sorted* first-order logic, which is the usual one, can we not quantify over predicates.2012-02-28