I am studying the predicate calculus in First Order Logic and I have some doubt about this argument. In my book I find that a formula in the predicate calculus is built from
- Literals constructed from
- Predicate Symbols: $P = \{p,q\}$
- Constants: $A = \{a,b\}$
- Variables: $X = \{x,y\}$
- Logical Connectives: (and, or, not, implication, etc)
- Quantifiers: (univeral and existential)
To build a syntactically correct formula I can use a BNF grammar.
So for example this one is a valid predicative forumla:
$$ \forall x.\exists y.(p(x,y) \to p(y,x)) $$
My question is: “what exactly is p?“
I think that $p$ is a predicate that represents a 2-ary relation. For example $p$ could be something like the relation that represent whether a number is the square root of another number. So for example:
\begin{gather} SQ(2,1) = F \\ SQ(2,2) = F \\ SQ(2,3) = F \\ SQ(2,4) = T \end{gather}
So if $p$ represents a 2-ary relation it is a subset of the $2\times 2$ cartesian product (in the previous case it is only the point that the first number is the square root of the second number).
So $p$ is a predicate that represents a $n$-ary relation $R$ on a domain $D$ and $R$ is a subset of $D^n$.
So, the predicate $p$ related to $R$ is true if:
$$R(d_1,\dots,d_n) = T \text{ iff } \langle d_1,\dots,d_n\rangle \in R $$
So, coming back to my previous predicative formula, can I say that it is built from some predicative symbol that uses variables and constants connected together by logical connectives, and in which I can “select” some or all variables by the universal and existential quantifiers?
The predicate symbol $p$ is part of the language. It has no meaning. It can only be part of a well formed formula. The interpretation of that language is a structure. It is in that structure that $p$ is interpreted as an $n$-ary relation on a given universe.
Let's use your square root predicate as an example. Suppose the symbol is 'SQ' and it is given in our language as a binary predicate symbol. Since it is a binary predicate $SQ(t_1,t_2)$ is a formula for any two terms $t_1$ and $t_2$ of our language. That is really all we can say about 'SQ' without a structure.
Now, if we have a structure that interprets our language, it must give meaning to a formula like $SQ(1,2)$, where $1$ and $2$ are also terms in our language. In your example, you interpreted this as meaning "the square root of $2$ is $1$". This is probably going to be evaluated as false in the structure you had in mind.