2
$\begingroup$

Let $T$ be a single directed tree, by parameters $(\kappa, \lambda, \zeta)$ of $T$ we mean: the number of root nodes in $T$, the strict upper bound on the number of children nodes per a node in $T$, the strict upper bound on the level of a node in $T$ respectively.

Would ZFC be interpreted in a Graph theory that stipulates the existence of any directed tree with parameters $(1, \operatorname{icc}, \omega)$, where $\operatorname {icc}$ stands for the first weakly inaccessible cardinal.

By a Graph theory I mean a first order theory about graphs, i.e. a theory that extends FOL+Equality with the primitive notions of node and arrow and set membership, and axiomatize Extensionality over sets, and unrestricted construction of sets of nodes and arrows, and restricts sets to only those of nodes and arrows. For simplicity a node cannot be an arrow. Of course by an arrow here it is mean a "directional" edge, and for any two nodes there exists an arrow stemming from one of them to the other in each direction, also no arrow can take the role of a node, so no arrow can link arrows or an arrow and a node.

$\endgroup$
2
  • $\begingroup$ Did you mean to ask if it can be interpreted in the theory of the structure given by (1, icc, w)? I mean, it doesn't really make sense to say "stipulates the existence of any directed tree" you just need some kinds of comprehension/existence principles if your language is really just the language of graph theory plus those few extras you mentioned. OTOH, if you add constants for each element in those graphs and take theory of that structure I think the answer will be yes. $\endgroup$ Commented May 11, 2022 at 7:41
  • 1
    $\begingroup$ @PeterGerdes, I agree. I think it better be written as there exists a directed tree with parameters $(1, \text{icc}, \omega)$, and the rest would be guranteed by the remaining axioms. $\endgroup$ Commented May 12, 2022 at 18:58

1 Answer 1

3
$\begingroup$

The details of your graph theory will matter - how, for example, are you going to experess "$(1,\mathsf{icc}, \omega)$" in your setting? - but certainly some version of this will work: in a (well-founded) model $M$ of $\mathsf{ZFC}$ there's a natural way to code sets by well-founded trees, and so a "rich enough" theory of trees will interpret $\mathsf{ZFC}$.

This coding idea (if not the specific interpretability fact you're asking about) actually gets used from time to time in purely technical ways, e.g. the coding of elements of $L_{\omega_1^L}$ by reals definably in $L_{\omega_1^L}$ (see the beginning of Sacks' Higher recursion theory).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .