It seems to me that the world is constructed in or as a first order logic. Its semantic is aggregative, with sharp distinctions, analytical after all. Logicians and scientists may go further on building up explanations on higher-order logics -i.e. in terms of classes, relations, and so on. And yet, first order logic comes as a sort of down-to-earth pole, if you allow me the expression. I have the hunch that if this is the case, then it's mostly because of tradition, customs, habits and conservatism - in a logical or epistemological sense. this is why most people - logicians included- believe that higher order logics can be expressed in terms of first order logic. This, I have the impression, is a sort of logical reductionism.

As a simple example, one might consider the ω-rule and the differences between Gödel's so-called "completeness proof" and "incompleteness proof".

For a much more subtle (and at times contentious) example, consider the context of Boolean algebra (the most frequently equated and perhaps most intuitively relatable algebraic formulation of classical logic). Specifically, while the utility of Boolean algebra is obvious, how might we understand its nature compared to other algebras? I would argue we do so largely via mathematical structure, and that is through the realization of the importance of such structures (fields, groups, algebras, etc.) that advances we have seen advances in everything from "pure mathematics" to quantum physics. While algebras are readily equated to standard first-order logics, understanding their structures is not so easily accomplished without extending FOL. It's true that in many cases the distinction is not only hard to determine, but also that for a good chunk of the history of symbolic logic from Frege onwards there wasn't really any such distinction. So for many purposes there are no benefits for second-order logic. Yet without a formal language which is enriched s.t. it can categorize/classify (simply, express) the nature (structure) of its expression we would not have the most important developments within formal logic and would lose many important applications of mathematical logic to the understanding of algebras.

@Peter Breuer

Thanks for your answer, but it does not seem to be right!

Yes, I aggree, it might be useful to have various, but equivalent languages to describe the same thing - each ofthem might be comfortable to describe a different phenomenon.

The problem is that 2nd order logic is *not* equivalent to the 1st order logic!!! It is *more*expressive*, yet more *difficult* to use with automated provers.

And if it were like you said (and as I, myself, suggested in the question), it *would* be equivalent.

Actually, I've just found an interesting comment in Wikipedia (I've read the Wikipedia articles before - so this one must have been added relatively recently), but it is hard to understand to me, a simple engineer:

http://en.wikipedia.org/wiki/Second-order_logic (paragraph: Non reducibility to first-order logic).

Does it mean, the way I tried in the question, we could substitute another entities for the subsets of X???

In many cases one can reduce a higher order formalization to a first-order, but it will come at the price of complexity of the formalization.

For instance, formalize the follow argument in both first order and second order logic:

All things with personal properties are persons. Being kind is a personal property. Peter is kind. Therefore, Peter is a person.

One can do this with either first or second order, but it is easier in second-order.

First-order formalization:

1. (∀x)(PersonalProperty(x)→((∀y)(HasProperty(y,x)→Person(y)))

2. PersonalProperty(kind)

3. HasProperty(peter,kind)

⊢ 4. Person(peter)

Second-order formalization

1. (∀Φ)(PersonalProperty(Φ)→(∀x)(Φx→Person(x)))

2. PersonalProperty(IsKind)

3. IsKind(peter)

⊢ 4. Person(peter)

where Φ is a second-order variable. Basically, whenever one uses first order to formalize arguments like this, one has to use a predicate like "HasProperty(x,y)" so that one can treat variables as properties indirectly. This is unnecessary in second-order logics.

That's a deep question. Its never simple to answer such question. My feeling is that the answer depends on the interpretation of the logic (e.g. if we consider countable subsets like naturals or uncountable ones, like the real numbers).

I recommend this online article, very clearly written on the topic of higher order logic, from the stanford encyclopaedia of philisophy, were this issue is nicely addressed:

http://plato.stanford.edu/entries/logic-higher-order/

In second order logic one can quantify over sets, not only individuals. Then we can say, for example that x=y if and only if they share all properties:

x=y iff for all P: P(x) P(y)

@Antii Hautamaki

Thanks for your answr, but that is ranging over functions, not over sets.

And - as I suggested in my question, we can transform such sentences to the 1st-order form.

@Andreas Blass

Thanks a lot! That seems like the answer I needed.

The 1st-order model, including sets (or functions) could describe several subclasses of sets (or functions).

Also, this means that for any (or almost any) *practical* situations we *can* transform the 2nd-order model to a proper 1st-order model that is useful for automated reasoning.

At least, I hope, I understood that...

I would like to know more about the equivalence between the non-reduced and the reduced side. Should we say that there is equivalence between the one side and a fragment of it on the other side? Is the way back afterwards still open?

If the question is why have 2nd Order when they can be expressed in 1st Order then my answer would be - because of convenience. That is the reason why 2nd Order is worth while, you simplify massive 1st Order formulation where 2nd Order abbreviates it.

Hi to all of you,

I am arriving late for this discussion, but I have something to ask you: if second order logic is, as you say, "more expressive" then

1) what do you mean by "expressive" and

2) what does it "express" in a stronger way than first order logic does?

And then how do you understand the statement by John Sowa saying that metalanguage which does not make use of higher order logic gets an enormous increase in expressive power?

:)

A key difference is related to their meta-logic properties. While, first-order logic is correct and complete, second-order logic is not complete. That is, not every truth sentence is provable.

:) great , thank you. I think I totally understood it by now. So 2nd order logic is more dense in its expressiveness but it is not able to express "more" than 1st order logic can express ? could we say it like that?

