How do we mathematically define the meaning of the word "undecidable"?

Question

I need to understand the meaning of this mathematical concept: "undecided/undecidable".

I know what it means in the English dictionary. But, I don't know what it means mathematically.

If You answer this question with possible mathematical examples, it will be very helpful to understand this issue.

Thank you very much!

Answer 1

Saying that a statement is "undecidable" means that there can be no proof, even theoretically, that the true nor can there be a proof that it is false.

Answer 2

If a proposition $p$ can be stated in the language of a theory $T$, we say $p$ is undecidable in $T$ if $T$ contains neither a proof nor a disproof of $p$.

Answer 3

Given a set of axioms, a statement is undecidable if neither it nor its negation follow from the axioms.

Example: If your only axiom is: $$ \forall z \forall x \forall y \ (y=x) \vee(y=z)\vee (x=z) $$ (in English, "for any three things, two of them are equal")

then it is undecidable whether

$$ \forall x \forall y (x=y) $$ (English, "there is only one thing.")

By contrast, it is decidable (and false) that $$ \exists x \exists y \exists z (x \neq y) \wedge (x\neq z) \wedge (y\neq z). $$ (English, "there exist three distinct things.")

Answer 4

A statement $P$ is undecidable in an theory $T$ if $t \cup \{P\}$ and $t \cup \{\neg P\}$ are both consistent. In practice, it's usually used more broadly: $P$ is undecidable in $T$ if $T \cup\{P\}$ and $T\cup\{\neg P\}$ are equiconsistent, becuase Gödel's Second Incompleteness Theorem is annoying that way: specifically, for most systems that we're interested in, we can't prove that the system is consistent (or, more precisely, we can't prove it in that system unless the system is inconsistent). Thus, rather than requiring two systems to be consistent (which we can't prove), we instead require that at least there's no consistency reason to prefer one over the other.

Answer 5

Suppose you have some logical system $S$ equipped with some initial axioms and some process for generating statements from previous statements. Suppose you have a set $T$ of statements such that each statement is either an axiom in $S$, or can be derived from other statements in $T$ using the process given by $S$ for generating statements (note that $T$ is a recursively defined set, in that each statement in $T$ is either an axiom, or a statement that can be derived from axioms, or a statement that can be derived from statements that can be derived from axioms, etc.) A statement is undecidable in $S$ if neither the statement nor its negation is in $T$.

Note that undecidability is a property of a statement and a logical system. A statement might be decidable in one logical system, but undecidable in another. For example, the Axiom of Choice is undecidable in Zermelo–Fraenkel set theory, but is taken as an axiom in ZFC (that is what the C stands for), and thus is decidable in ZFC.