Is "$\forall X\in\Gamma\forall Y\in \Sigma\exists x(x\in X\wedge x\in Y)$" a well-formed second-order logic formula?

49 Views Asked by At

I am trying to characterize some properties of argumentation framework of P.M.Dung with second-order logic formula. Such a framework is $AF=\langle Arg, R\rangle$, where $Arg$ is a finite set of arguments and $R$ is a binary relation on $Arg$. We use lowercase letters (i.e. $x,\ y,\ z,\ \cdots$) to denote elements of $Arg$, and uppercase letters (i.e., $X,\ Y,\ Z,\ \cdots$) to denote subsets of $Arg$. $\Gamma$ and $\Delta$ are fixed subsets of $2^{Arg}$, i.e. $\Gamma\subseteq 2^{Arg}$ and $\Sigma\subseteq 2^{Arg}$. Those are the backgrounds. Here are my qustions:

  1. Is "$\forall X\in\Gamma\forall Y\in \Sigma\exists x(x\in X\wedge x\in Y)$" a well-formed second-order logic formula? Note that "$\forall X\in\Gamma\varphi(X)$'' is short for ''$\forall X((X\in\Gamma)\wedge\varphi(X))$''

  2. Can I describe a set $\Delta$ of arguments as follows: $\Delta=\{x\in Arg\mid \forall X\in\Gamma\forall Y\in \Sigma(x\in X\wedge x\in Y) \}$

1

There are 1 best solutions below

5
On

What you have written for (1) is not a second order formula, but a third order formula. A first order formula has variables that range over individuals (i.e. elements of $Arg$), and no other kind of variable; a second order formula has variables that range over individuals, and variables that range over sets of individuals (i.e. over elements of $2^{Arg}$). The formula written here also has $\Gamma,\Sigma$ ranging over elements of $2^{2^{Arg}}$, which is what makes it third order.

What you have down for (2) is a perfectly sensible notation, if still involving a third order formula. But without knowing anything about the logical setup in the source you're working from, there's no telling if it actually exists. Presumably, if you're caring about second-order or third-order formulas, and are not just working set-theoretically, you should be working in some particular second order theory, and that theory will provide you with some comprehension axioms that tell you what formulas determine sets. Without knowing the comprehension axioms available to you, all that can be said is that it's not syntactically malformed.