Comment author: cousin_it 19 January 2012 05:56:19PM *  0 points [-]

We don't seem to understand each other yet :-(

If I understand correctly, you are saying that higher order logic cannot prove all theorems about the integers that ZFC can.

The argument wasn't specific to ZFC or HOL, it was intended to apply to any system that can have a proof checker.

Actually, I've never heard of the standard integers -- do you mean a unique standard model of the integers?

Sorry, I screwed up the wording there, meant to say simply "unique model of the integers". People often talk about "standard integers" and "nonstandard integers" within models of a first-order axiom system, like PA or ZFC, hence my screwup. "Standard model" seems to be an unrelated concept.

I've never heard it claimed that second-order logic has a unique model of the standard integers.

The original post says something like that, search for "we know that we have only one (full) model".

Comment author: Darmani 19 January 2012 11:22:52PM 0 points [-]

The argument wasn't specific to ZFC or HOL, it was intended to apply to any system that can have a proof checker.

Pointing out the Gödelian limitations of all systems with recursively enumerable axioms doesn't seem like much of criticism of the system of nth-order logic I mentioned. Now I have less of an idea of what you're trying to say.

By the way, I think he's using "full model" to mean "standard model." Presumably, the standard integers are the standard model that satisfies the Peano axioms, while nonstandard integers are any other satisfying model (see http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic ).

Comment author: cousin_it 18 January 2012 02:41:16PM *  2 points [-]

The comprehension axiom schema (or any other construction that can be used by a proof checker algorithm) isn't enough to prove all the statements people consider to be inescapable consequences of second-order logic. You can view the system you described as a many-sorted first-order theory with sets as one of the sorts, and notice that it cannot prove its own consistency (which can be rephrased as a statement about the integers, or about a certain Turing machine not halting) for the usual Goedelian reasons. But we humans can imagine that the integers exist as "hunks of Platoplasm" somewhere within math, so the consistency statement feels obviously true to us.

It's hard to say whether our intuitions are justified. But one thing we do know, provably, irrevocably and forever, is that being able to implement a proof checker algorithm precludes you from ever getting the claimed benefits of second-order logic, like having a unique model of the standard integers. Anyone who claims to transcend the reach of first-order logic in a way that's relevant to AI is either deluding themselves, or has made a big breakthrough that I'd love to know about.

Comment author: Darmani 19 January 2012 04:55:44PM *  0 points [-]

If I understand correctly, you are saying that higher order logic cannot prove all theorems about the integers that ZFC can. That's a very uninteresting statement. Since higher order logic was proven consistent* with ZFC, it is strictly weaker. Second order logic, is, of course, strictly weaker than 4th order logic, which is strictly weaker than 6th order logic, and so on, and is thus much weaker than higher-order logic.

I've never heard it claimed that second-order logic has a unique model of the standard integers. Actually, I've never heard of the standard integers -- do you mean a unique standard model of the integers? I hope not, as we actually can get a unique standard model of the integers in a system with machine-checkable proofs. See "To Truth Through Proof" by Peter Andrews. It's omitted in the Google Books preview, but I believe the proof is on page 327; i lent out my copy and cannot check. (It, naturally, does not have a unique general model, so this not of huge practical significance.)

* I have not actually read that, and should not really say that. However, type theory with an axiom of infinity, which is strictly stronger than type theory without an axiom of infinity, which can express all statements of higher-order logic, has been proven consistent. Also, any proof in higher order logic can be trivially converted into a proof of nth-order logic for some n, which can be shown consistent in (n+2)th-order logic.

Comment author: Sniffnoy 16 January 2012 10:38:10PM 7 points [-]

Hold on a minute. What does it even mean to speak of proving something in second-order logic? First order has various deduction systems for it, which we usually don't bother to mention by name because they're all equivalent. How does one actually perform deductions in proofs in second-order logic? I was under the impression that second-order logic was purely descriptive (i.e. a language to write precise statements which then may judged true or false) and did not allow for deduction. After all, to perform deductions about sets, one will need some sort of theory of how the sets work, no? And then you may as well just do set theory -- which is after all how we generally do things...

Comment author: Darmani 17 January 2012 03:22:51AM *  7 points [-]

Proofs in second-order logic work the exact same way as proofs in first-order logic: You prove a sentence by beginning with axioms, and construct the sentence using inference rules. In first-order logic, you have individuals, functions (from individuals to individuals), terms, and predicates (loosely speaking, functions from individuals to truth values), but may only quantify over individuals. In second-order logic, you may also quantify over predicates and functions. In third-order logic, you add functions of functions of individuals, and, in fourth-order logic, the ability to quantify over them. This continues all the way up to omega-eth order logic (a.k.a.: higher-order logic), where you may use functions of arbitrary orders. The axioms and inference rules are the same as in first-order logic.

Wait, I said nothing about sets above. Sets are no problem: a set containing certain elements is equivalent to a predicate which only returns true on those elements.

I also lied about it being the same as first-order logic -- a couple are added. One very useful axiom scheme is comprehension, which roughly means that you can find a predicate equivalent to any formula. You can think of this as being an axiom schema of first-order logic, except that, since it cannot be stated until fourth-order logic, it contains no axioms in first-order logic.

(My formal logic training is primarily in Church's theory of types, which is very similar to higher-order logic [though superficially extremely different]. I probably mixed-up terminology somewhere in the above.)

In response to [Link] Duolingo
Comment author: Darmani 05 January 2012 09:41:39PM *  2 points [-]

I used Duolingo for a few hours on its first day. (I used to TA for Luis, which helps for getting private invites, at least by knowing to sign up immediately.)

I've basically just gone through passing out of German lessons. This basically consists of taking a 20 question test, in which I translate sentences like "The woman drinks with her cat." and pray I don't make typos on three questions and have to start over. Except that all too often I give correct translations, but their checker isn't attuned to the flexibilities of German word ordering, or I use a different word for "chair." They said they'd teach it the distinction between "essen" ("to eat" for humans) and "fressen" ("to eat" for animals) so that their quizzes would stop recommending wrong answers, but I'm skeptical. I did another one just now, and it now seems to accept answers off by one character. I noticed this in a listening exercise not because I made a typo, but because the word for "is" is approximately homonymous with the word for "eats."

Oh, apparently Duolingo has something to do with translating the web, rather than just going through a bunch of German 1-level exercises. Maybe I have to repeat the above for the remaining 45 lessons before I see an option to do that.

Comment author: Solvent 30 December 2011 10:01:07AM 5 points [-]

I looked into the Thiel scholarship, being age eligible. The problem is, it's so ridiculously competitive. I did fairly well in school, and certainly got in the top 1% of grades, as well as attending the NYSF. However, I look at the kind of people who won the Thiel fellowship and kind of wither. They're way out of my league. If LessWrong had many teenagers like that around, I suspect we would have heard of them by now.

Comment author: Darmani 30 December 2011 11:34:39PM 1 point [-]

I think a lot of people get put off because Andrew Hsu is first in the alphabet. A lot of them barely come up in Google searches (save for the Fellowship itself).

In response to 2011 Survey Results
Comment author: gwern 04 December 2011 09:35:41PM 13 points [-]

The other 72.3% of people who had to find Less Wrong the hard way. 121 people (11.1%) were referred by a friend, 259 people (23.8%) were referred by blogs, 196 people (18%) were referred by Harry Potter and the Methods of Rationality, 96 people (8.8%) were referred by a search engine, and only one person (.1%) was referred by a class in school.

Of the 259 people referred by blogs, 134 told me which blog referred them. There was a very long tail here, with most blogs only referring one or two people, but the overwhelming winner was Common Sense Atheism, which is responsible for 18 current Less Wrong readers. Other important blogs and sites include Hacker News (11 people), Marginal Revolution (6 people), TV Tropes (5 people), and a three way tie for fifth between Reddit, SebastianMarshall.com, and You Are Not So Smart (3 people).

I've long been interested in whether Eliezer's fanfiction is an effective strategy, since it's so attention-getting (when Eliezer popped up in The New Yorker recently, pretty much his whole blurb was a description of MoR).

Of the listed strategies, only 'blogs' was greater than MoR. The long tail is particularly worrisome to me: LW/OB have frequently been linked in or submitted to Reddit and Hacker News, but those two account for only 14 people? Admittedly, weak SEO in the sense of submitting links to social news sites is a lot less time intensive than writing 1200 page Harry Potter fanfics and Louie has been complaining about us not doing even that, but still, the numbers look to be in MoR's favor.

In response to comment by gwern on 2011 Survey Results
Comment author: Darmani 05 December 2011 03:39:07AM 5 points [-]

Keep in mind that many of these links were a long time ago. I came here from Overcoming Bias, but I came to Overcoming Bias from Hacker News.

Comment author: Darmani 27 November 2011 06:13:46AM 2 points [-]

For a lot of subjects, it's hard to beat school. You need constant feedback to improve in most areas, and good feedback is hard to come by without paying. I would recommend against trying to learn how to write a proof without a teacher as much as I would against learning piano. (I've tried both.)

I've been taught more things than I've learned on my own, but of the things I've learned poorly, most where things I learned on my own.

Comment author: Darmani 27 November 2011 06:41:22AM 0 points [-]

Looking at your other posts, it sounds like high school has tainted your opinion of schooling in general. However, college is Hard. A lot of people from my school make big bucks and find the rest of life extremely easy in comparison.

Comment author: Curiouskid 27 November 2011 01:36:12AM 2 points [-]

Why are so few people interested in applying for the Thiel scholarshp? I feel that it's obviously more educational than going to school. Are you so afraid of not getting it that you don't bother applying?

Comment author: Darmani 27 November 2011 06:13:46AM 2 points [-]

For a lot of subjects, it's hard to beat school. You need constant feedback to improve in most areas, and good feedback is hard to come by without paying. I would recommend against trying to learn how to write a proof without a teacher as much as I would against learning piano. (I've tried both.)

I've been taught more things than I've learned on my own, but of the things I've learned poorly, most where things I learned on my own.

Raytheon to Develop Rationality-Training Games

15 Darmani 18 November 2011 09:07PM

Meetup : Pittsburgh Meetup

1 Darmani 30 September 2011 05:48PM

Discussion article for the meetup : Pittsburgh Meetup

WHEN: 05 October 2011 05:45:00PM (-0400)

WHERE: 151 N Craig St, Apt 7C

This will be hopefully the first of many bi-weekly meetups in Pittsburgh.

We will do a few simple surprise activities, present some of the stuff the hosts learned at the LW minicamp earlier this year, and then open it up for a discussion of what we all want to schedule for this year.

Also, there will be free snacks and drinks! Afterwards, we're going to go out to dinner and everyone is welcome to tag along. If you can't come exactly at the start, that's fine, you will be able to jump right in anyway.

We'll be hosting it at Josh Albrecht's apartment (which is comfortably large enough for 10 to 15 people). The address is 151 N Craig St, Apt 7C. Call his cell phone when you get here if you cant get in (585 506 6900).

Discussion article for the meetup : Pittsburgh Meetup

View more: Prev | Next