text:
A black raven
Non-black non-ravens
The paradox: Do these images both contribute evidence that all ravens are black?

The Raven paradox, also known as Hempel's paradox or Hempel's ravens is a paradox arising from the question of what constitutes evidence for a statement. Observing objects that are neither black nor ravens may formally increase the likelihood that all ravens are black—even though intuitively these observations are unrelated.

This problem was proposed by the logician Carl Gustav Hempel in the 1940s to illustrate a contradiction between inductive logic and intuition. A related issue is the problem of induction and the gap between inductive and deductive reasoning.[1]

Hempel describes the paradox in terms of the hypothesis:[2][3]

(1) All ravens are black.

In strict logical terms, via contraposition, this statement is equivalent to:

(2) Everything that is not black is not a raven.

It should be clear that in all circumstances where (2) is true, (1) is also true; and likewise, in all circumstances where (2) is false (i.e. if a world is imagined in which something that was not black, yet was a raven, existed), (1) is also false. This establishes logical equivalence.

Given a general statement such as all ravens are black, a form of the same statement that refers to a specific observable instance of the general class would typically be considered to constitute evidence for that general statement. For example,

(3) Nevermore, my pet raven, is black.

is evidence supporting the hypothesis that all ravens are black.

The paradox arises when this same process is applied to statement (2). On sighting a green apple, one can observe:

(4) This green (and thus not black) thing is an apple (and thus not a raven).

By the same reasoning, this statement is evidence that (2) everything that is not black is not a raven. But since (as above) this statement is logically equivalent to (1) all ravens are black, it follows that the sight of a green apple is evidence supporting the notion that all ravens are black. This conclusion seems paradoxical, because it implies that information has been gained about ravens by looking at an apple.

## Proposed resolutions

Nicod's criterion says that only observations of ravens should affect one's view as to whether all ravens are black. Observing more instances of black ravens should support the view, observing white or coloured ravens should contradict it, and observations of non-ravens should not have any influence.[4]

Hempel's equivalence condition states that when a proposition, X, provides evidence in favor of another proposition Y, then X also provides evidence in favor of any proposition which is logically equivalent to Y.[5]

The paradox shows that Nicod's criterion and Hempel's equivalence condition are not mutually consistent. A resolution to the paradox must reject at least one out of:[6]

1. negative instances having no influence (!PC),
2. equivalence condition (EC), or,
3. validation by positive instances (NC).

A satisfactory resolution should also explain why there naively appears to be a paradox. Solutions which accept the paradoxical conclusion can do this by presenting a proposition which we intuitively know to be false but which is easily confused with (PC), while solutions which reject (EC) or (NC) should present a proposition which we intuitively know to be true but which is easily confused with (EC) or (NC).

### Accepting non-ravens as relevant

Although this conclusion of the paradox seems counter-intuitive, some approaches accept that observations of (coloured) non-ravens can in fact constitute valid evidence in support for hypotheses about (the universal blackness of) ravens.

#### Hempel's resolution

Hempel himself accepted the paradoxical conclusion, arguing that the reason the result appears paradoxical is because we possess prior information without which the observation of a non-black non-raven would indeed provide evidence that all ravens are black.

He illustrates this with the example of the generalization "All sodium salts burn yellow", and asks us to consider the observation which occurs when somebody holds a piece of pure ice in a colorless flame which does not turn yellow:[2]

This result would confirm the assertion, "Whatever does not burn yellow is not sodium salt", and consequently, by virtue of the equivalence condition, it would confirm the original formulation. Why does this impress us as paradoxical? The reason becomes clear when we compare the previous situation with the case of an experiment where an object whose chemical constitution is as yet unknown to us is held into a flame and fails to turn it yellow, and where subsequent analysis reveals it to contain no sodium salt. This outcome, we should no doubt agree, is what was to be expected on the basis of the hypothesis ... thus the data here obtained constitute confirming evidence for the hypothesis. In the seemingly paradoxical cases of confirmation, we are often not actually judging the relation of the given evidence, E alone to the hypothesis H ... we tacitly introduce a comparison of H with a body of evidence which consists of E in conjunction with an additional amount of information which we happen to have at our disposal; in our illustration, this information includes the knowledge (1) that the substance used in the experiment is ice, and (2) that ice contains no sodium salt. If we assume this additional information as given, then, of course, the outcome of the experiment can add no strength to the hypothesis under consideration. But if we are careful to avoid this tacit reference to additional knowledge ... the paradoxes vanish.

#### The standard Bayesian solution

One of the most popular proposed resolutions is to accept the conclusion that the observation of a green apple provides evidence that all ravens are black but to argue that the amount of confirmation provided is very small, due to the large discrepancy between the number of ravens and the number of non-black objects. According to this resolution, the conclusion appears paradoxical because we intuitively estimate the amount of evidence provided by the observation of a green apple to be zero, when it is in fact non-zero but extremely small.

I J Good's presentation of this argument in 1960[7] is perhaps the best known, and variations of the argument have been popular ever since [8] although it had been presented in 1958[9] and early forms of the argument appeared as early as 1940.[10]

Good's argument involves calculating the weight of evidence provided by the observation of a black raven or a white shoe in favor of the hypothesis that all the ravens in a collection of objects are black. The weight of evidence is the logarithm of the Bayes factor, which in this case is simply the factor by which the odds of the hypothesis changes when the observation is made. The argument goes as follows:

... suppose that there are $N$ objects that might be seen at any moment, of which $r$ are ravens and $b$ are black, and that the $N$ objects each have probability $\tfrac{1}{N}$ of being seen. Let $H_i$ be the hypothesis that there are $i$ non-black ravens, and suppose that the hypotheses $H_1, H_2, ... ,H_r$ are initially equiprobable. Then, if we happen to see a black raven, the Bayes factor in favour of $H_0$ is
$\tfrac{r}{N} \Big / \text{average} \left( \tfrac{r-1}{N},\tfrac{r-2}{N}, ...\ ,\tfrac{1}{N}\right) \ = \ \tfrac{2r}{r-1}$
i.e. about 2 if the number of ravens in existence is known to be large. But the factor if we see a white shoe is only
$\tfrac{N-b}{N} \Big / \text{average} \left( \tfrac{N-b-1}{N},\tfrac{N-b-2}{N}, ...\ ,\max(0,\tfrac{N-b-r}{N})\right)$
$\ = \ \frac{N-b}{\max\left(N-b-\tfrac{r}{2}-\tfrac12\ , \ \tfrac12(N-b-1)\right)}$
and this exceeds unity by only about $r/(2N-2b)$ if $N-b$ is large compared to $r$. Thus the weight of evidence provided by the sight of a white shoe is positive, but is small if the number of ravens is known to be small compared to the number of non-black objects.[11]

Many of the proponents of this resolution and variants of it have been advocates of Bayesian probability, and it is now commonly called the Bayesian Solution, although, as Chihara[12] observes, "there is no such thing as the Bayesian solution. There are many different 'solutions' that Bayesians have put forward using Bayesian techniques." Noteworthy approaches using Bayesian techniques include Earman,[13] Eells,[14] Gibson,[15] Hosaisson-Lindenbaum,[16] Howson and Urbach,[17] Mackie,[18] and Hintikka,[19] who claims that his approach is "more Bayesian than the so-called 'Bayesian solution' of the same paradox." Bayesian approaches which make use of Carnap's theory of inductive inference include Humburg,[20] Maher,[21] and Fitelson et al.[22] Vranas[23] introduced the term "Standard Bayesian Solution" to avoid confusion.

#### The Carnapian approach

Maher[24] accepts the paradoxical conclusion, and refines it:

A non-raven (of whatever color) confirms that all ravens are black because
(i) the information that this object is not a raven removes the possibility that this object is a counterexample to the generalization, and
(ii) it reduces the probability that unobserved objects are ravens, thereby reducing the probability that they are counterexamples to the generalization.

In order to reach (ii), he appeals to Carnap's theory of inductive probability, which is (from the Bayesian point of view) a way of assigning prior probabilities which naturally implements induction. According to Carnap's theory, the posterior probability, $P(Fa|E)$, that an object, $a$, will have a predicate, $F$, after the evidence $E$ has been observed, is:

$P(Fa|E) \ = \ \frac{n_F+\lambda P(Fa)}{n+\lambda}$

where $P(Fa)$ is the initial probability that $a$ has the predicate $F$; $n$ is the number of objects which have been examined (according to the available evidence $E$); $n_F$ is the number of examined objects which turned out to have the predicate $F$, and $\lambda$ is a constant which measures resistance to generalization.

If $\lambda$ is close to zero, $P(Fa|E)$ will be very close to one after a single observation of an object which turned out to have the predicate $F$, while if $\lambda$ is much larger than $n$, $P(Fa|E)$ will be very close to $P(Fa)$ regardless of the fraction of observed objects which had the predicate $F$.

Using this Carnapian approach, Maher identifies a proposition which we intuitively (and correctly) know to be false, but which we easily confuse with the paradoxical conclusion. The proposition in question is the proposition that observing non-ravens tells us about the color of ravens. While this is intuitively false and is also false according to Carnap's theory of induction, observing non-ravens (according to that same theory) causes us to reduce our estimate of the total number of ravens, and thereby reduces the estimated number of possible counterexamples to the rule that all ravens are black.

Hence, from the Bayesian-Carnapian point of view, the observation of a non-raven does not tell us anything about the color of ravens, but it tells us about the prevalence of ravens, and supports "All ravens are black" by reducing our estimate of the number of ravens which might not be black.

#### The role of background knowledge

Much of the discussion of the paradox in general and the Bayesian approach in particular has centred on the relevance of background knowledge. Surprisingly, Maher[24] shows that, for a large class of possible configurations of background knowledge, the observation of a non-black non-raven provides exactly the same amount of confirmation as the observation of a black raven. The configurations of background knowledge which he considers are those which are provided by a sample proposition, namely a proposition which is a conjunction of atomic propositions, each of which ascribes a single predicate to a single individual, with no two atomic propositions involving the same individual. Thus, a proposition of the form "A is a black raven and B is a white shoe" can be considered a sample proposition by taking "black raven" and "white shoe" to be predicates.

Maher's proof appears to contradict the result of the Bayesian argument, which was that the observation of a non-black non-raven provides much less evidence than the observation of a black raven. The reason is that the background knowledge which Good and others use can not be expressed in the form of a sample proposition - in particular, variants of the standard Bayesian approach often suppose (as Good did in the argument quoted above) that the total numbers of ravens, non-black objects and/or the total number of objects, are known quantities. Maher comments that, "The reason we think there are more non-black things than ravens is because that has been true of the things we have observed to date. Evidence of this kind can be represented by a sample proposition. But ... given any sample proposition as background evidence, a non-black non-raven confirms A just as strongly as a black raven does ... Thus my analysis suggests that this response to the paradox [i.e. the Standard Bayesian one] cannot be correct."

Fitelson et al.[25] examined the conditions under which the observation of a non-black non-raven provides less evidence than the observation of a black raven. They show that, if $a$ is an object selected at random, $Ba$ is the proposition that the object is black, and $Ra$ is the proposition that the object is a raven, then the condition:

$\frac{P(\overline{Ba}|\overline{H})}{P(Ra|\overline{H})} \ - \ P(\overline{Ba}|Ra\overline{H}) \ \geq \ P(Ba|Ra\overline{H}) \frac{P(\overline{Ba}|H)}{P(Ra|H)}$

is sufficient for the observation of a non-black non-raven to provide less evidence than the observation of a black raven. Here, a line over a proposition indicates the logical negation of that proposition.

This condition does not tell us how large the difference in the evidence provided is, but a later calculation in the same paper shows that the weight of evidence provided by a black raven exceeds that provided by a non-black non-raven by about $-\log P(Ba|Ra\overline{H})$. This is equal to the amount of additional information (in bits, if the base of the logarithm is 2) which is provided when a raven of unknown color is discovered to be black, given the hypothesis that not all ravens are black.

Fitelson et al.[25] explain that:

Under normal circumstances, $p=P(Ba|Ra\overline{H})$ may be somewhere around 0.9 or 0.95; so $1/p$ is somewhere around 1.11 or 1.05. Thus, it may appear that a single instance of a black raven does not yield much more support than would a non-black non-raven. However, under plausible conditions it can be shown that a sequence of $n$ instances (i.e. of n black ravens, as compared to n non-black non-ravens) yields a ratio of likelihood ratios on the order of $(1/p)^n$, which blows up significantly for large $n$.

The authors point out that their analysis is completely consistent with the supposition that a non-black non-raven provides an extremely small amount of evidence although they do not attempt to prove it; they merely calculate the difference between the amount of evidence that a black raven provides and the amount of evidence that a non-black non-raven provides.

### Disputing the induction from positive instances

Some approaches for resolving the paradox focus on the inductive step. They dispute whether observation of a particular instance (such as one black raven) is the kind of evidence that necessarily increases confidence in the general hypothesis (such as that ravens are always black).

#### The red herring

Good[26] gives an example of background knowledge with respect to which the observation of a black raven decreases the probability that all ravens are black:

Suppose that we know we are in one or other of two worlds, and the hypothesis, H, under consideration is that all the ravens in our world are black. We know in advance that in one world there are a hundred black ravens, no non-black ravens, and a million other birds; and that in the other world there are a thousand black ravens, one white raven, and a million other birds. A bird is selected equiprobably at random from all the birds in our world. It turns out to be a black raven. This is strong evidence ... that we are in the second world, wherein not all ravens are black.

Good concludes that the white shoe is a "red herring": Sometimes even a black raven can constitute evidence against the hypothesis that all ravens are black, so the fact that the observation of a white shoe can support it is not surprising and not worth attention. Nicod's criterion is false, according to Good, and so the paradoxical conclusion does not follow.

Hempel rejected this as a solution to the paradox, insisting that the proposition 'c is a raven and is black' must be considered "by itself and without reference to any other information", and pointing out that it "... was emphasized in section 5.2(b) of my article in Mind ... that the very appearance of paradoxicality in cases like that of the white shoe results in part from a failure to observe this maxim."[27]

The question which then arises is whether the paradox is to be understood in the context of absolutely no background information (as Hempel suggests), or in the context of the background information which we actually possess regarding ravens and black objects, or with regard to all possible configurations of background information.

Good had shown that, for some configurations of background knowledge, Nicod's criterion is false (provided that we are willing to equate "inductively support" with "increase the probability of" - see below). The possibility remained that, with respect to our actual configuration of knowledge, which is very different from Good's example, Nicod's criterion might still be true and so we could still reach the paradoxical conclusion. Hempel, on the other hand, insists that it is our background knowledge itself which is the red herring, and that we should consider induction with respect to a condition of perfect ignorance.

#### Good's baby

In his proposed resolution, Maher implicitly made use of the fact that the proposition "All ravens are black" is highly probable when it is highly probable that there are no ravens. Good had used this fact before to respond to Hempel's insistence that Nicod's criterion was to be understood to hold in the absence of background information:[28]

...imagine an infinitely intelligent newborn baby having built-in neural circuits enabling him to deal with formal logic, English syntax, and subjective probability. He might now argue, after defining a raven in detail, that it is extremely unlikely that there are any ravens, and therefore it is extremely likely that all ravens are black, that is, that $H$ is true. 'On the other hand', he goes on to argue, 'if there are ravens, then there is a reasonable chance that they are of a variety of colours. Therefore, if I were to discover that even a black raven exists I would consider $H$ to be less probable than it was initially.'

This, according to Good, is as close as one can reasonably expect to get to a condition of perfect ignorance, and it appears that Nicod's condition is still false. Maher made Good's argument more precise by using Carnap's theory of induction to formalize the notion that if there is one raven, then it is likely that there are many.[29]

Maher's argument considers a universe of exactly two objects, each of which is very unlikely to be a raven (a one in a thousand chance) and reasonably unlikely to be black (a one in ten chance). Using Carnap's formula for induction, he finds that the probability that all ravens are black decreases from 0.9985 to 0.8995 when it is discovered that one of the two objects is a black raven.

Maher concludes that not only is the paradoxical conclusion true, but that Nicod's criterion is false in the absence of background knowledge (except for the knowledge that the number of objects in the universe is two and that ravens are less likely than black things).

#### Distinguished predicates

Quine[30] argued that the solution to the paradox lies in the recognition that certain predicates, which he called natural kinds, have a distinguished status with respect to induction. This can be illustrated with Nelson Goodman's example of the predicate grue. An object is grue if it is blue before (say) 2015 and green afterwards. Clearly, we expect objects which were blue before 2015 to remain blue afterwards, but we do not expect the objects which were found to be grue before 2015 to be blue after 2015, since after 2015 they would be green. Quine's explanation is that "blue" is a natural kind; a privileged predicate which can be used for induction, while "grue" is not a natural kind and using induction with it leads to error.

This suggests a resolution to the paradox - Nicod's criterion is true for natural kinds, such as "blue" and "black", but is false for artificially contrived predicates, such as "grue" or "non-raven". The paradox arises, according to this resolution, because we implicitly interpret Nicod's criterion as applying to all predicates when in fact it only applies to natural kinds.

Another approach which favours specific predicates over others was taken by Hintikka.[19] Hintikka was motivated to find a Bayesian approach to the paradox which did not make use of knowledge about the relative frequencies of ravens and black things. Arguments concerning relative frequencies, he contends, cannot always account for the perceived irrelevance of evidence consisting of observations of objects of type A for the purposes of learning about objects of type not-A.

His argument can be illustrated by rephrasing the paradox using predicates other than "raven" and "black". For example, "All men are tall" is equivalent to "All short people are women", and so observing that a randomly selected person is a short woman should provide evidence that all men are tall. Despite the fact that we lack background knowledge to indicate that there are dramatically fewer men than short people, we still find ourselves inclined to reject the conclusion. Hintikka's example is: "... a generalization like 'no material bodies are infinitely divisible' seems to be completely unaffected by questions concerning immaterial entities, independently of what one thinks of the relative frequencies of material and immaterial entities in one's universe of discourse."

His solution is to introduce an order into the set of predicates. When the logical system is equipped with this order, it is possible to restrict the scope of a generalization such as "All ravens are black" so that it applies to ravens only and not to non-black things, since the order privileges ravens over non-black things. As he puts it:

If we are justified in assuming that the scope of the generalization 'All ravens are black' can be restricted to ravens, then this means that we have some outside information which we can rely on concerning the factual situation. The paradox arises from the fact that this information, which colors our spontaneous view of the situation, is not incorporated in the usual treatments of the inductive situation.[31]

### Rejections of Hempel's equivalence condition

Some approaches for the resolution of the paradox reject Hempel's equivalence condition. That is, they may not consider evidence supporting the statement all non-black objects are non-ravens to necessarily support logically-equivalent statements such as all ravens are black.

#### Selective confirmation

Scheffler and Goodman[32] took an approach to the paradox which incorporates Karl Popper's view that scientific hypotheses are never really confirmed, only falsified.

The approach begins by noting that the observation of a black raven does not prove that "All ravens are black" but it falsifies the contrary hypothesis, "No ravens are black". A non-black non-raven, on the other hand, is consistent with both "All ravens are black" and with "No ravens are black". As the authors put it:

... the statement that all ravens are black is not merely satisfied by evidence of a black raven but is favored by such evidence, since a black raven disconfirms the contrary statement that all ravens are not black, i.e. satisfies its denial. A black raven, in other words, satisfies the hypothesis that all ravens are black rather than not: it thus selectively confirms that all ravens are black.

Selective confirmation violates the equivalence condition since a black raven selectively confirms "All ravens are black" but not "All non-black things are non-ravens".

##### Probabilistic or non-probabilistic induction

Scheffler and Goodman's concept of selective confirmation is an example of an interpretation of "provides evidence in favor of," which does not coincide with "increase the probability of". This must be a general feature of all resolutions which reject the equivalence condition, since logically equivalent propositions must always have the same probability.

It is impossible for the observation of a black raven to increase the probability of the proposition "All ravens are black" without causing exactly the same change to the probability that "All non-black things are non-ravens". If an observation inductively supports the former but not the latter, then "inductively support" must refer to something other than changes in the probabilities of propositions. A possible loophole is to interpret "All" as "Nearly all" - "Nearly all ravens are black" is not equivalent to "Nearly all non-black things are non-ravens", and these propositions can have very different probabilities.[33]

This raises the broader question of the relation of probability theory to inductive reasoning. Karl Popper argued that probability theory alone cannot account for induction. His argument involves splitting a hypothesis, $H$, into a part which is deductively entailed by the evidence, $E$, and another part. This can be done in two ways.

First, consider the splitting:[34]

$H=A\ and\ B \ \ \ \ \ \ E=B\ and\ C$

where $A$, $B$ and $C$ are probabilistically independent: $P(A\ and\ B)=P(A)P(B)$ and so on. The condition which is necessary for such a splitting of H and E to be possible is $P(H|E)>P(H)$, that is, that $H$ is probabilistically supported by $E$.

Popper's observation is that the part, $B$, of $H$ which receives support from $E$ actually follows deductively from $E$, while the part of $H$ which does not follow deductively from $E$ receives no support at all from $E$ - that is, $P(A|E)=P(A)$.

Second, the splitting:[35]

$H=(H\ or\ E)\ and\ (H\ or\ \overline{E})$

separates $H$ into $(H\ or\ E)$, which as Popper says, "is the logically strongest part of $H$ (or of the content of $H$) that follows [deductively] from $E$," and $(H\ or\ \overline{E})$, which, he says, "contains all of $H$ that goes beyond $E$." He continues:

Does $E$, in this case, provide any support for the factor $(H\ or\ \overline{E})$, which in the presence of $E$ is alone needed to obtain $H$? The answer is: No. It never does. Indeed, $E$ countersupports $(H\ or\ \overline{E})$ unless either $P(H|E)=1$ or $P(E)=1$ (which are possibilities of no interest). ...
This result is completely devastating to the inductive interpretation of the calculus of probability. All probabilistic support is purely deductive: that part of a hypothesis that is not deductively entailed by the evidence is always strongly countersupported by the evidence ... There is such a thing as probabilistic support; there might even be such a thing as inductive support (though we hardly think so). But the calculus of probability reveals that probabilistic support cannot be inductive support.

#### The orthodox approach

The orthodox Neyman-Pearson theory of hypothesis testing considers how to decide whether to accept or reject a hypothesis, rather than what probability to assign to the hypothesis. From this point of view, the hypothesis that "All ravens are black" is not accepted gradually, as its probability increases towards one when more and more observations are made, but is accepted in a single action as the result of evaluating the data which has already been collected. As Neyman and Pearson put it:

