I'm trying to show that the sentence $$\forall_x \exists_y P(x,y) \land \forall_x \forall_y (P(x,y) \implies \neg P(y,x)) \land \forall_x \forall_y \forall_z (P(x,y) \implies (P(y,z)\implies P(x,z))$$ (where $P$ is binary predicate) is false in finite structures and true in some infinite structure. For the second task I took structure $<\mathbb{Z}, < >$ and it seems to work. But i have no idea how to do the first part of the exercise.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Every finite structure satisfying the second two conditions violates the first, because every finite partially ordered set has a greatest element. Show this by induction on the number of elements. $\endgroup$– mjqxxxxCommented Nov 16, 2015 at 21:37
-
$\begingroup$ @mjqxxxx Every finite nonempty partially ordered set has a greatest element. $\endgroup$– 5xumCommented Nov 16, 2015 at 21:59
-
1$\begingroup$ @5xum ... has a maximal element. $\endgroup$– BrianOCommented Nov 16, 2015 at 22:15
-
$\begingroup$ I added missing parentheses around the inner part of the 2nd clause, which says that $P$ is antisymmetric and strict ($\neg P(x,x)$ for any $x$). $\endgroup$– BrianOCommented Nov 16, 2015 at 22:18
-
$\begingroup$ @5xsum: Sure. But the sentence is true in the empty structure, anyway. $\endgroup$– mjqxxxxCommented Nov 18, 2015 at 18:50
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
What it says is that we have an "strict order" (last part says transitive, second says antisymmetric) on the set where every element has a larger element (which is strictly larger as $P(x,x)$ can never hold, due to part 2 of the statement).
So if $F$ is a finite (non-empty) model, take $f_0 \in F$, and by recursion we find $f_n$ with $P(f_n, f_{n+1})$ for all $n \ge 0$. By finiteness some $f_n = f_m$ for $n \neq m$. Find a contradiction with transitivity.
answered Nov 16, 2015 at 21:33
$\begingroup$
$\endgroup$
Your sentence is basically made up of three statements.
The proof should go something like:
- Start with some $x_0$ in your finite structure
- Because of the first statement, there exists some $x_1$ such that $P(x_0, x_1)$. And some $x_2$ such that $P(x_1,x_2)$. This way, you can define $x_n$ for each $n\in\mathbb N$.
- Obviously, since the structure is finite, there exists some repetition. Take the first $k$ for which $x_k$ appears twice in the sequence $(x_0,x_1,\dots)$, i.e. $x_k=x_{k+m}$ for some $m$
- Now, you have a chain $x_k, x_{k+1},\dots x_{k+m}$.
- Because of the second statement, you know that $P(x_{k+m-1}, x_{k+m})$.
- Because of the third statement, you know that (proove it by induction) $P(x_k, x_{k+m-1})$.
