army1987 comments on Godel's Completeness and Incompleteness Theorems - Less Wrong

34 Post author: Eliezer_Yudkowsky 25 December 2012 01:16AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (85)
Tags: math proofs logic numbers meaning seq_epistemology

Comments (85)

You are viewing a single comment's thread. Show more comments above.

Comment author: [deleted] 25 December 2012 11:48:53AM *  6 points [-]

a) I'm a little confused by the discussion of Cantor's argument. As I understand it, the argument is valid in first-order logic, it's just that the conclusion may have different semantics in different models. That is, the statement "the set X is uncountable" is cashed out in terms of set theory, and so if you have a non-standard model of set theory, then that statement may have non-standard sematics.

More clearly -- "X is uncountable" means "there is no bijection between X and a subset of N", but "there" stilll means "within the given model".

Comment author: bryjnar 25 December 2012 02:12:43PM 0 points [-]

Exactly (I'm assuming by subset you mean non-strict subset). Crucially, a non-standard model may not have all the bijections you'd expect it to, which is where EY comes at it from.

Comment author: [deleted] 25 December 2012 04:21:06PM 2 points [-]

I'm assuming by subset you mean non-strict subset

I was, but that's not necessary -- a countably infinite set can be bijectively mapped onto {2, 3, 4, ...} which is a proper subset of N after all! ;-)

Comment author: bryjnar 25 December 2012 09:56:50PM 0 points [-]

Oh yeah - brain fail ;)

Powered by Reddit Powered by Reddit