Without hoping to know whether each separate hypothesis is true or false, we may search for rules to govern our behaviour with regard to them, in following which we insure that, in the long run of experience, we shall not be too often wrong.[36]

According to this approach, it is not necessary to assign any value to the probability of a hypothesis, although one must certainly take into account the probability of the data given the hypothesis, or given a competing hypothesis, when deciding whether to accept or to reject. The acceptance or rejection of a hypothesis carries with it the risk of error.

This contrasts with the Bayesian approach, which requires that the hypothesis be assigned a prior probability, which is revised in the light of the observed data to obtain the final probability of the hypothesis. Within the Bayesian framework there is no risk of error since hypotheses are not accepted or rejected; instead they are assigned probabilities.

An analysis of the paradox from the orthodox point of view has been performed, and leads to, among other insights, a rejection of the equivalence condition:

It seems obvious that one cannot both accept the hypothesis that all P's are Q and also reject the contrapositive, i.e. that all non-Q's are non-P. Yet it is easy to see that on the Neyman-Pearson theory of testing, a test of "All P's are Q" is not necessarily a test of "All non-Q's are non-P" or vice versa. A test of "All P's are Q" requires reference to some alternative statistical hypothesis of the form $r$ of all P's are Q, $0, whereas a test of "All non-Q's are non-P" requires reference to some statistical alternative of the form $r$ of all non-Q's are non-P, $0. But these two sets of possible alternatives are different ... Thus one could have a test of $H$ without having a test of its contrapositive.[37]

#### Rejecting material implication

The following propositions all imply one another: "Every object is either black or not a raven", "Every Raven is black", and "Every non-black object is a non-raven." They are therefore, by definition, logically equivalent. However, the three propositions have different domains: the first proposition says something about "Every object", while the second says something about "Every raven".

The first proposition is the only one whose domain of quantification is unrestricted ("all objects"), so this is the only one which can be expressed in first order logic. It is logically equivalent to:

$\forall\ x, Rx\ \rightarrow\ Bx$

and also to

$\forall\ x, \overline{Bx}\ \rightarrow\ \overline{Rx}$

where $\rightarrow$ indicates the material conditional, according to which "If $A$ then $B$" can be understood to mean "$B$ or $\overline{A}$".

It has been argued by several authors that material implication does not fully capture the meaning of "If $A$ then $B$" (see the paradoxes of material implication). "For every object, $x$, $x$ is either black or not a raven" is true when there are no ravens. It is because of this that "All ravens are black" is regarded as true when there are no ravens. Furthermore, the arguments which Good and Maher used to criticize Nicod's criterion (see Good's Baby, above) relied on this fact - that "All ravens are black" is highly probable when it is highly probable that there are no ravens.

Some approaches to the paradox have sought to find other ways of interpreting "If $A$ then $B$" and "All $A$ are $B$" which would eliminate the perceived equivalence between "All ravens are black" and "All non-black things are non-ravens."

One such approach involves introducing a many-valued logic according to which "If $A$ then $B$" has the truth-value $I$, meaning "Indeterminate" or "Inappropriate" when $A$ is false.[38] In such a system, contraposition is not automatically allowed: "If $A$ then $B$" is not equivalent to "If $\overline{B}$ then $\overline{A}$". Consequently, "All ravens are black" is not equivalent to "All non-black things are non-ravens".

In this system, when contraposition occurs, the modality of the conditional involved changes from the indicative ("If that piece of butter has been heated to 32 C then it has melted") to the counterfactual ("If that piece of butter had been heated to 32 C then it would have melted"). According to this argument, this removes the alleged equivalence which is necessary to conclude that yellow cows can inform us about ravens:

In proper grammatical usage, a contrapositive argument ought not to be stated entirely in the indicative. Thus:
From the fact that if this match is scratched it will light, it follows that if it does not light it was not scratched.
is awkward. We should say:
From the fact that if this match is scratched it will light, it follows that if it were not to light it would not have been scratched. ...
One might wonder what effect this interpretation of the Law of Contraposition has on Hempel's paradox of confirmation. "If $a$ is a raven then $a$ is black" is equivalent to "If $a$ were not black then $a$ would not be a raven". Therefore whatever confirms the latter should also, by the Equivalence Condition, confirm the former. True, but yellow cows still cannot figure into the confirmation of "All ravens are black" because, in science, confirmation is accomplished by prediction, and predictions are properly stated in the indicative mood. It is senseless to ask what confirms a counterfactual.[39]

#### Differing results of accepting the hypotheses

Several commentators have observed that the propositions "All ravens are black" and "All non-black things are non-ravens" suggest different procedures for testing the hypotheses. E.g. Good writes:[40]

As propositions the two statements are logically equivalent. But they have a different psychological effect on the experimenter. If he is asked to test whether all ravens are black he will look for a raven and then decide whether it is black. But if he is asked to test whether all non-black things are non-ravens he may look for a non-black object and then decide whether it is a raven.

More recently, it has been suggested that "All ravens are black" and "All non-black things are non-ravens" can have different effects when accepted.[41] The argument considers situations in which the total numbers or prevalences of ravens and black objects are unknown, but estimated. When the hypothesis "All ravens are black" is accepted, according to the argument, the estimated number of black objects increases, while the estimated number of ravens does not change.

It can be illustrated by considering the situation of two people who have identical information regarding ravens and black objects, and who have identical estimates of the numbers of ravens and black objects. For concreteness, suppose that there are 100 objects overall, and, according to the information available to the people involved, each object is just as likely to be a non-raven as it is to be a raven, and just as likely to be black as it is to be non-black:

$P(Ra)=\frac{1}{2} \ \ \ \ \ \ \ \ P(Ba)=\frac{1}{2}$

and the propositions $Ra,\ Rb$ are independent for different objects $a$, $b$ and so on. Then the estimated number of ravens is 50; the estimated number of black things is 50; the estimated number of black ravens is 25, and the estimated number of non-black ravens (counterexamples to the hypotheses) is 25.

One of the people performs a statistical test (e.g. a Neyman-Pearson test or the comparison of the accumulated weight of evidence to a threshold) of the hypothesis that "All ravens are black", while the other tests the hypothesis that "All non-black objects are non-ravens". For simplicity, suppose that the evidence used for the test has nothing to do with the collection of 100 objects dealt with here. If the first person accepts the hypothesis that "All ravens are black" then, according to the argument, about 50 objects whose colors were previously in doubt (the ravens) are now thought to be black, while nothing different is thought about the remaining objects (the non-ravens). Consequently, he should estimate the number of black ravens at 50, the number of black non-ravens at 25 and the number of non-black non-ravens at 25. By specifying these changes, this argument explicitly restricts the domain of "All ravens are black" to ravens.

On the other hand, if the second person accepts the hypothesis that "All non-black objects are non-ravens", then the approximately 50 non-black objects about which it was uncertain whether each was a raven, will be thought to be non-ravens. At the same time, nothing different will be thought about the approximately 50 remaining objects (the black objects). Consequently, he should estimate the number of black ravens at 25, the number of black non-ravens at 25 and the number of non-black non-ravens at 50. According to this argument, since the two people disagree about their estimates after they have accepted the different hypotheses, accepting "All ravens are black" is not equivalent to accepting "All non-black things are non-ravens"; accepting the former means estimating more things to be black, while accepting the latter involves estimating more things to be non-ravens. Correspondingly, the argument goes, the former requires as evidence ravens which turn out to be black and the latter requires non-black things which turn out to be non-ravens.[42]

#### Existential presuppositions

A number of authors have argued that propositions of the form "All $A$ are $B$" presuppose that there are objects which are $A$.[43] This analysis has been applied to the raven paradox:[44]

... $H_1$: "All ravens are black" and $H_2$: "All nonblack things are nonravens" are not strictly equivalent ... due to their different existential presuppositions. Moreover, although $H_1$ and $H_2$ describe the same regularity - the nonexistence of nonblack ravens - they have different logical forms. The two hypotheses have different senses and incorporate different procedures for testing the regularity they describe.

A modified logic can take account of existential presuppositions using the presuppositional operator, '*'. For example,

$\forall\ x,\ *Rx\rightarrow Bx$

can denote "All ravens are black" while indicating that it is ravens and not non-black objects which are presupposed to exist in this example.

... the logical form of each hypothesis distinguishes it with respect to its recommended type of supporting evidence: the possibly true substitution instances of each hypothesis relate to different types of objects. The fact that the two hypotheses incorporate different kinds of testing procedures is expressed in the formal language by prefixing the operator '*' to a different predicate. The presuppositional operator thus serves as a relevance operator as well. It is prefixed to the predicate '$x$ is a raven' in $H_1$ because the objects relevant to the testing procedure incorporated in "All raven are black" include only ravens; it is prefixed to the predicate '$x$ is nonblack', in $H_2$, because the objects relevant to the testing procedure incorporated in "All nonblack things are nonravens" include only nonblack things. ... Using Fregean terms: whenever their presuppositions hold, the two hypotheses have the same referent (truth-value), but different senses; that is, they express two different ways to determine that truth-value.[45]

## Notes

