Hacker News Reader

Comment by statictype | Hacker News Reader

While we're on the topic, something that always puzzled me: doesn't Gödel's theorem apply only to 'non-trivial' axiomatic systems?

Meaning you could come up with a trivial system to which it doesn't apply. Which begs the question: How do you define triviality here?

View on HN

Trivial in this context means a system that's not powerful enough to express basic arithmetic.

This includes some surprisingly complicated systems, like real (as opposed to integer) arithmetic.

Bonus pedantipoint: it's not begging the question - that actually means 'to assume X in your proof of X'. It's just raising the question.

Following the derail a little further...while you got my vote for the pedantipoint, the misuse of "beg the question" is so pervasive that I've given up. It means what people use it to mean, now. We probably need a new name for the logical fallacy, unless lumping it into circular reasoning is sufficient.

English is my second language, and until a few years ago I wasn't even aware of the original usage, while I'd seen the "misuse" on a regular basis.

I don't think I've actually ever seen it used in the original usage "in the wild", as opposed to in the posts of pedants complaining about people using it wrongly.

I once told people the correct definition of "begs", and they refused to believe me, and thought I was wrong. To them begs means: raises a very obvious question.

So it's over, "begs" has a new meaning, and complaining about it is pointless.

It's because the original usage is rather technical--I've only seen philosophers use it, and only then as the adjective "question-begging".

This includes some surprisingly complicated systems, like real (as opposed to integer) arithmetic.

Real arithmetic is not enough to express integer arithmetic?

I suppose it all boils down to how you define "arithmetic", but what is it that the integers have that the reals lack under the relevant definition? I would think that real arithmetic by any reasonable definition would give you enough tools to check whether a number was an integer, and in that case, doesn't it necessarily contain integer arithmetic as a subset?

Cribbing from this book:

http://books.google.com/books?id=71pK8Zz9Dd8C&printsec=f...

"Since the natural numbers form a subset of the real numbers, it may seem odd that the theory of real numbers can be complete when the theory of the natural numbers is incomplete. The incompleteness of the theory of the natural numbers does not carry over to the theory of the real numbers because even though every natural number is also a real number, we cannot define the natural numbers as a subset of the real numbers [...]

How would we ordinarily define the natural numbers as a subset of the real numbers? The real numbers 0 and 1 can be identified with the corresponding natural numbers, and using addition of real numbers we get the natural numbers as the subset of the real numbers containing 0, 1, 1+1, 1+1+1, and so on. However, this "and so on" cannot be expressed in the language of the theory of real numbers [because it requires the notion of sets, a second-order concept outside of the theory]."

Your reasoning is correct, so it means that integers are not definable inside "real arithmetic".

http://en.wikipedia.org/wiki/Real-closed_field

If you don't believe this, try writing down a formula in the language of this theory that says "x is an integer".

Ultimately, the issue is that the first-order theory of real closed fields contains no axiom approaching the induction scheme of PA in power.

The system need be no more complex than first-order Peano arithmetic, which is the Peano axioms (reflexivity, transitivity, succession, etc.) combined with the concept of induction.

Well, leave out succession and you get the reals, which are still complex enough (no pun intended) to offer hours of fun.

To construct the Gödel number (a part of the proof) requires use of an arithmetic that can express addition and multiplication. If any one of them is missing, the system can be shown to be complete.

Been a while since I studied it, but I thought induction was the key ingredient.

Reply on news.ycombinator.com