# Prove that sentence is not tautology. Check if contradiction this one has finite model.

I am trying to prove that following sentence is not tautology. $$\phi=(\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))$$

For me, it is sufficient to show $f:\mathbb{N}\to\mathbb{N}$ such that $f(n)=n+1$. Then $f$ fulfill left side of $\to$, but there is no such $y$ that $f(y)=0$ because $f[\mathbb{N}]=\{1,2,3,...\}$.
I am not sure if I am correct.

When it comes to second part:
Check if $\neg\phi$ has finite model.
$\neg\phi$ is $(\forall x\forall y((f(x)=f(y))\to(x=y)))\wedge \exists_x\forall_y(f(y)=x)$.
I don't know what does it mean finite model... Moreover, I am not sure about corectness of first part. Can you help me ?

• Do you know what a model is? – hmakholm left over Monica Oct 19 '16 at 11:39
• No, I don't know – user343207 Oct 19 '16 at 11:41
• If you haven't been told what a model it, then it seems to be strange that you're being asked to solve an exercise about them. Are you sure you don't have a description in whatever text you're using? – hmakholm left over Monica Oct 19 '16 at 11:53
• I don't know, and it is my problem :( – user343207 Oct 19 '16 at 14:07
• First of order. – user343207 Oct 19 '16 at 16:47

The first part is just correct.

What does it mean to have finite model? Well, just to be satisfied in a model which has finite universe (sometimes called "domain"). A model is a structure where a formula can be interpreted - your example of $(\mathbb{N}, S)$ is a model - a structure consisting of set ($\mathbb{N}$) and some relations (in this case a function $S: \mathbb{N} \to \mathbb{N}$). However, this model is not finite, as $\mathbb{N}$ has infinitely many elements.

So basically the question is: can be $\neg \phi$ be true in (you could say: "about" instead of "in") finite structure? You have shown, that it can be true in infinite one.

Below I attach an answer to the second question, however I would recommend you to try to find it out yourself - it is really not hard, and It looks like you just should get familiar with basic definitions.

The answer is negative: note, that the antecedent of $\phi$ just states that $f$ is injective (i.e. does not map two distinct elements to one value). If we take any structure with finite universe, an injective function is a bijection (you can prove this easily, e.g. by induction). So it is not possible that there is an element which is not a value of the function.

• Thanks you very much, @Jędrek. Sounds like polish name ;) – user343207 Nov 5 '16 at 12:00
• Thanks you very much, @Jędrek. Sounds like polish name ;) I invite you for my other threads in logic section – user343207 Nov 5 '16 at 12:05

Well, if $0 \in \mathbb{N}$ in your class then the first one is right. If you want you could put some thought into what the two sides of $\phi$ stand for. Hint: it has something to do with injectivity/surjectivity...

In the second part you have a little error in the negation of $\phi$, you should check that before proceeding. What finite model means will surely stand in the textbook/lecture notes this question is from and you should use the notations provided there.