I'm trying to understand 0-1 law for random graphs. I think I get most of it, but I don't get one thing:
We assume that structures have to be purely relational (no constants or functions). That means that there are no 0-1 law for algebra (in first order logic).
I get why constants 'breaks' this theorem for random graphs (end of 2.2 in http://web.mit.edu/joshuah/www/projects/zeroone.pdf), but I struggling with concept, why functions are problematic.
I think that we could define function $F(v) = \frac{1}{2}$ and than 0-1 law wouldn't be fulfilled, but it looks 'sketchy' for me.
What is the logic behind limiting structures to purely relational in 0-1 law?
We can consider asymptotic properties even when we have function symbols. However in the general case where we consider all such finite structures there are no $0-1$ laws. To be specific: In the case where we have unary function symbols we have only a convergence law, i.e. not 0-1 but still convergence in the probabilities, while in the case of at least one binary function symbol we do not even have convergence. See this article for reference:
K.J. Compton, C.W. Henson, S. Shelah, Nonconvergence, Undecidability, and intractability in asymptotic problems, Annals of Pure and Applied Logic 36 (1987) 207-224.
The general statements, especially about binary and larger symbols is quite involved, however we can easily see that we do not have a $0-1$ law in the case of a single unary function symbol by looking at the following nice example:
Note the formula $\varphi$ which stands for $\exists x (f(x)= x)$. What is the assymptotic probability of $\varphi$? If we assume that we have a finite structure $M$ with universe $\{1,\ldots, n\}$ then the probability that $f(i)\neq i$ is $1-\frac{1}{n}$. This probability is independent for each $i$. Thus the probability that $\varphi$ is false in $M$ is $(1-\frac{1}{n})^n$. Hence the assymptotic probability of $\varphi$ being false is $$\lim_{n\to\infty} \left(1-\frac{1}{n}\right)^n = \frac{1}{e}$$ Thus $\varphi$ has asymptotic probability $1-\frac{1}{e}$, and thus we clearly do not have a $0-1$ law.