1

So far, I have used the domain, $\{1, 2, 3\}$, and have tried to determine an interpretation for $F$ in which $\forall y\; \exists x(Fxy)$ is true and $∃x\;∃y(Fxy ∧ Fyx)$ is false.

I began by trying to make $∃x\;∃y(Fxy ∧ Fyx)$ false. I reasoned that since this is an existential statement, for it to be false, every case of it, $∃y\;(Fxy ∧ Fyx)$, needs to be false. And since each of these cases, are themselves existentials, for them to be false each of their cases need to be false.

Here are the cases:

$∃y\;(F1y ∧ Fy1)$: $F11 ∧ F11$, $F12 ∧ F21$, $F13 ∧ F31$

$∃y\;(F2y ∧ Fy2)$: $F21 ∧ F12$, $F22 ∧ F22$, $F23 ∧ F32$

$∃y\;(F3y ∧ Fy3)$: $F31 ∧ F13$, $F32 ∧ F23$, $F33 ∧ F33$

Since each of these existentials' cases are conjunctions, for them each to be false at least one of the conjuncts need to be false, i.e. one of the ordered-pairs in the each conjunctions needs to be excluded from the extension of F.

Now, $∀y\;∃x(Fxy)$ is a universal, so to make it true, I need to make all of its instances true. And these instances, $∃x\;(Fxy)$, are themselves existentials, so to make them true, at least one of their instances need to be true. Here are the cases:

$∃x\;(Fx1)$: $F11$, $F21$, $F31$

$∃x\;(Fx2)$: $F12$, $F22$, $F32$

$∃x\;(Fx3)$: $F13$, $F23$, $F33$

So my approach was to rule out one of the ordered pairs from the conjunctions in order to falsify each of the first set of cases, while leaving enough of them not ruled out to make at least one of the ordered pairs in the second set true.

In the first place, I think I have to exclude from the extension of F each of the ordered pairs $<1, 1>$, $<2, 2>$, $<3, 3>$.

From there, I then decided to rule out $<1, 2>$, $<1, 3>$, $<1, 2>$, and $<2, 3>$.

But here's where I run into problems: If I rule out $<2, 3>$, then $'∃x\;(Fx3)$: $F13$, $F23$, $F33'$ turns false. If though, I include $<2, 3>$, then $'∃y\;(F2y ∧ Fy2)$: $F21 ∧ F12$, $F22 ∧ F22$, $F23 ∧ F32'$ turns true.

Note, I think that this extension for $F$ does the trick: $\{<1, 2>, <2, 3>, <3, 1>\}$. But I trying to more methodically work out how to produce this solution, if this is, in fact, a solution.

Thanks for any help. I really appreciate it!

This is IIIB2a from Goldfarb's Deductive Logic

Alex Pozo
  • 1,290
beachtrees
  • 209

2 Answers2

0

Your solution is fine. In order to make $\exists x \exists y (Fxy \wedge Fyx)$ false, you cannot have any of $F11,F22,F33$. You also can have only one of each pair $(F12,F21), (F13,F31),$ and $(F23,F32)$. To make $\forall y \exists x (Fxy)$ you need one instance with each element in the second position, which requires three instances to be true. You therefore need one of each pair. If you start with $F12$, you then need $F31$ as that is the only one available with $1$ in the second position. This forces $F23$ and your solution. Alternately you could start with $F21$ and get the corresponding solution $(F21,F32,F13)$

Ross Millikan
  • 374,822
0

There are two possible answers. One is what you already know and the other is $\{(1,3),(2,1),(3,2)\}$.

Since the domain is small it will help to draw a $3\times3$ table with $y$ values and $x$ values along the rows and columns. Place $1$ in the cell which will be contained in $F$ and cross out the rest.

  • The second condition crosses out all diagonal cells.
  • In each column i.e. $\forall y$, we have to place atleast one $1$ in the column due to the first condition.
  • When you place a $1$, the cell diagonally across gets automatically crossed out due to second condition.

For $y=1$, we may select $x=2$. So $(2,1)$ is selected and $(1,2)$ is crossed out. The only choice for $y=2$ is $x=3$ so $(3,2)$ is selected and $(2,3)$ is crossed. Finally $(1,3)$ is selected and we cross out $(3,1)$.

\begin{matrix}&y=1&y=2&y=3\\x=1&X&\color{red}X&1\\x=2&1&X&\color{red}X\\x=3&\color{red}X&1&X\end{matrix}

So we get $F=\{(1,3),(2,1),(3,2)\}$. In red are the non-diagonal $X$s. You will see that exchanging the $1$s and $X$s will also satisfy our requirements since each red $X$ was placed diagonally across a $1$ and there is a red $X$ in each column. Selecting the red $X$s gives us the $F$ you have mentioned which corresponds to selecting $x=3$ for $y=1$. Also note that this property is preserved for larger domains: flipping the member pairs of $F$ gives us another valid $F'$.

Shubham Johri
  • 17,659