Converting a sentence to a formula in second order logic and typed first-order logic

124 Views Asked by At

I was given the following sentence:

"There are sets X & Y, such that the function F from X to Y is injective but not surjective."

I need to turn this sentence into a formula in:

  1. second order logic
  2. typed first-order logic

For second order logic I defined:

  • $x_S$ - the relation to be a set
  • $x_F$ - the relation to be an injective function
  • $x_G$ - the relation to be an surjective function
  • $R(x, y, z)$ - the function $z$ is from $x$ to $y$

and the formula is $$\varphi = \exists_{x_{S}^X}\exists_{x_{S}^Y}\exists_{x_{F}}(\neg(x_{S}^X=x_{S}^Y)\wedge R(x_{S}^X, x_{S}^Y, x_{F}) \wedge \forall_{x_G}(\neg(x_{F}=x_{G}))$$

For typed first-order logic I defined

  • $X$, $Y$ - variables for the subset of sets
  • $f$, $g$ - variables for the subset of functions
  • $I(x)$ - the function x is injective
  • $S(x)$ - the function x is surjective
  • $R(X, Y, z)$ - the function $z$ is from $X$ to $Y$

and the formula is $$\psi = \exists_X\exists_Y\exists_f(\neg(X=Y)\wedge I(f) \wedge R(X, Y, f) \wedge \forall_g(S(g)\rightarrow \neg (g = f)))$$

I got the following comments:

  • The formula in second order logic is incorrect and does not describe the given sentence. Also the relation $R$ isn't needed
  • The formula for typed first-order logic is incorrect, being surjective isn't a relation

I don't understand why both formulas are incorrect and the comments, why is $R$ not needed in second order logic? can I define a relation, e.g $x_H$ - being an injective function from $X$ to $Y$, even if I don't know what $X$ and $Y$ are, and if they even exists? Also how can being injective be a relation but being surjective isn't?