1. ^ http://plato.stanford.edu/entries/hempel/
2. ^ a b Hempel, C. G. (1945). "Studies in the Logic of Confirmation I". Mind 54 (213): 1–26. doi:10.1093/mind/LIV.213.1. JSTOR 2250886.
3. ^ Hempel, C. G. (1945). "Studies in the Logic of Confirmation II". Mind 54 (214): 97–121. doi:10.1093/mind/LIV.214.97. JSTOR 2250948.
4. ^ Nicod had proposed that, in relation to conditional hypotheses, instances of their antecedents that are also instances of their consequents confirm them; instances of their antecedents that are not instances of their consequents disconfirm them; and non-instantiations of their antecedents are neutral, neither confirming nor disconfirming. Stanford Encyclopedia of Philosophy
5. ^ Swinburne, R. 1971. The Paradoxes of Confirmation – A Survey, American Philosophical Quarterly, 8, 318–30.
6. ^ Maher, P. (1999). "Inductive Logic and the Ravens Paradox". Philosophy of Science 66 (1): 50–70. doi:10.1086/392676. JSTOR 188737.
7. ^ Good, IJ (1960) The Paradox of Confirmation, The British Journal for the Philosophy of Science, Vol. 11, No. 42, 145-149 JSTOR
8. ^ Fitelson, B and Hawthorne, J (2006) How Bayesian Confirmation Theory Handles the Paradox of the Ravens, in Probability in Science, Chicago: Open Court Link
9. ^ Alexander, HG (1958) The Paradoxes of Confirmation, The British Journal for the Philosophy of Science, Vol. 9, No. 35, P. 227 JSTOR
10. ^ Hosaisson-Lindenbaum, J (1940) On Confirmation, The Journal of Symbolic Logic, Vol. 5, No. 4, p. 133 JSTOR
11. ^ Note: Good used "crow" instead of "raven", but "raven" has been used here throughout for consistency.
12. ^ Chihara, (1987) Some Problems for Bayesian Confirmation Theory, British Journal for the Philosophy of Science, Vol. 38, No. 4 LINK
13. ^ Earman, 1992 Bayes or Bust? A Critical Examination of Bayesian Confirmation Theory, MIT Press, Cambridge, MA.
14. ^ Eells, 1982 Rational Decision and Causality. New York: Cambridge University Press
15. ^ Gibson, 1969 On Ravens and Relevance and a Likelihood Solution of the Paradox of Confirmation, LINK
16. ^ Hosaisson-Lindenbaum 1940
17. ^ Howson, Urbach, 1993 Scientific Reasoning: The Bayesian Approach, Open Court Publishing Company
18. ^ Mackie, 1963 The Paradox of Confirmation, Brit. J. Phil. Sci. Vol. 13, No. 52, p. 265 LINK
19. ^ a b Hintikka, 1969
20. ^ Humburg 1986, The solution of Hempel's raven paradox in Rudolf Carnap's system of inductive logic, Erkenntnis, Vol. 24, No. 1, pp
21. ^ Maher 1999
22. ^ Fitelson 2006
23. ^ Vranas (2002) Hempel's Raven Paradox: A Lacuna in the Standard Bayesian Solution LINK
24. ^ a b Maher, 1999
25. ^ a b Fitelson, 2006
26. ^ Good, I. J. (1967). "The White Shoe is a Red Herring". British Journal for the Philosophy of Science 17 (4): 322. doi:10.1093/bjps/17.4.322. JSTOR 686774.
27. ^ Hempel 1967, The White Shoe - No Red Herring, The British Journal for the Philosophy of Science, Vol. 18, No. 3, p. 239 JSTOR
28. ^ Good, I. J. (1968). "The White Shoe qua Red Herring is Pink". The British Journal for the Philosophy of Science 19 (2): 156. doi:10.1093/bjps/19.2.156. JSTOR 686795.
29. ^ Maher 2004, Probability Captures the Logic of Scientific Confirmation LINK
30. ^ Quine, W. V. (1969). Natural Kinds, in Ontological Relativity and other Essays. New York: Columbia University Press. p. 114.
31. ^ Hintikka J. 1969, Inductive Independence and the Paradoxes of Confirmation LINK
32. ^ Scheffler I, Goodman NJ, Selective Confirmation and the Ravens, Journal of Philosophy, Vol. 69, No. 3, 1972 JSTOR
33. ^ Gaifman, H. (1979). "Subjective Probability, Natural Predicates and Hempel's Ravens". Erkenntnis 14 (2): 105–147. doi:10.1007/BF00196729.
34. ^ Popper, K. Realism and the Aim of Science, Routlege, 1992, p. 325
35. ^ Popper K, Miller D, (1983) A Proof of the Impossibility of Inductive Probability, Nature, Vol. 302, p. 687 Link
36. ^ Neyman J, Pearson ES (1933) On the Problem of the Most Efficient Tests of Statistical Hypotheses, Phil. Transactions of the Royal Society of London. Series A, Vol. 231, p289 JSTOR
37. ^ Giere, RN (1970) An Orthodox Statistical Resolution of the Paradox of Confirmation, Philosophy of Science, Vol. 37, No. 3, p.354 JSTOR
38. ^ Farrell RJ (1979) Material Implication, Confirmation and Counterfactuals LINK
39. ^ Farrell (1979)
40. ^ Good (1960)
41. ^ O'Flanagan (2008) Judgment LINK
42. ^ O'Flanagan (2008)
43. ^ Strawson PF (1952) Introduction to Logical Theory, methuan & Co. London, John Wiley & Sons, New York
44. ^ Cohen Y (1987) Ravens and Relevance, Erkenntnis LINK
45. ^ Cohen (1987)

## References

• Franceschi, P. The Doomsday Argument and Hempel's Problem, English translation of a paper initially published in French in the Canadian Journal of Philosophy 29, 139-156, 1999, under the title Comment l'urne de Carter et Leslie se déverse dans celle de Hempel
• Hempel, C. G. A Purely Syntactical Definition of Confirmation. J. Symb. Logic 8, 122-143, 1943.
• Hempel, C. G. Studies in the Logic of Confirmation (I) Mind 54, 1-26, 1945.
• Hempel, C. G. Studies in the Logic of Confirmation (II) Mind 54, 97-121, 1945.
• Hempel, C. G. Studies in the Logic of Confirmation. In Marguerite H. Foster and Michael L. Martin, eds. Probability, Confirmation, and Simplicity. New York: Odyssey Press, 1966. 145-183.
• Whiteley, C. H. Hempel's Paradoxes of Confirmation. Mind 54, 156-158, 1945.


text:
# American Institute of Mathematical Sciences

August  2022, 15(8): 2033-2052. doi: 10.3934/dcdss.2022092

## A moving boundary problem for reaction and diffusion processes in concrete: Carbonation advancement and carbonation shrinkage

 Istituto per le Applicazioni del Calcolo "Mauro Picone", Consiglio Nazionale delle Ricerche, via dei Taurini 19, 00185, Roma, Italy

* Corresponding author: Roberto Natalini

Received  February 2022 Published  August 2022 Early access  April 2022

The present work is devoted to modeling and simulation of the carbonation process in concrete. To this aim we introduce some free boundary problems which describe the evolution of calcium carbonate stones under the attack of ${CO}_2$ dispersed in the atmosphere, taking into account both the shrinkage of concrete and the influence of humidity on the carbonation process. Indeed, two different regimes are described according to the relative humidity in the environment. Finally, some numerical simulations here presented are in substantial accordance with experimental results taken from literature.

Citation: Gabriella Bretti, Maurizio Ceseri, Roberto Natalini. A moving boundary problem for reaction and diffusion processes in concrete: Carbonation advancement and carbonation shrinkage. Discrete and Continuous Dynamical Systems - S, 2022, 15 (8) : 2033-2052. doi: 10.3934/dcdss.2022092
##### References:
 [1] W. Ashraf, Carbonation of cement-based materials: Challenges and opportunities, Construction and Building Materials, 120 (2016), 558-570. [2] G. Bretti, M. Ceseri, M. C. Ciacchella, R. Natalini, M. L. Santarelli and G. Tiracorrendo, A forecasting model for the porosity variation during the carbonation process, International Journal on Geomathematics, 2022. Submitted [3] G. Bretti, L. Gosse and N. Vauchelet, Diffusive limits of 2D well-balanced schemes for kinetic models of neutron transport, ESAIM Math. Model. Numer. Anal., 55 (2021), 2949-2980.  doi: 10.1051/m2an/2021077. [4] M. Ceseri and J. M. Stockie, A three-phase free boundary problem with melting ice and dissolving gas, European J. Appl. Math., 25 (2014), 449-480.  doi: 10.1017/S0956792513000430. [5] F. Clarelli, A. Fasano and R. Natalini, Mathematics and monument conservation: Free boundary models of marble sulfation, SIAM J. Appl. Math., 69 (2008), 149-168.  doi: 10.1137/070695125. [6] F. Freddi and L. Mingazzi, Phase-field simulations of cover cracking in corroded RC beams, Procedia Structural Integrity, 33 (2021), 371-384. [7] R. M. Furzeland, A comparative study of numerical methods for moving boundary problems, J. Inst. Math. Appl., 26 (1980), 411-429.  doi: 10.1093/imamat/26.4.411. [8] Lindsey L Climate Change: Atmospheric Carbon Dioxide, 2020. https://www.climate.gov/news-features/understanding-climate/climate-change-atmospheric-carbon-dioxide (Accessed: 18 March 2022). [9] S. Kashef-Haghighi, Y. Shao and S. Ghoshal, Mathematical modeling of CO2 uptake by concrete during accelerated carbonation curing, Cement and Concrete Research, 67, 20151–0. [10] C. A. Kennedy and M. H. Carpenter, Additive Runge-Kutta schemes for convection-diffusion-reaction equations, Appl. Numer. Math., 44 (2003), 139-181.  doi: 10.1016/S0168-9274(02)00138-1. [11] K. Kovler and S. Zhutovsky, Overview and future trends of shrinkage research, Materials and Structures, 39 (2006), 827-847. [12] A. Leemann and F. Moro, Carbonation of concrete: The role of CO2 concentration, relative humidity and CO2 buffer capacity, Materials and Structures, 50 (2017), 1-4. [13] F. Matsushita, Y. Aono and S. Shibata, Calcium silicate structure and carbonation shrinkage of a tobermorite-based material, Cement and Concrete Research, 34 (2004), 1251-1257. [14] I. Monteiro, F. A. Branco, J. de Brito and R. Neves, Statistical analysis of the carbonation coefficient in open air concrete structures, Construction and Building Materials, 29 (2012), 263-269. [15] G. Pan and Q. Shen abd J. Li, Microstructure of cement paste at different carbon dioxide concentrations, Magazine of Concrete Research, 70 (2018), 154-162. [16] V. G. Papadakis, C. G. Vayenas and M. N. Fardis, Experimental investigation and mathematical modeling of the concrete carbonation problem, Chemical Engineering Science, 46 (1991), 1333-1338. [17] L. Pareschi and G. Russo, Implicit-Explicit Runge-Kutta schemes and applications to hyperbolic systems with relaxation, J. Sci. Comput., 25 (2005), 129-155.  doi: 10.1007/s10915-004-4636-4. [18] M. A. Peter, A. Muntean, S. A. Meier and M. Böhm, Competition of several carbonation reactions in concrete: A parametric study, Cement and Concrete Research, 38 (2008), 1385-1393. [19] B. Šavija and M. Luković, Carbonation of cement paste: Understanding, challenges, and opportunities, Construction and Building Materials, 117 (2016), 285-301. [20] A. Steffens, D. Dinkler and H. Ahrens, Modeling carbonation for corrosion risk prediction of concrete structures, Cement and Concrete Research, 32 (2002), 935-941. [21] Y. Sumra, S. Payam and I. Zainah, The pH of cement-based materials: A review, Journal of Wuhan University of Technology-Mater. Sci. Ed., 35 (2020), 908-924. [22] F. P. Torgal, S. Miraldo, J. A. Labrincha and J. De Brito, An overview on concrete carbonation in the context of eco-efficient construction: Evaluation, use of SCMs and/or RAC, Construction and Building Materials, 36 (2012), 141-150.

show all references

##### References:
 [1] W. Ashraf, Carbonation of cement-based materials: Challenges and opportunities, Construction and Building Materials, 120 (2016), 558-570. [2] G. Bretti, M. Ceseri, M. C. Ciacchella, R. Natalini, M. L. Santarelli and G. Tiracorrendo, A forecasting model for the porosity variation during the carbonation process, International Journal on Geomathematics, 2022. Submitted [3] G. Bretti, L. Gosse and N. Vauchelet, Diffusive limits of 2D well-balanced schemes for kinetic models of neutron transport, ESAIM Math. Model. Numer. Anal., 55 (2021), 2949-2980.  doi: 10.1051/m2an/2021077. [4] M. Ceseri and J. M. Stockie, A three-phase free boundary problem with melting ice and dissolving gas, European J. Appl. Math., 25 (2014), 449-480.  doi: 10.1017/S0956792513000430. [5] F. Clarelli, A. Fasano and R. Natalini, Mathematics and monument conservation: Free boundary models of marble sulfation, SIAM J. Appl. Math., 69 (2008), 149-168.  doi: 10.1137/070695125. [6] F. Freddi and L. Mingazzi, Phase-field simulations of cover cracking in corroded RC beams, Procedia Structural Integrity, 33 (2021), 371-384. [7] R. M. Furzeland, A comparative study of numerical methods for moving boundary problems, J. Inst. Math. Appl., 26 (1980), 411-429.  doi: 10.1093/imamat/26.4.411. [8] Lindsey L Climate Change: Atmospheric Carbon Dioxide, 2020. https://www.climate.gov/news-features/understanding-climate/climate-change-atmospheric-carbon-dioxide (Accessed: 18 March 2022). [9] S. Kashef-Haghighi, Y. Shao and S. Ghoshal, Mathematical modeling of CO2 uptake by concrete during accelerated carbonation curing, Cement and Concrete Research, 67, 20151–0. [10] C. A. Kennedy and M. H. Carpenter, Additive Runge-Kutta schemes for convection-diffusion-reaction equations, Appl. Numer. Math., 44 (2003), 139-181.  doi: 10.1016/S0168-9274(02)00138-1. [11] K. Kovler and S. Zhutovsky, Overview and future trends of shrinkage research, Materials and Structures, 39 (2006), 827-847. [12] A. Leemann and F. Moro, Carbonation of concrete: The role of CO2 concentration, relative humidity and CO2 buffer capacity, Materials and Structures, 50 (2017), 1-4. [13] F. Matsushita, Y. Aono and S. Shibata, Calcium silicate structure and carbonation shrinkage of a tobermorite-based material, Cement and Concrete Research, 34 (2004), 1251-1257. [14] I. Monteiro, F. A. Branco, J. de Brito and R. Neves, Statistical analysis of the carbonation coefficient in open air concrete structures, Construction and Building Materials, 29 (2012), 263-269. [15] G. Pan and Q. Shen abd J. Li, Microstructure of cement paste at different carbon dioxide concentrations, Magazine of Concrete Research, 70 (2018), 154-162. [16] V. G. Papadakis, C. G. Vayenas and M. N. Fardis, Experimental investigation and mathematical modeling of the concrete carbonation problem, Chemical Engineering Science, 46 (1991), 1333-1338. [17] L. Pareschi and G. Russo, Implicit-Explicit Runge-Kutta schemes and applications to hyperbolic systems with relaxation, J. Sci. Comput., 25 (2005), 129-155.  doi: 10.1007/s10915-004-4636-4. [18] M. A. Peter, A. Muntean, S. A. Meier and M. Böhm, Competition of several carbonation reactions in concrete: A parametric study, Cement and Concrete Research, 38 (2008), 1385-1393. [19] B. Šavija and M. Luković, Carbonation of cement paste: Understanding, challenges, and opportunities, Construction and Building Materials, 117 (2016), 285-301. [20] A. Steffens, D. Dinkler and H. Ahrens, Modeling carbonation for corrosion risk prediction of concrete structures, Cement and Concrete Research, 32 (2002), 935-941. [21] Y. Sumra, S. Payam and I. Zainah, The pH of cement-based materials: A review, Journal of Wuhan University of Technology-Mater. Sci. Ed., 35 (2020), 908-924. [22] F. P. Torgal, S. Miraldo, J. A. Labrincha and J. De Brito, An overview on concrete carbonation in the context of eco-efficient construction: Evaluation, use of SCMs and/or RAC, Construction and Building Materials, 36 (2012), 141-150.
The geometrical depiction of the setting we considered for the molar mass conservation, eq. (2). The grey area indicates the non-carbonated region while the light blue area indicates the carbonated one
Spatial evolution of $c$ for the case of concentration at $3\%$ at different times. The depicted results are obtained for grid spacing $\Delta \zeta = 0.1, \Delta t = 10^{-7}$
Relationship between carbonation depth and $\sqrt{t}$ for different concentration of pollutant. Plot of experimental data (red circles), theoretical slope (black dotted line) $K \sqrt{t}$ taken from [15] against numerical results obtained with the proposed model (magenta solid line) at time $t = 28$ days for $3\%$ (top figure) and $20\%$ (bottom figure) concentration of carbon dioxide
Carbonation front $\sigma$ and $\sigma_0 = \omega \sigma$
The evolution of carbonation shrinkage strain according to simulation results
The physical and chemical constants used in our mathematical model. Most of these represent typical values of characteristic properties of the materials under consideration. The value of $n_c$ has been found in [15,Table 7], that of $c^*$ in [8] and, that of $W^*$ in [5,Table 2]
 Parameter Meaning Value Dimension $\mu_c$ Molar Density of $CaCO_3$ $0.027086$ $mol\cdot cm^{-3}$ $\mu_h$ Molar Density of $Ca(OH)_2$ $0.02984$ $mol\cdot cm^{-3}$ $n_h$ Portland Cement porosity $0.2$ - $n_c$ Calcium Carbonate porosity $0.05$ - $t^*$ reference time (1 year) $3.1536 \cdot 10^{7}$ $s$ $c^*$ reference density ($CO_2$) $4.098 \cdot 10^{-4}$ $g \cdot cm^{-3}$ $W^*$ reference density ($H_2 O$) $17.3\cdot 10^{-6}$ $g \cdot cm^{-3}$ $M_w$ Molar weight (water) $18.01528$ $g\cdot mol^{-1}$ $M_c$ Molar weight ($CaCO_3$) $100.0869$ $g\cdot mol^{-1}$ $M_{cd}$ Molar weight ($CO_2$) $44.01$ $g\cdot mol^{-1}$
 Parameter Meaning Value Dimension $\mu_c$ Molar Density of $CaCO_3$ $0.027086$ $mol\cdot cm^{-3}$ $\mu_h$ Molar Density of $Ca(OH)_2$ $0.02984$ $mol\cdot cm^{-3}$ $n_h$ Portland Cement porosity $0.2$ - $n_c$ Calcium Carbonate porosity $0.05$ - $t^*$ reference time (1 year) $3.1536 \cdot 10^{7}$ $s$ $c^*$ reference density ($CO_2$) $4.098 \cdot 10^{-4}$ $g \cdot cm^{-3}$ $W^*$ reference density ($H_2 O$) $17.3\cdot 10^{-6}$ $g \cdot cm^{-3}$ $M_w$ Molar weight (water) $18.01528$ $g\cdot mol^{-1}$ $M_c$ Molar weight ($CaCO_3$) $100.0869$ $g\cdot mol^{-1}$ $M_{cd}$ Molar weight ($CO_2$) $44.01$ $g\cdot mol^{-1}$
Values for the parameter $\sigma^*$, $D_c$ and, $D_w$, determined by the procedures detailed. The values listed for $D_w$ are the lower bounds determined by equation (67). Note that the environmental $CO_2$ is converted from percentage concentration to $g/cm^3$ by applying formula (65)
 Parameter Value Dimension Environmental $CO_2$ $\sigma^*$ $2.87$ $cm$ $3\%$ $D_c$ $5.8\cdot 10^{-2}$ $cm^2\cdot sec^{-1}$ $3\%$ $D_w$ $1.1\cdot 10^{-1}$ $cm^2\cdot sec^{-1}$ $3\%$ $\sigma^*$ $5.69$ $cm$ $20\%$ $D_c$ $3.7\cdot 10^{-2}$ $cm^2\cdot sec^{-1}$ $20\%$ $D_w$ $4.5\cdot 10^{-1}$ $cm^2\cdot sec^{-1}$ $20\%$
 Parameter Value Dimension Environmental $CO_2$ $\sigma^*$ $2.87$ $cm$ $3\%$ $D_c$ $5.8\cdot 10^{-2}$ $cm^2\cdot sec^{-1}$ $3\%$ $D_w$ $1.1\cdot 10^{-1}$ $cm^2\cdot sec^{-1}$ $3\%$ $\sigma^*$ $5.69$ $cm$ $20\%$ $D_c$ $3.7\cdot 10^{-2}$ $cm^2\cdot sec^{-1}$ $20\%$ $D_w$ $4.5\cdot 10^{-1}$ $cm^2\cdot sec^{-1}$ $20\%$
Slope of the curve (4) for the two concentrations of ${CO}_2$ in the accelerated carbonation process. Data taken from [15]
 $CO_2$ concentration $K$ dimensions $3\%$ $1.5$ $mm\;d^{-1/2}$ $20\%$ $2.98$ $mm\;d^{-1/2}$
 $CO_2$ concentration $K$ dimensions $3\%$ $1.5$ $mm\;d^{-1/2}$ $20\%$ $2.98$ $mm\;d^{-1/2}$
Average percentage error (68) between simulated and experimental carbonation depth
 Carbon dioxide concentration Average $\%$ error $3\%$ $0.1\%$ $20\%$ $0.4\%$
 Carbon dioxide concentration Average $\%$ error $3\%$ $0.1\%$ $20\%$ $0.4\%$
Numerical accuracy of the approximation scheme in the computation of $w$
 Norm $\gamma_w$ $L^1$ $1.0$ $L^\infty$ $1.0$
 Norm $\gamma_w$ $L^1$ $1.0$ $L^\infty$ $1.0$
 [1] Kota Kumazaki. A mathematical model of carbon dioxide transport in concrete carbonation process. Discrete and Continuous Dynamical Systems - S, 2014, 7 (1) : 113-125. doi: 10.3934/dcdss.2014.7.113 [2] Claire david@lmm.jussieu.fr David, Pierre Sagaut. Theoretical optimization of finite difference schemes. Conference Publications, 2007, 2007 (Special) : 286-293. doi: 10.3934/proc.2007.2007.286 [3] Marcel Braukhoff, Ansgar Jüngel. Entropy-dissipating finite-difference schemes for nonlinear fourth-order parabolic equations. Discrete and Continuous Dynamical Systems - B, 2021, 26 (6) : 3335-3355. doi: 10.3934/dcdsb.2020234 [4] Emma Hoarau, Claire david@lmm.jussieu.fr David, Pierre Sagaut, Thiên-Hiêp Lê. Lie group study of finite difference schemes. Conference Publications, 2007, 2007 (Special) : 495-505. doi: 10.3934/proc.2007.2007.495 [5] Laurent Devineau, Pierre-Edouard Arrouy, Paul Bonnefoy, Alexandre Boumezoued. Fast calibration of the Libor market model with stochastic volatility and displaced diffusion. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1699-1729. doi: 10.3934/jimo.2019025 [6] Toyohiko Aiki, Adrian Muntean. On uniqueness of a weak solution of one-dimensional concrete carbonation problem. Discrete and Continuous Dynamical Systems, 2011, 29 (4) : 1345-1365. doi: 10.3934/dcds.2011.29.1345 [7] Gianluca Frasca-Caccia, Peter E. Hydon. Locally conservative finite difference schemes for the modified KdV equation. Journal of Computational Dynamics, 2019, 6 (2) : 307-323. doi: 10.3934/jcd.2019015 [8] Roumen Anguelov, Jean M.-S. Lubuma, Meir Shillor. Dynamically consistent nonstandard finite difference schemes for continuous dynamical systems. Conference Publications, 2009, 2009 (Special) : 34-43. doi: 10.3934/proc.2009.2009.34 [9] Eduardo Casas, Boris Vexler, Enrique Zuazua. Sparse initial data identification for parabolic PDE and its finite element approximations. Mathematical Control and Related Fields, 2015, 5 (3) : 377-399. doi: 10.3934/mcrf.2015.5.377 [10] Michael Eden, Michael Böhm. Homogenization of a poro-elasticity model coupled with diffusive transport and a first order reaction for concrete. Networks and Heterogeneous Media, 2014, 9 (4) : 599-615. doi: 10.3934/nhm.2014.9.599 [11] Robert Stephen Cantrell, Xinru Cao, King-Yeung Lam, Tian Xiang. A PDE model of intraguild predation with cross-diffusion. Discrete and Continuous Dynamical Systems - B, 2017, 22 (10) : 3653-3661. doi: 10.3934/dcdsb.2017145 [12] Toyohiko Aiki, Adrian Muntean. Large time behavior of solutions to a moving-interface problem modeling concrete carbonation. Communications on Pure and Applied Analysis, 2010, 9 (5) : 1117-1129. doi: 10.3934/cpaa.2010.9.1117 [13] Yuan Li, Lei Yan, Lingbo Wang, Wei Hou. Estimation of normal distribution parameters and its application to carbonation depth of concrete girder bridges. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1091-1100. doi: 10.3934/dcdss.2019075 [14] Hongsong Feng, Shan Zhao. A multigrid based finite difference method for solving parabolic interface problem. Electronic Research Archive, 2021, 29 (5) : 3141-3170. doi: 10.3934/era.2021031 [15] Adam M. Oberman. Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian. Discrete and Continuous Dynamical Systems - B, 2008, 10 (1) : 221-238. doi: 10.3934/dcdsb.2008.10.221 [16] Bernard Ducomet, Alexander Zlotnik, Ilya Zlotnik. On a family of finite-difference schemes with approximate transparent boundary conditions for a generalized 1D Schrödinger equation. Kinetic and Related Models, 2009, 2 (1) : 151-179. doi: 10.3934/krm.2009.2.151 [17] Lih-Ing W. Roeger. Dynamically consistent discrete Lotka-Volterra competition models derived from nonstandard finite-difference schemes. Discrete and Continuous Dynamical Systems - B, 2008, 9 (2) : 415-429. doi: 10.3934/dcdsb.2008.9.415 [18] Ronald E. Mickens. A nonstandard finite difference scheme for the drift-diffusion system. Conference Publications, 2009, 2009 (Special) : 558-563. doi: 10.3934/proc.2009.2009.558 [19] Boris Andreianov, Mostafa Bendahmane, Kenneth H. Karlsen, Charles Pierre. Convergence of discrete duality finite volume schemes for the cardiac bidomain model. Networks and Heterogeneous Media, 2011, 6 (2) : 195-240. doi: 10.3934/nhm.2011.6.195 [20] Takeshi Fukao, Shuji Yoshikawa, Saori Wada. Structure-preserving finite difference schemes for the Cahn-Hilliard equation with dynamic boundary conditions in the one-dimensional case. Communications on Pure and Applied Analysis, 2017, 16 (5) : 1915-1938. doi: 10.3934/cpaa.2017093

