0
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ Do you know what a model is? $\endgroup$ – hmakholm left over Monica Oct 19 '16 at 11:39
  • 1
    $\begingroup$ No, I don't know $\endgroup$ – user343207 Oct 19 '16 at 11:41
  • 1
    $\begingroup$ 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? $\endgroup$ – hmakholm left over Monica Oct 19 '16 at 11:53
  • 1
    $\begingroup$ I don't know, and it is my problem :( $\endgroup$ – user343207 Oct 19 '16 at 14:07
  • 1
    $\begingroup$ First of order. $\endgroup$ – user343207 Oct 19 '16 at 16:47
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks you very much, @Jędrek. Sounds like polish name ;) $\endgroup$ – user343207 Nov 5 '16 at 12:00
  • $\begingroup$ Thanks you very much, @Jędrek. Sounds like polish name ;) I invite you for my other threads in logic section $\endgroup$ – user343207 Nov 5 '16 at 12:05
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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