Decidability and Completeness or the reverse...

[fringe marlin]

I got the idea and I know examples of it too
the theory of algebraically closed fields of characteristic 0..

I just want to know a generalized proof rather case specific proof. Tb specific about how I can show that All complete system is decidable but not all decidable system is a complete one.... Any rigorous proof is also welcome but I want it to be in a convenient way from the first principle (if it's possible) and please help me to understand it bcz I'm not a math major... 🤧 Thank you in advance...

[fringe marlin]

Hello peeps! Nobody?🤐

[late sage]

Could you state your question more explicitly ?

[fringe marlin]

I need a proof , All complete system are not necessarily be decidable and all decidable system (Theory/set) not necessarily be complete (Theory/set) one...It's a statement that a system about completeness and decidability.

Either way u can just proof a general example of an incomplete but a decidable system or set.... One of them is very well known the theory of algebraically closed fields of characteristic 0. This theory is decidable, meaning there exists an algorithm to determine whether a sentence is provable within it, but incomplete, meaning there are statements in the language that are neither provable nor disprovable within the theory. ....

I need an generalised not just any special example that this theory holds that... I need u to show it by forming an example... mathematical logic or set theory whatever u please

[rose badger]

What is a "decidable system"?

I know problems can be decidable or not.

[stiff estuary]

#computer-science message

they defined decidability as the problem of provability being decidable in an earlier related conversation

[fringe marlin]

I'm talking about mathematical logic

To prove that a decidable incomplete theory can exist I just need a proof using mathematical logic in a simple way, not any preassumed example

It's basically related to the computability theory

[fringe marlin]

A theory/system is decidable if there exists an effective procedure (algorithm) that can determine whether any given sentence is a theorem of the theory.

[rose badger]

...so then if every theorem has a proof?

[fringe marlin]

any sentence, you can always determine whether it is provable within the system, either through a finite number of steps or by recognizing that it's not provable.

That's decidability

[rose badger]

In finite time, or?

[fringe marlin]

A system/theory is complete if you can either proof it's negation or the statement

[rose badger]

No. A theory is complete if and only if every statement which is true in the theory is provable in the theory.

[fringe marlin]

Finite steps is better way to say I guess

[rose badger]

By definition, a theorem is provable in finite (nondeterministic) time, because a theorem is by definition provable by a finite sequence of applications of the axioms.

[fringe marlin]

It's the same thing... U can prove a statement by defining proving it's negation is wrong, the induction method suppose... So proving a statement or is negation is same

[rose badger]

No, it's not the same, because there may be statements which are neither true nor false in the theory.

[fringe marlin]

That's incomplete

That's what I'm saying

[rose badger]

No it isn't.

[fringe marlin]

The system is incomplete for that theory

[rose badger]

Okay, if you're not referring to Godel completeness here, don't use the word "completeness", it's confusing.

[fringe marlin]

No it's not completeness and Godel completeness is the extention of completeness principle in computability theory

[rose badger]

...what?

[fringe marlin]

Yes Completeness and Godels completeness are not the same

That's what I'm saying

[rose badger]

Then don't use the word "completeness".

[fringe marlin]

But it is completeness what else should I say🫠

Godel's completeness is a special kind of completeness principle he defined

It's also a completeness