2021 Impact Factor: 1.865

format: plain


text:
# Math Help - [SOLVED] the cardinal number of a finite local ring

1. ## [SOLVED] the cardinal number of a finite local ring

If $R$ is a finite local commutative ring having residue field(= $R/M$ where $M$ is the unique maximal ideal of $R$) consisting of $p^n$ elements ( $p=$ prime integer) then prove that the cardinal number of $R$ is $p^{nm}$ i.e. $|R|=p^{nm}$ where $m$ denotes the length of the (Artinian) ring $R$.

2. Originally Posted by xixi
If $R$ is a finite local commutative ring having residue field(= $R/M$ where $M$ is the unique maximal ideal of $R$) consisting of $p^n$ elements ( $p=$ prime integer) then prove that the cardinal number of $R$ is $p^{nm}$ i.e. $|R|=p^{nm}$ where $m$ denotes the length of the (Artinian) ring $R$.
every simple module over a commutative ring $R$ is isomorphic with $R/I,$ where $I$ is some maximal ideal of $R.$ now your ring has only one maximal ideal $M$ and so if $N$ is a simple $R$ module, then

$N \cong R/M.$ In particular $|N|=|R/M|=p^n.$ now let $(0)=M_0 < M_1 < \cdots < M_{m-1}=M < M_m=R$ be a composition series for $R.$ then $|M_i/M_{i-1}|=p^n,$ for all $1 \leq i \leq m,$ because every

$M_i/M_{i-1}$ is a simple $R$ module. therefore $|R|=|M_m|=\prod_{i=1}^m |M_i|/|M_{i-1}|=\prod_{i=1}^m |M_i/M_{i-1}|=\prod_{i=1}^m p^n=p^{mn}.$

3. ## Thanks

Originally Posted by NonCommAlg
every simple module over a commutative ring $R$ is isomorphic with $R/I,$ where $I$ is some maximal ideal of $R.$ now your ring has only one maximal ideal $M$ and so if $N$ is a simple $R$ module, then

$N \cong R/M.$ In particular $|N|=|R/M|=p^n.$ now let $(0)=M_0 < M_1 < \cdots < M_{m-1}=M < M_m=R$ be a composition series for $R.$ then $|M_i/M_{i-1}|=p^n,$ for all $1 \leq i \leq m,$ because every

$M_i/M_{i-1}$ is a simple $R$ module. therefore $|R|=|M_m|=\prod_{i=1}^m |M_i|/|M_{i-1}|=\prod_{i=1}^m |M_i/M_{i-1}|=\prod_{i=1}^m p^n=p^{mn}.$
Thank YOU very much !


text:
# All Questions

38 views

### Futures Holiday Schedule

I am trying to find a place where I can get S&P Emini contract trading days. I would like to get the contract first appearance (September 9th 1997) until today. I can get Holidays but nothing ...
61 views

### What is the tail index for NIG and/or VG?

...as a function of NIG (Normal Inverse Gaussian) or VG (Variance Gamma) parameters, obviously. I've read that the NIG $\alpha$ is related to the $\alpha$-stable tail parameter, which conversely maps ...
198 views

93 views

### Put-Call Parity Arbitrage Exploitation for Binary-Asset-or-Nothing Options

Is the Put-Call-Parity valid for binary (asset-or-nothing) options? If not, is there another formula for such exotic options? I know that for regular options, there are arbitrage opportunities when ...
49 views

### Projecting cash flows via Monte Carlo Simulation

I am looking to model the cash flows associated with a company as part of a Project finance experiment, where I got the idea from here. I'm looking to project cash flows for an Automotive company in ...
148 views

### Historical calibration of Hull-White model

I have a question concerning 1-factor Hull-White model. For my master project I need to calibrate it to compute Counterparty credit risk metrics. I know that the model might be calibrated either for ...


text:
New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Uniform Limit Theorems for Sums of Independent Random Variables
 SEARCH THIS BOOK:
Proceedings of the Steklov Institute of Mathematics
1988; 222 pp; softcover
Volume: 174
Reprint/Revision History:
reprinted 1989
ISBN-10: 0-8218-3118-6
ISBN-13: 978-0-8218-3118-2
List Price: US$151 Member Price: US$120.80
Order Code: STEKLO/174

Among the diverse constructions studied in modern probability theory, the scheme for summation of independent random variables occupies a special place. In the study of even this comparatively simple scheme it is possible to become familiar with the fundamental regularities characterizing the cumulative influence of a large number of random factors. Further, this abstract model is useful in many important practical situations.

This book is devoted to the study of distributions of sums of independent random variables with minimal restrictions imposed on their distributions. The authors assume either that the distributions of the terms are concentrated on some finite interval to within a small mass, or that all the terms have the same, but arbitrary, distribution (or other conditions not connected with moment restrictions are introduced). Surprisingly, very substantive results are possible even under such a general statement of the problems.


text:
# Equipartition

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
 This article is a 'stub' page, it has no, or next to no, content. It is here at the moment to help form part of the structure of SklogWiki. If you add sufficient material to this article then please remove the {{Stub-general}} template from this page.

Equipartition usually refers to the fact that

in classical statistical mechanics each degree of freedom that appears quadratically in the energy (Hamiltonian) has an average value of $\frac{1}{2}k_B T$, where $k_B T$ is the thermal energy.

Thus, the thermal energy is shared equally ("equipartitioned") by all these degrees of freedom. This is a consequence of the equipartition theorem, which is very simple mathematically. As an immediate corollary, the translational energy of a molecule must equal $\frac{3}{2}k_B T$, since translations are described by three degrees of freedom.

For elastic waves, equipartition refers to the fact that the average potential and kinetic energies are equal (and therefore equal to half the total energy, which is thereby "equipartitioned".)


text:
1.4k+

# Trees

Authored by: Dinesh P. Mehta

# Handbook of Data Structures and Applications

Print publication date:  March  2018
Online publication date:  February  2018

Print ISBN: 9781498701853
eBook ISBN: 9781315119335

10.1201/9781315119335-3

#### Abstract

The tree is a natural representation for hierarchical information. Thus, trees are used to represent genealogical information (e.g., family trees and evolutionary trees), organizational charts in large companies, the directory structure of a file system on a computer, parse trees in compilers and the structure of a knock-out sports tournament. The Dewey decimal notation, which is used to classify books in a library, is also a tree structure. In addition to these and other applications, the tree is used to design fast algorithms in computer science because of its efficiency relative to the simpler data structures discussed in Chapter 2. Operations that take linear time on these structures often take logarithmic time on an appropriately organized tree structure. For example, the average time complexity for a search on a key is linear on a linked list and logarithmic on a binary search tree. Many of the data structures discussed in succeeding chapters of this handbook are tree structures.

#### 3.1  Introduction

The tree is a natural representation for hierarchical information. Thus, trees are used to represent genealogical information (e.g., family trees and evolutionary trees), organizational charts in large companies, the directory structure of a file system on a computer, parse trees in compilers and the structure of a knock-out sports tournament. The Dewey decimal notation, which is used to classify books in a library, is also a tree structure. In addition to these and other applications, the tree is used to design fast algorithms in computer science because of its efficiency relative to the simpler data structures discussed in Chapter 2. Operations that take linear time on these structures often take logarithmic time on an appropriately organized tree structure. For example, the average time complexity for a search on a key is linear on a linked list and logarithmic on a binary search tree. Many of the data structures discussed in succeeding chapters of this handbook are tree structures.

Several kinds of trees have been defined in the literature:

1. Free or unrooted tree: this is defined as a graph (a set of vertices and a set of edges that join pairs of vertices) such that there exists a unique path between any two vertices in the graph. The minimum spanning tree of a graph is a well-known example of a free tree. Graphs are discussed in Chapter 4.
2. Rooted tree: a finite set of one or more nodes such that
• There is a special node called the root.
• The remaining nodes are partitioned into n ≥ 0 disjoint sets T 1,…, T n , where each of these sets is a tree. T 1,…, T n are called the subtrees of the root.
If the order in which the subtrees are arranged is not important, then the tree is a rooted, unordered (or oriented) tree. If the order of the subtrees is important, the tree is rooted and ordered. Figure 3.1 depicts the relationship between the three types of trees. We will henceforth refer to the rooted, ordered tree simply as “tree.”
3. k-ary tree: a finite set of nodes that is either empty or consists of a root and the elements of k disjoint k-ary trees called the 1st, 2nd, …, kth subtrees of the root. The binary tree is a k-ary tree with k = 2. Here, the first and second subtrees are respectively called the left and right subtrees of the root. Note that binary trees are not trees. One difference is that a binary tree can be empty, whereas a tree cannot. Second, the two trees shown in Figure 3.2 are different binary trees but would be different drawings of the same tree.

Figure 3.1   The three trees shown are distinct if they are viewed as rooted, ordered trees. The first two are identical if viewed as oriented trees. All three are identical if viewed as free trees.

Figure 3.2   Different binary trees.

