Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Neither is a statement. In the usual formalized set theory, the statement that $W$ is equal to either the first or the second is first-order. In many other settings, the statement that $W$ is equal to the first is first-order, and the statement that $W$ is equal to the second is second order. For the first, all we need to say is that $x_1$ and $x_2$ satisfy the predicate $A$, and $x_1\ne x_2$. –  André Nicolas Feb 24 '12 at 18:28
    
@AndréNicolas I don't fully understand what you mean by setting. For this example we may assume FOL with ZFC axioms, I think it is all that is needed to define syncatical setting. –  Trismegistos Feb 24 '12 at 18:48
    
If you are working within ZFC, everything is first-order. If you have been asked this question in a course, things have to be interpreted in the (unknown to me) context of that course. My guess is that you are supposed to say the second is second-order, because you are considering subsets rather than elements. –  André Nicolas Feb 24 '12 at 18:59
    
@AndréNicolas I am not taking any course this question emerged when I was trying to answer this question about how to state all set that have two elements(second notation is obvious mistake but third is valid). I do not understand why you claims that everything is first order it is obvious that I can not quantify over predicate so not everything can be first order. –  Trismegistos Feb 24 '12 at 19:21
    
Predicates can be realized as sets in ZFC. –  André Nicolas Feb 24 '12 at 20:42
show 3 more comments

2 Answers 2

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.

share|improve this answer
    
I think now I understand. –  Trismegistos Feb 24 '12 at 20:06
    
To make things clear to me. Does it mean that in ZFC I can quantify over anything I want except $\in$ relation? –  Trismegistos Feb 24 '12 at 20:12
    
In ZFC the elements are sets. If you want to say that a certain set has a high-order property, then you still only quantify over sets. However you lose something in the sense that your universe is not a set, but a class. –  Asaf Karagila Feb 24 '12 at 20:18
    
@Trismegistos: Don't worry about unclear things. It took me years before I fully understood this concept properly. –  Asaf Karagila Feb 24 '12 at 21:37
add comment

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.

share|improve this answer
    
When you talk about Henkin semantics(which is as you said FOL) you said that there is separate domain for the set quantifiers to range over. Could you write something more about it? How this domain is specified(I thought FOL can quantify over anything but predicate symbols). Could you give some simple and intuitive example about this domain. Thank you. –  Trismegistos Feb 27 '12 at 22:02
    
@trismegistos: it's like multisorted FOL. There is a domain $I$ of "individuals" as in normal FOL. There is a second domain that contains some subsets of $I$, but not necessarily all of them. This second domain is used as the range of set quantifiers within the model. In full generality there is another domain for sets of pairs of individuals, and in general for each $k$ a domain for $k$-ary relations on the individuals and a domain for $k$-ary functions from $I$ to $I$. However, in arithmetic there are definable pairing functions, so we can get by with just a domain for subsets of $I$. –  Carl Mummert Feb 28 '12 at 0:27
    
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. –  Carl Mummert Feb 28 '12 at 0:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.