Possible structures in first order logic

Question

So i was studying about structures in first order logic and i saw a question of this form:

Given a syntax A:{P} where P is 2-ary predicate symbol and {0,1} as universe we work.

How many different structures can we create with the above?

In other words, how many different meanings can P get?

So when i asked i was told as a brute asnwer that there are 4 different ways to set P.

Can someone explain me why? And also explain me if there is general rule for calculating how many structures can be created given a universe and a predicate symbol of a-arity.

Answer 1

For any ordered pair $(a,b)$ where $a$ and $b$ are in the universe, we are free to decide whether the interpretation of $P$ is true at $(a,b)$ or false at $(a,b)$. There are $2^2$ such ordered pairs, so altogether there are $2^{(2^2)}$ possible interpretations of $P$.

A similar calculation works for predicate symbols $P$ of arity $k$, and universes of finite size $n$. There are $n^k$ ordered $k$-tuples, and therefore $2^{(n^k)}$ possible interpretations of $P$.

Answer 2

\begin{align} P(0,0) & & \text{true or false?} \\ P(0,1) & & \text{true or false?} & & \\ P(1,0) & & \text{true or false?} \\ P(1,1) & & \text{true or false?} \end{align} For each of the four pairs $(x,y)$ above, $P(x,y)$ is either true or false. For each of four cases choose whether each is true or false. There are $2^4=16$ ways to do that.