Figure 3.3 shows a tree with 11 nodes. The number of subtrees of a node is its degree. Nodes with degree 0 are called leaf nodes. Thus, node A has degree 3, nodes B, D, and I have degree 2, node E has degree 1, and nodes C, F, G, H, J, and K have degree 0 (and are leaves of the tree). The degree of a tree is the maximum of the degree of the nodes in the tree. The roots of the subtrees of a node X are its children. X is the parent of its children. Children of the same parent are siblings. In the example, B, C, and D are each other's siblings and are all children of A. The ancestors of a node are all the nodes excluding itself along the path from the root to that node. The level of a node is defined by letting the root be at level zero. If a node is at level l, then its children are at level l + 1. The height of a tree is the maximum level of any node in the tree. The tree in the example has height 4. These terms are defined in the same way for binary trees. See [1–6] for more information on trees.

Figure 3.3   An example tree.

#### 3.2.1  List Representation

The tree of Figure 3.3 can be written as the generalized list (A (B (E (I (J, K)), F), C, D(G, H))). The information in the root node comes first followed by a list of subtrees of the root. This enables us to represent a tree in memory using generalized lists as discussed in Chapter 2.

#### 3.2.2  Left Child-Right Sibling Representation

Figure 3.4a shows the node structure used in this representation. Each node has a pointer to its leftmost child (if any) and to the sibling on its immediate right (if any). The tree in Figure 3.3 is represented by the tree in Figure 3.4b.

Figure 3.4   Tree representations.

#### 3.2.3  Binary Tree Representation

Observe that the left child-right sibling representation of a tree (Figure 3.4b) may be viewed as a binary tree by rotating it clockwise by 45 degrees. This gives the binary tree representation shown in Figure 3.4c. This representation can be extended to represent a forest, which is defined as an ordered set of trees. Here, the roots of the trees are viewed as siblings. Thus, a root's right pointer points to the next tree root in the set. We have

There is a one-to-one correspondence between the set of forests and the set of binary trees.

#### 3.3  Binary Trees and Properties

Binary trees were defined in Section 3.1. For convenience, a binary tree is sometimes extended by adding external nodes. External nodes are imaginary nodes that are added wherever an empty subtree was present in the original tree. The original tree nodes are known as internal nodes. Figure 3.5a shows a binary tree and (b) the corresponding extended tree. Observe that in an extended binary tree, all internal nodes have degree 2 while all external nodes have degree 0. (Some authors use the term full binary tree to denote a binary tree whose nodes have 0 or two children.) The external path length of a tree is the sum of the lengths of all root-to-external node paths in the tree. In the example, this is 2 + 2 + 3 + 3 + 2 = 12. The internal path length is similarly defined by adding lengths of all root-to-internal node paths. In the example, this quantity is 0 + 1 + 1 + 2 = 4.

Figure 3.5   (b) shows the extended binary tree corresponding to the binary tree of (a). External nodes are depicted by squares.

#### 3.3.1  Properties

A binary tree with n internal nodes has n + 1 external nodes.

Proof. Each internal node in the extended tree has branches leading to two children. Thus, the total number of branches is 2n. Only n − 1 internal nodes have a single incoming branch from a parent (the root does not have a parent). Thus, each of the remaining n + 1 branches points to an external node.

For any non-empty binary tree with n 0 leaf nodes and n 2 nodes of degree 2, n 0 = n 2 + 1.

Proof. Let n 1 be the number of nodes of degree 1 and n = n 0 + n 1 + n 2 (Equation 1) be the total number of nodes. The number of branches in a binary tree is n − 1 since each non-root node has a branch leading into it. But, all branches stem from nodes of degree 1 and 2. Thus, the number of branches is n 1 + 2n 2. Equating the two expressions for number of branches, we get n = n 1 + 2n 2 + 1 (Equation 2). From Equations 1 and 2, we get n 0 = n 2 + 1.

The external path length of any binary tree with n internal nodes is 2n greater than its internal path length.

Proof. The proof is by induction. The lemma clearly holds for n = 0 when the internal and external path lengths are both zero. Consider an extended binary tree T with n internal nodes. Let E T and I T denote the external and internal path lengths of T. Consider the extended binary tree S that is obtained by deleting an internal node whose children are both external nodes (i.e., a leaf) and replacing it with an external node. Let the deleted internal node be at level l. Thus, the internal path length decreases by l while the external path length decreases by 2(l + 1)−l = l + 2. From the induction hypothesis, E S = I S + 2(n−1). But, E T = E S + l + 2 and I T = I S + l. Thus, E T I T = 2n.

The maximum number of nodes on level i of a binary tree is 2 i , i ≥ 0.

Proof. This is easily proved by induction on i.

The maximum number of nodes in a binary tree of height k is 2 k + 1− 1.

Proof. Each level i, 0 ≤ ik, has 2 i nodes. Summing over all i results in $1 n + 1 ( 2 n n )$

.

The height of a binary tree with n internal nodes is at least ⌈ log2(n + 1)⌉ and at most n − 1.

Proof. The worst case is a skewed tree (Figure 3.6a) and the best case is a tree with 2 i nodes at every level i except possibly the bottom level (Figure 3.6b). If the height is h, then n + 1 ≤ 2 h , where n + 1 is the number of external nodes.

Figure 3.6   (a) Skewed and (b) complete binary trees.

The number of distinct binary trees with n nodes is $C n = 1 n + 1 ( 2 n n )$

.

Proof. For a detailed proof, we refer the reader to [7]. However, we note that $near [ s ] ← 0$

are known as the Catalan numbers, which occur frequently in combinatorial problems. The Catalan number C n also describes the number of trees with n + 1 nodes and the number of binary trees with 2n + 1 nodes all of which have 0 or 2 children.

#### 3.3.2  Binary Tree Representation

Binary trees are usually represented using nodes and pointers. A TreeNode class may be defined as: class TreeNode { TreeNode* LeftChild; TreeNode* RightChild; KeyType data; };

In some cases, a node might also contain a parent pointer which facilitates a “bottom-up” traversal of the tree. The tree is accessed by a pointer root of type TreeNode* to its root. When the binary tree is complete (i.e., there are 2 i nodes at every level i, except possibly the last level which has nodes filled in from left to right), it is convenient to use an array representation. The complete binary tree in Figure 3.6b can be represented by the array 1 2 3 4 5 6 7 8 9 10 11 12 [ A B C D E F G H I J K L ]

Observe that the children (if any) of a node located at position i of the array can be found at positions 2i and 2i + 1 and its parent at ⌊i/2⌋.

#### 3.4  Binary Tree Traversals

Several operations on trees require one to traverse the entire tree: that is, given a pointer to the root of a tree, process every node in the tree systematically. Printing a tree is an example of an operation that requires a tree traversal. Starting at a node, we can do one of three things: visit the node (V), traverse the left subtree recursively (L), and traverse the right subtree recursively (R). If we adopt the convention that the left subtree will be visited before the right subtree, we have three types of traversals LV R, V LR, and LRV which are called inorder, preorder, and postorder, respectively, because of the position of V with respect to L and R. In the following, we will use the expression tree in Figure 3.7 to illustrate the three traversals, which result in infix, prefix, and postfix forms of the expression. A fourth traversal, the level order traversal, is also studied.

Figure 3.7   An expression tree.

#### 3.4.1  Inorder Traversal

The following is a recursive algorithm for an inorder traversal that prints the contents of each node when it is visited. The recursive function is invoked by the call inorder(root). When run on the example expression tree, it returns A*B+C*D.

inorder(TreeNode* currentNode) { if (currentNode) { inorder(currentNode->LeftChild); cout << currentNode->data; inorder(currentNode->RightChild); } }

#### 3.4.2  Preorder Traversal

The following is a recursive algorithm for a preorder traversal that prints the contents of each node when it is visited. The recursive function is invoked by the call preorder(root). When run on the example expression tree, it returns +*AB*CD.

preorder(TreeNode* currentNode) { if (currentNode) { cout << currentNode->data; preorder(currentNode->LeftChild); preorder(currentNode->RightChild); } }

#### 3.4.3  Postorder Traversal

The following is a recursive algorithm for a postorder traversal that prints the contents of each node when it is visited. The recursive function is invoked by the call postorder(root). When run on the example expression tree, it prints AB*CD*+.

postorder(TreeNode* currentNode) { if (currentNode) } postorder(currentNode->LeftChild); postorder(currentNode->RightChild); cout << currentNode->data; } }

The complexity of each of the three algorithms is linear in the number of tree nodes. Non-recursive versions of these algorithms may be found in Reference 6. Both versions require (implicitly or explicitly) a stack.

#### 3.4.4  Level Order Traversal

The level order traversal uses a queue. This traversal visits the nodes in the order suggested in Figure 3.6b. It starts at the root and then visits all nodes in increasing order of their level. Within a level, the nodes are visited in left-to-right order.

