A = (∀x∀y∀z(P xy → (P yz → P xz)))

B = (∀x∀y(P xy → (P yx → x = y)))

C = (∀x∃yP xy) → (∃y∀xP xy)

I want to show that {A, B} does not imply C by constructing a structure.

What I've done so far is just translated it to English so I can visualize it better:

A: For all x, y, z: If XY, then YZ implies XZ

B: For all x, y: If XY, then YX implies X=Y

C: IF For all X there exists some Y where XY, THEN there exists a Y such that for all X, XY.

I'm going about this problem by using C as a constraint, since it's what we want to contradict. But this is where I'm stuck. I would like to know how to actually construct the required structure.


Hint: A says that $P$ is a transitive relation. B says that $P$ is anti-symmetric. This is perhaps obscured by the sentences using only implication "$\to$". For example, A is usually stated in the equivalent form $\forall x \forall y \forall z\,((P(x,y) \land P(y,z)) \to P(x,z))$.

For any set of numbers, finite or infinite, the usual ordering $\le$ is an example of such a relation. (Actually, so is $<$, but B is true for $<$ "vacuously", as there are no numbers $x,y$ such that $x<y$ and $y<x$.) If you interpret $P$ as $\le$, consider what C says about $\le$. The antecedent (first part of the implication) is true; how about the consequent (the second part)?

  • $\begingroup$ Thank you. I actually was thinking along the same lines but was thinking of an addition relationship instead of a $\le$ relationship. This brings me to a couple questions: 1. How do you start questions like this? Do you just stare at it and try to reason it out? Do you draw something? 2. How would you actually write this as a structure? It seems clear, have the structure be a set of natural numbers, xyz be elements in that set. Therefore A, B are satisfied and in C there is always exists some y that x $\le$ y, BUT there's no single y that x $\le$ y. But the actual notation is frustrating. $\endgroup$
    – user120920
    Nov 6 '15 at 0:24
  • 1
    $\begingroup$ Good questions. In this case I'm familiar with this example, so no staring required. It's a great, maybe standard example showing why $\forall x \exists y P(x,y)$ doesn't imply the stronger statement $\exists y \forall x P(x,y)$ (the latter does imply the former). In general I would start as you did, getting a handle on what the "theory" (A and B) says about (interpretations of) $P$. The set of natural numbers is $\mathbb{N}$, so the structure in question is $\mathcal{N} = (\mathbb{N}, \le)$. You want to confirm that in $\mathcal{N}$, A and B are true but C is false. $\endgroup$
    – BrianO
    Nov 6 '15 at 0:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.