I need to prove whether the following statement is true or false:
let $L$ be a first order language with the following signature $\sigma = \{{p_1, p_2, p_3}\}$ which are all 1-ary predicates. Does there exist a formula $A$ in $L$ such that there exists a structre and a variable assginment that satisfies $A$ only if the size of the domain of the structure is at least 5
Now, it seems wrong to me, because we don't have any way to "compare" 2 items with this signature. What direction should I go in? thanks.
I guess the problem said if and only if, rather than only if. Otherwise the question is trivial (any self-contradictory formula would be fine).
Think about unary predicates as subsets. As a hint, I show you the solution of a simpler problem. You can modify the proof to get a solution for your problem.
Modified problem: same signature, and we are looking for a formula which is satisfyable in some structure $A$ if and only if $|A|\geq 8$.
The formula should say there exists an element in all $8$ possible Boolean combinations that you can express using $p_1, p_2, p_3$. So there is an $x$ with $p_1(x)\wedge p_2(x)\wedge p_3(x)$. Also there is a $y$ with $\neg p_1(x)\wedge p_2(x)\wedge p_3(x)$. Etc. with the remaining six combinations.
The conjuction of these 8 requirements is equivalent to the structure having at least $8$ elements. (Think about it).
Now modify the proof to get it with $5$ instead of $8$.