Skip to main content
added 895 characters in body
Source Link
blub
  • 4.8k
  • 3
  • 17
  • 39

I don't know what youyour underlying language is, but if your set of variables includes $X,Y,x$ and your signature is just consisting of $\in$, taking $\subseteq$ as exactly the abbreviation as the right hand side, then (i) is a well-formed formula in the language of set theory. You may even add $\subseteq$ as a binary relation symbol to make it well-formed in some other signature of your taste.

(ii) seems to suggest that $P$ is a unary predicate which is quantified at the beginning, thus this formula isseems not be well-formed in first-order logic.

I think there is needed information missing to really answer the questions for which you should search yourself(in the book where this question is from). The question

  1. There is no pure $FO$(at least not per se). First-order logic is defined, in its classical form, over a signature $\sigma=(\mathrm{Fun},\mathrm{Rel},\mathrm{Con},\mathrm{ar})$ with $\mathrm{Fun},\mathrm{Rel},\mathrm{Con}$ being the sets of function, relation and constant symbols respectively(it may be that the formalism you were introduced to is slightly different, don't worry about that too much). The object of discourse is thus always $FO(\sigma)$, i.e. first-order logic of/to a signature $\sigma$. $\mathrm{ar}$ is a function, associating every predicate and function symbol with the arity, i.e. how many arguments they are required(and permitted) to take.
  2. The set of variables needs to be formally specified. $FO(\sigma)$ is built over a set of variables, here denoted $Var$ similarly. Similarly as the set of function symbols, relation symbols, etc., this set in general may have any size, i.e. cardinality, but is usually either assumed to be finite or countably infinite. With formally specified, I mean that e.g. taking $Var=\{x_1,x_2,\dots\}$, then my variable symbols for $FO(\sigma)$ are(technically) only the syntactical constructs $x_1,x_2,\dots$
  1. Every variable $x$(note that I take $x$ here as a variable for a variable symbol which is a concrete object, a string, and a member of $Var$) is a term.
  2. Every constant $C$$c$(similar note as to the variables) is a term.
  3. If $t_1,\dots,t_n$ are terms, and $f$(similar note as to the variables) is a $n$-ary function symbol($\mathrm{ar}(f)=n$), then $f(t_1,\dots,t_n)$ is a term.
  • If $t_1,\dots,t_n$ are terms and $P$(similar note as to the variables) is an $n-ary$$n$-ary predicate symbol(\mathrm{ar}(P)=n$\mathrm{ar}(P)=n$), then $P(t_1,\dots,t_n)$ is a formula.
  • If $\phi\land\psi$ are formulas, then $(\phi\land\psi)$, $\neg\phi$ and $(\phi\lor\psi)$ are formulas.
  • If $\phi$ is a formula and $x$ is a variable, then $\forall x\phi$ is a formula
  • Every variable symbol in a formula is a member of $Var$ and concretely specified as a syntactical object(I omit that comment in the following).
  • Every predicate symbol in a formula is a member of $\mathrm{Rel}$
  • Every function symbol in a formula is a member of $\mathrm{Fun}$
  • The arity is also a syntactical feature, e.g. a function symbol is ought to have $n $ argument strings syntactically to be well defined.

So for you to analyse if a formula if it is well-formed, your first question has to be over what signature and over what set of variables. Then you may assert membership in $FO(\sigma)$.

We all use shorthand notations and deviate from this formal specification. Thus e.g. even when some author formally defined $Var=\{x_1,x_2,\dots\}$, you're likely to see $\forall x\phi$ as a formula. This is meant to be a shorthand but it is not technically fine, but such a minor detail that normally no one gets hurt. A good mantra is that you are allowed to deviate if you can always rephrase it properly.

Another common shorthand also used in your example is that binary predicates are often denoted in infix notation, that is, instead of writing $>(x,y)$ you write $x>y$. 

There are however situations where the concrete syntactical structure matters, that is why this is set on such a firm ground.

I want to end with, that working with these objects is a purely syntactical matter. There is no meaning attached to these strings(yet) and that is how they ought to be treated. Two strings differ if they differ in one symbol already. It is not about representing (semantically) the same.

I don't know what you underlying language is, but if your set of variables includes $X,Y,x$ and your signature is just consisting of $\in$, taking $\subseteq$ as exactly the abbreviation as the right hand side, then (i) is a well-formed formula in the language of set theory.

(ii) seems to suggest that $P$ is a unary predicate which is quantified at the beginning, thus this formula is not well-formed in first-order logic.

I think there is needed information missing for which you should search yourself(in the book where this question is from). The question

  1. There is no pure $FO$(at least not per se). First-order logic is defined, in its classical form, over a signature $\sigma=(\mathrm{Fun},\mathrm{Rel},\mathrm{Con},\mathrm{ar})$ with $\mathrm{Fun},\mathrm{Rel},\mathrm{Con}$ being the sets of function, relation and constant symbols respectively(it may be that the formalism you were introduced to is slightly different, don't worry about that too much). The object of discourse is thus always $FO(\sigma)$, i.e. first-order logic of/to a signature $\sigma$. $\mathrm{ar}$ is a function, associating every predicate and function symbol with the arity, i.e. how many arguments they are required(and permitted) to take.
  2. The set of variables needs to be formally specified. $FO(\sigma)$ is built over a set of variables, here denoted $Var$ similarly as the set of function symbols, relation symbols, etc., this set in general may have any size, i.e. cardinality, but is usually either assumed to be finite or countably infinite. With formally specified, I mean that e.g. taking $Var=\{x_1,x_2,\dots\}$, then my variable symbols for $FO(\sigma)$ are(technically) only the syntactical constructs $x_1,x_2,\dots$
  1. Every variable $x$(note that I take $x$ here as a variable for a variable symbol which is a concrete object of $Var$) is a term.
  2. Every constant $C$ is a term.
  3. If $t_1,\dots,t_n$ are terms, and $f$ is a $n$-ary function symbol($\mathrm{ar}(f)=n$), then $f(t_1,\dots,t_n)$ is a term.
  • If $t_1,\dots,t_n$ are terms and $P$ is an $n-ary$ predicate symbol(\mathrm{ar}(P)=n), then $P(t_1,\dots,t_n)$ is a formula.
  • If $\phi\land\psi$ are formulas, then $(\phi\land\psi)$, $\neg\phi$ and $(\phi\lor\psi)$ are formulas.
  • If $\phi$ is a formula and $x$ is a variable, then $\forall x\phi$ is a formula
  • Every variable symbol in a formula is a member of $Var$.
  • Every predicate symbol in a formula is member of $\mathrm{Rel}$
  • Every function symbol in a formula is a member of $\mathrm{Fun}$

So for you to analyse a formula if it is well-formed, your first question has to be over what signature and over what set of variables. Then you may assert membership in $FO(\sigma)$.

We all use shorthand notations and deviate from this formal specification. Thus e.g. even when some author formally defined $Var=\{x_1,x_2,\dots\}$, you're likely to see $\forall x\phi$ as a formula. This is meant to be a shorthand but it is not technically fine, but such a minor detail that normally no one gets hurt. There are however situations where the concrete syntactical structure matters, that is why this is set on such a firm ground.

I don't know what your underlying language is, but if your set of variables includes $X,Y,x$ and your signature is just consisting of $\in$, taking $\subseteq$ as exactly the abbreviation as the right hand side, then (i) is a well-formed formula in the language of set theory. You may even add $\subseteq$ as a binary relation symbol to make it well-formed in some other signature of your taste.

(ii) seems to suggest that $P$ is a unary predicate which is quantified at the beginning, thus this formula seems not be well-formed in first-order logic.

I think there is needed information missing to really answer the questions for which you should search yourself(in the book where this question is from). The question

  1. There is no pure $FO$(at least not per se). First-order logic is defined, in its classical form, over a signature $\sigma=(\mathrm{Fun},\mathrm{Rel},\mathrm{Con},\mathrm{ar})$ with $\mathrm{Fun},\mathrm{Rel},\mathrm{Con}$ being the sets of function, relation and constant symbols respectively(it may be that the formalism you were introduced to is slightly different, don't worry about that too much). The object of discourse is thus always $FO(\sigma)$, i.e. first-order logic of/to a signature $\sigma$. $\mathrm{ar}$ is a function, associating every predicate and function symbol with the arity, i.e. how many arguments they are required(and permitted) to take.
  2. The set of variables needs to be formally specified. $FO(\sigma)$ is built over a set of variables, here denoted $Var$. Similarly as the set of function symbols, relation symbols, etc., this set in general may have any size, i.e. cardinality, but is usually either assumed to be finite or countably infinite. With formally specified, I mean that e.g. taking $Var=\{x_1,x_2,\dots\}$, then my variable symbols for $FO(\sigma)$ are(technically) only the syntactical constructs $x_1,x_2,\dots$
  1. Every variable $x$(note that I take $x$ here as a variable for a variable symbol which is a concrete object, a string, and a member of $Var$) is a term.
  2. Every constant $c$(similar note as to the variables) is a term.
  3. If $t_1,\dots,t_n$ are terms, and $f$(similar note as to the variables) is a $n$-ary function symbol($\mathrm{ar}(f)=n$), then $f(t_1,\dots,t_n)$ is a term.
  • If $t_1,\dots,t_n$ are terms and $P$(similar note as to the variables) is an $n$-ary predicate symbol($\mathrm{ar}(P)=n$), then $P(t_1,\dots,t_n)$ is a formula.
  • If $\phi\land\psi$ are formulas, then $(\phi\land\psi)$, $\neg\phi$ and $(\phi\lor\psi)$ are formulas.
  • If $\phi$ is a formula and $x$ is a variable, then $\forall x\phi$ is a formula
  • Every variable symbol in a formula is a member of $Var$ and concretely specified as a syntactical object(I omit that comment in the following).
  • Every predicate symbol in a formula is a member of $\mathrm{Rel}$
  • Every function symbol in a formula is a member of $\mathrm{Fun}$
  • The arity is also a syntactical feature, e.g. a function symbol is ought to have $n $ argument strings syntactically to be well defined.

So for you to analyse if a formula is well-formed, your first question has to be over what signature and over what set of variables. Then you may assert membership in $FO(\sigma)$.

We all use shorthand notations and deviate from this formal specification. Thus e.g. even when some author formally defined $Var=\{x_1,x_2,\dots\}$, you're likely to see $\forall x\phi$ as a formula. This is meant to be a shorthand but it is not technically fine, but such a minor detail that normally no one gets hurt. A good mantra is that you are allowed to deviate if you can always rephrase it properly.

Another common shorthand also used in your example is that binary predicates are often denoted in infix notation, that is, instead of writing $>(x,y)$ you write $x>y$. 

There are however situations where the concrete syntactical structure matters, that is why this is set on such a firm ground.

I want to end with, that working with these objects is a purely syntactical matter. There is no meaning attached to these strings(yet) and that is how they ought to be treated. Two strings differ if they differ in one symbol already. It is not about representing (semantically) the same.

Source Link
blub
  • 4.8k
  • 3
  • 17
  • 39

I don't know what you underlying language is, but if your set of variables includes $X,Y,x$ and your signature is just consisting of $\in$, taking $\subseteq$ as exactly the abbreviation as the right hand side, then (i) is a well-formed formula in the language of set theory.


(ii) seems to suggest that $P$ is a unary predicate which is quantified at the beginning, thus this formula is not well-formed in first-order logic.


If you assume for (iii) that $t$ is a variable symbol, and $G,U$ are unary/binary predicate symbols respectively and $P$ is a unary predicate, then this formula does not really make sense, as we have a predicate applied to another predicate.


I think there is needed information missing for which you should search yourself(in the book where this question is from). The question

Is the formula $\phi$ a well-formed $FO$-formula?

is always to be read with some appropriate context.

  1. There is no pure $FO$(at least not per se). First-order logic is defined, in its classical form, over a signature $\sigma=(\mathrm{Fun},\mathrm{Rel},\mathrm{Con},\mathrm{ar})$ with $\mathrm{Fun},\mathrm{Rel},\mathrm{Con}$ being the sets of function, relation and constant symbols respectively(it may be that the formalism you were introduced to is slightly different, don't worry about that too much). The object of discourse is thus always $FO(\sigma)$, i.e. first-order logic of/to a signature $\sigma$. $\mathrm{ar}$ is a function, associating every predicate and function symbol with the arity, i.e. how many arguments they are required(and permitted) to take.
  2. The set of variables needs to be formally specified. $FO(\sigma)$ is built over a set of variables, here denoted $Var$ similarly as the set of function symbols, relation symbols, etc., this set in general may have any size, i.e. cardinality, but is usually either assumed to be finite or countably infinite. With formally specified, I mean that e.g. taking $Var=\{x_1,x_2,\dots\}$, then my variable symbols for $FO(\sigma)$ are(technically) only the syntactical constructs $x_1,x_2,\dots$

Now, what is the set of well-formed formulas, $FO(\sigma)$? This set is generated in the following way from the before mentioned sets:

First, we form the set of terms of this signature $\sigma$.

  1. Every variable $x$(note that I take $x$ here as a variable for a variable symbol which is a concrete object of $Var$) is a term.
  2. Every constant $C$ is a term.
  3. If $t_1,\dots,t_n$ are terms, and $f$ is a $n$-ary function symbol($\mathrm{ar}(f)=n$), then $f(t_1,\dots,t_n)$ is a term.

Then $FO(\sigma)$ is formed using this set of terms and $\sigma$ again:

  • If $t_1,\dots,t_n$ are terms and $P$ is an $n-ary$ predicate symbol(\mathrm{ar}(P)=n), then $P(t_1,\dots,t_n)$ is a formula.
  • If $\phi\land\psi$ are formulas, then $(\phi\land\psi)$, $\neg\phi$ and $(\phi\lor\psi)$ are formulas.
  • If $\phi$ is a formula and $x$ is a variable, then $\forall x\phi$ is a formula

We remark a few things on the process of forming the set of well-formed first-order logic formulas over a signature $\sigma$ and a set of variable $Var$ I just sketched:

  • Every variable symbol in a formula is a member of $Var$.
  • Every predicate symbol in a formula is member of $\mathrm{Rel}$
  • Every function symbol in a formula is a member of $\mathrm{Fun}$

So for you to analyse a formula if it is well-formed, your first question has to be over what signature and over what set of variables. Then you may assert membership in $FO(\sigma)$.


As I said before, this is just a sketch. First, what I was describing was first-order logic without equality, but the differences are marginal(on the syntactical level).

We all use shorthand notations and deviate from this formal specification. Thus e.g. even when some author formally defined $Var=\{x_1,x_2,\dots\}$, you're likely to see $\forall x\phi$ as a formula. This is meant to be a shorthand but it is not technically fine, but such a minor detail that normally no one gets hurt. There are however situations where the concrete syntactical structure matters, that is why this is set on such a firm ground.

EDIT: I tried to not give you an answer but to explain to you the context of how to find an answer yourself(which some of my perspective on the top). I could not have given a precise answer as you we're asking about a syntactic technicality for which I don't know the complete surrounding to, i.e. the signature, etc. This answer turned out longer than expected and thus if something is unclear, we should clarify this together in the comments.