Hacker News Reader

Comment by abjKT26nO8 | Hacker News Reader

That's not what Gödel's first theorem says. What Gödel's theorem tells us about linear algebra is that either it's inconsistent, or there are statements which are true for some models of linear algebra, but false for others.

In fact, we do know that any statement in linear algebra that is true[1], is provable. That's because vector spaces are first-order structures, so that's covered by Godel's completeness theorem[2].

[1]: I.e. it's true for all models of linear algebra.

[2]: https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_th...

View on HN

What about the moral matrix problem? Given a finite set of matrices with integer entries, determine if you can multiply them in some order, possibly with repetition, to get the zero matrix. It's proven undecidable for "a set of six or more 3 × 3 matrices, or a set of two 15 × 15 matrices" at least according to wikipedia. https://en.wikipedia.org/wiki/List_of_undecidable_problems . Is that because it incorporates the integers or something?

To say that a statement is undecidable relative to a set of axioms is to say that this set of axioms is satisfied by several structures and this statement is true for some of them, but false for some others. The structures which satisfy a set of axioms are called models of this set of axioms.

The whole deal with undecidable statements in mathematics is that in our language we make the illusion that there is only one structure deserving of the name "natural numbers", but "natural numbers" are defined by a set of axioms. What Gödel proved is that, when a set of axioms (and the language that is used) is powerful enough, then this set of axioms is either inconsistent (i.e. it has no model), or there are multiple models and there exist statements in the language which are true in some models, but not in others; so you could say that the "truth status" of these statements isn't decided by the set of axioms.

EDIT: Related issue: given a class of structures, in general it may not be possible to write down a set of axioms for which this class of structures will be the class of all models of this set of axioms. An example of that in first-order logic is well-ordered sets. You need second-order logic for that (i.e. you need to be able to quantify over subsets, instead of just elements of universum).

So the way I think about all that is that sets of axioms are inherently imprecise. When you add another axiom, in order to restrict yourself to a smaller number of structures, you always jump over several of them. You're never able to throw out just one.

OK, so the general idea of OPs comment is true, that we have statements about linear algebra for which (in ZFC) we can neither prove nor disprove, like the mortal matrix problem, correct? It's just that his wording was inexact?

It's true that -we have statements about linear algebra for which (in ZFC) we can neither prove nor disprove-[1]. However, given that these statements simply aren't true, it doesn't tell us much: it's not that we can't know everything there is to know about linear algebra. It's that these things we can't know about linear algebra aren't facts about linear algebra to start with.

[1]: On a second thought, let me rephrase that: we have statements about structures partially described by linear algebra which (in ZFC) we can neither prove nor disprove for all of them at the same time.

You’ve given excellent explanations on this topic. It’s rare that someone writes about the meaning of the Incompleteness theorems correctly.

I think it’s worth pointing out or adding that when talking about The Natural Numbers most people are implicitly talking about the standard model with the first order Peano axioms. There are statements in this model that are true (have no counterexample) but which can’t be proven by this set of axioms.

I think many people making claims like,

“There are true statements about The Natural Numbers that aren’t provable.”

don’t realize exactly the nuances you’ve pointed out. Assuming The Natural Numbers are consistent then all true statements are provable in some axiom system. Just take the collection of all true statements as the axiom system. Now every true statement is trivially provable.

I hope what I’ve written doesn’t muddy your excellent explanations!

Thank you.

> Assuming The Natural Numbers are consistent then all true statements are provable in some axiom system. Just take the collection of all true statements as the axiom system. Now every true statement is trivially provable.

That axiom system wouldn't be particularly useful to humans though. When we talk about sets of axioms, we almost always talk about finite sets of axioms. This is what makes them useful to us, allows us to use them for describing things.

But you do have the right intuition here. The next step is using the compactness theorem[1].

[1]: https://en.wikipedia.org/wiki/Compactness_theorem

It doesn’t have to be a finite set of axioms just recursively enumerable. The first order Peano axioms are not finite in number. One of them is an axiom schema. (I believe.)

You are correct.

Hey thanks for clarifying. Do you have any good resources to further my intuition? It's clearly incomplete.

You're welcome.

My understanding of the subject is based on a course in mathematical logic which I took at a university. According to the lecturer, there are no good books on the subject. There was one book they referenced, but it was fat and unapproachable. So, unfortunately, I can't really give any recommendations.

Reply on news.ycombinator.com