Talk:Craig's theorem

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Low	This article has been rated as Low-priority on the project's priority scale.

Philosophy: Logic Low‑importance

This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy

Low

This article has been rated as Low-importance on the project's importance scale.

Associated task forces:
/
	Logic

Motivation and explanation

The lead para says:

Craig's theorem states that any recursively enumerable set of well-formed formulas of a first-order language is (primitively) recursively axiomatizable.

Now, this is so replete with jargon, that a general reader will not grasp why this theorem matters, or even what it's about. Mathematically, it's admirably succinct. And the jargon has appropriate wikilinks. But for a general intro, we need to at least introduce these notions right here, without sending the reader off into the wilderness, chasing the meanings of four different expressions.

If I can make time to do this, I will, but please don't wait for that to happen! yoyo (talk) 02:13, 13 July 2018 (UTC)[reply]

Computability of this process?

It seems like the process to turn T into T* can't be done computably, right? In other words, if I'm given a machine which enumerates the axioms A_n of T, this shouldn't be able to be turned into a machine which checks if a candidate C is in T, *despite* the fact that we can build both a machine that enumerates the axioms of T*, *and* a machine which checks if a candidate C is in T*.

If this is correct, I'd like to include in the article a sentence emphasizing that even though T is equivalent to a computable set this doesn't at all help the tractability of T. Purplehat7 (talk) 21:50, 29 June 2025 (UTC)[reply]