Any non-recursive definitions for a binary tree?

Question

Edit: Is it possible to non-recursively define a (possibly infinite) binary tree? Here is my attempt with partial functions $L$ and $R$ on the set of natural numbers $N$ with nodes numbered by $N$

1. $\forall x,y:[L(x)=y \implies x,y\in N]$
2. $\forall x,y\in N: [L(x)=L(y) \implies x=y]$
3. $\forall x,y:[R(x)=y \implies x,y\in N]$
4. $\forall x,y\in N: [R(x)=R(y) \implies x=y]$
5. $n\in N$

6. $\forall x\in N: [L(x)\neq n \land R(x)\neq n]$

7. $\forall x,y\in N: [L(x)=y => \forall z\in N: R(z)\neq y]\space\space$ (Edit)

8. $\forall x,y\in N: [R(x)=y => \forall z\in N: L(z)\neq y]\space\space$ (Edit)

where

$L(x)=y$ means $y$ is the left child of node $x$

$R(x)=y$ means $y$ is the right child of node $x$

$n$ is the root node

Answer 1

No, these axioms are far too weak. For instance, you could have $N=\{n,a,b\}$ where $a=L(b)$ and $b=L(a)$.

Note that more generally, it will be impossible to give any first-order axiomatization of binary trees over the language $\{L,R,n\}$. The statement that every element is obtained from $n$ by finitely many applications of $L$ and $R$ cannot be expressed in first-order logic (e.g., by compactness).

Answer 2

How about we don't have $N$ be the natural numbers, and we consider $R(x) = n$ to mean $x$ has no right child, and $L(x) = n$ to be $x$ has no left child, and $n$ is the root of the tree. These axioms do allow for infinite trees however I think it captures everything else. Realize when I say $\forall x$ and $\exists x$ I really mean $\forall x \in N$ and $\exists x \in N$.

• $n \in N$
  • This insists the tree is not empty, and contains a root, $n$.
• $\forall x,y[(R(x) = R(y) \land R(x) \not=n )\implies x=y ]$
  • From this every $x\in N$ with a right child is the only element of $N$ with that right child.
• $\forall x,y[(L(x) = L(y) \land L(x) \not=n )\implies x=y ]$
  • From this every $x\in N$ with a left child is the only element of $N$ with that left child.
• $\forall x[x\not=n \implies (\exists y[R(y) = x] \iff \lnot\exists y[L(y)=x])$
  • From this every $x \not=n \in N$, $x$ is either a right child of some node, or a left child of some node, but not both.

This does allow for infinite binary trees, but does not require trees be infinite.