The concept "order" in "first order" or "second order" was defined by Frege. Its primary meaning is that , in a logic expression, when a modified variable is a simple object without any functional word (the expressoin of this object is not a predicate or relation or function),then the sentence belong to the first order. J.-Y. Vion-Dury · showed http://plato.stanford.edu/entries/logic-higher-order/ , there are "exist R", "all P" expressions, which are quantitatively modifing relations or predicates, so they are second order's expressions.

An essential difference between first order and higher order logic is Löwenheim-Skolem. In first order logic, a consistent theory which have infinite models will have models in every cardinality greater or equal with ist language. So, if Zermello-Fraenkel is consistent, there are countable models of the set theory! Inside the model, one has all infinite cardinalities - but looked from outside, they are all countable sets! In first order logic, if a consistent theory has an infinite model of some cardinality, there will be models in all bigger cardinalities. This is not so in higher order logics. In second order logic one can write down the condition to have a linearly ordered field, real closed and complete. There is only one field enjoying those properties: the field of real numbers R. So there are no countable models and no models of bigger cardinality - just one model of cardinality 2^\omega. In the same way one can define archimedean fields in second order logic, but not in first order logic. It is much more difficult to make model theory in second order logic, and almost impossible to make things like nonstandard Analysis...

Mr.Mihai Prunescu ,could you please give us a simple sample, to show the difference beween models in first order logic and second order logic ?

Dear Yinsheng, as I told you, the main difference from model-theoreti point of view is that in 1-st order logic the Theorem Löwenheim-Skolem (denoted here LS) is true, but in 2-nd order logic such a statement is false. There are a lot of examples. As I said, ZF is a first order theory and LS implies that there are countable models, if consistent. As examples of 2-nd order logic models which do not satisfy Löwenheim-Skolem I gave the definition of the field of real numbers and arhimedic fields. Of course, there are many other examples, most of them from topology. The second order definition of compact metric sets implies that they can be only finite, countable or of cardinality of continuum. This is again a violation of Löwenheim-Skolem, because LS says that first order theories which have infinite models, have models in every cardinality. The only connected locally compact fields are R and C. Again a 2-nd order theory, again only two models, again a violation of Löwenheim Skolem, which clearly does not work for 2-nd order logic. Mathematics offers a lot of such examples.

Maybe something more about Löwenheim Skolem. I quote the following from Wikipedia: """In its general form, the Löwenheim–Skolem Theorem states that for every signature σ, every infinite σ-structure M and every infinite cardinal number κ ≥ |σ|, there is a σ-structure N such that |N| = κ and

if κ < |M| then N is an elementary substructure of M;

if κ > |M| then N is an elementary extension of M.

The theorem is often divided into two parts corresponding to the two bullets above. The part of the theorem asserting that a structure has elementary substructures of all smaller infinite cardinalities is known as the downward Löwenheim–Skolem Theorem. The part of the theorem asserting that a structure has elementary extensions of all larger cardinalities is known as the upward Löwenheim–Skolem Theorem."""

So, what I meant with my counterexamples coming from second order logic was basically to upwards Löwenheim Skolem, but sometimes also to the existence of a countable model (downwards Löwenheim Skolem). R and C are uncountable, more precisely of cardinality 2^\omega.

@ Mihai Prunescu .

Thanks a lot for your explaining. I had waiting for your reply, in fact no notice goes to my email box.So I am so late reading your words above.

But I am afraid, you didn't give a uncountable model. for example, say 2+3=5 is a model of 1st order language's countable model satisfying LS, could you polease give the similiarly simple sample of 2nd-order uncountable model violating LS? I mean where is the uncountability in expression in your upcoming sample?

@ Mihai Prunescu .

Do you mean that the number N of Propostions

No.1: 3.14 ...

@ Mihai Prunescu

There has not been yet the answer from Mr.Mihai Prunescu. So I am afraid,no sample that a simply showing the formal difference between 1_order and 2_order  propositions distinguished by Löwenheim–Skolem Theorem.

I.e., 1_order and 2_order propositions are not related to denumerability.

Any one has refutation？

@  Yinsheng Zhang ·

Dear Yinsheng, first you write a first order sentence (using constants): 2 + 3 = 5. There are a lot of models, there is no contradiction to anything. Then you write another countable set of first order sentences using constants - telling that the Approximations of $\pi$ are smaller than 3.15. There are again infinitely many models of this set of sentences, in all cardinality. We can manage to make theese models real closed fields containing $\pi$ for example. Again no contradiction. In both cases Löwenheim Skolem works. Your both exampes are sets of first order sentences, and you did not give any sentence using second order logic. Second order logic means to quantify over subsets, over functions, or over more complicated sets - but when you quantify, you must refer to all of them. If you say for example "every bounded set has an infimum and a supremum", this is already a statement of second order, telling that an ordered set is complete. When you say that "every Cauchy sequence is convergent" you did also a statement of second order about tzhe same thing, completion. Now there is a Theorem  telling that the only one complete real closed field is R. (complete real closed = second order axiomatization). Now Löwenheim Skolem is violated, because you stop having models in all cardinalities. OK?

 @Mihai Prunescu

Could you please  simply give a sample of 2_order proposition, which is related to Löwenheim–Skolem Theorem?

I think I do not need your discussion about ......You need to show a proposition (instance) of 2_order, and then to show its relativity to  Löwenheim–Skolem Theorem or  denumerability. 

