Expressive power of digraph solvability
axiom of choicecompletenessdagdigraphinfinitary propositional logickernelmany-one reductionreverse mathematicsset theory
Classical propositional logic (03B05) Foundations of classical theories (including reverse mathematics) (03B30) Other degrees and reducibilities in computability and recursion theory (03D30) Axiom of choice and related propositions (03E25) Second- and higher-order arithmetic and fragments (03F35) Infinite graphs (05C63)
A directed graph (digraph) is said to be solvable if it has a kernel. A kernel is an independent set of vertices \(K\) such that for every vertex \(v\) not in \(K\) there is an edge from \(v\) to some vertex of \(K\). An overview of kernel theory can be found in the work of \textit{E. Boros} and \textit{V. Gurvich} [Discrete Math. 306, No. 19--20, 2336--2354 (2006; Zbl 1103.05034)]. Solvability of digraphs is related to solvability of systems of Boolean equations. Consequently, the solvability problem for digraphs is closely related to satisfiability in both finite and infinitary propositional logic theories. Capitalizing on this connection, the authors prove that the solvability problem for digraphs is \(\Sigma^1_1\)-complete, and then conclude that the consistency of PL\(^\omega\)-theories is also \(\Sigma^1_1\)-complete. Applying the methods of reverse mathematics, they prove that the solvability of countable, finitely bounded, acyclic digraphs is equivalent to WKL\(_0\) over RCA\(_0\). The authors note that in [``Kernel tower theory. I, FOM 407 (email list) (2010), \url{http://cs.nyu.edu/pipermail/fom/2010-March/014507.html}] \textit{H. Friedman} states that solvability of well-founded dags is equivalent to ATR\(_0\) over RCA\(_0\). Turning to set theory, they show that ZF proves that every tree is solvable, and that weak forms of AC prove that forests are solvable. The paper concludes with a proof that over ZF, full AC is equivalent to the solvability of disjoint unions of indexed families of solvable digraphs.
- Graphes Noyau-Parfaits
- scientific article; zbMATH DE number 1201510 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3106184 (Why is no real title available?)
- On a Theorem of Richardson
- On directed graphs with an independent covering set
- On kernels and semikernels of digraphs
- On kernels in strongly connected graphs
- Paradox without Self-Reference
- Patterns of paradox
- Perfect graphs, kernels, and cores of cooperative games
- Solutions of irreflexive relations
- Subsystems of second order arithmetic
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
- Kernels of digraphs with finitely many ends
- On the existence of 3- and 4-kernels in digraphs
- On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
- Quasi-transitive digraphs and their extensions
- Finding kernels or solving SAT
- Kernels in digraphs that are not kernel perfect
- Propositional discourse logic
- Resolving infinitary paradoxes
- The elimination of direct self-reference
- A study on token digraphs
- Compositions of digraphs: a survey
- The theorem of Richardson and its generalizations: a survey
This page was built for publication: Expressive power of digraph solvability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409316)
