lo.logic - Graph properties and infinite FOL sentences

Let me suppose for simplicity at first that we are speaking here just of countable graphs. There are continuum many isomorphism types of countable graphs, and any collection of such isomorphism types would seem to constitute a property of countable graphs. Thus, there are $2^{2^omega}$ many properties of countable graphs.

If your infinitary logic does not have this many sentences, therefore, then clearly not every property can be described by an infinitary sentence. For example, if as you seem to, you only allow countable conjunctions, disjunctions and quantifications, so that every sentence is countable, then there are only continuum many sentences, but more than continuum many properties.

If you are more generous with the infinitary sentences, by allowing larger iterated disjunctions (but still just countable quantifications in any one block of quantifiers), then the answer is yes. The reason is that every countable graph $G$ is uniquely specified up to isomorphism by a sentence $sigma_G$ in infinitary logic saying: there are such-and-such vertices connected in exactly such-and-such way and no other vertices (according to what is true in the particular graph $G$). This assertion, which is expressible provided that we have countable conjunctions and quantifications, is true in a graph exactly when it is isomorphic to $G$. Now for any property $P$, let $Gamma_P$ be the disjunction over all $sigma_G$ among the $G$ with property $P$, which will be a size at most continuum disjunction, if we use at most one $G$ of each isomorphism type. The sentence $Gamma_P$ is true of a countable graph exactly when that graph has property $P$. (The same idea works for uncountable $G$ by allowing larger quantifier blocks and disjunctions.)

I take this answer to show that one needs to be more specific about which infinitary logic is to be used. If the logic is too generous, then the infinitary language doesn't seem really to give any insight to the nature of the graphs, since it amounts to describing the property just by listing the graphs that have that property, and we can already do this in our ordinary mathematical treatment of graphs, without any formal language. But when the logic is restricted, for example, if you consider a specific infinitary logic $L_{kappa,lambda}$ and focus in detail on what is describable in that logic, then interesting answers may emerge. The answer above shows that larger logics will be more expressive.