Up to now you didn't give any one of  proposition (instance) of 2_order!

If you can't give a sample, then it means that there is not a model of proposition (instance) of 2_order related to Löwenheim–Skolem Theorem or  denumerability.  

@  Yinsheng Zhang ·

Dear Yinsheng, I already did it in a non-formal way. But if you really want a formal way, look at Tarski's axiomatization of the real numbers:

http://en.wikipedia.org/wiki/Tarski's_axiomatization_of_the_reals

Here all axioms are first order, excepting Axiom 3:

"

@  Yinsheng Zhang ·

And again, to convince you: the Axiom System at

http://en.wikipedia.org/wiki/Tarski's_axiomatization_of_the_reals

is finite, as it consists of only 8 axioms, no Axiom Schemes. Now, let A be the conjunction of the 8 axioms (all of them written with quantifiers, etc). Proposition A has only one model, (so violates Löwenheim Skolem) and is second order. Let B be the conjuction of the 7 axioms 1, 2, 4, 5, 6, 7, 8 (without Axiom 3). Proposition B is first order, has models in all infinite cardinalities, and respects of course Löwenheim Skolem (being first order).

@Mihai Prunescu

Dear Mihai Prunescu : Tarski's Axiom 3 (say Proposition A ) is of 2-order , yes. But there is still problem, I am afraid, you say "Proposition A has only one model (a field of reals)" . How does Proposition A violate Löwenheim Skolem? "One model" is countable too.

@Peter T Breuer

One model is countably finite .I.e., 1 is countable and finite.  Why does it violate L-S?

I say "x+1=1", there is only one model ( x=0 if x is nutural number). Why "x+1=1" does not violate L-S?  You can't say because of Tarski's Axiom 3 ( Proposition A )  is 2-order and  "x+1=1"  is 1-order, for that you use L-S to identify which one is 1-order, which 2-order.

Thank you Peter, for help. I was no more sure what Yinsheng does actually not understand. Yinsheng, it is as Peter says: the Proposition A has only one infinite model. If Proposition A would have been first order, L-S would have had as an effect, that the Proposition has infinitely many infinite models, at least one in every infinite cardinality. Proposition A is essentially of second order (there is no Proposition in first order which is equivalent to it) and so has only one model, the unique field of real numbers. This is for me the most important difference between first order and second order.

@Mihai Prunescu 

I seem to understand your explanations,however, let me think about  your words further. I try to find a L-S in a precise version in Wikipedia encyclopedia, but it is worse to understand it. Would you please re-write L-S here? Thanks !

I think I shall give a final assertion about our disagreement, and write down my final point  here ( now it is reaching a final result soon, I think  ) even I am wrong.

@Mihai Prunescu 

Dear Mr.Mihai Prunescu:

I propose to inspect  why a proposition,  like  proposition A, having one model, violates L-S. Hope you could give a standard version of L-S  here.

In its general form, the Löwenheim–Skolem Theorem states that for every signature σ, every infinite σ-structure M and every infinite cardinal number κ ≥ |σ|, there is a σ-structure N such that |N| = κ and

if κ < |M| then N is an elementary substructure of M;

if κ > |M| then N is an elementary extension of M.

_______________________________________________________________________

