Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

Question

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4):

Prove:

In a dyadic tree, define x to be to the left of y if there is a junction point whose left successor dominates x and whose right successor dominates y. Prove that if x is to the left of y and y is to the left of z, then x is to the left of z.

Relevant definitions:

1. Dyadic Tree: a tree in which each junction point has exactly 2 successors
2. x dominates y: point x is above point y in the tree, or x is identical to y

So far, I have this for the proof:

1. x is to the left of y. So there is some junction j1 whose left successor s1 dominates x, and whose right successor s2 dominates y
2. y is to the left of z. So there is some junction j2 whose left successor s3 dominates y, and whose right successor s4 dominates z

I'm pretty sure what I need to prove from 1 and 2 is:

There is some junction j3 whose left successor s5 dominates x, and whose right successor s6 dominates z. So x is to the left of z.

So far, I've tried a proof that begins with cases (j1=j2; j1 dominates j2; j2 dominates j1; j1 and j2 are the let and right successors of j); and I've tried to work out a proof whereby every successor to s1 is to the left of every successor of s2, etc., but I get stuck each time. Any suggestions would be greatly appreciated.

Answer 1

I have thought of a similar way to prove transitivity as mentioned by Curious Yogurt, and it goes as follows: Let's consider that we have three points $x$, $y$, and $z$ in a dyadic tree $\mathcal{T}$.

First, let's assume $x$ is to the left of $y$. This implies the existence of a junction point $j_1$ in $\mathcal{T}$ such that the left successor of $j_1$ dominates $x$, and the right successor of $j_1$ dominates $y$.

Next, consider that $y$ is to the left of $z$. Consequently, there is another junction point $j_2$ where the left successor of $j_2$ dominates $y$, and its right successor dominates $z$.

Given that both $j_1$ and $j_2$ dominate $y$, and since $\mathcal{T}$ is a dyadic tree (implying $j_1 \neq j_2$), we have two scenarios:

• If $j_1$ dominates $j_2$: Since $x$ is dominated by the left successor of $j_1$, and both $y$ and $z$ are dominated by the right successor of $j_1$, it follows that $x$ is left of $z$.

• If $j_2$ dominates $j_1$: Given $y$ is dominated by the left successor of $j_2$ and $x$ is also dominated by the left successor of $j_2$, this leads to the conclusion that $x$ is left of $z$.

Therefore, we can conclude that if $x$ is left of $y$ and $y$ is left of $z$ in a dyadic tree $\mathcal{T}$, then $x$ is indeed left of $z$.