7 ms·

To your last question, Godel's incompleteness theorem prevents use from proving everything about linear algebra. So there might be surprising statements that a

To your last question, Godel's incompleteness theorem prevents use from proving everything about linear algebra. So there might be surprising statements that are true but can never be proved to be true given the axioms.

contravariant 6y ago
Be careful with your phrasing there. The axioms for the real numbers [1] are complete and consistent (within ZFC). Hence I'm almost sure the axioms for each of the finite dimensional vector spaces will also be complete and consistent. Part of the reason is that you can't define the integers within the context of the real numbers. [1]: https://math.stackexchange.com/questions/362837/are-real-numbers-axioms-a-consistent-or-complete-system https://math.stackexchange.com/questions/362837/are-real-num...
abjKT26nO8 6y ago
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_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_th...
- openasocket 6y ago
  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 https://en.wikipedia.org/wiki/List_of_undecidable_problems . Is that because it incorporates the integers or something?
  - abjKT26nO8 6y ago
    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.
    - openasocket 6y ago
      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?
      - abjKT26nO8 6y ago
        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.

contravariant 6y ago

Be careful with your phrasing there. The axioms for the real numbers [1] are complete and consistent (within ZFC). Hence I'm almost sure the axioms for each of the finite dimensional vector spaces will also be complete and consistent. Part of the reason is that you can't define the integers within the context of the real numbers. [1]: https://math.stackexchange.com/questions/362837/are-real-numbers-axioms-a-consistent-or-complete-system https://math.stackexchange.com/questions/362837/are-real-num...

abjKT26nO8 6y ago

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_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_th...

openasocket 6y ago
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 https://en.wikipedia.org/wiki/List_of_undecidable_problems . Is that because it incorporates the integers or something?
- abjKT26nO8 6y ago
  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.
  - openasocket 6y ago
    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?
    - abjKT26nO8 6y ago
      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.