LevelOrder(TreeNode* root) { Queue q<TreeNode*>; TreeNode* currentNode = root; while (currentNode) { cout << currentNode->data; if (currentNode->LeftChild) q.Add(currentNode->LeftChild); if (currentNode->RightChild) q.Add(currentNode->RightChild); currentNode = q.Delete( ); //q.Delete returns a node pointer } }

Lemma 3.2 implies that a binary tree with n nodes has n + 1 null links. These null links can be replaced by pointers to nodes called threads. Threads are constructed using the following rules:

1. A null right child pointer in a node is replaced by a pointer to the inorder successor of p (i.e., the node that would be visited after p when traversing the tree inorder).
2. A null left child pointer in a node is replaced by a pointer to the inorder predecessor of p.

Figure 3.8   A threaded binary tree.

#### 3.5.2  Inorder Traversal of a Threaded Binary Tree

Threads make it possible to perform an inorder traversal without using a stack. For any node p, if p's right thread is 1, then its inorder successor is p->RightChild. Otherwise the inorder successor is obtained by following a path of left-child links from the right child of p until a node with left thread 1 is reached. Function Next below returns the inorder successor of currentNode (assuming that currentNode is not 0). It can be called repeatedly to traverse the entire tree in inorder in O(n) time. The code below assumes that the last node in the inorder traversal has a threaded right pointer to a dummy head node.

TreeNode* Next(TreeNode* currentNode) { TreeNode* temp = currentNode->RightChild; if (currentNode->RightThread == 0) while (temp->LeftThread == 0) temp = temp->LeftChild; currentNode = temp; if (currentNode == headNode) return 0; else return currentNode; }

Threads simplify the algorithms for preorder and postorder traversal. It is also possible to insert a node into a threaded tree in O(1) time [6].

#### 3.6.1  Definition

A binary search tree (BST) is a binary tree that has a key associated with each of its nodes. The keys in the left subtree of a node are smaller than or equal to the key in the node and the keys in the right subtree of a node are greater than or equal to the key in the node. To simplify the discussion, we will assume that the keys in the binary search tree are distinct. Figure 3.9 shows some binary trees to illustrate the definition.

Figure 3.9   Binary trees with distinct keys: (a) is not a BST. (b) and (c) are BSTs.

#### 3.6.2  Search

We describe a recursive algorithm to search for a key k in a tree T: first, if T is empty, the search fails. Second, if k is equal to the key in T's root, the search is successful. Otherwise, we search T's left or right subtree recursively for k depending on whether it is less or greater than the key in the root.

bool Search(TreeNode* b, KeyType k) { if (b == 0) return 0; if (k == b->data) return 1; if (k < b->data) return Search(b->LeftChild,k); if (k > b->data) return Search(b->RightChild,k); }

#### 3.6.3  Insert

To insert a key k, we first carry out a search for k. If the search fails, we insert a new node with k at the null branch where the search terminated. Thus, inserting the key 17 into the binary search tree in Figure 3.9b creates a new node which is the left child of 18. The resulting tree is shown in Figure 3.10a.

Figure 3.10   Tree of Figure 3.9b with (a) 18 inserted and (b) 12 deleted.

typedef TreeNode* TreeNodePtr; Node* Insert(TreeNodePtr& b, KeyType k) { if (b == 0) {b = new TreeNode; b->data= k; return b;} if (k == b->data) return 0; // don't permit duplicates if (k < b->data) Insert(b->LeftChild, k); if (k > b->data) Insert(b->RightChild, k); }

#### 3.6.4  Delete

The procedure for deleting a node x from a binary search tree depends on its degree. If x is a leaf, we simply set the appropriate child pointer of x's parent to 0 and delete x. If x has one child, we set the appropriate pointer of x's parent to point directly to x's child and then delete x. In Figure 3.9c, node 20 is deleted by setting the right child of 15 to 25. If x has two children, we replace its key with the key in its inorder successor y and then delete node y. The inorder successor contains the smallest key greater than x's key. This key is chosen because it can be placed in node x without violating the binary search tree property. Since y is obtained by first following a RightChild pointer and then following LeftChild pointers until a node with a null LeftChild pointer is encountered, it follows that y has degree 0 or 1. Thus, it is easy to delete y using the procedure described above. Consider the deletion of 12 from Figure 3.9b. This is achieved by replacing 12 with 14 in the root and then deleting the leaf node containing 14. The resulting tree is shown in Figure 3.10b.

#### 3.6.5  Miscellaneous

Although Search, Insert, and Delete are the three main operations on a binary search tree, there are others that can be defined which we briefly describe below.

• Minimum and Maximum that respectively find the minimum and maximum elements in the binary search tree. The minimum element is found by starting at the root and following LeftChild pointers until a node with a 0 LeftChild pointer is encountered. That node contains the minimum element in the tree.
• Another operation is to find the kth smallest element in the binary search tree. For this, each node must contain a field with the number of nodes in its left subtree. Suppose that the root has m nodes in its left subtree. If km, we recursively search for the kth smallest element in the left subtree. If k = m + 1, then the root contains the kth smallest element. If k > m + 1, then we recursively search the right subtree for the km − 1st smallest element.
• The Join operation takes two binary search trees A and B as input such that all the elements in A are smaller than all the elements of B. The objective is to obtain a binary search tree C which contains all the elements originally in A and B. This is accomplished by deleting the node with the largest key in A. This node becomes the root of the new tree C. Its LeftChild pointer is set to A and its RightChild pointer is set to B.
• The Split operation takes a binary search tree C and a key value k as input. The binary search tree is to be split into two binary search trees A and B such that all keys in A are less than or equal to k and all keys in B are greater than k. This is achieved by searching for k in the binary search tree. The trees A and B are created as the search proceeds down the tree as shown in Figure 3.11.
• An inorder traversal of a binary search tree produces the elements of the binary search tree in sorted order. Similarly, the inorder successor of a node with key k in the binary search tree yields the smallest key larger than k in the tree. (Note that we used this property in the Delete operation described in the previous section.)

Figure 3.11   Splitting a binary search tree with k = 26.

All of the operations described above take O(h) time, where h is the height of the binary search tree. The bounds on the height of a binary tree are derived in Lemma 3.7. It has been shown that when insertions and deletions are made at random, the height of the binary search tree is O(log n) on the average.

#### 3.7.1  Priority Queues

Heaps are used to implement priority queues. In a priority queue, the element with highest (or lowest) priority is deleted from the queue, while elements with arbitrary priority are inserted. A data structure that supports these operations is called a max(min) priority queue. Henceforth, in this chapter, we restrict our discussion to a max priority queue. A priority queue can be implemented by a simple, unordered linked list. Insertions can be performed in O(1) time. However, a deletion requires a search for the element with the largest priority followed by its removal. The search requires time linear in the length of the linked list. When a max heap is used, both of these operations can be performed in O(log n) time.

#### 3.7.2  Definition of a Max-Heap

A max heap is a complete binary tree such that for each node, the key value in the node is greater than or equal to the value in its children. Observe that this implies that the root contains the largest value in the tree. Figure 3.12 shows some examples of max heaps.

Figure 3.12   Max heaps.

We define a class Heap with the following data members.

private: Element *heap; int n; // current size of max heap int MaxSize; // Maximum allowable size of the heap

The heap is represented using an array (a consequence of the complete binary tree property) which is dynamically allocated.

#### 3.7.3  Insertion

Suppose that the max heap initially has n elements. After insertion, it will have n + 1 elements. Thus, we need to add a node so that the resulting tree is a complete binary tree with n + 1 nodes. The key to be inserted is initially placed in this new node. However, the key may be larger than its parent resulting in a violation of the max property with its parent. In this case, we swap keys between the two nodes and then repeat the process at the next level. Figure 3.13 demonstrates two cases of an insertion into a max heap.

Figure 3.13   Insertion into max heaps.

The algorithm is described below. In the worst case, the insertion algorithm moves up the heap from leaf to root spending O(1) time at each level. For a heap with n elements, this takes O(log n) time.

void MaxHeap::Insert(Element x) { if (n == MaxSize) {HeapFull( ); return;} n++; for (int i = n; i > 1; i = i/2) { if (x.key <= heap[i/2].key) break; heap[i] = heap[i/2]; } heap[i] = x; }

#### 3.7.4  Deletion

The element to be deleted (i.e., the maximum element in the heap) is removed from the root node. Since the binary tree must be restructured to become a complete binary tree on n − 1 elements, the node in position n is deleted. The element in the deleted node is placed in the root. If this element is less than either of the root's (at most) two children, there is a violation of the max property. This is fixed by swapping the value in the root with its larger child. The process is repeated at the other levels until there is no violation. Figure 3.14 illustrates deletion from a max heap.

Figure 3.14   Deletion from max heaps.

The deletion algorithm is described below. In the worst case, the deletion algorithm moves down the heap from root to leaf spending O(1) time at each level. For a heap with n elements, this takes O(log n) time.

Element* MaxHeap::DeleteMax(Element& x) { if (n == 0) {HeapEmpty( ); return 0;} x = heap[1]; Element last = heap[n]; n--; for (int i = 1, j = 2; j <= n; i = j, j *= 2) { if (j < n) if (heap[j].key < heap[j+1].key) j++; // j points to the larger child if (last.key >= heap[j].key) break; heap[i] = heap[j]; // move child up } heap[i] = last; return &x; }

#### 3.8  Tournament Trees

Consider the following problem: suppose we have k sequences, each of which is sorted in nondecreasing order, that are to be merged into one sequence in nondecreasing order. This can be achieved by repeatedly transferring the element with the smallest key to an output array. The smallest key has to be found from the leading elements in the k sequences. Ordinarily, this would require k − 1 comparisons for each element transferred. However, with a tournament tree, this can be reduced to log2 k comparisons per element.

#### 3.8.1  Winner Trees

A winner tree is a complete binary tree in which each node represents the smaller of its two children. The root represents the smallest node in the tree. Figure 3.15 illustrates a winner tree with k = 8 sequences. The winner of the tournament is the value 8 from sequence 0. The winner of the tournament is the smallest key from the 8 sequences and is transferred to an output array. The next element from sequence 0 is now brought into play and a tournament is played to determine the next winner. This is illustrated in Figure 3.16. It is easy to see that the tournament winner can be computed in Θ(log n) time.

Figure 3.15   A winner tree for k = 8. Three keys in each of the eight sequences are shown. For example, sequence 2 consists of 15, 20, and 26.

Figure 3.16   Winner tree of Figure 3.15 after the next element of sequence 0 plays the tournament. Matches are played at the shaded nodes.

#### 3.8.2  Loser Trees

The loser tree is an alternative representation that stores the loser of a match at the corresponding node. The loser tree corresponding to Figure 3.15 is shown in Figure 3.17. An advantage of the loser tree is that to restructure the tree after a winner has been output, it is sufficient to examine nodes on the path from the leaf to the root rather than the siblings of nodes on this path.

Figure 3.17   Loser tree corresponding to the winner tree of Figure 3.15.

#### Acknowledgments

The author would like to thank Kun Gao and Mr. U. B. Rao for proofreading this chapter. This work was supported, in part, by the National Science Foundation under grant CCR-9988338.

#### References

D. Knuth , The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Third edition. Addison Wesley, NY, 1997.
T. Cormen , C. Leiserson , R. Rivest , and C. Stein , Introduction to Algorithms, Second edition. McGraw-Hill, New York, NY, 2001.
S. Sahni , Data Structures, Algorithms, and Applications in C++, McGraw-Hill, NY, 1998.
S. Sahni , Data Structures, Algorithms, and Applications in Java, McGraw-Hill, NY, 2000.
R. Sedgewick , Algorithms in C++, Parts 1–4, Third edition. Addison-Wesley, NY, 1998.
E. Horowitz , S. Sahni , and D. Mehta , Fundamentals of Data Structures in C++, W. H. Freeman, NY, 1995.
D. Stanton and D. White , Constructive Combinatorics, Springer-Verlag, NY, 1986.

## Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.


text:
The OMOP reference set A reference set of 165 drug-outcome pairs where we believe the drug causes the outcome ( positive controls) and 234 drug-outcome pairs where we believe the drug does not cause the outcome (negative controls). The controls involve 4 health outcomes of interest: acute liver injury, acute kidney injury, acute myocardial infarction, and GI bleeding.

data(omopReferenceSet)

## Format

A data frame with 399 rows and 10 variables:

exposureId

Concept ID identifying the exposure

exposureName

Name of the exposure

outcomeId

Concept ID identifying the outcome

outcomeName

Name of the outcome

groundTruth

0 = negative control, 1 = positive control

indicationId

Concept Id identifying the (primary) indication of the drug. To be used when one wants to nest the analysis within the indication

indicationName

Name of the indication

comparatorId

Concept ID identifying a comparator drug that can be used as a counterfactual

comparatorName

Name of the comparator drug

comparatorType

How the comparator was selected

## References

Ryan PB, Schuemie MJ, Welebob E, Duke J, Valentine S, Hartzema AG. Defining a reference set to support methodological research in drug safety. Drug Safety 36 Suppl 1:S33-47, 2013


text:
Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals → CMB
Abstract view

# Structure of the Set of Norm-attaining Functionals on Strictly Convex Spaces

 Read article[PDF: 148KB]
Published:2011-01-26
Printed: Jun 2011
• Ondřej Kurka,
Department of Mathematical Analysis, Faculty of Mathematics and Physics, Charles University, Sokolovská 83, 186 75 Prague 8, Czech Republic
 Format: HTML LaTeX MathJax PDF

## Abstract

Let $X$ be a separable non-reflexive Banach space. We show that there is no Borel class which contains the set of norm-attaining functionals for every strictly convex renorming of $X$.
 Keywords: separable non-reflexive space, set of norm-attaining functionals, strictly convex norm, Borel class
 MSC Classifications: 46B20 - Geometry and structure of normed linear spaces 54H05 - Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) [See also 03E15, 26A21, 28A05] 46B10 - Duality and reflexivity [See also 46A25]

 top of page | contact us | privacy | site map |

© Canadian Mathematical Society, 2018 : https://cms.math.ca/