Suppose the first-order language with equality and a unary function symbol $S$.

Want to find a sentence $\gamma $ such that no finite structure for this language satisfies $\gamma $ and some infinite structure $B$ for this language satisfies $\gamma.$ (finite means $|B|$ was a finite set.)

I solved it by making sure $S$ was injective and there was an element in $B$ could never be mapped. Thus any finite set could not satisfy the relation since its range would be smaller than its domain, i.e. $\forall x \forall y \wedge \rightarrow =SxSy =xy \neg \exists z =0Sz $

However, I couldn't figure out if there is any "weaker sentence" or "weakest sentence" $\gamma$ such that $\gamma$ satisfies the question, and whenever $\vDash_B \forall x \forall y \wedge \rightarrow =SxSy =xy \neg \exists z =0Sz$, then $\vDash_B \gamma$.

  • $\begingroup$ Are you polish? $\endgroup$ – Hagen von Eitzen Oct 27 '17 at 16:17
  • $\begingroup$ A weaker form would be $\forall x\forall y\land\to =SxSy=xy\exists w\forall z\neg=wSz$, simply because it gets rid of the constant $0$ $\endgroup$ – Hagen von Eitzen Oct 27 '17 at 16:21
  • 1
    $\begingroup$ To clarify Hagen von Eitzen's comment: the notation you're using is Polish notation, which is not standard in modern texts (normally the sentence you've written would be expressed as "$\forall x\forall y(S(x)=S(y)\implies x=y)\wedge\neg\exists z(0=S(z)))$." $\endgroup$ – Noah Schweber Oct 27 '17 at 16:22
  • $\begingroup$ prefix notion was kind of a rule since no parentheses or any confusion, infix $\forall x \forall y (((Sx=Sy)\rightarrow (x=y))\wedge (\neg \exists z (0=Sz)))$, was there any weaker condition? I was thinking if we can get rid of injective or some other cases? $\endgroup$ – user416486 Oct 27 '17 at 16:25
  • 3
    $\begingroup$ The prefix notation can actually be intrinsically ambiguous in a way that the (fully parenthesized) infix version cannot. What does $fgxy$ mean? $f(g(x,y))$ or $f(g(x),y)$ or even $f(g(x(y)))$ or $f(g,x,y)$? Or in a higher-order context e.g. $f(g)(x,y)$? But the real issue is readability. While Polish notation has some benefits, like easily seeing the outermost operator, the cost is mental stack management, needing to know arities, and the inability to quickly skim through the formula. For example, there's no way to tell what the second argument of $\land$ is without fully parsing the first. $\endgroup$ – Derek Elkins left SE Oct 27 '17 at 22:34

Yes, we can get weaker sentences: for example, expressing "$S$ is surjective but not injective" (in contrast with $\gamma$, which says "$S$ is injective but not surjective") in first-order logic is easy, and this sentence too is only true in infinite structures. We can now take the disjunct $$\mbox{Either $S$ is surjective but not injective, or injective but not surjective.}$$ This statement is strictly weaker than $\gamma$ and only true in infinite structures.

Note that "$0$" isn't needed here: we can express everything here without using a constant symbol. E.g. "$S$ is not surjective" is just "$\exists u\forall v(\neg S(v)=u)$."

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy