A new paper (pdf) by Wang et al. shows that selection in homo sapiens has continued even after the Out-of-Africa expansions which resulted in racial diversification. The researchers have found regional selection for about 1,800 genes, the bulk of which fall into the following categories: those having to do with pathogen response, cell cycle, neuronal function, reproduction, DNA metabolism, and protein metabolism. See the entries and comments at GNXP, Dienekes, John Hawks, and iSteve for more detail.

I'll emphasize a point Steve Sailer raised, which is that this is contra the assumption in Evolutionary Psychology (TM) that selection worked its stuff while our species was located in Africa, and more or less froze us in that state before various groups left, since natural selection hasn't had "enough time" to work on our brain within the ~50,000 years since. Most cultural differences are assumed to reflect differences in the local ecology -- that is, we're all born with mostly the same cognitive architecture, but depending on how this interacts during our lifetime with salient features of the environment, some groups could show a psychological or behavioral difference from others. For example, many in the modernized West take our personal safety largely for granted because we have laws, police forces, and courts. Were we to be thrown into a hunter-gatherer society, we would take nothing for granted about our safety and would show roughly the same level of violence as the members of our adoptive society, as we learned what worked to keep us alive. In sum, the same human mind shared by all humans reacts in different ways depending on the environment it finds itself in.

However, as is the problem with Jared Diamond's Guns, Germs, and Steel, the more one emphasizes long-lasting differences in the local ecology, the more they are implicitly arguing that the populations occupying these areas over time face different selection pressures, which would tend to introduce a greater genetic component into explaining why different populations differ, as they became adapted to their region. This is uncontroversial when it comes to the most obvious racial difference: skin color. Whatever the particular genes turn out to be, it's clear that variation in skin color across populations has a large genetic component -- a sub-Saharan African baby born and raised in Finland will still have brownish skin, while a Finn raised in Ughanda will still have whitish skin. While exposure to lots of sun may make a white person a bit more tan than they would have been otherwise, this trait seems to not respond strongly to the here-and-now environment in which the individual finds himself (i.e., strongly enough to make a person dark brown vs pale white). No one alternatively proposes a Super Suntanning Model -- SSM -- whereby our innate endowment has been naturally selected to come in some common default color until it interacts with some environmental feature such as sun exposure (or lack thereof). Note that this SSM is not the blank slate theory -- according to the SSM, the endowment is rich and innate (contra blank slate) but common to all normal humans.

When it comes to the brain, however, the psychological / behavioral equivalent of the SSM is assumed to account for population differences. However, way back in 1993 Steven Gangestad and David Buss published an article, "Pathogen prevalence and human mate preferences" (Ethology and Sociobiology, 14, 89-96), wherein they described how the degree to which nasty pathogens were present in the local ecology strongly correlated with the degree to which the people of that region placed an emphasis on physical attractiveness when selecting a mate, as documented by Buss' seminal 1989 cross-cultural survey of human mate preferences (Ctrl+F BBS). I read both articles on Buss' website as recently as June of 2005, but since then the pathogen pdf has been removed for some reason, and I cannot locate it anywhere else on the web. I have no access to online journals, nor am I about to lay down $30 to read it at sciencedirect. Here's the gist, though. Buss had already examined how much emphasis people in various cultures place on good looks when choosing a mate; each subject rated this from 0 to 3, with 3 being most important, and he took the mean of all subjects in a given culture. G&B then examined the correlation of this average with the prevalence of 6 or so nasty pathogens in the geographical areas studied in mate preferences study -- by nasty I mean something like malaria, whose post-Out-of-Africa pressure has resulted in vast group differences in sickle-cell anemia. The hypothesis was that those in more pathogen-ridden areas would place more emphasis on good looks since they are a reliable cue for good health & immune system, which are more crucial for survival in an area teeming with microscopic bugs ready to eat you up. Here's Buss' summary from another paper which is available online (under 2001, "Human Nature and Culture..."):

G&B "found that cultural variation in the prevalence of pathogens was correlated +.71 with the average cultural importance placed on physical attractiveness in a potential mate, accounting for a virtually unprecedented 50% of the cultural variation (Gangestad & Buss, 1993). Assuming further tests confirm this hypothesis, cultural variation in a psychological variable, in this example, can be traced, in part, to variation in an important hazard of the local ecology" (p. 969; my emphasis).

Aha! So despite the wording here about local hazards and the abstract's claim that "the [universal] human mind contains many complex psychological mechanisms that are selectively activated, depending on cultural contexts" (my emphasis) -- this is actually an instance of the Baldwin Effect, whereby learned behaviors become progressively more "hard-wired," even if not completely so, in order to increase fitness. But as anticipated by Darwin the Second (aka William Hamilton), and as confirmed now by the Wang et al paper, nasty pathogens play a central role in the directions natural selection takes in human beings. Combine this with the great variation in pathogen prevalence between geographical regions plus the Baldwin Effect, and you get psychological group differences with substantial genetic components. As I recall from the G&B paper, the Finns and Zulus face a milder pathogen army and on average don't care much about how their partner looks, whereas the Nigerians and Bulgarians are the reverse. A future test of how hard-wired these psychological differences are would be to survey members of an ethnic group whose ancestral region is high (or low) in pathogens but who were raised in a region with a low (or high) level of pathogens. Would their preferences cluster more closely around the population average of their ancestral or "adoptive" region? Also, what other psychological group differences might trace back partly to the selective pressure of pathogens?

Typo: Buss' 1989 survey used a scale from 0 to 3, not 0 to 4 as I had at first. No change in meaning, though.

## December 22, 2005

## December 13, 2005

### Spanish Girls I

Oddly enough, this post is just for comparison with US girls, but I'll get to the Spanish girls themselves soon. First, I'm 25, and I feel uneasy calling females of my age range "women," as if they already had one foot in the grave. That's one difference with the Spanish (or the French for that matter) -- the females under 50 there prefer being called girls because it emphasizes their youthfulness and femininity. Second, I obviously intend this as a general survey, permitting plenty of exceptions on an absolute level even if not on a percentage-of-the-whole level.

I don't know exactly when it happened, but women of the US on the whole have shifted their mating strategies increasingly toward the short-term. Of all marriages, some 49% end in divorce. People my age on average do not plan to find someone and stay with them for more or less the rest of their life. I won't belabor this too much. What I'd like to point out is one consequence of this -- that women's mate-selection criteria are approaching the limit of a 0-length relationship, namely that of choosing a sperm donor from a catalog.

Imagine yourself in her postion: what do you really want to know about the potential donors? Their height, physical appearance / attractiveness, occupation / status / wealth, IQ / education level, and so on. In other words, you're primarily interested in the aspects that are most influenced by his genetic endowment. The rules of ettiquette, gentlemanly conduct, and so on can be "taught" more than can superior visuo-spatial skills. Even things like fidelity and desire to spend time with children can be compelled from an unwilling man as long as the average woman's criteria make them central, whereas no amount of female emphasis will raise a male's IQ or height during his lifetime.

Sure enough, these strongly heritable traits are the ones US women increasingly rely on. For now, I only mention my own anecdotal data from browsing personals sites both here and abroad, as well as that of other males in my age range and above. (However, in the next post, I'll refer to David Buss' seminal study of global mating preferences, noting differences between the US and Spain.) So I wouldn't want to finely quantify the trend, but I just claim that this is occurring. Sidenote: most people claim that the most important traits to them are touchy-feely things like kindness, warmth, and so on. While true, this doesn't say what their role is in weeding out undesirables. That is, how high must one score on that trait in order to pass through that filter? Must one have the selfless devotion of Mother Teresa to be judged "kind"? No: just as long as you aren't a mean nasty SOB. Must one have the razor-sharp wit of Oscar Wilde to be judged as having a "great sense of humor"? No: so long as you don't stare blankly once told the punchlines of typical jokes. These touchy-feely criteria are there to weed out the worst offenders -- the cruel, the humorless, etc. It's like putting together a sports team: first you cut the flabby and the wimps, then worry later on about finer details like field goal kicking (or good looks in dating).

I have yet to really ask someone out on a date after having returned from Barcelona. Browsing through the various sites, watching popular TV shows on dating, and discussing the issue with others, I have come to the conclusion that -- exceptions aside -- the most likely situation would involve an "interview date" where she would try to size me up much as if she were leafing through a sperm donor catalog. Needless to say, that prospect doesn't exactly excite me -- for one thing, I'm not an ideal donor (only 5'8, not rich nor will be, somewhat introverted). For another thing, even if I were an ideal donor, I'd feel about as great as a large-breasted girl must feel when hooted and hollered at: vaguely flattered but more put off. I want to have fun on a date, not be grilled by her HR rep to see if I'm the male to fill the vacant slot in the corporation of her existence.

Allow me to end with a few examples from the women seeking men section of my local craigslist. (Yes, it may not be totally representative of all women, nor of professional women in all geographical areas, etc. I know: this is just to give an impression.) Title: "5'11 or taller please," in which a self-described "5'6 overweight" woman makes it clear that she doesn't want men who are "5'9 with shoes that make you 5'11 but men who are really that tall." This is almost the entirety of her post. Another: "Calling on Black males under 35 over 6'2." Most posts require something similar but are not so brazen to stick it in the title. Imagine reading through the men seeking women section and noting that most men stated a minimum requirement for breast size or waist-to-hip ratio, with not a few bearing inviting titles like "Double-D Hourglass Latinas wanted" or "No Fat Chicks." You'd think the men were soliciting prostitutes or one-nighters, their verbal disclaimers notwithstanding. Equivalently, I infer that the women are looking for sperm donors rather than stand-up gentlemen in it for the long haul.

Next post: how Spanish girls differ.

I don't know exactly when it happened, but women of the US on the whole have shifted their mating strategies increasingly toward the short-term. Of all marriages, some 49% end in divorce. People my age on average do not plan to find someone and stay with them for more or less the rest of their life. I won't belabor this too much. What I'd like to point out is one consequence of this -- that women's mate-selection criteria are approaching the limit of a 0-length relationship, namely that of choosing a sperm donor from a catalog.

Imagine yourself in her postion: what do you really want to know about the potential donors? Their height, physical appearance / attractiveness, occupation / status / wealth, IQ / education level, and so on. In other words, you're primarily interested in the aspects that are most influenced by his genetic endowment. The rules of ettiquette, gentlemanly conduct, and so on can be "taught" more than can superior visuo-spatial skills. Even things like fidelity and desire to spend time with children can be compelled from an unwilling man as long as the average woman's criteria make them central, whereas no amount of female emphasis will raise a male's IQ or height during his lifetime.

Sure enough, these strongly heritable traits are the ones US women increasingly rely on. For now, I only mention my own anecdotal data from browsing personals sites both here and abroad, as well as that of other males in my age range and above. (However, in the next post, I'll refer to David Buss' seminal study of global mating preferences, noting differences between the US and Spain.) So I wouldn't want to finely quantify the trend, but I just claim that this is occurring. Sidenote: most people claim that the most important traits to them are touchy-feely things like kindness, warmth, and so on. While true, this doesn't say what their role is in weeding out undesirables. That is, how high must one score on that trait in order to pass through that filter? Must one have the selfless devotion of Mother Teresa to be judged "kind"? No: just as long as you aren't a mean nasty SOB. Must one have the razor-sharp wit of Oscar Wilde to be judged as having a "great sense of humor"? No: so long as you don't stare blankly once told the punchlines of typical jokes. These touchy-feely criteria are there to weed out the worst offenders -- the cruel, the humorless, etc. It's like putting together a sports team: first you cut the flabby and the wimps, then worry later on about finer details like field goal kicking (or good looks in dating).

I have yet to really ask someone out on a date after having returned from Barcelona. Browsing through the various sites, watching popular TV shows on dating, and discussing the issue with others, I have come to the conclusion that -- exceptions aside -- the most likely situation would involve an "interview date" where she would try to size me up much as if she were leafing through a sperm donor catalog. Needless to say, that prospect doesn't exactly excite me -- for one thing, I'm not an ideal donor (only 5'8, not rich nor will be, somewhat introverted). For another thing, even if I were an ideal donor, I'd feel about as great as a large-breasted girl must feel when hooted and hollered at: vaguely flattered but more put off. I want to have fun on a date, not be grilled by her HR rep to see if I'm the male to fill the vacant slot in the corporation of her existence.

Allow me to end with a few examples from the women seeking men section of my local craigslist. (Yes, it may not be totally representative of all women, nor of professional women in all geographical areas, etc. I know: this is just to give an impression.) Title: "5'11 or taller please," in which a self-described "5'6 overweight" woman makes it clear that she doesn't want men who are "5'9 with shoes that make you 5'11 but men who are really that tall." This is almost the entirety of her post. Another: "Calling on Black males under 35 over 6'2." Most posts require something similar but are not so brazen to stick it in the title. Imagine reading through the men seeking women section and noting that most men stated a minimum requirement for breast size or waist-to-hip ratio, with not a few bearing inviting titles like "Double-D Hourglass Latinas wanted" or "No Fat Chicks." You'd think the men were soliciting prostitutes or one-nighters, their verbal disclaimers notwithstanding. Equivalently, I infer that the women are looking for sperm donors rather than stand-up gentlemen in it for the long haul.

Next post: how Spanish girls differ.

## December 6, 2005

### First snow in DC

Yay! Lots of people hate winter, but it's great. Cancelled school days. Sledding. Warm blankets. I'll take those over the 90-degree pea soup humidity of DC summers any day. Once upon a time I wrote a wintery haiku to a girl I had a crush on, which I'll post to ring in the winter.

Snowfall at twilight

Tiny feathers nestle in

Her dusky tresses

Snowfall at twilight

Tiny feathers nestle in

Her dusky tresses

## December 4, 2005

### Mathematical induction in linguistics

Just another quick example of how inductive proofs can help in linguistics. Well, any nerd who appreciates language will find this one cool. What we'll prove is the property P that the word that describes the most recently developed missile-seeking missile used in an arms race is given, in English, by the formula: anti^(n-1)missile^n. What that says is that the word will contain n copies of the word "missile" stuck one next to the other in a row, preceded by the n-1 copies of the word "anti" stuck together in a row. It may help to think of missiles designed for tanks rather than other missiles: first you start with the intended target, a tank, then stick "anti" to the left to show that it's aimed against a tank, then stick "missile" on the right to show that it's a missile that's taking out the tank. Note that in writing, such a compound word is often spelled as two separate words like "speed limit," but it is really just the same as "bookcase" or "man-breasts." Only the unimportant written forms are different.

OK, consider the Basis n=1, where we're talking about the first missile one country designs. Well, they call it just that, "missile," nothing fancy yet. Sure enough, there is 1 copy of "missile" preceded by 1-1 = 0 copies of "anti." Now, as the arms race gets going, the other country will design an "anti-missile missile," which will in turn prompt the first to design an "anti-anti-missile-missile missile," and so forth. For the Inductive step, assume that P(n) is true, i.e that the above formula describes the nth development. Now consider what the enemy country will do, i.e. the n+1th development: they will design something that is "anti" what the other country just developed at stage n and will also label it a "missile." Since we already began with anti^(n-1)missile^n, now we have something that is "anti" that thing and which is a "missile," and we stick on yet another "anti" to the left and another "missile" to the right in order to capture that. So this n+1th development is an anti^(n)missile^(n+1), which means that P(n+1) is true. This followed from our assumption that P(n) was true, which completes the Inductive step. In conclusion, the formula above gives the word form of the nth development in an arms race for missile-seeking missiles.

The observation of the recursive nature of this English compound word is due to pioneering morphologist and phonologist Morris Halle.

OK, consider the Basis n=1, where we're talking about the first missile one country designs. Well, they call it just that, "missile," nothing fancy yet. Sure enough, there is 1 copy of "missile" preceded by 1-1 = 0 copies of "anti." Now, as the arms race gets going, the other country will design an "anti-missile missile," which will in turn prompt the first to design an "anti-anti-missile-missile missile," and so forth. For the Inductive step, assume that P(n) is true, i.e that the above formula describes the nth development. Now consider what the enemy country will do, i.e. the n+1th development: they will design something that is "anti" what the other country just developed at stage n and will also label it a "missile." Since we already began with anti^(n-1)missile^n, now we have something that is "anti" that thing and which is a "missile," and we stick on yet another "anti" to the left and another "missile" to the right in order to capture that. So this n+1th development is an anti^(n)missile^(n+1), which means that P(n+1) is true. This followed from our assumption that P(n) was true, which completes the Inductive step. In conclusion, the formula above gives the word form of the nth development in an arms race for missile-seeking missiles.

The observation of the recursive nature of this English compound word is due to pioneering morphologist and phonologist Morris Halle.

### More proof techniques: by induction

I posted below on a simple proof technique (proof by contradiction) which is useful in both math / science as well as everyday arguments. Mathematical induction is only useful in math / science but worth knowing if you don't, regardless of your field. For the mathematically inclined, I prove in the post just below why induction works. This post is just to show how it works.

The basic logic is that of dominoes: in a row of dominoes, any randomly chosen domino will knock down the one just after it, and the first domino is knocked down to get things going. What you're using induction for is to prove that some property P is true for all the natural numbers: i.e. 1, 2, 3, ... , n. Say, the property that the sum of the first n nat. numbers is given by a particular formula. There are two steps in an inductive proof: the Basis, and the Inductive step. The Basis is like the first domino -- it says that there's at least one number for which P is true. The Inductive step mimics the "domino effect" -- it says that, if you assume P is true for the number n, then it follows that P is also true for the next number n+1. This is crucial: the Inductive step is an If-Then statement: if you assume bla, then you can conclude bla bla. The conclusion statement is optional, but probably worth reiterating when you're first getting used to the technique. It just re-states your claim: because the domino effect is at work, and because the first domino is knocked down, all of them are -- i.e. the property P is true for all nat. numbers n.

Example: the handshake problem. We want to find out how many possible distinct handshakes there can be in room full of n people, and then prove this formula by induction. OK, imagine yourself as any randomly chosen person in that room -- how many people's hands can you shake? Well, you can shake everybody's but your own, which means there are n-1 handshakes a random person can make. Now, if there are n such people, then there should be n(n-1) handshakes, right? Almost -- but if A shakes B's hand, that's the same as B shaking A's hand, so we've accidentally counted each handshake twice. No problem, we'll just cut our number in half: (n(n-1))/2. This is usually the hardest part of an inductive proof -- just figuring out what the damn thing is you want to prove.

For the proof, we begin with a "let" statement. Let the property P(n) be defined (on the set of natural numbers) as the property that in a room of n people, there are (n(n-1))/2 distinct handshakes. We first establish the Basis. Here we'll pick n=2 since there need to be at least 2 people for a handshake to be defined. In a room full of 2 people, there is only 1 possible handshake. Substituting n=2 into our formula gives us (2(2-1))/2 = 1. The Basis checks out, so P(2) is true.

For the Inductive step, we assume that P(n) is true, and we want to show that this assumption implies that P(n+1) is true. So we assume that in a room of n people, the formula above gives the number of handshakes. Consider what would happen if another person entered the room. By our inductive hypothesis, there were already (n(n-1))/2 handshakes before he entered, and by the time he's shaken the hand of the n people who were already there, he'll have contributed an additional n handshakes to the total. By simple algebra, (n(n-1))/2 + n = ((n+1)n)/2. But we can re-write that as ((n+1)(n+1-1))/2 -- which means that P(n+1) is also true. That is, assuming P(n) is true, P(n+1) follows. This completes the Inductive step: it assures us that the domino effect happens. So in conclusion, P is true for all nat. numbers n -- the formula above gives the number of possible distinct handshakes in a room of n people.

Exercise 1: how many possible distinct diagonals can be drawn between the vertices of a polygon that has n sides? A polygon is just like the shapes you saw in high school geometry (triangle, rectangle, pentagon, etc.). Prove this formula is true by induction. Note: the Basis will be n=3 since you need at least 3 sides for a polygon. Hint for finding the formula: it's not a coincidence that this exercise follows the handshake example.

Exercise 2: prove by induction that the sum of the first n nat. numbers is given by the formula (n(n+1))/2.

Exercise 3: find a formula for the sum of the first n CUBES -- that is, 1^3 + 2^3 + ... + n^3. Prove this formula by induction.

The basic logic is that of dominoes: in a row of dominoes, any randomly chosen domino will knock down the one just after it, and the first domino is knocked down to get things going. What you're using induction for is to prove that some property P is true for all the natural numbers: i.e. 1, 2, 3, ... , n. Say, the property that the sum of the first n nat. numbers is given by a particular formula. There are two steps in an inductive proof: the Basis, and the Inductive step. The Basis is like the first domino -- it says that there's at least one number for which P is true. The Inductive step mimics the "domino effect" -- it says that, if you assume P is true for the number n, then it follows that P is also true for the next number n+1. This is crucial: the Inductive step is an If-Then statement: if you assume bla, then you can conclude bla bla. The conclusion statement is optional, but probably worth reiterating when you're first getting used to the technique. It just re-states your claim: because the domino effect is at work, and because the first domino is knocked down, all of them are -- i.e. the property P is true for all nat. numbers n.

Example: the handshake problem. We want to find out how many possible distinct handshakes there can be in room full of n people, and then prove this formula by induction. OK, imagine yourself as any randomly chosen person in that room -- how many people's hands can you shake? Well, you can shake everybody's but your own, which means there are n-1 handshakes a random person can make. Now, if there are n such people, then there should be n(n-1) handshakes, right? Almost -- but if A shakes B's hand, that's the same as B shaking A's hand, so we've accidentally counted each handshake twice. No problem, we'll just cut our number in half: (n(n-1))/2. This is usually the hardest part of an inductive proof -- just figuring out what the damn thing is you want to prove.

For the proof, we begin with a "let" statement. Let the property P(n) be defined (on the set of natural numbers) as the property that in a room of n people, there are (n(n-1))/2 distinct handshakes. We first establish the Basis. Here we'll pick n=2 since there need to be at least 2 people for a handshake to be defined. In a room full of 2 people, there is only 1 possible handshake. Substituting n=2 into our formula gives us (2(2-1))/2 = 1. The Basis checks out, so P(2) is true.

For the Inductive step, we assume that P(n) is true, and we want to show that this assumption implies that P(n+1) is true. So we assume that in a room of n people, the formula above gives the number of handshakes. Consider what would happen if another person entered the room. By our inductive hypothesis, there were already (n(n-1))/2 handshakes before he entered, and by the time he's shaken the hand of the n people who were already there, he'll have contributed an additional n handshakes to the total. By simple algebra, (n(n-1))/2 + n = ((n+1)n)/2. But we can re-write that as ((n+1)(n+1-1))/2 -- which means that P(n+1) is also true. That is, assuming P(n) is true, P(n+1) follows. This completes the Inductive step: it assures us that the domino effect happens. So in conclusion, P is true for all nat. numbers n -- the formula above gives the number of possible distinct handshakes in a room of n people.

Exercise 1: how many possible distinct diagonals can be drawn between the vertices of a polygon that has n sides? A polygon is just like the shapes you saw in high school geometry (triangle, rectangle, pentagon, etc.). Prove this formula is true by induction. Note: the Basis will be n=3 since you need at least 3 sides for a polygon. Hint for finding the formula: it's not a coincidence that this exercise follows the handshake example.

Exercise 2: prove by induction that the sum of the first n nat. numbers is given by the formula (n(n+1))/2.

Exercise 3: find a formula for the sum of the first n CUBES -- that is, 1^3 + 2^3 + ... + n^3. Prove this formula by induction.

### Why induction works

This is a footnote to the above post for the mathematically inclined, or those who've heard it before but don't remember why it works. If you can already give a proof... pat yourself on the back! The proof is by contradiction. Induction says that if the following premises 1) and 2) are true, then the conclusion 3) is true:

1) P(1) is true.

2) If P(n) is true, then P(n+1) is also true.

3) In conclusion, the property P is true for all natural numbers n.

Let's assume the argument is false. Again, that means we grant that 1) and 2) are true, but claim that 3) is false. If 3) is false, that means P is not true for all natural numbers n. Let's call the set of nat. numbers for which P is false, X. The only new idea is the Well Ordering Principle, which says that any non-empty set of the nat. numbers has a least element, i.e. an element which is less than all others. There's nothing fishy here -- you can either assume the WOP by axiom and then prove induction, or assume induction works by axiom and then prove the WOP, however you like. Now, our set X is non-empty if we assume 3) is false, and X is also a subset of the nat. numbers; thus, it has a least element, which we'll call k. It cannot be 1, because that would contradict 1).

Let's look at that nat. number before k, namely k-1. Either P is true or false for k-1. If it's true for k-1, then by 2), P is also true for k-1+1, which is k -- but we chose k so that P(k) was false, a contradiction. What if P is not true for k-1? Then it belongs to the set X. Ah, but we chose k so that it was the least element of X, and surely k-1 is less than k, also a contradiction. No matter what, we get a contradiction, and therefore our assumption that induction doesn't work must be false: it is valid after all.

1) P(1) is true.

2) If P(n) is true, then P(n+1) is also true.

3) In conclusion, the property P is true for all natural numbers n.

Let's assume the argument is false. Again, that means we grant that 1) and 2) are true, but claim that 3) is false. If 3) is false, that means P is not true for all natural numbers n. Let's call the set of nat. numbers for which P is false, X. The only new idea is the Well Ordering Principle, which says that any non-empty set of the nat. numbers has a least element, i.e. an element which is less than all others. There's nothing fishy here -- you can either assume the WOP by axiom and then prove induction, or assume induction works by axiom and then prove the WOP, however you like. Now, our set X is non-empty if we assume 3) is false, and X is also a subset of the nat. numbers; thus, it has a least element, which we'll call k. It cannot be 1, because that would contradict 1).

Let's look at that nat. number before k, namely k-1. Either P is true or false for k-1. If it's true for k-1, then by 2), P is also true for k-1+1, which is k -- but we chose k so that P(k) was false, a contradiction. What if P is not true for k-1? Then it belongs to the set X. Ah, but we chose k so that it was the least element of X, and surely k-1 is less than k, also a contradiction. No matter what, we get a contradiction, and therefore our assumption that induction doesn't work must be false: it is valid after all.

### Everyday proof techniques: by contradiction

This is a great technique to know, whether you're using it in math theorems, linguistic analyses, or just everyday argument. It's also great if you're a teacher, because it's pretty simple to teach. Basically, rather than directly prove your claim, you're going to assume that it's wrong and then show how a contradiction follows from that mistaken assumption. Sidebar: a cause-and-effect argument takes the form "If X is the case, then Y is the case." It is only wrong if the premises (if-part) are true but the conclusion (then-part) is false -- in other words, if a supposed cause doesn't result in the supposed effect, your cause-and-effect argument is false. Now, only false statements can imply contradictions, so your mistaken assumption must have been false -- that is, your claim was correct after all!

In everyday arguments, your assumption may imply only an "absurdity," whether a logical contradiction or otherwise, in which case the technique is called reductio ad absurdum. Just bear in mind that what's absurd to one may not be so to another. Two examples, one from high school geometry and another from linguistics.

First, let's say you want to prove the statement that "If a quadrilateral x is a square, then that quadrilateral x is also a rectangle." Let's assume this statement is false -- then we grant the premises are true, but deny that the conclusion follows from them. So the shape x is a square, which means it has all 90-degree angles. But if shape x is not a rectangle, then at least one of the angles must be something other than 90. However, this contradicts what we said before about all of them measuring 90 -- this is a contradiction, and we only arrived at it by assuming the original statement was false. Therefore, the original statement must be true.

Second, one from the field of syntax in linguistics, which has to do with how words are put together into phrases and sentences. The claim is that "There is no longest sentence" -- i.e. a sentence which is longer than all others in how many words it contains. You may think this is true, but we'll prove that it is. Let's assume it's false -- so there is a longest sentence, which we'll call K. Now, in English as in all languages, there are rules that show how sentences can be formed, one of which is the following:

1) S --> S and S

What this says is "a sentence may-consist-of a sentence, followed by the word 'and,' followed by another sentence." Some version of this rule is going to be in anybody's grammar for any language since they all have sentences and conjunctions like "and." So, we'll just take our longest sentence K, stick "and" to the right of it, and then to the right of that stick any other sentence in the language we want -- let's call this one L. So, now we have "K and L" -- which in turn is a sentence according to 1). Let's say that sentence K is of length n, while L is of length m (which is less than n), where both m and n are nat. numbers. Then our new sentence has length n + m + 1, which is surely longer than just n. But that contradicts how we chose K -- we chose it to be the longest sentence. This contradiction arose from assuming there is a longest sentence in the language, which must be false; thus, the original statement must be true. Note that the words that make up K and L are irrelevant -- we didn't say it would be an interesting sentence; we only cared about how long it was.