The point is, that for EVERY cardinal number k there is a model of cardinality k. There are infinitely many different cardinal numbers. So, if the theory has only one model, it cannot be first order!!! Also, if a theory has a finite signature (as it was in the example with Tarski's axiomatization of the reals) and is first order, there must be a countable model. In our case there is only one model (contradicting that there should be infinitely many, at least one for every cardinality) and this only one model is not countable (contradicting that there must be at least a countable model). So Tarski's axiomatization of the reals violates both the upward and the downward LLöwenheim Skolem, and it does it because of the only one reason that this axiomatization is not first order.

The word "elementary" used in the LS given here means "first order". It is said that M and N have the same first order theory.

At

http://legacy.earlham.edu/~peters/courses/logsys/low-skol.htm

You will find also the following more convenient form: """Let S be any first-order theory. The Löwenheim-Skolem Theorem (LST) states that if S has a model (i.e. if it is consistent), then it has a model with a countable domain."""

As I have shown above, this is also contradicted by Tarski's Axiomatization of the reals, because it is second order.

@Mihai Prunescu

Could you please give an annotation about what is |σ|, and what does it equal to? Thank you !

The signature σ is a collection of symbols for functions (with their arities), relations (with their arities) and constants. Some authors do not consider constants anymore - they take instead functions of arity 0, which is the same. In alternative - one speaks instead of the signature σ, about the language L. It is again the same thing. The notation  |σ| means the cardinality of the signature - so it means how many primitive symbols are already there. The point is that if  |σ| is finite - as in our example - and if there are infinite models, then one has models of the first possible infinite cardinality, which is the countable infinity (denoted by \aleph_0 or by \omega).

@ Mihai Prunescu

I am looking for a good version of proof of L-S.

Do you think the following version is eaziest  for understanding it?

Thoral Skolem.Some remark on axiomatized set theory (1922)//From Frege to Godel/A Source Book in Mathematical Logic,1879~1931.Havard University Press,1977.pp.290~301.

I will summarize our discussion and write some words formally here.

@ Yinsheng

It might be difficult to read Skolem's historical article. Better try some contemporary treatment, like this:

http://www.mcmp.philosophie.uni-muenchen.de/students/math/metalogic-fm2012.pdf

but read it very slowly. And then Hodges' book, where the remaining proofs are. Another possibilities are books by Prestel, or by Flum and co., or by Ziegler. There are a lot of modern books and a lot of online sketches of proof. I don't know what is the best.

However, in order to read LS you must be already familiar with thr compactness theorem for first order logic. (from the same resources)

 @Mihai Prunescu，@ Bartlomiej Jacek Kubica

With the help of Mr.Mihai Prunescu, I confirm that there is truly a difference between 1st and 2nd order formula to apply  Löwenheim–Skolem Theorem.That is, for a 1st formula, according to L-S, there is at least one countably infinite model, yet for a 2nd order formula, it might only one  uncountably infinite model and no any  countably infinite model as Mihai Prunescu set the sample (July 23,see above,page 3). Thanks!

Another question is that how to express L-S theorem. Skolem writes his theorem as follows:

Every propostion in normal form either a contradiction or is already satisfiable in a finite or denumberably infinite domain.

(Thoral Skolem.Logico-combinational investigations in the satisfiability or provability of mathematical propositions:A simplified proof of a theorem by L.Lowenheim and generalizations of the theorem (1920)//From Frege to Godel/A Source Book in Mathematical Logic,1879~1931.Havard University Press,1977.pp.256.)

But some versions are difficult to understand.

Mihai Prunescu writes:

In its general form, the Löwenheim–Skolem Theorem states that for every signature σ, every infinite σ-structure M and every infinite cardinal number κ ≥ |σ|, there is a σ-structure N such that |N| = κ and

if κ < |M| then N is an elementary substructure of M;

if κ > |M| then N is an elementary extension of M.

Here, if  |N| , |M| , K and |σ| are all infinite, how to compare their  cardinality?

Please note follow facts:

A={1,2,3,.....}

B={2,3,4,.....}

Could we say |A|>|B|? If not, I am afraid |N|,|M|, K and |σ|  can't be compared to assert which is more or less. What do you think your comparision?Are you sure your version is proper for rewriting L-S?

Thanks again!!!

Yinsheng, one of the most outstanding contribution of Cantor was to discover that infinity has a structure, or more precisely, the so-called cardinal numbers of infinite sets can be compared and managed through operators, and that's why Aleph zero (the cardinal of natural numbers) is strictly smaller than Aleph 1, the cardinal of reals. 

As the basis of this outstanding result, G. Cantor defined cardinality through bijections , so that he could abstract from counting by enumeration...

see http://en.wikipedia.org/wiki/Cardinal_number

http://en.wikipedia.org/wiki/Cardinal_number

@J.-Y. Vion-Dury

According to Cantor, if we set up an one-to-one mapping between two infinite sets, then the two sets pessess a same cardinality.For A and B, A={1,2,3,.....}, and B={2,3,4,.....}, we can say |A|=|B|. So we must say |N| , |M| , K and |σ| are equal with each other for they are all countably infinite. But there are many versions of Löwenheim–Skolem Theorem, in which |N| , |M| , K and |σ| are compared to be bigger or smaller. One version is in Wikipedia encyclopedia, cited by Mihai Prunescu :

http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem

Do you have answer?

In these versions, the models are not necessarily countable, its more general. It was precisely the goal of this work to understand/explore the general relationship between logical constructs and models, aka interpretations of the logic based on mathematical structures that appeared as simpler and therefore having more "intuitive" or "well-defined" behaviors (sets with operations).

There are several ways to go about answering your question. One approach is to note that there are properties of first-oder logics that second-order don't have. For example, first-order logics are compact in the sense that given any set of first-order sentences S, it has a model if every finite subset of S has a model. Second-order logic are not compact. There is an infinite set of second order sentences that has no models even though  all of its subsets have models. Let $\phi$ be the second-order sentence true on all and only interpretations whose domains are finite. For each n, let $\psi_{n}$ be that first order sentence true on all interpretations of cardinality n or greater. Let S=${\phi}\cap [\psi_[n}\ n is in omega}$. every finite subset of S has a model (a finite one at that), bur S does not have a model. The various Lowenheim-Skolem theorems hold in first-order logic, but they fail in second-order. The reason for this is that periodic features of cardinal numbers are characterized by second-order sentences. For example, there is a second-order sentence true on all and only those interpretations whose domain is a limit cardinal. Same thing is true for successor cardinals. Let $\beta$ be an infinite cardinal. If $\beta$ is uncountable and a limit, then (1) the cardinal successor of $\beta$ is not a limit cardinal and there are infinite successor cardinals strictly less than $\beta$. If $\beta$ is $\aleph_{0}$ there are infinite successor cardinals strictly larger than $\beta$. Hence both the upward and the downward Lowenheim-Skolem theorems fail in second-order logic. I have attached an old paper about the Lowenheim-Skolem theorems and their various generalization that goes into more detail, if you are interested. 

Finally, note that the set of logically  true first order sentences (those true on all interpretations) is recursively enumerable, but the set of logically true second-order sentences are not. This is a simple consequence of the incompleteness of  first-order arithmetic and the fact that the standard model of arithmetic is finitely characterizable-i.e. that there is a finite set of second-order sentences each of which is true on the standard model and every model of this set of sentences is isomorphic to the standard model. Hence, all second-order sentences true on the standard model are consequences of this finite set of sentences. The final bit of reasoning involves the observation that if the set of logically true second-order  sentences were recursively enumerable, then there would be a decision procedure for first-order arithmetic. If you are having problems seeing what is going on here, look at "First-order logic +Most". it is on my Research gate account. Look at the proof that the set of logical truths of this extension of first order logic is not recursively enumerable. 

There is another approach that is worth mentioning. Let WO be the proper class of binary relational systems (B, R) where B is a non empty set and R is a binary relation on B and R is a strict well order on B- i.e. a strict partial order in which every non empty subset  of the domain(B) has a least member relative to the ordering on the  domain (R). Let L1 be a first order language whose non-logical vocabulary consists of a single binary relational constant($\rho$$. Let L2 be the second-order language with the same non-logical vocabulary. In L2 there is a finite set of sentences such that the binary relational system (B, R) is a model of the set iff (B, R) is in WO. There is no infinite set of first order sentences with this property. The reasoning for this claim uses the compactness of first-order logic. Suppose that there were such a set of first-order sentences. Cal it T. Briefly, add infinitely many individual constant to the non-logical vocabulary of L1. Let c_{1},   c_{n},... be these  and now add all the following sentences to T ;  $\rho(c_{n+1}, c_{n})$ for each n. Let T' be the result of adding these sentences to T. Every finite subset of T' has a model, but T' does not. To see this last point note that a model of T' is of the form (B, R, d_{1}...d_{n}...)where d_{n} is the denotation of c_{n.} {d_{n}|n is in omega} has no least member relative to R. 

The best way to get a sense of the difference between first and second -order logic is to get clear about the grammar and semantics of both languages and look at trying to express things in second-order languages. It is very easy to get carried away with making what seems like minor additions to first order languages. The best check I can think of is to think about the semantics of the language you have introduced.  I have attached a prepublication copy of a paper that appeared in "History and Philosophy of Logic". The topic may be a little interest to you, but there are several examples of second order sentences. There are two other papers  in Studia Logica on Dedekind algebras("Homogeneous Universal Dedekind Algebras" and "The First-order Theories of Dedekind Algebras") that you might find interesting for similar reasons. I have written several papers on Dedekind algebras and second-order languages. Together they are a mathematically interesting and  accessible application of the model theory of second-order languages. 

One final observation. Yes,  one can express information about sets in first-order languages. But this is just doing set theory in first order logic. The trick to getting clear here about second-order logic and first order set theory is to think about the interpretations of the second-order language and the models of first-order set theory. In the first order case all members of the domain are sets. In second-order languages interpretations have domains that are sets, but the members of the domains need not be sets. In order to quantify over all subsets of the domain, as one does in second-order, in first order one must assume that all subsets of the domain are in the domain. Similar remarks apply to n-ary relations on the domain and n-ary functions on the domain.  Consider the problem of finding a first-order sentences that is true on an interpretation just in case all these subsets etc are in the domain.  That is we need a first-order sentences true only and only interpretations where all subsets of the domain etc are in the domain. Here is something else to think about: if we get all of the subsets of the domain in the domain how do we stop getting all subsets of subsets in the domain etc in the domain as well. If you can stop this process somewhere you run the risk of domains being proper classes. 

Thank you so much ! could you please write the following formula in formal :

 S=${\phi}\cap [\psi_[n}\ n

What doe "cap []\n" mean?

Sorry, I was using LATEX code. And not being as careful as I should. 

S= etc is the set whose members are the sentence phi (\phi) and all sentences phin ( \phi_{n}) for n  in is omega (n \in \omega). (S={\phi} U {\phin| n a member of omega})

The code is $S=\{\phi\}\cup \{\phi_{n}| n\in \omega\}$.

What is ”cup” ？

LATEX code for union(U).  'cap' is code for intersection.

Thanks! Let me read the two articles and your words in several days!  

I have read the two papers ( GeneralsettingforDedekind4.pdf  and Tarski-Vaught and L-S 2004.pdf). I accepted the points of views in the two papers. I am here trying to summarizie the actual difference between 1st order and higher order logic. In grammar of a proposition of  1st order languages, there are modifiyers only modifiying terms such as All x, Exist X; yet for 2-order languages, the modifiers are perrmited to modify the function symbols such as  All f, Exist f; just due to  modifying the function symbols , uncountable terms can be assigned to function symbols (  if we assign the two modifiers to terms, yet in 1-order languages, terms are countable, so assigned terms by the two modifiers are countable too), this is why 2-order languages are offen uncountable (not recursively enumerable). In sumary, the formal difference between 1-order and 2 order lies in modifers+ terms (1-order) or modifers+ functions(2-order) ; the actual difference  1-order and 2 order lies in countable subset (1-order) and uncountable subset (2-order). Am I right?

I think that your characterization of the differences between first and second-order languages is missing something. You can have countable first order languages and you can have uncountable first order languages as well. The same applies to second-order languages.  I am going to suggest a way of looking at the grammatical details that, I hope will make things clear. 

We start with a set whose members are called non-logical constants. We then build two languages on K; one first order(LK(1)) the other second order(LK(2)). These two languages are of the same cardinality (meaning the the cardinality of the formulas/sentences in the first order language is the same as the cardinality of the set of formulas/sentences in the second order language). The cardinality of these languages is a function of the cardinality of K; to be precise: if K is countable (finite, or countably infinite), then both languages are countably infinite; and, if K is uncountably infinite, then both languages are of the cardinality of K (hence, uncountable). K can be empty. If it is not empty, then if k is a member of K, then one of the following is true: k is an individual constant, k is a unary predicate constant, k is a relational constant of k is a functional constant. If k is a relational constant, then d(k) is a natural number, greater than or equal to 2, called the degree of k. If k is a functional constant, then d(k) is a natural number, greater than or equal than 1, called the degree of k. Both languages have the same logical vocabulary. This vocabulary consists of sentential connectives, quantifiers (usually two: the existential quantifier and the universal quantifier) and finally the identity symbol(=). The languages differ in the variables in their vocabulary. First order languages have one type of variable: the individual variable. There are a countably infinite of individual variables.  Every formula in LK(1) is a finite sequence of  symbols from the vocabulary. When K is countable, the vocabulary is countably infinite and the set of finite strings in the vocabulary is countably infinite. To establish that the set of formulas is countably infinite, it suffices to note that there is a subset of the formulas that is countably infinite. Consider the set of formulas 'x=x' were 'x' is an individual variable. Now, consider the case where K is uncountable. The vocabulary is a uncountable  set whose cardinality is the same as that as of K. As above, to show that LK(1) has a set of formulas of the same cardinality as K. We can think of K as the union of countably  many disjoint sets: the individual constants, the unary predicate constants, for each n, greater than or equal to 2, the set of predicate constants of degree n and for each n, greater than or equal to 1, the set of functional constants of degree n. Since K is uncountable and the union of a countable family of sets, one of these sets must be uncountable. More importantly, one of these must have the same cardinality as K. The reasoning here proceeds by considering the cases. Suppose that K and the set of individual constants are of the same cardinality.  Consider the set of formulas 'k=k', where 'k' is an individual  constant. This set is of the same cardinality as K. Suppose that the set of unary predicate constants and K are of the same cardinality. Consider the set of formulas 'k(x)', where k is a unary predicate constant. You can see how this goes when the set of relational constants of degree n and k are of the same cardinality. Finally, suppose that for some n the set of functional constants of degree n and K is of the same cardinality. Consider the set of formulas 'k(x,...,x)', were k is a functional constant of degree n and the variable 'x' occurs in this formula n times.  

What to do in the case of second order languages? Notice that the above argument hinges on the cardinality of the vocabulary of the language. Second order languages have more than one kind of variable. This is the the key to the differences between first and second order languages. First of all, in addition to the countably infinite set of  individual they have a countably infinite set of set variables. Monadic second order languages have no other variables. Second order languages that are not monadic have lots more types of variables: for each n, greater than or equal to 2, there is a countably infinite set of n-ary relational variables. Some second order languages have no other types of variables. Others, however, have for each n, greater than or equal to 1, a countable infinite set of n-ary functional variables. In any of these cases the cardinality of the set of all variables in the language is countably infinite (the cardinality of a countably infinite family of countably infinite sets is countably infinite). Thus, if K is countable, the cardinality of the vocabulary of LK(2) is countably infinite. Hence, by reasoning as above, the cardinality of LK(2) is countably infinite. Finally, if K is uncountable, the cardinality of the vocabulary of LK(2) is the same as that of K. Hence, the cardinality of LK(2) is the cardinality of K. 

Perhaps the best reference to the grammar and semantics of second order languages is Stewart Shapiro's "Foundations without Foundationalism:A  Case for Second-order Logic.  It was published in 1991 as one of the Oxford Logic Guides. I would be very surprised if it was out of print. If you want help understanding  the details  of cardinality arguments , you might consider Paul Halmos's "Naive Set Theory". The first edition was published in 1960. I believe that Springer now publishes the book. It ought to be pretty easy to get a second hand copy.  This thing is short (not more than 100 pages), very well written and does not drag the reader through axiomatic set theory. 

If the above does not help, there are other approaches to take. Note that none of the above talks about how these languages are interpreted. Given K, interpretations for both languages are order pairs (A, f) where  A is a nonempty set (the domain) and f is a function defined on K as follows: if k is an individual  constant, f(k) (the denotation of k) is a member of the domain; if k is a unary predicate constant, f(k) (the extension of k) is a subset of A; if k is an relational constant of degree n, then f(k) (the extension of k) is a subset of the n-th cartesian power of A; and, finally, if k is a  functional constant of degree n, then f(k) (the extension of k) is an n-ary function on A. 

@ Andreas Blass

We define natural number N using a structure (0,S), here, S is the fucnction  to find a successor. This definition should be made by 2-order as follows : N={0 and for All x Exist S}, which we say 2-order ,for  "Exist S" ,i.e., a modifier modifying a function symbol.So in formal, a modifier modifying function symbols constitutes a fatal characteristics of  2-order language.

@George Edward Weaver   

Could you please set a sample of uncountable 1-order language? And what do you think about Lowenheim Skolem theorem which says that 1-order language has finite models and does not effective for 2-order language which can be a infinite language?

I  think that the main difference between languages of the first order and languages of higher order is the following: for higher order logic the compactness theorem does not valid (but for some classes of second order formulas the compactness theorem is proven).

There are several ways to get uncountable languages. Remember, the cardinality is a function of the cardinality of the non-logical vocabulary. Here are two easy examples. Let A be an uncountable set and let K included as many individual constants as there are members of K. Suppose that K does not include any other non-logical constants. Both LK(1) and LK(2) are uncountable. Here is another way to get an uncountable language. Let A be an infinite and K includes as many individual constants as there are members of A, as many unary predicate constants as there are subsets of A. The cardinality of K will be at least the cardinality of the power set of A, hence uncountable. (If you want to more about the uncountable first order languages, I have a paper on Research Gate: "Small Models" that you might find interesting. 

To your second question. I am a little concerned that the following does not answer your question. I am assuming that you are asking whether there is a Loewenheim-Skolem theorem that says that every interpretation of the language is equivalent (in the language) to a finite  interpretation.   Let LK(1) be any first order language whose non-logical vocabulary is K. Since the identity sign (=) is in the logical vocabulary and the language is closed under forming negations (i.e. if phi is a formula then so is ~phi (the negation of phi) is a formula). For each n (n in omega, but non-zero) there is a first-order sentence true on all and only interpretations of the language of cardinality n or larger. All of these sentences are true on any infinite interpretation, On any finite interpretation, at least one is false. (in fact most of them are false.) Thus no infinite interpretation is equivalent to a finite interpretation. Note this is true for any second order language as well. 

 In the second-order logic, in addition to allowing quantifications over the element of a domain, as in ordinary first-order logic, we allow also quantifications over relations and functions on the domain.

The compactness theorem: If every finite subset of set of sentences has a model, the whole set has a model.

The downward Lowenheim-Skolem theorem: If asset sentences has a model, it has an enumerable model.

The upward Lowenheim-Skolem theorem: If a set of sentences has an infinite model, it has a nonenumerable model.

The Godel completeness theorem: The set of valid sentences is semirecursive.

All these results fail for second-order logic.

@Sergey Davidov ：

Using compactness theorem  to discrime  1-order or 2-oder langaues is to assert a effect for 1-order or 2-oder langaues  . We should extract the formal features which result in that effect. Could you please write down the formal features which can discrime  1-order or 2-oder langaues?

@George Edward Weaver :

 You say it could be, and state some methods, to constitute  uncountable 1-order languages,yet no sample, a proposition sample in uncountable 1-order.  Could you please set a sample?

As i understand you, you want an example of an uncountable first order language. One thing to keep in mind is that if LK(1) is a first order language whose non-logical vocabulary is the members of the set K, then LK(1) is uncountable if and only if K is uncountable. Suppose that you are interested in studying the reals. Your non-logical vocabulary starts with binary functional constants whose extensions are say addition and multiplication,  a unary functional constant whose extension is the additive inverse and  a binary relational constant whose extension is the less than relation on the reals. This set of constants is finite. Thus, the first and second order languages with this set of non-logical constants are countable. Now, make one further addition to the non-logical vocabulary. For each real number r, add the individual constant k(r) where if r and r' are different real numbers, then the individual constants k(r) and k(r')  are different. Think of k(r) as denoting the real number r. Since the reals are uncountable, {k(r): r is a real number} is uncountable. Let K be the set whose members are k(r), for each r, and the functional and relational constants mentioned above. K is uncountable. hence, LK(1) is uncountable. Also, LK(2), the second order language whose non-logical vocabulary is K, is also uncountable. 

Here is a second kind of example. Suppose now that you are interested in the  integers. You could start with a non logical vocabulary like the above: two binary functional constant whose extensions are addition and multiplication (of  integers, rather than reals) a unary functional constant whose extension is subtraction (of integers) and a binary relational constant whose extension is the less than ordering on the integers. You could also add a predicate constant whose extension is the set of even integers. Now, if you were to add a name for each integer, the resulting first order language would only be countable, as the set of integers is countable. However, the number of subset of the integers is uncountable. Let S be any subset of the integers and let k(S) be a predicate constant such that if S and S' are different subsets of the integers, then k(S) and k(S') are different predicates. Think of the extension of k(S) as the set S. As above, {k(S); S  is a set of integers} is uncountable. Let K be the collection of all of the non-logical constants mentioned in this example. K is uncountable. Hence, both LK(1) and LK(2) are uncountable. 

Uncountable first order languages are used a lot in the model theory of first-order languages.,  A. Mal'cev, a  Soviet mathematician, is generally credited with introducing the study of uncountable first order languages in a series of papers, the first of which appeared in the 30's and the second in the 40's. Both A. Robinson and L. Henkin played major roles after the end of the second world war.  But, that is a more complicated story. I hope this answers your question. 

@ George Edward Weaver

It seems that if you use  {k(r)}  in your language, then the languages would be 2-order, just as Peano Axiom 9 (axiom of induction).So I am afraid, no uncountable 1-order language.Henkin model is of LK(2), i.e., 2-order. Do you have any paper uploaded here to confirm that the author says "uncountable 1-order language"?

@Yinsheng Zhang

I think that I confused the situation by using 'k(r)'. The idea is to add as many individual constants to the non-logical vocabulary as there real numbers and to indicate which real number they are to denote. What I was trying  to do was to both make it clear that there are as many different individual constants as there are real numbers and also indicate the semantics of those constants- that is,  how they are to be interpreted. The grammar of these languages is such that an equation (for example, k(r)=k(r') is a sentence). This sentence is true on the intended interpretation provided the two individual constant denote the same real number- that is that r and r' are identical. 

I have attached the paper "Small Models" where uncountable first order languages are discussed. There is a brief discussion (I think on the first page) about the conceptual importance of the study of uncountable language: the move from viewing languages as vehicles for communication (comparable to natural languages)  to viewing them merely as sets of objects satisfying certain conditions. I quote a paper by Robert Vaught  in which this issue comes up. there are also references to the Mal'cev papers.  I included as well a second paper  on the same general topic (it is also on my ReasearchGate account):" A Downward Lowenheim-Skolem Theorem for Elementary Extensions". This paper was never published. Most of this material ended up in Chapter 7 of "Henkin-Keisler Models"  (a book published in 1997 by Kluwer, but now published by Springer). If you can get a copy you might find it interesting to read the Preface and Chapter 1 as well. Springer has both hard and soft covers and a e-version. All are expensive,by just about any standard you want to use. It is my impression that the second paper is much more demanding in the terms of the amount of set theory that gets used. The book may take you further into the theory of models for first order languages than you want to go. The general topic of the book is a specialization of Henkin's method of constants introduced by Keisler. The basic idea is to take members of a direct product of a family of sets as individual constants. The resulting Henkin models turn out to be isomorphic to ultraproducts. 

@ George Edward Weaver   

Good！ Many thanks for your providing helpful papers ! I shall read them.

@ George Edward Weaver   

May I ask some questions on your two papers:

1) What does "  elementary extention of sth" mean?

2) What does "a k |-> b" or "a k |=> b" mean?

Help will be appreciated!

@Yinsheng Zhang

1) Question 1.

As usual, K is a set of non-logical constants. Members of K are either individual constants, unary predicate constants, n-ary relational constants[n greater than or equal to 2] or n-ary functional constants [n greater than or equal to 1]. Interpretations for the language are ordered pairs (A, f) where A is a non-empty set (the domain), and f is a function defined on K that satisfies the following:

(1) if k is an individual constant, f(k) (the denotation of k on (A,  f)) is a member of A;

(2) if k is a unary predicate constant, f(k) (the extension of k on (A, f)) is a subset of A;

(3) if k is an n-ary relational constant, f(k) (the extension of k on (A, f)) is a subset of An  ;

(4) if k is an n-ary functional constant, f(k) (the extension of k on (A, f)) is a function from An to A. 

Interpretations of the language are sometimes called interpretations of type K. Let (A, f) and (B, g) be two interpretations of type K. We want to define what it means to say that (A, f) is a subsystem (or sub interpretation) of (B, g) and when (B, g) is an extension of (A, f). The easy part first: (B, g) is an extension of (A, f) if and only if (A, f) is a subsystem of (B, g). Now, in the same way, (B, g)  is an elementary extension of (A, f) if and only if (A, f) is an elementary subsystem of (B, g). The terminology functions to allow talk about the same relation between (A, f) and (B, g), but  in a way that shifts the focus between the interpretations. For example suppose you start with (A, f) and you are looking for (B, g) such that (A, f) is a subsystem of (B, g), it is useful to focus on (B, g) and say I want an extension of (A, f). From a different perspective, if you start with (B, f), it is useful to talk about subsystems of (B, g). There are two equivalent ways to define the notion that (A, f) is a subsystem of (B, g). "Small Models" uses one. The other definition is more common: (A, f) is a subsystem of (B, g) iff the following hold

(1) A is a subset of B;

(2) if k is an individual constant, f(k)=g(k);

(3) if k is a unary predicate constant, f(k) is the intersection of  g(k) and A; and

(4) if k is a functional constant or relational constant, then f(k) is g(k) restricted to A. 

(2) Question 2

Start with the relation ->. alpha, bata and kappa are  infinite cardinals. The point of introducing this relation was to provide a uniform way to discuss various results in the literature. Here is the general problem: suppose you start with infinite cardinal alpha where alpha is strictly smaller than the cardinal beta and (A, f) an interpretation of type K of cardinality alpha, and ask does (A, f) have an elementary extension (B, g) of cardinality beta. It turns out that the answer depends of the cardinality of the first order language with non-logical vocabulary K. kappa is the cardinality of this language. If the language is countable (kappa is omega, the first infinite cardinal) then by the upward Lowenheim-Skolem theorem there is such an elementary extension of (A, f). Thus, the triple (alpha, omega, beta) is in the relation ->. When kappa is strictly greater than omega (that is the language is uncountable), then (alpha, kappa, beta) are in the relation -> when alpha

@George Edward Weaver

You say

“ (B, g)  is an elementary extension of (A, f) if and only if (A, f) is an elementary subsystem of (B, g). ”

Here, the definition is circle, that is , to define "elementary extension" by  "elementary extension". So I am not very clear what is you called  "elementary extension" . By your helpful explaination, I understood the terminology  "extension of sth"; could you please redefine in another way the terminology  "elementary extension of sth"?  Especially, what does  "elementary" here?   Thanks!

@Yinsheng Zhang 

(1) the relation between elementary extension and elementary subsystem is roughly the  relation between successor and predecessor on the integers. You can define one or the other of them and then define the second in terms of the first. Thus, you can define predecessor first and then define successor in terms of predecessor, or you can define predecessor first and then define successor in terms of predecessor. You can also define both independently  and prove that n is a successor  of m if and only if m is a predecessor of n. The definitions are only circular if you define predecessor in terms of successor and define successor in terms of predecessor. However, the following are fine: n is a predecessor of m if and only if n

@Yinsheng Zhang

The logical/grammatical  form of  "the sequence s satisfies phi  on one system but not the other" is " either s satisfies  phi on (A, f) and s does not satisfy phi on (B, g) or s satisfies phi on (B, g) and s does not satisfy phi on (A, f)". This is why the sentence in the next to the last paragraph of my message  does not imply either of Proposition 2 or Proposition 3.  

very informative and research oriented conversation dear professors.