We consider a second-order logic where, in addition to first-order variables, on

Question

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 p_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 ).

Explanation / Answer

Solution:- Predicate is a function ,but a function is not necessarily a predicate.A predicate takes one or more arguments and evaluate to a Boolean value.Function takes one or more arguments in a set and assign a unique element of another set.

An m-ary function is an (m+1)-ary predicate. If F is a binary function symbol then { (x,y,z) / F(x,y) =z} is a definable ternary relation in every structure.

Predicate symbols are used to denote a property of objects or a relation between objects.We use upper case letters P,Q,R and P1,P2,.....Q1,Q2,.... as predicate symbols.Predicates of arity 1,2,3 are also called unary, binary, and ternary predicates.

A quantifier on an individual variable is assigned the domain of the structure, and if only such quantifieres are allowed, then it is a first order syste.

A quantifier on a predicate variable is assigned the domain of all sets of tuples of the appropriate arty, and in the presence of such quantifiers is called 2nd order system.

A sentence in 2nd order logic, as in first order logic, is a well fomed formula with no free variables.

First order logic uses only variables that range over individuals , 2nd order logic has these variables as well as additional variables that range over sets of individuals.

A 2nd order langualge is an extenstion of a first order language .2nd order quantifiers bind predicate variables, and they range over extension of predicates.

Unary function is a binary relation.

Given that A is a subset of X,If F(a,b1)=F(a,b2) then b1=b2 which is a one-one function,

So, F(a,b1,b2 ) is a unary function which maps from b1 to b2,which means F is an one-one from subset X to the subset Y.

Conversly if F is an one-one map from the subset X to subset Y, then (F,X,Y) contain one free binary predicate variable F and two free unary predicate variables X and Y .

That is F(a,b1)=F(a ,b2) implies b1=b2 ,the unary function F,which is a binary predicate.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.