Exercise: this relates somewhat the the previous example. Prove by contradiction that, in addition there not being any longest sentence, there are an infinite number of possible sentences in any language. You only have to use the simple rule 1) above to do it.

In everyday arguments, your assumption may imply only an "absurdity," whether a logical contradiction or otherwise, in which case the technique is called reductio ad absurdum. Just bear in mind that what's absurd to one may not be so to another. Two examples, one from high school geometry and another from linguistics.

First, let's say you want to prove the statement that "If a quadrilateral x is a square, then that quadrilateral x is also a rectangle." Let's assume this statement is false -- then we grant the premises are true, but deny that the conclusion follows from them. So the shape x is a square, which means it has all 90-degree angles. But if shape x is not a rectangle, then at least one of the angles must be something other than 90. However, this contradicts what we said before about all of them measuring 90 -- this is a contradiction, and we only arrived at it by assuming the original statement was false. Therefore, the original statement must be true.

Second, one from the field of syntax in linguistics, which has to do with how words are put together into phrases and sentences. The claim is that "There is no longest sentence" -- i.e. a sentence which is longer than all others in how many words it contains. You may think this is true, but we'll prove that it is. Let's assume it's false -- so there is a longest sentence, which we'll call K. Now, in English as in all languages, there are rules that show how sentences can be formed, one of which is the following:

1) S --> S and S

What this says is "a sentence may-consist-of a sentence, followed by the word 'and,' followed by another sentence." Some version of this rule is going to be in anybody's grammar for any language since they all have sentences and conjunctions like "and." So, we'll just take our longest sentence K, stick "and" to the right of it, and then to the right of that stick any other sentence in the language we want -- let's call this one L. So, now we have "K and L" -- which in turn is a sentence according to 1). Let's say that sentence K is of length n, while L is of length m (which is less than n), where both m and n are nat. numbers. Then our new sentence has length n + m + 1, which is surely longer than just n. But that contradicts how we chose K -- we chose it to be the longest sentence. This contradiction arose from assuming there is a longest sentence in the language, which must be false; thus, the original statement must be true. Note that the words that make up K and L are irrelevant -- we didn't say it would be an interesting sentence; we only cared about how long it was.

Exercise: this relates somewhat the the previous example. Prove by contradiction that, in addition there not being any longest sentence, there are an infinite number of possible sentences in any language. You only have to use the simple rule 1) above to do it.

Subscribe to:
Posts (Atom)