2
$\begingroup$

I had to solve a question in Logics, disprove the fact that "if two statements without free variables are satisfiable in the same finite structures, then they are logically equivalent".

The only property found that doesn't translate from finite fields to infinite structures(that I could prove) was the over finite structures, a function is one-to one (Injective) iff it is onto (surjective) but this isn't true over infinite structures, and those statements were easy to write.

My first thought was to use the property that over finite structures every relation has a maximum member that satisfies it - but I couldn't write specific statement that catches that. (Remark - as always, I am free to define whichever dictionary I want) - Is it impossible to state in general, because I can't control how a binary relation R that I might use will be interpreted in some structure, and it won't be the $\le$ relation, or even if the domain of that structure will be numbers, so "maximum" may not even be well defined over most structures?

Also - are there other properties that I could have used that are general enough to work over every structure and are correct over finite structures and don't carry to infinite structures?

$\endgroup$
2
$\begingroup$

HINT: You can write a sentence $\varphi$ with a binary relation symbol $R$ that says that $R$ is a non-empty linear order with no minimum element. You can write a similar sentence $\psi$ that says that $R$ is a non-empty linear order with no maximum element. Then $\varphi$ and $\psi$ are satisfiable in exactly the same finite structures (which ones?), but ...

$\endgroup$
  • $\begingroup$ What does it mean non-empty linear order, with emphasis on the linear-order part? I was told that despite the fact that I cant actually write a sentence that says "every relation has a maximum member that satisfies it " but there is a way to talk about "maximum element" by defining a sentence that talks about "Total order" - but I don't know how does Total order relate to maximum element that satisfies a relation, nor how to formally write the statement. Would appreciate some help. Thanks $\endgroup$ – jon Prime Jun 10 '15 at 20:05
  • $\begingroup$ @jon: A linear order is a partial order (i.e., a reflexive, transitive, antisymmetric binary relation) that is total, meaning that it also satisfies $\forall x\,\forall y\big(R(x,y)\lor R(y,x)\big)$. All of these are first-order properties. To say that $R$ has no minimum element is then simply to say that $\forall x\,\exists y\big(x\ne y\land R(y,x)\big)$. $\endgroup$ – Brian M. Scott Jun 10 '15 at 20:08
  • $\begingroup$ I created the following statement that states that every total (non strict) order has a minimum, and then I negated it and it is satisfiable only over infinit sets: a= not ( (total) and (transitive) and (antisymmetry) -> (∃y∀x(R(y,x))) is that ok? $\endgroup$ – jon Prime Jun 11 '15 at 17:57
0
$\begingroup$

Exploiting your idea that injective and surjective functions coincide exactly in a finite universe, you could contrast $$ \forall x\forall y(f(x)=f(y)\to x=y) \leftrightarrow \forall x\exists y(x=f(y)) $$ with $$ \forall x(x=x) $$

Both are satisfied in all finite structures, but since there are infinite structures satisfying only one of them, they are not logically equivalent.

$\endgroup$
  • $\begingroup$ That's what i did, thanks $\endgroup$ – jon Prime Jun 10 '15 at 20:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.