First-Order Definability and Second-Order Definability. We consider a second-ord
ID: 3184899 • Letter: F
Question
First-Order Definability and Second-Order Definability. We consider a second-order logic where, in addition to first-order variables, only unary-predicate and binary-predicate variables are allowed. No function variables of any arity are allowed.
Note the following:
• If M , (A, . . .) is a model of second-order logic with domain A, then a subset of A can be represented by a unary predicate X, in which case we simply say “the subset X”.
• A unary function f on domain A is represented by a binary predicate F such that for all a, b1, b2 A, if F(a, b1) and F(a, b2) hold, then b1 = b2. For simplicity, we say “the unary function F”, with the understanding that F is formally a binary predicate. In the second-order WFF’s you have to write below, you can use the equality symbol “ .=” between first-order variables, but not between second-order variables.
(1) Write a second-order WFF injective(F, X, Y ) with one free binary-predicate variable F, and two free unary-predicate variables X and Y , which holds iff F is a unary function which maps the subset X to the subset Y injectively (i.e., F is one-one, but not necessarily onto, from X to Y ).
(2) Write a second-order WFF 6(X, Y ) with two free unary-predicate variables X and Y which holds iff the size of the set represented by X is 6 the size of the set represented by Y . Hint for (2): Use injective(F, X, Y ) from part (1).
In the parts below, from (3) to (9), we consider second-order WFF’s over the signature (or vocabulary) of graphs. Each graph is a model of the form M , (A, RM) where A is the set of nodes and RM is a binary relation RM A × A representing the edges of the graph, i.e., RM(a, b) means there is an edge from node a to node b.
(3) Write a closed second-order WFF simple which holds in a graph M iff M is undirected and contains no self-loops. Such graphs are usually called simple.
Hint for (3): The required simple is in fact first-order and, thus, also second-order.
(4) Write a second-order WFF clique(X) with one free unary-predicate variable X which holds in a graph M iff M is simple and X is a clique of M.
Hint for (4): clique(X) is a conjunct of two parts, the first of which is simple from part (3).
(5) Write a second-order WFF maximal-clique(X) with one free unary-predicate variable X which holds in a graph M iff M is simple and X is a maximal clique of M, i.e., it is not contained in a strictly larger clique.
Hint for (5): Use clique(X) from part (4).
(6) Write a second-order WFF maximum-clique(X) with one free unary-predicate variable X which holds in a graph M iff M is simple and X is a maximum clique of M, i.e., X is a maximal clique of maximum size in M (see Figure 1).
Hint for (6): Use clique from part (4), maximal-clique from part (5), and 6 from part (2).
(7) In a simple graph M there is always a maximum clique, which may or may not be unique. Write a closed second-order WFF only-one-maximum which holds in a graph M iff M is simple and contains only one maximum clique.
Hint for (7): Use maximum-clique from part (6).
(8) In a simple graph M, a trivial maximal clique consists of a single node (an isolated node) or two nodes (the end-points of an edge which is not part of any triangle in M). Write a closed second-order WFF all-nontrivial-are-maximum which holds in a graph M iff M is simple and all its non-trivial maximal cliques are maximum cliques.
Hint for (8): Use maximal-clique from part (5) and maximum-clique from part (6).
Explanation / Answer
In short, a predicate is a (strictly Boolean-valued) function, but a function is not necessarily, and usually not, a predicate.
A predicate takes one or more argument(s) and evaluates to a Boolean value: true, or false. For x,yZ
, xy, is a predicate: its "output" is true, or false. (x,y){true or false}
.
Functions takes of one or more "arguments" (elements) in a set (from the domain of the function) and assign a unique element of another set (which is the range of the function). Note, sometimes the domain is the same set as the range. Arguments of the domain and elements of the range are in the "domain of discourse."
Note: Both predicates and functions have an associated "arity," meaning the number of arguments in in the domain that are mapped onto each value, or respectively, element, of range.
So, e.g., the "arity" of the predicate "x is a parrot": P(x)
is one; the arity of the predicate "y sits between x and z": B(x,y,z)
is three. In each case the output is true or false.
Addition of integers, on the other hand, is a function of arity two, which takes two numbers as arguments, say x,yZ
and returns a number z=x+yZ.
Syntactically predicates are used to form formulas; function symbols are used to form terms.
Terms later translate to objects in the structure, whereas formulas are evaluated to be true or false in a particular structure and assignment.
From the semantic point of view there is little difference from how we usually treat functions and relations. In the sense that an $n$-ary function is just an $(n+1)$-ary predicate. In fact if $F$ is a binary function symbol then ${(x,y,z)mid F(x,y)=z}$ is a definable ternary relation in every structure.
In the other direction if we have a predicate $R(x,y)$ and we know that in a certain structure for the language, $M$, every $u$ has exactly one $v$ such that $Mmodels R(u,v)$ then in fact $R$ defines a function $f_R(u)$, by saying that "$f_R(u)$ is the unique object $v$ such that $R(u,v)$ holds" we essentially write $f_R(u)=v$, and while we cannot use this to create syntactical terms, we can always write a formula and require that a variable satisfies this condition - so effectively we do write $f_R(u)$.
This is why when we deal with theories rather than structures we can always assume the symbols are relations, because we can add axioms specifying that these relations are really functions (or constants which are constant functions of course, or relations which exactly one object satisfies).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.