1

Hello I just want a suggestion on how to solve this problem.

Show that the formula:

$A_{pigeon} = \forall x \exists y (Pxy \wedge y \neq c) \wedge \forall x,y,z (x = y \vee not Pyz \vee not Pxz)$

Is not satisfiable in any finite (nonempty) universe. Oh and c is a constant.

It's my understanding that I need to provide a concrete example in order to prove, but I'm not fully sure. If I need to prove this more generally can anybody provide some hint or technique to tackle this problem. Thank you for any advice!

Ross Millikan
  • 374,822
InsigMath
  • 2,073
  • 2
  • 18
  • 27

1 Answers1

4

Let denote $x_1,\dots,x_n$ the elements of the universe $U$, with $c=x_1$. The second part of the sentence tells us that if $Pxz$ and $Pyz$, then $x=y$, for any $x,y,z$. This means we can think of $P$ as a partial function $f:U\to U$, mapping the second argument to the first.

The first part tells us that for all $x$ there is $y\neq c$ such that $f(y)=x$. This means two things:

1)everything is reached by $f$.

2)$c$ has no image by $f$.

It is easy to see that there is a contradiction: if $c$ has no image, then only $n-1$ elements can be reached, contradicting 1).

Notice that $\mathbb N$ is a counter-example which satisfies $A_{pigeon}$, with $c=0$ and $Pxy$ being "$x+1=y$".

Denis
  • 6,945
  • 1
  • 21
  • 22