i. (∃x)(∀y)Fxy
ii. (∀y)(∃x)Fxy
I am supposed to show that these are not logically equivalent by giving an interpretation that makes one true and the other false. I have the intuition that I need a two element universe of discourse, but I'm not sure how to write this out. Thank all for any help!
On
Consider the following formula over the set of natural numbers: $$F(x,y) \equiv (x>y).$$ Then $\forall y\exists x F(x,y)$ holds, but $\exists x\forall y F(x,y)$ fails.
We can in fact give an interpretation of finite domain which shows these two formulas are not equivalent. The idea is to consider a direct graph and mimicking my previous example. Here is a concrete description: let $D =\{0,1,2\}$ and $F=\{(0,1),\,(1,2),\,(2,0)\}$.
On
In predicate logic, quantifiers ($\exists, \forall$), always implicitly quantify over the whole universe (that is your base set of values the variables can take).
If we name the universe $U$, then formula i. can also be written as: $(\exists x\in U)(\forall y \in U) \big(F(x,y)\big)$
We can set $U$ to be an almost abitrary set - but for usual, you want to set $U$ to a set of natural numbers, e.g. $U = \{1,2\}$ for a two element universe.
To check your hunch, we only need to find all possibilities to define $F$, and pair each of those possibilities up with our universe and check.
$F$ is called a relation symbol or predicate symbol. It basically maps a tuple to a truth value by the following principle:
If $F$ has the arity of $n$ (i.e. $F$ takes $n$ variables), then $F$ is a set of tuples $\\(x_1,...,x_n)$, and it's defined like this:
$F(x_1,...,x_n) = \begin{cases} 1, \text{ if } (x_1,...,x_n) \in F\\ 0, \text{ else } \end{cases}$
In our example, $F$ has the arity 2, and could therefore be defined as $F = \{(1,1),(2,1)\}$. Therefore, e.g. $F(1,1) = 1, F(1,2) = 0$.
In this example, both i. and ii. evaluate to $0$, so this particular version of $F$ doesn't solve the question. So we choose another version for $F$, and try again...
On
$\exists x~\forall y~F(x,y)$ versus $\forall y~\exists x~F(x,y)$
Imagine $F(x,y)$ to say: there is mail in row $x$ and column $y$ of the square pigeon-hole board.
Then $\exists x~\forall y~F(x,y)$ says there some row with mail in every column. The mail that makes this true has to line up in the same row.
While $\forall y~\exists x~F(x,y)$ says in every column there is mail in some row. The mail that makes this true does not have to be in the same row.
I have the intuition that I need a two element universe of discourse, but I'm not sure how to write this out.
Consider the universe $\{0,1\}$ and relation $F$ that makes $\exists x\forall y~F(x,y)$ false, but $\forall y~\exists x~F(x,y)$ true.
Ie: Put mail in every column but not the same row...$$\begin{array}{l|l:l}F& 0 & 1\\ \hline 0& & \times \\ \hdashline 1 & \times & \end{array}$$
On
I have the intuition that I need a two element universe of discourse
Ok lets start with that. Lets call those elements 1 and 2.
$$\exists x.\forall y.Fxy$$ $$\exists x.(Fx1 \text{ and } Fx2)$$ $$(F11 \text{ and } F12) \text { or } (F21 \text{ and } F22)$$
and for the second
$$\forall y.\exists x.Fxy$$ $$\forall y.(F1y \text{ or } F2y)$$ $$(F11 \text{ or } F21) \text{ and } (F12 \text{ or } F22)$$ and now distribute: apply $(x \text{ or } y) \text{ and } z$ is equivalent to $(x \text{ and } z) \text{ or } (y \text{ and } z)$: $$(F11 \text{ and } F12) \text { or } (F11 \text{ and } F22) \text{ or } (F21 \text{ and } F12) \text { or } (F21 \text{ and } F22)$$
Can you see which is the stronger statement ?
It has been a while since I have done these, but I think you could formulate the answer as so.
Fxy means that person y knows person x's name
Then the first expression means there is a person who everyone knows. The second expression means that all people are known by someone. These are not equivalent; one example is that the universe of discourse contains the people Alice, Bob, and Charlie. Bob and Charlie know Alice, but neither Alice nor Charlie know Bob (poor Bob!). Since these can both be true at the same time, and i is true while ii is false, i and ii are not logically equivalent.
The reason this was hard to get to (to my mind at least) was that the role of x and y are 'backward' in the function Fxy - Fxy means "y knows x" in order to make this work.