1307.3435

## On Nicod's Condition, Rules of Induction and the Raven Paradox Hadi Mohasel Afshar & Peter Sunehag Research School of Computer Science Australian National University Canberra, ACT, 0200, Australia hadi.afshar@anu.edu.au peter.sunehag@anu.edu.au October 26, 2018 ## Abstract Philosophers writing about the ravens paradox often note that Nicod's Condition (NC) holds given some set of background information, and fails to hold against others, but rarely go any further. That is, it is usually not explored which background information makes NC true or false. The present paper aims to fill this gap. For us, '(objective) background knowledge' is restricted to information that can be expressed as probability events. Any other configuration is regarded as being subjective and a property of the a priori probability distribution. We study NC in two specific settings. In the first case, a complete description of some individuals is known, e.g. one knows of each of a group of individuals whether they are black and whether they are ravens. In the second case, the number of individuals having a particular property is given, e.g. one knows how many ravens or how many black things there are (in the relevant population). While some of the most famous answers to the paradox are measure-dependent, our discussion is not restricted to any particular probability measure. Our most interesting result is that in the second setting, NC violates a simple kind of inductive inference (namely projectability ). Since relative to NC, this latter rule is more closely related to, and more directly justified by our intuitive notion of inductive reasoning, this tension makes a case against the plausibility of NC. In the end, we suggest that the informal representation of NC may seem to be intuitively plausible because it can easily be mistaken for reasoning by analogy. ## Keywords Nicod's condition (NC), Raven paradox, weak projectability (PJ), reasoning by analogy (RA), inductive inference. ## 1 Introduction In this article, we study induction and in particular Nicod's Condition (NC) from a Bayesian (in the sense of subjective probability ) point of view. Rules of induction can be thought of as such restrictions on the class of probability measures (or equivalently, on the class of rational agents 1 ). The question is: 'How can we agree that any particular rule of induction is plausible and generally entails sensible consequences and therefore should be accepted a priori?'. We are interested in a specific rule, namely NC which informally speaking states that 'A proposition of the form All F are G is supported by the observation that a particular object is both F and G ' [Hem45]. Does the fact that NC, does not seem to be counterintuitive suffice to persuade us that it is a plausible rule of induction? How can we be sure that it does not violate other intuitively acceptable rules and principles? As the notorious raven paradox [Hem45] shows, NC actually does entail counterintuitive consequences, and more than seven decades of discussion about this paradox shows that assessment of rules of induction can be extremely problematic. A summary of the raven paradox is as follows: The hypothesis H := ' All ravens are black ' is logically equivalent to ˆ H := ' Every thing that is not black is not a raven '. A green apple is neither black nor a raven therefore according to NC its observation should confirm ˆ H . But H is logically equivalent to ˆ H , so we end up with a Paradoxical Conclusion (PC), that an observation of a green apple confirms that all ravens are black, which is counterintuitive. In order to resolve the paradox, either it should be shown that NC is not a plausible rule of induction or it should be claimed that PC holds and should not be considered as being counterintuitive. 2 In order to study the paradox from a Bayesian perspective, first we make a distinction between (objective) background knowledge by which we exclusively refer to the knowledge that can be represented (and consequently can be thought of) as previously observed events, and any other kinds of information which we consider as being subjective and a property of the a priori chosen probability measure (i.e. the initial degrees of beliefs). The cogency of inductive rules is significantly affected by the given background knowledge and the chosen measures. For example, it is already known that relative to some background knowledge, NC violates intuition (e.g. see [Goo67]). In Section 2.1, we argue that relative to unrestricted background knowledge, not only NC but any rule of induction can be refuted. Hempel himself believed that NC and the raven paradox should be considered in the context of absolutely no background information [Hem67]. From a Bayesian perspective, 1 The term rational agent (that is, the performer of induction), as used in fields such as decision theory and artificial intelligence [RN03], by definition, refers to an agent that satisfies certain consistency axioms (see [Sav54]). Representation theorems show that this implies that the agent has a probability distribution representing a priori beliefs for what will happen and utilities for the various possible outcomes, such that decisions can be explained as maximizing expected utility. Given utilities we can from simpler axioms [SH11] infer the existence of a probability distribution. 2 Some authors have even denied the equivalence of H and ˆ H [SG72]. however, this does not solve the problem. The reason is that background knowledge and priors are convertible (in the sense that they can produce the same effects). For example if we are not allowed to consider NC in the context that we possess the background knowledge that 'an object a has a property F ' (denoted as: F a ), we can (approximately) produce the same situation by subjectively believing that the probability that that object has the property F , is sufficiently close to 1 (denoted as: pr ( F a ) ≈ 1). 3 , 4 Therefore, if we want to restrict ourselves to the context of perfect ignorance , not only should we possess no objective knowledge, we should also only be permitted to reason based on an absolutely unbiased probability measure. This raises an important question: 'What is an unbiased measure?' Due to its subjective nature, this question does not have a definitive answer but by far, the most widely considered choice is the uniform measure . 5 , 6 On the other hand, it is well known that using the uniform measure, inductive learning is not possible [Car50]. This shows that from the subjective probabilistic perspective, choosing a probability measure that satisfies the condition of perfect ignorance and allows inductive learning, is arguably impossible. It is also notable that demonstrating that a specific probability measure does (or does not) comply with a rule of induction (or a statement such as PC), does not illuminate the reason why a typical human observer believes that such a rule (or statement) is implausible (or plausible). Conversely, one might argue that compliance of a probability measure with a counterintuitive statement such as PC, may 3 According to Cournot's principle [Cou43], we do not allow 1 (or 0) priors for events that may or may not happen. If it was allowed then assuming pr ( F a ) = 1, would exactly produce the same effect that possessing the background knowledge ' a is F ' would. This would be problematic, because assigning probability 1 to the events that are not determined (by background knowledge) may lead to undefined conditional probabilities (in case the complement events occur). However, assigning a probability that is arbitrarily close to one (i.e. pr ( F a ) ≈ 1) does not cause such a problem while it approximately produces the effect of the same background knowledge to arbitrary precision. Although for Hempel and his contemporaries, the confirmation theory was (more or less) a logical relation, akin to deductive entailment, rather than a probabilistic relation (in the formal sense) [FH10], what we mentioned about the convertibility of objective information and subjective beliefs, was in a way reflected in their discussions: Good's Red Herring [Goo67] provided a hypo- thetical objective background setting with respect to which, NC does not hold. Hempel's assertion that 'NC should be considered in the context of no (objective) background information' was in fact an attempt to address such an issue. However, nothing could prevent Good from producing the same effect by simply replacing the objective information with subjective a priori beliefs of a Good's baby new born baby ( [Goo68]). 5 The main justification is due to the principle of maximum entropy [Jay03]. This principle recommends that one choose, among all the probability measures satisfying a constraint, the measure which maximizes the Shannon entropy . In the absence of any background knowledge (i.e. no constraint), the uniform probability measure maximizes entropy. 6 An alternative to the uniform measure is Solomonoff's theory of universal inductive inference [Sol64] which mathematically formalizes and puts together Occam's razor (the principle that the simplest model consistent with the background knowledge should be chosen) and Epicurus' principle of multiple explanations (that all explanations consistent with background knowledge should be kept) (see [Hut07] or [RH11]). suggest that this measure does not provide a suitable model for inductive reasoning. As an example, consider the following two works: [Mah99] and [Mah04]. They are among the most famous answers to the raven paradox. Using Carnap's measure [Car80], in 1999 Maher argued that both NC and PC hold. In 2004 he suggested a more complex measure that led to opposite results: Maher showed that for this latter measure, neither NC nor PC holds in all settings. Although Maher's works successfully show that at least for one probability measures NC holds and for another probability measures it does not, they do not show whether NC and PC are generally plausible or not. The mainstream contemporary Bayesian solutions are not restricted to a particular measure and in this sense, are more general. According to [FH06] almost all of them accept PC and argue that observation of a non-black non-raven does provide evidence in support of H ; however, in comparison with the observation of a black raven , the amount of confirmation is very small. This difference, they argue, is due to the fact that the number of ravens is much less than the number of non-black objects. However as [Vra04] explains, these arguments have only been able to reach their intended conclusion by adding some extra assumptions about the characteristics of the chosen probability measure. He shows that the standard Bayesian solution relies on the almost never explicitly defended assumption that 'the probability of H should not be affected by evidence that an object is non-black .' - a supposition that he believes, is implausible, i.e. may hold or not. To summarize the above discussion: the general plausibility of a rule of induction cannot be determined if we restrict our study to particular (objective) background knowledge or a particular probability measure. On the other hand, no rule of induction holds in the presence of an unrestricted choice of background knowledge and probability measure. We conclude that rules of induction should be studied for different classes of background knowledge and priors. If a rule of induction holds relative to a large class of reasonable background knowledge (i.e. information similar to our actual configuration of knowledge obtained from observations that often take place in real life) and relative to reasonable probability measures (i.e. measures that have intuitively reasonable characteristics e.g. comply with other rules of induction which are more directly justified by our intuitive notion of induction), then we can claim that the studied rule is plausible, otherwise we cannot. In this paper, we study NC with such an approach. In Section 2, we present a formal representation for three rules of induction, namely, projectability (PJ), reasoning by analogy (RA) and Nicod's condition (NC). We also define the form of background knowledge that is studied throughout the paper. Informally speaking, we only study pieces of knowledge that do not link the properties of one object to another object. They can be though of as knowledge that can be gained directly by observing the properties of some distinct objects. For example, the background knowledge: 'if object a is a raven , then object b is not a raven ', is not of this form. While one can easily constitute pieces of information that do not have such a form and violate the aforementioned rules of induction, we have not found any illuminating counterexample to the assumption that relative to a piece of information that does not link properties of distinct objects together, PJ and RA comply with intuition. In the case of NC, we are more inquiring. In the next two sections, we study the restrictions of the probability measures that guarantee the validity of NC relative to two more specific background configurations (that can be expressed in the mentioned form). In Section 3, we find some sufficient conditions for the validity of NC and some sufficient conditions for its invalidity, relative to information about the kind (i.e. being raven or not) and color (i.e. being black or not) of some objects. The sufficient condition that we present for the validity of NC is less restrictive. However, this is insufficient for claiming that in this setting NC is generally plausible. Section 4 deals with the setting where the exact number of objects having one property is known. For example we know how many ravens (or how many non-black objects) exist. We show that in this setting, measures that comply with Nicod's condition, do not always comply with PJ which seems to be the simplest formalization of inductive inference . It is also shown that in the case of contradiction, intuition (arguably) follows PJ rather than NC. We think that this result is both interesting and somewhat surprising and should be considered as a main contribution of this paper. One limitation of our basic setup is that it limits us to a universe with an arbitrary but known size. However, in Section 5, this strong assumption is replaced by the weaker assumption that there is a probability distribution over the possible sizes of the universe and this distribution is not affected by an observation of a single object. We show that under this weaker assumption, the results from the former sections remain valid. In Section 6, we summarize the paper and conclude that there is a tension between NC and our intuitive notion of inductive reasoning. We also suggest that reasoning by analogy provides a viable alternative to formalize the seemingly intuitive statement that 'the observation that a particular object is both F and G confirms the hypothesis that any object that is F is also G ' without suffering form the shortcomings of NC. All theorems are proven in Section 7. ## 1.1 Notation, Basic Definitions and Assumptions Throughout sections 2 to 4 we work with a first-order language L whose only nonlogical symbols are a pair of monadic predicates F and G and a set of constants U (officially shown as) { u 1 , u 2 , . . . , u N } where N is a known positive integer. However, for simplicity we drop ' u ' and refer to each constant by its index. We rely on the domain closure axiom [Rei80], that is: $$\begin{array} { r l } { \forall x } & ( x = 1 ) \lor ( x = 2 ) \lor \dots \lor ( x = N ) } \end{array}$$ /negationslash /negationslash where 1 to N are distinct constants i.e. (1 = 2) ∧ (1 = 3) ∧ . . . . Clearly, models of this axiom are restricted to interpretations with domains containing exactly N distinct individuals (objects) each of which is denoted by a constant in U . Using this bijection between the elements of the domain and constants, we refer to U as the universe. Negation, conjunction, disjunction and material implication are respectively represented by ' ¬ ', ' . ' (or ' ∧ '), ' ∨ ' and ' → '. If b is an individual and ψ is a 1-place predicate (either atomic or a sentential combination of atomic predicates), ψ b is defined as a proposition that involves predicate ψ and indicates: ' b has (or satisfies or is described by) ψ '. Conjunction of several propositions ψ m , ψ m +1 , . . . , ψ n is abbreviated by ψ m : n . By definition, for n < m , ψ m : n := /latticetop (i.e. tautology) and ψ m : m := ψ m . More generally, if b m to b n are some objects (not necessarily consecutive), ψ b m : b n := ψ b m ∧ . . . ∧ ψ b n . The general hypothesis H := ( ∀ x F → G x ) (which is equivalent to F → G 1: N ) where F → G b := F b → G b . We also let: $$\begin{array} { c } \bar { F } \bar { G } _ { b } \colon = \neg F _ { b } . \neg G _ { b } ; \quad \bar { F } G _ { b } \colon = \neg F _ { b } . G _ { b } ; \quad F \bar { G } _ { b } \colon = \neg ( F \rightarrow G _ { b } ) = F _ { b } . \neg G _ { b } ; \quad F G _ { b } \colon = F _ { b } . G _ { b } \\ & ( 1 . 2 ) \end{array}$$ Any of ¯ F ¯ G b to FG b defined by relation (1.2) is referred to as a complete description of an object b . 7 For example if F and G represent 'ravenhood' and 'blackness' properties respectively, then ¯ F ¯ G b means ' b is not a raven and is not black' and so on. F → G b means 'if b is a raven then it is black' and H is the general hypothesis that 'for all b , if b is a raven then it is black'. Clearly all complete descriptions which provide counterexample to H are in the form F ¯ G b . We define ∆ as the set of all propositions ρ which are in the following form (or by simplification can be converted to it): $$\rho \colon = \psi _ { b _ { 1 } } ^ { 1 } . \psi _ { b _ { 2 } } ^ { 2 } \dots \psi _ { b _ { k } } ^ { k } = \bigwedge _ { x = 1 } ^ { k } \psi _ { b _ { x } } ^ { x } & & ( 1 . 3 )$$ where ψ 1 to ψ k are some predicates in { F , ¬ F , G , ¬ G , ¯ F ¯ G , ¬ ¯ F ¯ G , ¯ FG , ¬ ¯ FG , F ¯ G , F → G , FG , ¬ FG } and b 1 to b k are some mutually distinct objects: { b 1 , b 2 , . . . b k } ⊆ U . Note that ∆ is in fact the set of all propositions that do not link the properties of different objects together. We define the set of all individuals described by ρ as: I ρ := { b 1 , b 2 , . . . b k } . We refer to the set of (simple) predicates involved in ρ by: A ρ := { ψ 1 , . . . , ψ k } . For example, the proposition ρ ′ := FG 1 ∨ F ¯ G 3 is not in ∆ but ρ ′′ := FG 1 .FG 3 .F → G 4 ∈ ∆ (assuming N ≥ 4). I ρ ′′ = { 1 , 3 , 4 } and A ρ ′′ = { FG,F → G } . By definition, empty (or tautologous) proposition /latticetop is a member of ∆ with I /latticetop = ∅ . Two subsets of ∆ are defined as follows: $$\delta \coloneqq \{ d \in \Delta \colon \mathcal { A } _ { d } = \{ \bar { F } \bar { G } , \bar { F } G , F G \} \} \\ \Omega \coloneqq \{ d \in \Delta \colon \mathcal { I } _ { d } = U , \mathcal { A } _ { d } = \{ \bar { F } \bar { G } , \bar { F } G , F \bar { G } , F G \} \}$$ Informally speaking, δ is the set of propositions that completely describe some individuals and do not falsify H . Likewise, Ω is the set of propositions that completely 7 ¯ F ¯ G , ¯ FG , F ¯ G and FG are what Maher calls Q 4 , Q 3 , Q 2 and Q 1 respectively. What we call complete description , he calls sample proposition [Mah99]. describe all objects of the universe. We refer to any member of Ω as a Complete Description Vector (CDV). Note that each CDV corresponds to a unique model or world (up to isomorphism). In other words, every interpretation that makes a CDV (and aforementioned axiom (1.1)) true, uniquely determines the value of any sentence in L , 8 therefore we can consider them as (representatives of) different worlds. The probability measures which we are concerned with, are defined over the sample space Ω with the power set as σ -algebra. No other restriction is imposed on the choice of measure unless it is mentioned explicitly. For each proposition ρ , let ω Ω ρ := { o ∈ Ω : o | = ρ } be the set of all CDVs that entail ρ . We say that the event ω Ω ρ corresponds to the proposition ρ (and vice versa). For convenience' sake, except in Section 5, we represent the probability of events by the probability of their corresponding propositions 9 ; formally, for propositions ρ , we let pr ( ρ ) := pr ( ω Ω ρ ). According to Cournot's principle [Cou43], we do not allow 1 (resp. 0) priors to the sentences that are not valid (resp. unsatisfiable). Objective background knowledge (or simply background knowledge) is what we are certain about and can be represented by a subset of Ω. The more formal definition of the background setting studied throughout this paper and its corresponding restrictions are given in Section 2.1. We equate 'inductive support' with 'probability increment': It is said that in the presence of background knowledge D , evidence E confirms hypothesis H iff: $$p r ( H | E . D ) > p r ( H | D )$$ We are only interested in the case where E and D are consistent, pr ( E ) and pr ( D ) are positive and E is not determined by D , i.e. 0 < pr ( E | D ) < 1. ## 2 Inductive Reasoning and Nicod's Condition The fundamental assumption behind inductive inference is the so-called principle of the uniformity of nature [Hum88] (or the immutability of natural processes [Pop59]) based on which, uniformity and trend are more probable than diversity and anomaly a priori. Let us assume that ∆ is a set of background knowledge configurations for which we 'intuitively' expect that inductive inference holds (for more discussion refer to Section 2.1). Relative to pieces of information in ∆, we present the following varieties of inductive inference (i.e. inductive rules ): 8 The proof is straightforward. With respect to the domain closure axiom, all quantifiers are bounded. Therefore all sentences are convertible to quantifier-free forms and consequently convertible to full disjunctive normal form (DNF) which is in fact a disjunction of some CDVs. In any world, only one CDV is true, therefore only sentences containing that CDV (when expressed in full DNF) are true. 9 In Section 5, we simultaneously deal with more than one sample space. While w.r.t. different sample spaces, propositions may correspond to different events, in that section we directly represent probability events by their relevant sample space subsets. Projectability. For all objects a and b and background knowledge D ∈ ∆ that does not determine ψ a or ψ b , based on [Mah04], one (and apparently the simplest) kind of inductive inference, namely projectability 10 , 11 , is defined as follows: $$\text {Strong projectability} \colon \quad & \forall a , b \in U \quad p r ( \psi _ { b } | \, \psi _ { a } . D ) > p r ( \psi _ { b } | D ) \\ \text {Weak projectability (PJ)} \colon \quad & \forall a , b \in U \quad p r ( \psi _ { b } | \, \psi _ { a } . D ) \geq p r ( \psi _ { b } | D ) \quad ( 2 . 1 )$$ Projectability (relative to predicate ψ ) can be justified as follows: The evidence ψ a increases the proportion of the observed individuals that have the predicate ψ . Thus, according to the principle of the uniformity of nature, the estimated frequency of the predicate ψ in the total population should also be increased because the uniformity between the characteristics of the sample and the total population is considered to be likely. Reasoning by Analogy (RA). The observation that two individuals have some common properties, increases the probability that their unobserved properties are also alike, because it is likely that there is a uniformity between the characteristics of unobserved properties and the observed ones. Maher has formalized one variation of reasoning by analogy (or inference by analogy [Car50]) as: ∀ a, b ∈ U pr ( G b | F b .FG a ) > pr ( G b | F b ) [Mah04]. We generalize the relation to cover the case where background knowledge D ∈ ∆ (that does not determine the value of F a , G a and G b ) is also present: $$\begin{array} { r l } & { R e a s o n i n g b y a n a l o g y \left ( R A \right ) \colon \forall a , b \in U \quad p r ( G _ { b } | F _ { b } . F G _ { a } . D ) > p r ( G _ { b } | F _ { b } . D ) \quad ( 2 . 2 ) } \end{array}$$ Nicod's Condition (NC). For U := { 1 , . . . , N } , H := F → G 1: N , all a ∈ U and D ∈ ∆ that does not determine the value of FG a or H , we say NC holds for D iff: $$N i c o d ' s C o n d i t i o n ( N C ) \colon \ p r ( H | F G _ { a } . D ) > p r ( H | D ) \quad ( 2 . 3 )$$ NC is stronger than PJ or RA in the sense that it deals with the confirmation of a generalization rather than a singular prediction. In other words, NC is a form of enumerative induction but PJ and RA are forms of singular predictive inference . ## 2.1 Restrictions on the Background Knowledge Obviously, relative to unconstrained background knowledge, no rule of induction holds in general. For example, in the presence of background knowledge D ′ := F 1 → ( ¬ F ) 2: N , at least relative to evidence F 1 , PJ does not hold. Similarly, (as 10 According to [Car50] predictive inference (i.e. inference from a sample to another sample) is the most important kind of inference and the most important special kind of it, singular predictive inference , is inference from a sample to an individual object. Maher's projectability is in fact a special kind of singular predictive inference : inference from one individual to another individual. 11 Maher's original relation does not mention background knowledge, and only deals with strong projectability (which he calls absolute projectability ). [Mah04], Theorem 12 formally shows), in the presence of background knowledge D ′′ := FG 1 →¬ H , NC does not hold (for evidence FG 1 ). To prevent such problems, the biggest set of background configurations studied through out this paper is ∆ 12 , which according to its definition in Section 1.1, is the set of all consistent propositions that can be expressed in the form of a conjunction of some propositions that involve F , G , ¯ F ¯ G , ¯ FG , F ¯ G , FG or their negations. Obviously, each member of ∆ can be expressed in the form of a conjunction of some propositions each of which describes only one individual. Consequently, problematic statements that interlink properties of different individuals are not expressible. As an example, the mentioned pathological examples D ′ and D ′′ are not in ∆. In the case of PJ and RA, we did not find a pathological example in ∆, relative to which, the rule of induction contradicts intuition. However, in the case of NC it is already claimed that relative to background knowledge D ′′′ := ¬ F a ∈ ∆, it is not intuitively sound to expect that the evidence ¯ F ¯ G a confirms H [FH10]. In Sections 3 and 4, we will investigate the validity of NC relative to two interesting subsets of ∆. ## 2.2 Restrictions on the probability measure. In Section 3 (Setting 1), we impose no restriction on the choice of the probability measure but in Section 4 (Setting 2), we assume that the probability measure is exchangeable [Car80] in a sense that probabilities are not changed by permuting individuals (i.e. swapping the name of objects). To introduce this restriction formally, we need the following definitions: Definition. By the term permutation , we always refer to a bijection from a set of all objects U to itself. Throughout this paper, we denote any arbitrary permutation by π (or π ′ and π ′′ when we deal with more than one permutation). Having a proposition ρ , the proposition ρ π is obtained from ρ by replacing any occurrence of any individual b with π ( b ). Example 1. If U := { 1 , 2 , 3 } , the function π : U → U defined by π (1) = 1; π (2) = 3 and π (3) = 2, is a permutation with a fixed point 1. For short we write π := { 2 / 3; 3 / 2 } . If we define ρ := F 1 ∨ G 3 , then ρ π = F 1 ∨ G 2 . ♦ Exchangeability. The probability measure pr is exchangeable if for all propositions A and B and all permutations π , pr ( A | B ) = pr ( A π | B π ). 12 Note that we do not claim that no background knowledge that is not a member of ∆ is not plausible. Investigation of rule of inductions relative to such knowledge, is simply beyond the scope of this paper. ## 3 Validity of NC when Background Knowledge Consists of Complete Descriptions of Some Individuals (Setting 1) In Section 1.1, δ was defined as the set of all background knowledge that do not refute H and describe some individuals completely (e.g. in the case of the raven paradox, members of δ represent the knowledge that we are already aware of the color and kind (i.e. the state of being raven) of some individuals and none of these known objects have been a non-black raven). Clearly, δ ⊂ ∆. Theorem 3.1 shows that if the chosen probability measure satisfies some conditions, then for any background knowledge D ∈ δ , NC holds (for predicates F and G ). On the other hand, Theorem 3.2 shows that under alternative conditions, for some D ∈ δ , NC does not hold. Theorem 3.1. If a probability measure complies with the following relation: $$\forall B \in \Delta , \forall a , b \notin \mathcal { I } _ { B } \quad p r ( F \bar { G } _ { b } | F G _ { a } . B ) \leq p r ( F \bar { G } _ { b } | B ) \quad ( 3 . 1 )$$ then, for this measure and any D ∈ δ that does not determine FG a or H , NC holds, i.e. relation (3.1) entails: pr ( H | FG a .D ) > pr ( H | D ). Example 2. If background knowledge consists of complete descriptions of some individuals, by Theorem 3.1 for all pairs of predicates F and G , the uniform measure complies with NC since regardless of the interpretation of F and G , for this measure, ∀ B ∈ ∆ & ∀ a, b / ∈ I B pr ( F ¯ G b | FG a .B ) = pr ( F ¯ G b | B ). This is not surprising since using this measure, learning is impossible (see [Car50]). This means that no observation changes the probability of being F ¯ G for an unobserved object. Nonetheless, for this measure NC is valid because any evidence in the form of ¯ F ¯ G a , ¯ FG a or FG a confirms H for the simple reason that it removes the possibility that the observed object (i.e. a ) is a counterexample to H . ♦ Example 3. In Carnap's theory of inductive probability [Car80]: $$p r ( \psi _ { b } | E ) = \frac { n _ { \psi } + \lambda \cdot p r ( \psi _ { b } ) } { n + \lambda }$$ In the above relations, n is the number of objects mentioned by evidence E ; n ψ is the number of mentioned objects which satisfy predicate ψ , and λ is a constant measuring the resistance to generalization. Note that b should not be mentioned by E , i.e. b /negationslash∈ I E . Using this measure and choosing ψ ∈ { ¯ F ¯ G, ¯ FG,F ¯ G, FG } , in the presence of background knowledge D ∈ δ such that a, b / ∈ I D : pr ( F ¯ G b | FG a .D ) = λ.pr ( F ¯ G b | D ) 1+ λ < pr ( F ¯ G b | D ). Thus by Theorem 3.1, for the class of background knowledge in the form of conjunction of some ¯ F ¯ G , ¯ FG and/or FG for distinct individuals, this measure complies with NC. This is equivalent to the setting chosen by [Mah99] and its corresponding results. ♦ Theorem 3.2. If a probability measure complies with restrictions (3.2) and (3.3), then for this measure (and predicates F and G ) and background knowledge D ∈ δ , NC does not hold. $$& \forall B \in \Delta , \forall a , b \notin \mathcal { I } _ { B } & p r ( F \bar { G } _ { b } | F G _ { a } . B ) > p r ( F \bar { G } _ { b } | B ) \\ & \forall a \notin \mathcal { I } _ { D } & p r ( \neg F \to G _ { a } | F \to G _ { b _ { 1 } \colon b _ { n } } . D ) < p r ( F \bar { G } _ { b _ { 1 } } | \, F G _ { a } . D ) - p r ( F \bar { G } _ { b _ { 1 } } | \, D )$$ /negationslash In the above relations a = b and b 1 to b n represent an arbitrary enumeration of all individuals (except a ) that are not mentioned by D (that is, I D = U \{ b 1 . . . b n , a } ). According to restriction (3.3), the probability that a is not F → G given that all other objects in the universe are F → G should be less than the degree of confirmation by evidence FG a of a hypothesis that an unobserved object b 1 is F ¯ G . Note that b 1 can be the index of any unobserved object. Example 4. [Mah04] proposes a measure based on the formula: $$p r ( F \bar { G } _ { b } | E ) = p r ( I ) \cdot \frac { n _ { F } + \lambda \cdot p r ( F _ { b } ) } { n + \lambda } \cdot \frac { n _ { \overline { G } } + \lambda \cdot p r ( \neg G _ { b } ) } { n + \lambda } + p r ( \neg I ) \cdot \frac { n _ { F \bar { G } } + \lambda \cdot p r ( F \bar { G } _ { b } ) } { n + \lambda }$$ In the above relation, n is the number of objects mentioned by E ; n F and n G denote the number of mentioned objects which are F and ¬ G respectively. In this expression, the prior probability of F ¯ G i.e. pr ( F ¯ G b ) has to be equal to pr ( F b ) · pr ( ¬ G b ) and pr ( I ) and λ are parameters. Maher proposes a counterexample for NC where N = 2 (Let U := { a, b } ), λ = 2, pr ( I ) = 0 . 5 and prior probabilities are pr ( F b ) = 0 . 001 and pr ( G b ) = 0 . 1. This conclusion can be confirmed independently by Theorem 3.2 as follows: 1. For these parameters, the only member of ∆ that does not contain a and b , is B = ∅ for which relation (3.2) holds if pr ( F b ) < 0 . 25. 2. By assuming: ( pr ( F ¯ G b | FG a ) -pr ( F ¯ G b ) ) ≥ 0 . 06 and pr ( G b ) = 0 . 1, a cumbersome calculation shows that (for empty background knowledge) relation (3.3) holds if: pr ( F b ) < 0 . 0983 which covers Maher's proposed configuration. ♦ Comparing Theorems 3.1 and 3.2 shows that creating a probability measure that contradicts NC (w.r.t. D ∈ δ ) is harder than making a measure that complies with it (for the same background setting) because the former measure has to satisfy more constraints. The reason is that even if in a measure, evidence E := FG a does not affect the probability of F ¯ G for unobserved objects (as in the case of the uniform distribution), every hypothesis that is not refuted by E (including H ) is confirmed by it since the observation has reduced the number of possible counterexamples by one. On the other hand, in the case of a measure that does not comply with NC, not only should E confirm F ¯ G for unobserved objects, but the effect of this confirmation should be so substantial that it overwhelms the effect of the elimination of one counterexample to H . 13 However, in the case where the size of the universe 13 To see how the effect of elimination of one possible counterexample leads to relation (3.3), refer to the proof of Theorem 3.2 in Section 7. is large, the latter effect should be minute. This is reflected in relation (3.3) as follows: If N is large, then at least for measures that comply with projectability, pr ( ¬ F → G a | F → G b 1 : b n .D ) ≈ 0, because if it is known that all objects in the universe except a are F → G , then it should be quite probable that a is F → G too. Therefore, even if the degree of confirmation of F ¯ G b 1 by evidence FG a (i.e. pr ( F ¯ G b 1 | FG a .D ) -pr ( F ¯ G b 1 | D )) is very small 14 , relation (3.3) holds. 15 To summarize: - If regardless of the choice of background knowledge, an observation F a .G a does not confirm that any unobserved individual is an F that is not G , then relative to any background knowledge in δ , NC holds. - If regardless of the choice of background knowledge, an observation F a .G a confirms that any unobserved individual is an F that is not G , and on the other hand, the effect of elimination of one counterexample via an observation is negligible, then relative to any background knowledge in δ , NC does not hold. The above statements delegate the assessment of NC (a form of enumerative induction) to the assessment of expressions which deal with singular predictions. Hence, a new perspective on the nature of NC is provided: Should regardless of the interpretation of F and G , (the observation of) an F that is G disconfirm that any unobserved object is F but not G ? For example, relative to background knowledge and a probability measure that reflect our actual configuration of knowledge, should the observation of an F ='walnut' that is G ='round' decrease the probability that any unobserved object is a walnut but not round? Indeed yes; therefore by Theorem 3.1, in this case and for these predicates, NC holds. Should the observation of an F ='round', G='walnut' decrease the probability that any unobserved object is 'round' but not a 'walnut'? Arguably not. Should the observation of an F ='ogre' which is G ='old' decrease the probability that we might encounter an ogre which is not old? Definitely not! 16 Therefore, in 14 Note that by relation (3.2), this degree of confirmation is positive. 15 Here is another justification for the above argument: By definition, a probability measure defined over a first-order language with an infinite domain is Gaifman iff the probability of the generalization of any predicate (in our case, F → G ) is equal to the probability of the conjunction of some positive instances when their number tends to infinity [GS82] or alternatively, pr ( ∀ x ψ x | ψ 1: n ) n →∞ - - - - → 1 (see [HLNU13] thm. 27) and consequently pr ( ¬ ψ a | ψ 1: n ) n →∞ - - - - → 0. Since the Gaifman condition is what we intuitively expect from generalization over an infinite universe, it can be considered as a very simple and intuitive rule of induction. In our case, if the universe was infinite and the measure was assumed to be Gaifman, inequality (3.3) would always hold. However we have assumed that the universe is finite therefore we cannot remove this inequality. What we can say is that for very large domains, relation (3.3) is a very weak condition. 16 This confirmation asymmetry may be due to possible asymmetry in background knowledge and/or prior possibilities of different predicates. For example according to our actual configuration of knowledge, the prior probability of 'being an ogre' (for any individual) is quite low. This is a key point in the existing arguments: Good's baby [Goo68] (that assigns low probability to ravenhood ) and Maher's unicorn [Mah04]. But unlike our discussion, these arguments do not reduce the assessment of NC to a singular prediction. this case, we are intuitively using a probability measure that satisfies the condition (3.2). Now assume that we have seen all objects of the world except one. It has happened that any observed object that has been an ogre has been old as well. Is it reasonable to believe that it is improbable that the last unobserved object is a young ogre? If yes, then our intuitive measure also complies with restriction (3.3), hence by Theorem 3.2, by this denotation for F and G , plausible probability measures do not comply with Nicod's condition. ## 4 NC vs. PJ when the Number of Objects having One Predicate is Known (Setting 2) This section studies NC in the presence of a completely different background setting where we know that exactly k individuals are F (e.g. ravens) and the rest are not F , but we do not know anything about the other property (e.g. their color). First we focus on a simpler setting where we know exactly which objects are F and which objects are not F (e.g. we know that objects 1 to k are F and the rest of the universe i.e. objects k +1 to N are not F ). Theorem 4.1. For U := { 1 , 2 , . . . N } and D := F 1: k . ( ¬ F ) k +1: N , weak projectability (PJ) entails: $$p r ( H \, | \, G _ { k } \, . \, D ) > p r ( H | D ) \quad ( 4 . 1 )$$ $$p r ( H \, | \, G _ { N } \, . \, D ) \geq p r ( H | D ) \quad ( 4 . 2 )$$ $$p r ( H \, | \, \neg G _ { N } \, . \, D ) \leq p r ( H | D )$$ and reasoning by analogy (RA) entails: 17 $$p r ( H \, | \, G _ { k } . D ) > p r ( H | D ) \quad ( 4 . 4 )$$ Next, we show that these results are valid in the general setting where the background knowledge is such that we only know the exact number of objects being F but we do not know their names. In other words, we know that exactly one combination of k out of N objects of the universe are F but we do not know which combination. But before that, we should formalize such knowledge in the form of an event (i.e. a subset of the sample space). Definition. C U,k := { C : C ⊆ U, | C | = k } is defined as the set of all (distinct) subsets of U which contain exactly k individuals. Obviously, the cardinality of C U,k is ( N k ) . 17 Therefore, in this setting both PJ and RA suggest that H := ∀ b F → G b is confirmed by evidence G k but RA provides no answer whether or not evidence G N should confirm (or disconfirm) H . The reason is that (as the proof of the theorem which is provided in Section 7 shows) in the presence of background knowledge F 1: k . ( ¬ F ) k +1: N , validity of H only depends on property G of objects 1 to k that do not have a common property with object N . $$\begin{array} { r l } & { \text {Example 5. Given $U\colon=\{1,2,3,4\}$, $\mathfrak{C}_{U,2}= \left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}$} , } \\ & { \quad \{ 3 , 4 \} . } \end{array}$$ Definition. For 1 ≤ k ≤ N , 'Exactly k objects of the universe U are F ' is formally defined as follows: $$\text {EXACT} ( k , U , F ) \coloneqq \bigvee _ { C \in \mathfrak { C } _ { U , k } } \left ( \bigwedge _ { b ^ { \prime } \in C } F _ { b ^ { \prime } } \cdot \bigwedge _ { b ^ { \prime \prime } \notin C } \neg F _ { b ^ { \prime \prime } } \right )$$ $$\begin{array} { r l } { E x a m p l e \ 6 . I n t h e p r e v i o u s e x a m p l e , E X A C T ( 2 , U , F ) = ( F _ { 1 } . F _ { 2 } . \neg F _ { 4 } ) \lor ( F _ { 1 } . F _ { 4 } . \neg F _ { 2 } . \neg F _ { 3 } . \neg F _ { 4 } ) \lor } \\ { ( F _ { 1 } . F _ { 3 } . \neg F _ { 2 } . \neg F _ { 4 } ) \lor ( F _ { 1 } . F _ { 4 } . \neg F _ { 2 } . \neg F _ { 3 } ) \lor ( F _ { 2 } . F _ { 3 } . \neg F _ { 1 } . \neg F _ { 4 } ) \lor } \\ { ( F _ { 2 } . F _ { 4 } . \neg F _ { 1 } . \neg F _ { 3 } ) \lor ( F _ { 3 } . F _ { 4 } . \neg F _ { 3 } . \neg F _ { 4 } ) . } & { \diamondsuit } \end{array}$$ By comparing definition (4.5) with the definition of ∆, it becomes clear that for 1 < k < N , Exact ( k, U, F ) /negationslash∈ ∆, therefore we do not expect that in the presence of such background knowledge, rules of induction hold in general and they actually don't. For instance, knowing that exactly k objects are F , the evidence that a particular object is F , confirms that any other object is not F , 18 which contradicts PJ: /negationslash However, the following theorem shows that for the hypothesis that we are interested in i.e. H := ∀ b F → G b , the background knowledge Exact ( k, U, F ) is equivalent to F 1: k . ¬ F k +1: N which is a member of ∆. Therefore, in the case of the raven paradox and background knowledge Exact ( k, U, F ), the rules of induction (that are assumed to hold relative to background knowledge in ∆) should still hold. $$\begin{array} { r l } & { ( i n t u i t i v e l y ) \colon \forall b \neq a \in U \ p r \left ( F _ { b } | F _ { a } . E x A c T ( k , U , F ) \right ) < p r \left ( F _ { b } | E x A c T ( k , U , F ) \right ) } \\ & { H o v o r y , t h e f l o w i n g t h e o r m s h o w s t a t f o r t h e h o p t h o c i s t h e t w o a r o i n t e r } \end{array}$$ Theorem 4.2. If U = { 1 , . . . , N } and a is an arbitrary member of U and assuming that a probability measure pr is exchangeable: $$p r \left ( H | \, E x A C T ( k , U , F ) \right ) & = p r \left ( H | \, F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } \right ) \\ p r \left ( H | \, E x A C T ( k , U , F ) . F _ { a } . G _ { a } \right ) & = p r \left ( H | \, F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { k } \right )$$ $$\begin{array} { r l } & { p r \left ( H | E x A C T ( k , U , F ) . \neg F _ { a } . G _ { a } \right ) = p r \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { N } \right ) } \\ & { p r \left ( H | E x A C T ( k , U , F ) . \neg F _ { a } . \neg G _ { a } \right ) = p r \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . \neg G _ { N } \right ) } \end{array}$$ $$\begin{array} { r l } & { p r \left ( H | E x a c t ( k , U , F ) . F _ { a } . G _ { a } \right ) = p r \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { k } \right ) } \\ & { p r \left ( H | E x a c t ( k , U , F ) . \neg F _ { a } . G _ { a } \right ) = p r \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { N } \right ) } \end{array}$$ $$\begin{array} { r l } & { p r \left ( H | E X A C T ( k , U , F ) . \neg F _ { a } . \neg G _ { a } \right ) = p r \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . \neg G _ { N } \right ) \quad ( 4 . 9 ) } \\ \end{array}$$ The formal proof of this theorem is presented in Section 7.3, but the following simple example shows the main idea behind the general proof. Example 7. Having U := { 1 , 2 , 3 } , we show that: pr ( H | Exact (2 , U, F ) .F 3 .G 3 ) = pr ( H | F 1 .F 2 . ¬ F 3 .G 2 ) (that is relation (4.7) for a := 18 Suppose that you are in a camp populated by 100 captives, and it is known that 10 of them will be chosen randomly to be executed; Whenever someone except you is chosen, it is reasonable to be more optimist about your fate, for the simple reason that 9 99 < 10 100 . 3 and k := 2) as follows: $$3 \text { and } k \colon = 2 ) \text { as follows} \colon \\ p r ( \text {Exact} ( 2 , U , F ) . F _ { 3 } . G _ { 3 } | H ) \\ = p r ( ( F _ { 1 } . F _ { 2 } . \neg F _ { 3 } \vee F _ { 1 } . F _ { 3 } . \neg F _ { 2 } \vee F _ { 2 } . F _ { 3 } . \neg F _ { 1 } ) . ( F _ { 3 } . G _ { 3 } ) | F _ { \to } G _ { 1 } . F _ { \to } G _ { 2 } . F _ { \to } G _ { 3 } ) , \text { by def.} \\ = p r ( F _ { 1 } . F _ { 3 } . \neg F _ { 2 } . G _ { 3 } \vee F _ { 2 } . F _ { 3 } . \neg F _ { 1 } . G _ { 3 } | \, F _ { \to } G _ { 1 } . F _ { \to } G _ { 2 } . F _ { \to } G _ { 3 } ) , \text { by simplification} \\ = p r ( F _ { 1 } . F _ { 3 } . \neg F _ { 2 } . G _ { 3 } | \, F _ { \to } G _ { 1 } . F _ { \to } G _ { 2 } . F _ { \to } G _ { 3 } ) + p r ( F _ { 2 } . F _ { 3 } . \neg F _ { 1 } . G _ { 3 } | \, F _ { \to } G _ { 1 } . F _ { \to } G _ { 2 } . F _ { \to } G _ { 3 } ) , \\ \text {by $\sigma$-additivity of disjoint events (3rd Kolmogorov probability axiom)} \\ = p r ( F _ { 1 } . F _ { 2 } . \neg F _ { 3 } . G _ { 2 } | \, F _ { \to } G _ { 1 } . F _ { \to } G _ { 3 } . F _ { \to } G _ { 2 } ) + p r ( F _ { 1 } . F _ { 2 } . \neg F _ { 3 } . G _ { 2 } | \, F _ { \to } G _ { 3 } . F _ { \to } G _ { 1 } . F _ { \to } G _ { 2 } ) , \\ \text {by exchangeability assumption} , \text {using premutation $\pi^{\prime}$ := ${3/2; 2/3}$} \} <text><loc_0><loc_499><loc_16><loc_499>Powered by TCPDF (www.tcpdf.org)</text> </doctag>$$ Similarly it can easily be shown that: pr ( Exact (2 , U, F ) .F 3 .G 3 ) = 2 · pr ( F 1 .F 2 . ¬ F 3 .G 2 ) . Therefore by Bayes rule: $$\begin{array} { r l } & { p r \left ( H | E x A C T ( 2 , U , F ) . F _ { 3 } . G _ { 3 } \right ) = \frac { p r \left ( H \right ) \cdot p r \left ( E X A C T ( 2 , U , F ) | H \right ) } { p r \left ( E X A C T ( 2 , U , F ) \right ) } } \\ & { \quad = \frac { 2 \cdot p r \left ( H \right ) \cdot p r \left ( F _ { 1 } . F _ { 2 } . \neg F _ { 3 } . G _ { 2 } | H \right ) } { 2 \cdot p r \left ( F _ { 1 } . F _ { 2 } . \neg F _ { 3 } . G _ { 2 } \right ) } = p r \left ( H | F _ { 1 } . F _ { 2 } . \neg F _ { 3 } . G _ { 2 } \right ) } \end{array}$$ which is what we wanted to show by this example. ♦ Theorems 4.1 and 4.2 directly entail the main theorem of this section: Theorem 4.3. If Exact ( k, U, F ) := 'exactly k objects (of the universe U ) are F ' and a ∈ U is an object, and the probability measure pr is exchangeable, weak projectability (PJ) entails: $$\begin{array} { r l } { p r \left ( H | E x A C T ( k , U , F ) . F _ { a } . G _ { a } \right ) > p r \left ( H | E x A C T ( k , U , F ) \right ) } & { \quad ( 4 . 1 0 ) } \\ { p r \left ( H | E x A C T ( k , U , F ) . \neg F _ { a } . G _ { a } \right ) \geq p r \left ( H | E x A C T ( k , U , F ) \right ) } & { \quad ( 4 . 1 1 ) } \end{array}$$ $$\begin{array} { r l } & { p r \left ( H | E x A C T ( k , U , F ) . \neg F _ { a } . \neg G _ { a } \right ) \leq p r \left ( H | E x A C T ( k , U , F ) \right ) } \\ & { \quad } \end{array}$$ $$\begin{array} { r l } & { p r \left ( H | E x a c t ( k , U , F ) . \neg F _ { a } . G _ { a } \right ) \geq p r \left ( H | E x a c t ( k , U , F ) \right ) } \\ & { p r \left ( H | E x a c t ( k , U , F ) . \neg F _ { a } . \neg G _ { a } \right ) \leq p r \left ( H | E x a c t ( k , U , F ) \right ) } \end{array}$$ and reasoning by analogy (RA) assumption entails: $$\ p r \left ( H \, | \, E x a c t ( k , U , F ) . F _ { a } . G _ { a } \right ) > p r \left ( H \, | \, E x a c t ( k , U , F ) \right )$$ The above relations seem to be compatible with intuition. While the total number of objects that satisfy F is known in advance, the consideration of F a or ¬ F a should not affect our estimation of the frequency of the objects being F . On the other hand, the probability of G can still be affected by observations. Therefore, assuming PJ, consideration of G a increases the probability of G and consequently decreases the probability of F ¯ G . As a result it seems reasonable that the evidence G a confirms H = ( ¬ F ¯ G ) 1: N , and the evidence ¬ G a disconfirms it. Moreover, an observation F a .G a has an extra effect: While it is known that only k objects can be counterexamples to H (because in order to be F ¯ G , one should be F ), the observation F a .G a decreases the number of possible counterexamples by one. This holds even in the case where the chosen measure is such that inductive reasoning is not possible (e.g. the uniform measure is used). Consequently, in (4.10) inequality is strict, but in (4.11) and (4.12) it is not. Theorem (4.3) implies the following results: Corollary 4.4. If F := raven and G := black, according to relation (4.10) (or 4.13), PJ (or RA) leads to: pr ( H | (exactly k objects are ravens).(a specific object is raven and black)) > pr ( H | exactly k objects are ravens) Corollary 4.5. If F := nonBlack & G := nonRaven w.r.t. relation (4.10) (or 4.13), PJ (or RA) leads to: pr ( H | (exactly k objects are not black).(a specific object is nonBlack and nonRaven)) > pr ( H | exactly k objects are not black) Corollary 4.6. If F := raven and G := black, w.r.t. (4.11), PJ leads to: pr ( H | (exactly k objects are ravens).(a specific object is nonRaven and black)) ≥ pr ( H | exactly k individuals are ravens) Corollary 4.7. If F :=nonBlack & G :=nonRaven w.r.t. (4.11), PJ leads to: pr ( H | (exactly k individuals are not black).(a specific object is black and not raven)) ≥ pr ( H | exactly k individuals are not black) Corollary 4.8. If F := raven and G := black, w.r.t. (4.12), PJ leads to: pr ( H | (exactly k individuals are ravens).(a specific object is not raven and not black)) ≤ pr ( H | exactly k individuals are ravens) Corollary 4.9. If F := nonBlack & G := nonRaven, w.r.t. (4.12), PJ leads to: pr ( H | (exactly k individuals are not black).(a specific object is black and raven)) ≤ pr ( H | exactly k individuals are not black) Corollaries (4.4) to (4.9) are summarized in (Table 1). NC, if assumed to hold in this setting, suggests that the observation of a non-black non-raven and the observation of a black raven (i.e. entries in the first and fourth rows of the table) should confirm H which clearly contradicts what PJ suggests, therefore, there is a tension between these two rules. When background knowledge is neglected, intuition goes with PJ in the first column of the table. On the other hand, it does not completely match the suggestions of either NC or PC in the second column. This may indicate that intuition is more inclined to the case where 'the number of ravens' and not 'the number of non-blacks' is known in advance. In real life, none of these numbers is known but the total number of ravens can be estimated much easier than the Table 1: Weak projectability (PJ) vs. Nicod's condition (NC) and reasoning by analogy (RA) in setting 2. | | no. of the ravens is known | no. of non-blacks is known | |--------------------------------------|------------------------------------------------------------------------------|--------------------------------------------------------------------| | observation of a non-black non-raven | PJ: doesn't confirm H (Cor. 4.8) NC: confirms H RA: n/a | PJ: confirms H (Cor. 4.5) NC: confirms H RA: confirms H (Cor. 4.5) | | observation of a non-black raven | evidence refutes H | evidence refutes H | | observation of a black non-raven | PJ: doesn't disconfirm H (Corollary 4.6) NC: n/a RA: n/a | PJ: doesn't disconfirm H (Corollary 4.7) NC: n/a RA: n/a | | observation of a black raven | PJ: confirms H (Corollary 4.4) NC: confirms H RA: confirms H (Corollary 4.4) | PJ: does not confirm H (Corollary 4.9) NC: confirms H RA: n/a | number of non-black objects. On the other hand, if we are explicitly informed of the total number of non-black objects, at least in cases similar to the following example, intuition seems to follow PJ's suggestions in the second column: Imagine that you are only concerned about objects which are placed inside a bag (i.e. U := set of objects inside a bag ). Also imagine that you are told that only 4 objects are not black. In this case, there are just four possible counterexamples to H . Now suppose that a green apple comes out of the bag. Since it is green , it is one of those 4 non-blacks . Therefore, one possible counterexample is removed. Meanwhile, the fact that it is a non-raven may increase the probability of non-ravenhood (w.r.t. PJ). Therefore it is more probable that the 3 remaining non-blacks are also nonraven . Thus, this observation should confirm H . Now suppose that a black raven comes out. Its color informs us that it is not among the possible counterexamples but its kind increases the probability of ravenhood which is not in favor of H . So, this observation cannot confirm H . Therefore, this example suggests that in Setting 2, given the proper background knowledge, intuition does not follow NC. It follows PJ even if it advises that the observation of a green apple confirms that 'all ravens are black' and the observation of a black raven does not! Clearly, we can never 'prove' that a particular measure or a particular proposition is (or is not) 'intuitively plausible', due to the subjective nature of the problem. The former example presented a particular method of reasoning that relative to a given configuration supports PJ more than NC. This has convinced us that generally in setting 2, PJ is more plausible than NC but as we mentioned, some people might not be convinced. For example, one might argue that if we are told that the number of non-black objects is precisely 7 million, we can still believe that black ravens confirm that all ravens are black. Such reasoning might be on grounds of some 'hidden' background information such as knowing that ravens are animals and animals of the same kind often have similar colors. This particular background knowledge is not in ∆ (and therefore not in Setting 2) however as it was mentioned in the introduction, this knowledge is convertible to the subjectively chosen a priori probability measure. Of course given such knowledge, there will be no surprise if NC holds for F := raven and G := black but not for F := non-black and G := non-raven . However, it is up to the readers to judge about what is intuitive for them and what is not. What was formally provable (and is proved formally) is that in setting 2, no probability measure can simultaneously satisfy PJ and NC for a couple of predicates F and G . Reasoning by analogy vs. Nicod's condition: Table 1 clearly shows that the only cases where PJ and NC do not contradict is when according to RA, the general hypothesis H should be confirmed. In other cases, RA do not impose a restriction; therefore, it never contradicts either PJ or NC. A little thought reveals that RA and NC have many commonalities. We go a step further and propose a conjecture that NC may seem intuitively valid since it can easily be conflated with RA as follows: According to the informal definition of NC: 'The observation of an F that is G confirms that all F are G (or any F is G ).' Although this informal statement seems to be plausible a priori, it is vague and NC is not necessarily its only possible formalization. To begin with, it should be noticed that in informal language, the scopes of quantifiers are often ambiguous; For example the informal expression 'for all b , the probability of ψ b . . . ' can easily be mistaken for 'the probability that for all b , ψ b '. However the most suitable formalization of the former (i.e. ∀ b pr ( ψ b )) differs from that of the latter (i.e. pr ( ∀ b ψ b )). On the other hand, the informal 'if' does not exclusively stand for material implication ; in a proper context it can also mean conditional probability . Putting these together, it can be seen that: (Informal NC): 'The observation of an object a which is both F and G confirms that all (or any) object b that is F is also G .' can alternatively be formalized as: ∀ b pr ( G b | F b .F a .G a ) > pr ( G b | F b ). This relation is the definition of RA (see relation 2.2) - a rule of induction which is used in many fields (e.g. in case-based reasoning [AP94]), is directly justified by the principle of the uniformity of nature and does not suffer from the shortcomings of NC such as contradicting PJ or producing counterintuitive conclusions such as PC in the raven paradox. ## 5 When the Size of the Universe is Unknown In Section 1.1, we defined our probability space using the sample space Ω, the set of all complete description vectors (CDVs), all involving N objects. Thus, from the beginning, we had to assume that the cardinality of the universe is known. In this section, we instead assume that: 1. The size of the universe (i.e. N ) is unknown; however it is known that it is fixed and bounded by some known constants α and β . E.g. assume it is known that the number of the objects of the universe is larger than α = 10 10 and less than β = 10 1000 . 2. The new evidence E := F a .G a , does not affect the way the rational agent estimates the size of the universe. E.g., the observation of a black raven does not change the probability distribution over the possible sizes of the universe. We show that in this setting, our previous conclusions are still valid. Informally speaking, the reason is that all (in)equalities of the previous sections hold for any arbitrary (but fixed) size of the universe, therefore this number does not play a role, and consequently, even if it is unknown, (as long as new evidence does not affect the agent's beliefs about it) all (qualitative) relations should still hold. To justify this claim formally, we need some new notation: If it is known that the size of universe is υ , we let the enumeration of its objects be U υ := { 1 , 2 , . . . υ } (created recursively by U υ := U υ -1 /unionsq { υ } ). 19 Instead of ∆, we write ∆ υ to indicate that the members of this set describe individuals which belong to the universe U υ . Similarly, instead of Ω, we write Ω υ to emphasize that the sample space corresponds to a universe of size υ (i.e. U υ ). 20 Similarly, instead of pr ( · ), we write pr υ ( · ) to indicate that by definition, pr υ (defined on Ω υ ) is a measure that provides a probabilistic model for the rational agent (who performs induction), only if he/she/it knows the cardinality of the universe is υ . To prevent ambiguity, instead of representing the events by propositions, we directly use subsets of the sample spaces: The event that corresponds to an arbitrary proposition ρ relative to a sample space Ω υ is: ω Ω υ ρ := { o ∈ Ω υ : o | = ρ } . For example, if ρ := F 1 , then ω Ω 1 ρ represents the event { F ¯ G 1 , FG 1 } , while ω Ω 2 ρ stands for the event { F ¯ G 1 ¯ F ¯ G 2 , F ¯ G 1 ¯ FG 2 , F ¯ G 1 F ¯ G 2 , . . . , FG 1 FG 2 } . The Complete Description Vectors (CDVs) are here bold-faced and conjunction symbols '.' are dropped to emphasize that they are not ordinary propositions. For example FG 1 FG 2 is a CDV that not only entails the ordinary proposition FG 1 .FG 2 , but also indicates that the universe is U 2 = { 1, 2 } . The reason is that by definition, each CDV describes all objects of the universe (see Section 1.1). Let α and β be some known lower and upper bound for the size of the universe. 21 We define a new sample space Ω α : β as a set that contains all members of all sample spaces that correspond to universes with sizes at least equal to α and at most equal to β : $$\forall \alpha , \beta \in \mathbb { N } \ s . t . \ \alpha \leq \beta \quad \Omega _ { \alpha ; \beta } \colon = \bigsqcup _ { v = \alpha } ^ { \beta } \Omega _ { v }$$ 19 Note that ' /unionsq ' denotes the disjoint union operation. 20 While Ω υ contains CDVs that exactly describe υ objects, for all distinct υ ′ and υ ′′ , Ω υ ′ ∩ Ω υ ′′ = ∅ . 21 α is at least equal to the number objects mentioned by background knowledge or evidence. β can be arbitrarily large but for simplicity, we assume that it is finite. To see what would be needed if we wanted to allow β →∞ , refer to Footnote 23. Relative to the sample space Ω α : β and for all υ ∈ [ α, β ], the subset Ω υ represents the event that 'the size of the universe is υ '. We let: $$\omega _ { \rho } \colon = \{ o \in \Omega _ { \alpha ; \beta } \colon o \models \rho \} = \bigsqcup _ { v = \alpha } ^ { \beta } \{ o \in \Omega _ { v } \colon o \models \rho \} = \bigsqcup _ { v = \alpha } ^ { \beta } \omega _ { \rho } ^ { \Omega _ { v } } = \bigsqcup _ { v = \alpha } ^ { \beta } ( \omega _ { \rho } ^ { \Omega _ { v } } \cap \Omega _ { v } )$$ /negationslash ω ρ corresponds to the event that regardless of the size of the universe, proposition ρ holds. 22 We refer to ω ρ as the generalized correspondent of ρ . While ω Ω υ ρ ⊆ Ω υ and for all υ ′ = υ ′′ , Ω υ ′ ∩ Ω υ ′′ = ∅ , the above relation entails: $$\omega _ { \rho } ^ { \Omega _ { v } } = \omega _ { \rho } \cap \Omega _ { v } \quad ( 5 . 2 )$$ Likewise, the event that represents 'exactly k objects of a universe of unknown size (but bounded by α and β ) are F ' is defined as follows: $$\omega _ { E X A C T ( k , F ) } \colon = \bigsqcup _ { \upsilon = \alpha } ^ { \beta } \omega _ { E X A C T ( k , U _ { \upsilon } , F ) } ^ { \Omega _ { \upsilon } } = \bigsqcup _ { \upsilon = \alpha } ^ { \beta } ( \omega _ { E X A C T ( k , U _ { \upsilon } , F ) } ^ { \Omega _ { \upsilon } } \cap \Omega _ { \upsilon } )$$ We refer to ω Exact ( k,F ) as the generalized correspondent of Exact ( k, U α , F ) to Exact ( k, U β , F ). Over the sample space Ω α : β , we let Pr denote the probability measure that explains the rational agent 's a priori degrees of beliefs in the events. As mentioned in footnote (1), the existence of such a measure is deduced from the rationality axioms 23 [Sav54]. Note that: $$\forall \omega \subseteq \Omega _ { \alpha \colon \beta } , \forall v \in \mathbb { N } \, s . t . \, \alpha \leq v \leq \beta \quad P r ( \omega \, | \, \Omega _ { v } ) = p r _ { v } ( \omega ) \quad ( 5 . 3 )$$ The reason is that by definition, both sides of the above equation represent the probability measure chosen by the rational agent , when the size of the universe is known to be i . 24 Let E := F a .G a where a ∈ U α (consequently for all υ ≥ α , a ∈ U υ ), and ω D be either the generalized correspondent of Exact ( k, U α , F ) to Exact ( k, U β , F ) or the generalized correspondent of any D ∈ ∆ α . Roughly speaking, this means that ω D is the generalized correspondent of any piece of background knowledge which is discussed in the previous sections. Based on these notations, relation (5.4) represents a formal version of Assumption (2) (i.e. the assumption that the estimated size of the universe is not affected by evidence E ): $$\begin{array} { r l } & { ( A s u m p t i o n ) \, \forall v \in [ \alpha , \beta ] \, s . t . \, P r ( \Omega _ { v } ) > 0 } & { P r ( \Omega _ { v } | \omega _ { E } \cap \omega _ { D } ) = P r ( \Omega _ { v } | \omega _ { D } ) } & { ( 5 . 4 ) } \end{array}$$ 22 More specifically, ω ρ represents: ' N = α and ρ w.r.t. U α ' or ' N = α +1 and ρ w.r.t. U α +1 ' or . . . or ' N = β and ρ w.r.t. U β '. 23 For the case where Ω α : β is finite, Savages axioms are sufficient. If we wanted to study the case where it is infinite (i.e. no upper bound exists: β → ∞ ), we needed to add the monotone continuity assumption [Arr70] to the rationality axioms to guarantee countable additivity. 24 Evidently, if Pr(Ω υ ) = 0, both Pr( ω | Ω υ ) and pr υ ( ω ) are undefined. Having this setting, it is easy to show that all (in)equalities of the previous sections hold for the case where the exact number of objects in the universe is unknown. As an example, consider the relation (5.5). This is a typical inequality that informally speaking states that 'for any possible universe-size υ , if it is known that the size of the universe is equal to υ , relative to background knowledge D , the evidence E confirms the hypothesis H .' (Note that by the notation that we were using in the previous sections, this equation would be represented by pr ( H | E.D ) > pr ( H | D ) where the size of the universe was not mentioned explicitly.) $$\forall v \in \mathbb { N } \, s . t . \, \alpha \leq v \leq \beta , \, P r ( \Omega _ { v } ) > 0 \quad p r _ { v } ( \omega _ { H } ^ { \Omega _ { v } } | \, \omega _ { E } ^ { \Omega _ { v } } \cap \omega _ { D } ^ { \Omega _ { v } } ) > p r _ { v } ( \omega _ { H } ^ { \Omega _ { v } } | \, \omega _ { D } ^ { \Omega _ { v } } ) \ ( 5 . 5 )$$ Proposition 5.1 proves that the mentioned typical inequality entails that: Pr( ω H | ω E ∩ ω D ) > Pr( ω H | ω D ), which informally speaking asserts that relative to a universe of an unknown size (that is bounded by α and β ), in the presence of background knowledge D , the evidence E confirms H . Proposition 5.1. Let the size of the universe be unknown but known to be bounded by α and β . Let Pr be a probability measure that corresponds to the degrees of beliefs of a rational agent in the events of the sample space Ω α : β , defined by relation (5.1). If Pr complies with relation (5.4), then relation (5.5) entails: $$\Pr ( \omega _ { H } | \, \omega _ { E } \cap \omega _ { D } ) > \Pr ( \omega _ { H } | \, \omega _ { D } )$$ Proof. Let S := { s ∈ N : α ≤ s ≤ β, Pr(Ω s ) > 0 } be the set of all possible sizes of the universe. $$\forall v \in S \quad p r _ { v } ( \omega _ { H } ^ { \Omega _ { v } } | \, \omega _ { E } ^ { \Omega _ { v } } \cap \omega _ { D } ^ { \Omega _ { v } } ) > p r _ { v } ( \omega _ { H } ^ { \Omega _ { v } } | \, \omega _ { D } ^ { \Omega _ { v } } ) , \, b y ( 5 . 5 ) a n d d e f i n i t i o n o f S$$ $$\Rightarrow \forall v \in S \quad P r ( \omega _ { H } ^ { \Omega _ { v } } | \, \omega _ { E } ^ { \Omega _ { v } } \cap \omega _ { D } ^ { \Omega _ { v } } \cap \Omega _ { v } ) > P r ( \omega _ { H } ^ { \Omega _ { v } } | \, \omega _ { D } ^ { \Omega _ { v } } \cap \Omega _ { v } ) , b y r e l a t i o n ( 5 . 3 )$$ $$\begin{array} { r l } & { \Rightarrow \forall v \in S \quad P r \left ( \omega _ { H } \cap \Omega _ { v } \, | \, ( \omega _ { E } \cap \Omega _ { v } ) \cap ( \omega _ { D } \cap \Omega _ { v } ) \cap \Omega _ { v } \right ) > P r \left ( \omega _ { H } \cap \Omega _ { v } \, | \, ( \omega _ { D } \cap \Omega _ { v } ) \cap \Omega _ { v } \right ) , } \\ & { b y r e l a t i o n \, ( 5 . 2 ) } \end{array}$$ $$\Rightarrow \forall v \in S \quad P r ( \omega _ { H } | \, \omega _ { E } \cap \omega _ { D } \cap \Omega _ { v } ) > P r ( \omega _ { H } | \, \omega _ { D } \cap \Omega _ { v } ) , \ b y s i m p l i c a t i o n$$ $$\begin{array} { r l } & { \Rightarrow \forall v \in S \quad P r ( \Omega _ { v } | \omega _ { E } \cap \omega _ { D } ) \cdot P r ( \omega _ { H } | \omega _ { E } \cap \omega _ { D } \cap \Omega _ { v } ) > P r ( \Omega _ { v } | \omega _ { D } ) \cdot P r ( \omega _ { H } | \omega _ { D } \cap \Omega _ { v } ) , } \\ & { b y m u l t i p l y i n g t h e r . h . s . a n d l . h . s . b y t h e r . h . s . a n d l . h . s . o f r e l a t i o n ( 5 . 4 ) } \end{array}$$ $$\Rightarrow \sum _ { v \in S } \Pr ( \Omega _ { v } | \omega _ { E } \cap \omega _ { D } ) \cdot \Pr ( \omega _ { H } | \omega _ { E } \cap \omega _ { D } \cap \Omega _ { v } ) > \sum _ { v \in S } \Pr ( \Omega _ { v } | \omega _ { D } ) \cdot \Pr ( \omega _ { H } | \omega _ { D } \cap \Omega _ { v } )$$ The above inequality is equivalent to Pr( ω H | ω E ∩ ω D ) > Pr( ω H | ω D ) (where Ω υ is marginalized out), which is the intended result. ## 6 Conclusion We argued that from a Bayesian perspective, (a) objective background information (from previous observations) and subjective prior information (i.e. prior degrees of beliefs) can produce the same effects and in this sense, are convertible; therefore, in this context, 'the state of perfect ignorance' should be interpreted as 'the state of possessing no objective information and no subjective biased beliefs'. On the other hand, if we assume that the uniform probability measure corresponds to unbiased subjective degrees of beliefs (as it is often assumed), then we should conclude that: (b) with unbiased subjective beliefs, inductive reasoning is impossible. Therefore, based on (a) and (b), induction in a condition of perfect ignorance is impossible. In addition, by examples we have shown that relative to unrestricted objective/subjective prior information, common rules of induction do not always hold. We concluded that rules of induction should be considered plausible, if they hold relative to a large class of plausible (objective) background knowledge (i.e. knowledge similar to our actual background knowledge) and plausible probability measures (i.e. measures with reasonable characteristics such as complying with more intuitive rules of induction). Subsequently, we scrutinized the plausibility of NC by fixing the background knowledge and studying the characteristics of measures that do or do not comply with it. In the first setting, the background knowledge is composed of complete descriptions of several objects. It is shown that in this setting, validity of NC is implied by the answer to a simpler question that does not seem to have a general intuitive answer i.e. for distinct objects a and b , whether E = F a .G a confirms F b . ¬ G b or not. While due to the chosen probability measure and characteristics of F and G , the latter condition does not hold in general, we concluded that in this setting NC is not significantly more reasonable than ¬ NC. In the second setting, the number of objects satisfying a particular predicate is known by background knowledge. It is shown that in this case, NC may contradict PJ while seemingly, intuition follows the latter. In summary: 1. There are reasonable (i.e. not implausible a priori) probability measures for which NC does not hold; 2. There are reasonable probability measures for which weak projectability, i.e. one of the simplest forms of inductive inference, opposes NC; 3. In the case of contradiction, intuition 'seems to' follow projectability rather than NC; Hence, we conclude that we have gathered some evidence against the assumption that NC is a generally reliable rule of induction. If NC is not considered plausible then the raven paradox is also dispelled since even if NC holds for two predicates F and G , it does not mean that it should hold for ¬ G and ¬ F . This asymmetry may be due to possible asymmetry in background knowledge and/or priors. Of the three mentioned points, point (1) had already been demonstrated [Mah04]. The distinction is that we have dealt with NC without relying on any particular a priori measure. As mentioned throughout the paper, in the Bayesian framework one's choice of prior probability distribution is subjective. Nevertheless, Bayesian agents' beliefs at any time are (heavily) dependent on their prior distributions. Therefore, different subjective choices may lead to contradictory results. In the case of variations of Carnap's measure, this freedom of choice also resurfaces in the form of one or several arbitrary parameters. [Mah99] and [Mah04] are two variations of Carnap's measure but for the former, NC always holds and for the latter, for some parameter configurations, it does not. Although one might claim that the existence of at least one measure that does not comply with NC is sufficient to discredit NC, one should note that any rule of induction can be violated by some measures and remains valid for some others. In fact one might contrarily claim that contradiction of a measure with an 'intuitive' rule of induction should discredit that particular measure rather than the rule. Therefore, our sufficient condition for ( ¬ NC) that covers a class of measures rather than a specific one, should be considered a more general and interesting relation. The main contribution of our work is the conjunction of points (2) and (3). We believe that compared to the raven paradox's PC and other counterintuitive consequences of NC, the conflict between NC and PJ is more important. To our knowledge, other counterintuitive consequences (such as The red herring [Goo67] and Good's baby [Goo68] problems) are either related to arguably implausible background configurations, or as is the case with PC, some claim that they are not counterintuitive. PJ is a very simple form of inductive inference. It is more directly justified by our intuitive notion of inductive reasoning than NC, and it's plausibility cannot be challenged as easily. We also proposed a conjecture that NC seems to be plausible because it can be mistaken for reasoning by analogy (RA) which has a closely related informal representation. We proved that in the case where the exact number of objects satisfying one property is known, RA is compatible with both PJ and NC. It is a conservative condition that intuitively seems plausible and does not suffer from the shortcomings of NC (such as contradicting PJ or producing counterintuitive conclusions such as PC) and is directly justified by the principle of the uniformity of nature. ## 7 Proof of Theorems ## 7.1 Proof of Theorems 3.1 and 3.2 Lemma 1. In relation (2.3), if D ∈ δ , NC is equivalent to Ξ 1 · Ξ 2 > 1 where: U \I D := { b 1 , . . . b n , a } is 'the set of objects not described by D ', Ξ 1 := pr ( F → G b 1 : bn | FG a .D ) pr ( F → G b 1 : bn | D ) and Ξ 2 := 1 pr ( F → G a | F → G b 1 : bn .D ) . Proof. Objects are either completely described by D ∈ δ or are not described at all. Therefore: $$p r ( F _ { \rightarrow } G _ { 1 ; N } | D ) = p r ( F _ { \rightarrow } G _ { b _ { 1 } \colon b _ { n } } . F _ { \rightarrow } G _ { a } | D ) \quad ( 7 . 1 )$$ $$p r ( F \rightarrow G _ { 1 \colon N } | F G _ { a } . D ) = p r ( F \rightarrow G _ { b _ { 1 } \colon b _ { n } } | F G _ { a } . D )$$ Combination of (7.1), (7.2) and (2.3) proves the lemma. 25 Proof of Theorem 3.1. Due to pr ( F ¯ G b |· ) = 1 -pr ( F → G b |· ), relation (3.1) is equal to: $$\forall B \in \Delta , \forall a , b \notin \mathcal { I } _ { B } \quad p r ( F \to G _ { b } | F G _ { a } . B ) \geq p r ( F \to G _ { b } | B ) \quad ( 7 . 3 )$$ Let arbitrary D ∈ δ and I D = U \{ b 1 , . . . , b n , a } (i.e. b 1 to b n are the objects not mentioned by background knowledge or evidence). According to the definitions of δ and ∆, for all i < n : F → G b 1 . . . F → G b i .D ∈ ∆ (because it is consistent) and a, b i +1 / ∈ I F → G b 1 ...F → G b i .D . Therefore, from (7.3) it follows that: $$\forall i < n \, & \ p r ( F _ { \to } G _ { b _ { i + 1 } } | F _ { \to } G _ { b _ { 1 } \colon b _ { i } } . F G _ { a } . D ) \geq p r ( F _ { \to } G _ { b _ { i + 1 } } | F _ { \to } G _ { b _ { 1 } \colon b _ { i } } . D ) \\ & \Longrightarrow \prod _ { i = 0 } ^ { n - 1 } p r ( F _ { \to } G _ { b _ { i + 1 } } | F _ { \to } G _ { b _ { 1 } \colon b _ { i } } . F G _ { a } . D ) \geq \prod _ { i = 0 } ^ { n - 1 } p r ( F _ { \to } G _ { b _ { i + 1 } } | F _ { \to } G _ { b _ { 1 } \colon b _ { i } } . D ) \quad ( 7 . 4 )$$ Due to the chain rule, the r.h.s. of the above equation is equal to pr ( F → G b 1 : b n | D ): $$\prod _ { i = 0 } ^ { n - 1 } p r ( F _ { \rightarrow } G _ { b _ { i + 1 } } | F _ { \rightarrow } G _ { b _ { 1 } \colon b _ { i } } . D ) = \\ p r ( F _ { \rightarrow } G _ { b _ { 1 } } | D ) \cdot p r ( F _ { \rightarrow } G _ { b _ { 2 } } | F _ { \rightarrow } G _ { b _ { 1 } } . D ) \dots p r ( F _ { \rightarrow } G _ { b _ { n } } | F _ { \rightarrow } G _ { b _ { 1 } } \dots F _ { \rightarrow } G _ { b _ { n - 1 } } . D ) = p r ( F _ { \rightarrow } G _ { b _ { 1 } \colon b _ { n } } | D )$$ Similarly, the l.h.s. of (7.4) is equal to pr ( F → G b 1 : b n | FG a .D ). Therefore: $$p r ( F \rightarrow G _ { b _ { 1 } \colon b _ { n } } | F G _ { a } . D ) \geq p r ( F \rightarrow G _ { b _ { 1 } \colon b _ { n } } | D )$$ This entails Ξ ≥ 1 and since Ξ > 1 2 1, according to Lemma 1, NC holds. Proof of Theorem 3.2. Similar to the method used in the proof of Theorem 3.1 and by using inequality (3.2) instead of inequality (3.1) it can be proved that: $$\begin{array} { r l } { \forall i < n } & p r ( F _ { \rightarrow } G _ { b _ { i + 1 } } | \, F _ { \rightarrow } G _ { b _ { 1 } \colon b _ { i } } . \, F G _ { a } . \, D ) < p r ( F _ { \rightarrow } G _ { b _ { i + 1 } } | \, F _ { \rightarrow } G _ { b _ { 1 } \colon b _ { i } } . \, D ) } \end{array}$$ Consequently: $$\Xi _ { 1 } = \frac { \prod _ { i = 1 } ^ { n - 1 } p r ( F _ { \to } G _ { b _ { i + 1 } } | F _ { \to } G _ { b _ { 1 } \colon b _ { i } } . F G _ { a } . D ) } { \prod _ { i = 1 } ^ { n - 1 } p r ( F _ { \to } G _ { b _ { i + 1 } } | F _ { \to } G _ { b _ { 1 } \colon b _ { i } } . D ) } \cdot \frac { p r ( F _ { \to } G _ { b _ { 1 } } | F G _ { a } . D ) } { p r ( F _ { \to } G _ { b _ { 1 } } | D ) } < \frac { p r ( F _ { \to } G _ { b _ { 1 } } | F G _ { a } . D ) } { p r ( F _ { \to } G _ { b _ { 1 } } | D ) } \\$$ 25 Note that Ξ 1 indicates the effect of the observation F a .G a , on the probability that unobserved individuals satisfy F → G and Ξ 2 corresponds to the effect of elimination of the possibility that the observed object is a counterexample to the generalization. $$^ { \prime }$$ For conciseness, let p := pr ( F → G b 1 | FG a .D ) and q := pr ( F → G b 1 | D ). $$& \ p r ( \neg F _ { \to } G _ { a } | F _ { \to } G _ { b _ { 1 } \colon b _ { n } } . D ) < ( 1 - p ) - ( 1 - q ) , \quad \text {since $F_{\to}G=\neg F_{\bar{G}}$ and by inequality $(3.3)$} \\ & \implies p r ( F _ { \to } G _ { a } | F _ { \to } G _ { b _ { 1 } \colon b _ { n } } . D ) > 1 - q + p$$ Finally, $$\begin{array} { l l } 1 - p > 1 - q \implies p < q , & \text {since $D\in\Delta$ and by $(3.2)$} \\ \implies p \cdot ( 1 - q ) < q \cdot ( 1 - q ) \implies p < q \cdot ( 1 - q + p ) , & \text {since $q<1$} \\ \implies \frac { p } { q } < 1 - q + p & \text {since $q>0$} \\ \implies \Xi _ { 1 } < p r ( F _ { \to } G _ { a } | F _ { \to } G _ { b _ { 1 } \colon b _ { n } } . D ) , & \text {by $(7.5)$ and $(7.6)$} \\ \implies \Xi _ { 1 } \cdot \Xi _ { 2 } < 1 \implies N C \text { does not hold.} & \text {by Lemma $1$} \end{array}$$ ## 7.2 Proof of Theorem 4.1 Lemma 2. Under PJ, for any set of objects { 1 , 2 , . . . , n } ⊆ U , a ∈ U and any D ∈ ∆ that does not determine the value of ψ a : $$& \text {(Group PJ)} & & p r ( \psi _ { 1 \colon n } | \, \psi _ { a } . D ) \geq p r ( \psi _ { 1 \colon n } | \, D ) \\ & \text {(Negative Group PJ)} & & p r ( \psi _ { 1 \colon n } | \neg \psi _ { a } . D ) \leq p r ( \psi _ { 1 \colon n } | \, D )$$ Proof. The proof is based on mathematical induction. 1. Proof of relation (7.7): 2. (I) For n = 1, relation (7.7) is equivalent to relation (2.1) and therefore valid. 3. (II) Assume for n = k relation (7.7) holds. We prove that for n = k +1, it holds as well: $$\begin{array} { r l } & { p r ( \psi _ { 1 \colon k + 1 } | \psi _ { a } . D ) = p r ( \psi _ { 1 \colon k } . \psi _ { k + 1 } | \psi _ { a } . D ) } \\ & { \quad = p r ( \psi _ { k + 1 } | \psi _ { a } . D ) \cdot p r ( \psi _ { 1 \colon k } | \psi _ { a } . \psi _ { k + 1 } . D ) } \\ & { \geq p r ( \psi _ { k + 1 } | \, D ) \cdot p r ( \psi _ { 1 \colon k } | \psi _ { a } . \psi _ { k + 1 } . D ) , \quad b y i n e q u a l i t y \, ( 2 . 1 ) } \\ & { \geq p r ( \psi _ { k + 1 } | \, D ) \cdot p r ( \psi _ { 1 \colon k } | \psi _ { k + 1 } . D ) , \quad ( 2 . 1 ) a p p l i e d t o \, ( \psi _ { k + 1 } . D ) \in \Delta } \\ & { = p r ( \psi _ { 1 \colon k + 1 } | D ) } \end{array}$$ By (I) & (II), mathematical induction implies (7.7) for all n . 2. Proof of relation (7.8): Under PJ: ∀ b pr ( ¬ ψ b | ¬ ψ a .D ) ≥ pr ( ¬ ψ b | D ), therefore: $$1 - p r ( \psi _ { b } | \neg \psi _ { a } . D ) \geq 1 - p r ( \psi _ { b } | \, D ) \implies p r ( \psi _ { b } | \neg \psi _ { a } . D ) \leq p r ( \psi _ { b } | \, D )$$ Similar to the previous case and by using (7.9) instead of (2.1), inequality (7.8) can be proved easily. Lemma 3. For all 1 ≤ k ≤ N , D := F 1: k . ( ¬ F ) k +1: N and E being an arbitrary proposition: pr ( H | E.D ) = pr ( G 1: k | E.D ). $$\begin{array} { r l } & { P r o f . \, l . h . s . = p r \left ( F \rightarrow G _ { 1 \colon k } . F \rightarrow G _ { k + 1 \colon N } | E \, . \, F _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } \right ) } \\ & { = p r \left ( F \rightarrow G _ { 1 \colon k } . F _ { 1 \colon k } . F \rightarrow G _ { k + 1 \colon N } . ( \neg F ) _ { k + 1 \colon N } | E \, . \, F _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } \right ) } \\ & { = p r \left ( ( F \rightarrow G . F ) _ { 1 \colon k } . ( F \rightarrow G . \neg F ) _ { k + 1 \colon N } | E \, . \, F _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } \right ) } \\ & { = p r \left ( ( F . G ) _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } | E \, . \, F _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } \right ) \left ( s i n c e F \rightarrow G _ { b } . F _ { b } \equiv F _ { b } . G _ { b } a n d F \rightarrow G _ { b } . \neg F _ { b } \right ) } \\ & { \equiv \neg F _ { b } \right ) } \\ & { = p r \left ( F _ { 1 \colon k } . G _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } | E \, . \, F _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } \right ) } \\ & { = p r \left ( G _ { 1 \colon k } | E \, . \, F _ { 1 \colon k } . ( \neg F ) _ { k + 1 \colon N } \right ) = r . h . s . } \end{array}$$ Proof of Theorem 4.1. In the following relations, D := F 1: k . ( ¬ F ) k +1: N . - (I) Proof of relation (4.1), i.e. pr ( H | G k . D ) > pr ( H | D ) by PJ: $$\begin{array} { l l } & p r ( H | \, G _ { k } \, . \, D ) = p r ( G _ { 1 \colon k } | \, G _ { k } \, . \, D ) , & b y L e m m a \, 3 \\ & = p r ( G _ { 1 \colon k - 1 } | \, G _ { k } \, . \, D ) \geq p r ( G _ { 1 \colon k - 1 } | \, D ) , & b y L e m m a \, 2 \\ & > p r ( G _ { 1 \colon k } | \, D ) , & a d d i n g \, G _ { k } \, \& C o u r n o t ^ { \prime } s p . \, ( n o t e \colon \, D \, \nmid \, G _ { k } ) \\ & = p r ( H | \, D ) , & b y L e m m a \, 3 . \end{array}$$ - (II) Proof of relation (4.2), i.e. pr ( H | G N . D ) ≥ pr ( H | D ) by PJ: $$\begin{array} { l l } { p r ( H | G _ { N } . D ) = p r ( G _ { 1 \colon k } | G _ { N } . D ) , } & { b y L e m m a 3 } \\ { \geq p r ( G _ { 1 \colon k } | D ) , } & { b y r e l a t i o n ( 7 . 7 ) ( G r o u p P J ) } \\ { = p r ( H | D ) , } & { b y L e m m a 3 . } \end{array}$$ - (III) Proof of relation (4.3) i.e. pr ( H | ¬ G N . D ) ≤ pr ( H | D ) by PJ: $$\begin{array} { r l r l } & { p r ( H | \neg G _ { N } \, . \, D ) = p r ( G _ { 1 \colon k } | \neg G _ { N } \, . \, D ) , } & & { b y L e m m a 3 } \\ & { \leq p r ( G _ { 1 \colon k } | \, D ) , } & & { b y r e l a t i o n ( 7 . 8 ) ( N e g . G r o u p P J ) } \\ & { = p r ( H | \, D ) , } & & { b y L e m m a 3 . } \end{array}$$ (IV) Proof of relation (4.4) , i.e. pr ( H | G k . D ) > pr ( H | D ) by RA: pr $$( \text {IV} ) & \quad \text {Proof of relation (4.4)} \, , \, i . e . \, p r ( H \, | \, G _ { k } \, . \, D ) > p r ( H \, | \, D ) \, b y \, R A \colon \\ & \ p r ( H \, | \, G _ { k } \, . \, D ) = p r ( G _ { 1 \colon k - 1 } | \, G _ { k } \, . \, D ) , \, b y \, L e m m a \, 3 \\ & = \prod _ { i = 1 } ^ { k - 1 } p r ( G _ { i } | G _ { 1 \colon i - 1 } . G _ { k } . D ) , \quad b y \, t h e \, c a n \, r u l e \\ & = \prod _ { i = 1 } ^ { k - 1 } p r ( G _ { i } | F _ { i } . F _ { k } . G _ { k } . G _ { 1 \colon i - 1 } . D ) , \quad s i n c e \, D \vdash F _ { i } . F _ { k } \\ & > \prod _ { i = 1 } ^ { k - 1 } p r ( G _ { i } | F _ { i } . G _ { 1 \colon i - 1 } . D ) , \quad b y \, R A \, ( a n d \, s i n c e \, G _ { 1 \colon i - 1 } . D \in \Delta ) \\ & = \prod _ { i = 1 } ^ { k - 1 } p r ( G _ { i } | G _ { 1 \colon i - 1 } . D ) , \quad s i n c e \, f o r \, i \in \{ 1 , \dots , k \} \, \colon D \vdash F _ { i } \\ & = p r ( G _ { 1 \colon k - 1 } | \, D ) , \quad b y \, t h e \, c a n \, r u l e \\ & > p r ( G _ { 1 \colon k } | \, D ) , \quad b y \, d o d i n g \, G _ { k } \, \& \, C o u r n o t ^ { \prime } s \, p p . \, ( n o t e \colon \, D \not \, G _ { k } ) \\ & = p r ( H | \, D ) , \quad b y \, L e m m a \, 3 .$$ ## 7.3 Proof of Theorem 4.2 Definition. Having a set C ⊆ U and π being a permutation (of U ), C π is defined as: C π := { π ( b ) : b ∈ C } . It is obvious that U π = U . The following two relations directly follows from the assumption that π is a bijection: $$\begin{array} { l l } \forall C \subseteq U & | C | = | C ^ { \pi } | \\ \forall C , C ^ { \prime } \subseteq U & C \neq C ^ { \prime } \implies C ^ { \pi } \neq C ^ { \prime \pi } \end{array}$$ $$\forall C , C ^ { \prime } \subseteq U \quad & C \neq C ^ { \prime } \implies C ^ { \pi } \neq C ^ { \prime \pi } \\$$ /negationslash /negationslash Lemma 4. H = H π where π is an arbitrary permutation (of U ). $$P r o f . \ H ^ { \pi } = \bigwedge _ { b \in U } F \rightarrow G _ { \pi ( b ) } = \bigwedge _ { \pi ( b ) \in U ^ { \pi } } F \rightarrow G _ { b ^ { \prime } } = \bigwedge _ { b ^ { \prime } \in U } F \rightarrow G _ { b ^ { \prime } } = H$$ The first equality holds by definition. The second equality holds because: b ∈ U ⇐⇒ π ( b ) ∈ U π . In the r.h.s. of the third equality, π ( b ) is renamed to b ′ . The fourth equality holds because U = U π (note that π is a permutation in U ). The last equality is the definition of H . Lemma 5. For all 1 ≤ k ≤ N , all permutations π and C U,k being defined as the set of all subsets of U which have size k : $$\mathfrak { C } _ { U , k } ^ { \pi } \colon = \{ C ^ { \pi } \, \colon C \in \mathfrak { C } _ { U , k } \} = \mathfrak { C } _ { U , k }$$ Proof. Equality (7.10) implies, ∀ C π ∈ C π U,k | C π | = | C | = k , which means: C π is a k-combination from U ; So from the definition of C U,k it follows that C π ∈ C U,k . Therefore, C π U,k ⊆ C U,k . Conversely, according to relation (7.11) and the definition of C π U,k in (7.12), there is a one-to-one relation between the members of C U,k and C π U,k . This entails: | C π U,k | = | C U,k | . Thus: C π U,k = C U,k . Lemma 6. For all permutations π (of the set U ), and for all integers k ∈ [1 , N ]: Exact ( k, U, F ) = Exact π ( k, U, F ) Proof. By definition, Exact π ( k, U, F ) := ∨ C ∈ C U,k ( ∧ a ∈ C F π ( a ) . ∧ b /negationslash∈ C ¬ F π ( b ) ) $$& = \bigvee _ { C \in \mathfrak { E } _ { U , k } } ( \bigwedge _ { \pi ( a ) \in C ^ { \pi } } F _ { \pi ( a ) } \cdot \bigwedge _ { \pi ( b ) \not \in C ^ { \pi } } \neg F _ { \pi ( b ) } ) , \\ & = \bigvee _ { C ^ { \prime } \in \mathfrak { E } _ { U , k } ^ { \pi } } ( \bigwedge _ { a ^ { \prime } \in C ^ { \prime } } F _ { a ^ { \prime } } \cdot \bigwedge _ { b ^ { \prime } \not \in C ^ { \prime } } \neg F _ { b ^ { \prime } } ) , \\ & = \bigvee _ { C ^ { \prime } \in \mathfrak { E } _ { U , k } ^ { \pi } } ( \bigwedge _ { a ^ { \prime } \in C ^ { \prime } } F _ { a ^ { \prime } } \cdot \bigwedge _ { b ^ { \prime } \not \in C ^ { \prime } } \neg F _ { b ^ { \prime } } ) , \\ & = \text {EXACT} ( k , U , F ) ,$$ since c ∈ C ⇐⇒ π ( c ) ∈ C π since C ∈ C U,k ⇐⇒ C π ∈ C π U,k renaming C π to C ′ and π ( c ) to c ′ $$\sin c e \, { \mathfrak C } _ { U , k } ^ { \pi } = { \mathfrak C } _ { U , k } , \, ( L e m m a \ 5 )$$ by definition. Definition. For each C ⊆ U , the proposition Z ( C,F ) is defined as: $$Z _ { ( C , F ) } \colon = \bigwedge _ { a \in C } F _ { a } \cdot \bigwedge _ { b \not \in C } \neg F _ { b }$$ which allows to write definition (4.5) as: Exact ( k, U, F ) := ∨ C ∈ C U,k Z ( C,F ) Lemma 7. For arbitrary propositions A and B and 1 ≤ k ≤ N : $$\ p r ( \text {Exact} ( k , U , F ) . A | B ) = \sum _ { C \in \mathfrak { C } _ { U , k } } \ p r ( Z _ { ( C , F ) } . A | B )$$ /negationslash Proof. ∀ C ′ = C ′′ ∈ C U,k : $$\begin{array} { r l } & { \exists b \in U \quad b \in C ^ { \prime } a n d b \not \in C ^ { \prime \prime } , } & { C ^ { \prime } \, \& \, C ^ { \prime \prime } b e i n g d i s t i c t w i t h s a m e s i z e } \\ & { \Longrightarrow Z _ { ( C ^ { \prime } , F ) } \models F _ { b } a n d Z _ { ( C ^ { \prime \prime } , F ) } \models \neg F _ { b } , \quad b y d e f i n t i o n ( 7 . 1 3 ) } \\ & { \Longrightarrow Z _ { ( C ^ { \prime } , F ) } . Z _ { ( C ^ { \prime \prime } , F ) } \models F _ { b } . \neg F _ { b } \equiv \bot } \end{array}$$ Therefore, the sequence { Z ( C,F ) } C ∈ C U,k consists of mutually disjoint events. Hence, by the third Kolmogorov probability axiom, for all propositions A and B : $$p r ( \text {Exact} ( k , U , F ) . A | B ) = p r ( \bigvee _ { C \in \mathfrak { C } _ { U , k } } ( Z _ { ( C , F ) } . A ) | B ) = \sum _ { C \in \mathfrak { C } _ { U , k } } p r ( Z _ { ( C , F ) } . A | B ) \quad ( 7 . 1 5 )$$ Lemma 8. Let 1 ≤ k ≤ N . For all C ∈ C U,k and for all permutations π : $$Z _ { ( C , F ) } ^ { \pi } = Z _ { ( C ^ { \pi } , F ) }$$ by relation (7.13) ) by def. c ∈ C ⇐⇒ π ( c ) ∈ C π renaming π ( a ) to a ′ and π ( b ) to b ′ by relation (7.13) . Proof. $$P r o o f . \\ Z _ { ( C , F ) } ^ { \pi } & = \bigwedge _ { a \in C } F _ { \pi ( a ) } \cdot \bigwedge _ { b \not \in C } \neg F _ { \pi ( b ) } \\ & = \bigwedge _ { \pi ( a ) \in C ^ { \pi } } F _ { \pi ( a ) } \cdot \bigwedge _ { \pi ( b ) \not \in C ^ { \pi } } \neg F _ { \pi ( b ) } \\ & = \bigwedge _ { a^{\prime} \in C ^ { \pi } } F _ { a^{\prime } } \cdot \bigwedge _ { b^{\prime} \not \in C ^ { \pi } } \neg F _ { b^{\prime } } \\ & = Z _ { ( C ^ { \pi } , F ) }$$ Proof of Theorem 4.2. For the sake of conciseness, here we only prove relation (4.7) i.e.: $$\forall a \in U , 1 \leq k \leq N \quad p r { \left ( H | E x a c t ( k , U , F ) \, . F _ { a } . G _ { a } \right ) } = p r { \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { k } \right ) } \\ \begin{array} { r l } & { \forall a \in U , 1 \leq k \leq N \quad p r { \left ( H | E x a c t ( k , U , F ) \, . F _ { a } . G _ { a } \right ) } = p r { \left ( H | F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { k } \right ) } } \\ & { T h e r m a i n i n g r e l a t i o n s ( 4 . 6 , 4 . 8 \, \& \, 4 . 9 ) \, c a n b e p r o v e d u s i n g t h e s a m e m y t h e d o m a n d } \\ & { T h e r m a i n i n g r e l a t i o n s ( 4 . 6 , 4 . 8 \, \& \, 4 . 9 ) \, c a n b e p r o v e d u s i n g t h e s a m e m y t h e d o m a n d } \end{array}$$ The remaining relations (4.6, 4.8 & 4.9) can be proved using the same method and by small (and obvious) appropriate modifications. For the sake of simplicity, we first swap the names of the objects a and 1 as follows: Let π ′ := { a/ 1; 1 /a } . By the exchangeability assumption: $$& \quad p r ( H | \text {Exact} ( k , U , F ) . F _ { a } . G _ { a } ) = p r ( H ^ { \pi ^ { \prime } } | \text {Exact} ^ { \pi ^ { \prime } } ( k , U , F ) \, . F _ { \pi ^ { \prime } ( a ) } . G _ { \pi ^ { \prime } ( a ) } ) \\ & \quad = p r ( H | \text {Exact} ( k , U , F ) . F _ { 1 } . G _ { 1 } ) , & & \text {by Lemmas 4 and 6} \\ & \quad = \frac { p r ( H ) \cdot p r ( \text {Exact} ( k , U , F ) . F _ { 1 } . G _ { 1 } | H ) } { p r ( \text {Exact} ( k , U , F ) . F _ { 1 } . G _ { 1 } ) } , & & \text {by Bayes rule.} \\$$ Now: $$& \ p r ( \text {Exact} ( k , U , F ) \, . F _ { 1 } . G _ { 1 } | H ) = \sum _ { C \in \mathfrak { E } _ { U , k } } p r ( Z _ { ( C , F ) } . F _ { 1 } . G _ { 1 } | H ) , \quad \text {by Lemma 7} \\ & = \sum _ { C \in \mathfrak { E } _ { U , k } \ s . t . \, 1 \in C } p r ( Z _ { ( C , F ) } . F _ { 1 } . G _ { 1 } | H ) \quad + \sum _ { C \in \mathfrak { E } _ { U , k } \ s . t . \, 1 \notin C } p r ( Z _ { ( C , F ) } . F _ { 1 } . G _ { 1 } | H ) \\ & = \sum _ { C \in \mathfrak { E } _ { U , k } \ s . t . \, 1 \in C } p r ( Z _ { ( C , F ) } . F _ { 1 } . G _ { 1 } | H )$$ The second summation is eliminated because in the case of any C ∈ C U,k such that 1 /negationslash∈ C , Z ( C,F ) /satisfies ¬ F 1 (see definition (7.13)), therefore in this case, pr ( Z ( C,F ) .F 1 .G 1 | H ) = pr ( Z ( C,F ) . ¬ F 1 .F 1 .G 1 | H ) = pr ( ⊥| H ) = 0. Due to the exchangeability assumption, the members of the first summation are all equal. The reasoning is as follows: In the case of any C ∈ C U,k such that 1 ∈ C , there exists some permutation that map each of the members of C to the set { 1 , 2 , . . . k } with 1 as a fixed point i.e.: $$\forall C \in { \mathfrak { C } } _ { U , k } \, s . t . \, 1 \in C \colon \quad \exists \pi \quad C ^ { \pi } = \{ 1 , 2 , \dots , k \} , \, \pi ( 1 ) = 1$$ In fact, for any member of C U,k , exactly ( k -1)! permutations with such properties exist. Using such permutations, ∀ C ∈ C U,k s.t. 1 ∈ C : $$\exists \pi & \ p r ( Z _ { ( C , F ) } . F _ { 1 } . G _ { 1 } | H ) = p r ( Z ^ { \pi } _ { ( C , F ) } . F _ { \pi ( 1 ) } . G _ { \pi ( 1 ) } | H ^ { \pi } ) , \text { by exchangeability} \\ & = p r ( Z _ { ( \{ 1 , \dots , k \} , F ) } . F _ { \pi ( 1 ) } . G _ { \pi ( 1 ) } | H ^ { \pi } ) , & \text { using } ( 7 . 1 8 ) \text { in Lemma } 8 \\ & = p r ( Z _ { ( \{ 1 , \dots , k \} , F ) } . F _ { 1 } . G _ { 1 } | H ^ { \pi } ) , & \text { by Lemma } 4 \\ & = p r ( F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { 1 } | H ) , & \text { expanding } Z _ { ( \dots , ) } \text { by def. } ( 7 . 1 3 )$$ Thus, combining (7.17) and (7.19): $$& p r \left ( \text {EXACT} ( k , U , F ) . F _ { 1 } . G _ { 1 } | H \right ) = \sum _ { C \in \mathfrak { C } _ { U , k } \text { s.t. } 1 \in C } p r ( Z _ { ( C , F ) } . F _ { 1 } . G _ { 1 } | H ) \\ & \quad = \binom { N - 1 } { k - 1 } p r ( F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { 1 } | H )$$ By a similar justification: $$p r \left ( E X A C T ( k , U , F ) . F _ { 1 } . G _ { 1 } \right ) = \binom { N - 1 } { k - 1 } p r ( F _ { 1 \colon k } . \neg F _ { k + 1 \colon N } . G _ { 1 } )$$ Combining equations (7.20), (7.21) and (7.16): $$& \ p r { \left ( E X A C T ( k , U , F ) \, . F _ { 1 } . G _ { 1 } | H \right ) } = \frac { \ p r { \left ( H \right ) \cdot p r { \left ( E X A C T ( k , U , F ) \, . F _ { 1 } . G _ { 1 } | H \right ) } } { \ p r { \left ( E X A C T ( k , U , F ) \, . F _ { 1 } . G _ { 1 } \right ) } } \\ & = \frac { \binom { N - 1 } { k - 1 } \ p r { \left ( H \right ) \ p r { \left ( F _ { 1 \colon k } \neg F _ { k + 1 \colon N } . G _ { 1 } | H \right ) } } { \binom { N - 1 } { k - 1 } \ p r { \left ( F _ { 1 \colon k } \neg F _ { k + 1 \colon N } . G _ { 1 } \right ) } } = \ p r { \left ( H | F _ { 1 \colon k } \neg F _ { k + 1 \colon N } . G _ { 1 } \right ) }$$ ## References - [AP94] Aamodt, A. and Plaza, E. (1994). Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches, Artificial Intelligence Communications 7 , 1: 39-52. - [Arr70] Arrow, K. (1970). Essays in the Theory of Risk-Bearing , North-Holland. - [Car50] Carnap, R. (1950). Logical Foundations of Probability , Chicago: Chicago University Press. 2nd Ed. 1962. - [Car80] Carnap, R. (1980). A Basic System of Inductive Logic, Part II. (In Richard C. Jeffrey (Ed.), Studies in Inductive Logic and Probability , vol. 2. Berkeley: University of California Press) - [Cou43] Cournot, A. (1943). Exposition de la th´ eorie des chances et des probbilit´ es . L. Hachette, Paris. - [FH06] Fitelson, B. and Hawthorne, J. (2006). How Bayesian Confirmation Theory Handles the Paradox of the Ravens. (In E. Eells & J. Fetzer (Eds.) Probability in Science ). http://fitelson.org/research.htm. - [FH10] Fitelson, B. and Hawthorne, J. (2010). The Wason Task(s) and the Paradox of Confirmation. Philosophical Perspectives . - [Goo67] Good I. J. (1967). The White Shoe is a Red Herring. British Journal for the Philosophy of Science , Vol. 17, No. 4: 322. - [Goo68] Good, I. J. (1968). The White Shoe qua Red Herring is Pink. British Journal for the Philosophy of Science 19: 156-157. - [GS82] Gaifman, H. and Snir, M. (1982). Probabilities over rich languages, testing and randomness. Journal of Symbolic Logic , 47(3):495-548. - [Hem45] Hempel, C. G. (1945). Studies in the Logic of Confirmation. Mind 54: 1-26, 97-121. - [Hem67] Hempel, C. G. (1967). The White Shoe - No Red Herring. British Journal for the Philosophy of Science , Vol. 18, No. 3: 239. - [HLNU13] Hutter, M., Lloyd. J.W., Ng K.S. and Uther W.T.B. (2013). Probabilities on Sentences in an Expressive Logic. Journal of Applied Logic . - [Hum88] Hume, D. (1888). Hume's Treatise of Human Nature, edited by L. A. Selby Bigge, Oxford, Clarendon Press. Originally published 1739-40. - [Hut07] Hutter M. (2007). On universal prediction and Bayesian confirmation. Theoretical Computer Science , 384(1):33-48. - [Jay03] Jaynes, E. T. (2003). Probability theory: The logic of science . Cambridge: Cambridge University Press. - [Mah99] Maher, P. (1999). Inductive Logic and the Ravens Paradox. Philosophy of Science 66: 50-70. - [Mah04] Maher, P. (2004). Probability Captures the Logic of Scientific Confirmation. (In C. Hitchcock (Ed.) Contemporary Debates in the Philosophy of Science , Oxford: Blackwell, 69-93). - [Pop59] Popper, K. (1959). The Logic of Scientific Discovery . London: Hutchinson. (1st German Ed., Logik der Forschung , 1935.) - [Rei80] Reiter, R. (1980) Equality and domain closure in first-order databases. JACM, 27:235-249. - [RH11] Rathmanner, S. and Hutter M. (2011). A Philosophical Treatise of Universal Induction, Enthropy , Vol. 13, No. 6, 1076-1136. - [RN03] Russell S.J. and Norvig P. (2003). Artificial Intelligence: A Modern Approach , (2nd ed.), New Jersey: Prentice Hall. - [Sav54] Savage, L. J. (1954). The Foundations of Statistics , New York, Wiley. - [SG72] Scheffler, I. and Goodman, N.J. (1972). Selective Confirmation and the Ravens. Journal of Philosophy 69: 78-83. - [SH11] Sunehag P. and Hutter M. (2011). Axioms for rational reinforcement learning Proceedings of 22:nd international conference on algorithmic learning theory, Springer Lecture Notes in Computer Science 6925:338-352. - [Sol64] Solomonoff, R. J. (1964). A formal theory of inductive inference: Parts 1 and 2, Information and Control , 7:1-22 and 224-254. - [Vra04] Vranas, P. (2004). Hempel's Raven Paradox: A Lacuna in the Standard Bayesian Solution. British Journal for the Philosophy of Science 55: 545-560. ## A List of Notation ## Symbol ## Explanation $$U = \{ 1 , 2 , \dots , v \}$$ universe of arbitrary size N $$1 , 2 , \dots , N$$ objects of universe U (short form) υ, υ ′ , υ ′′ ∈ N symbols used to denote the size of universe $$U _ { \upsilon } = \{ 1 , 2 , \dots , \upsilon \}$$ universe of size υ α ≤ β lower and higher bounds for the size of the universe a, b, c and b 1 , b 2 , . . . typical objects (or individuals) (not necessarily consecutive) ψ typical 1-place predicate ψ b a proposition assigning predicate ψ to object b ψ b i : b j $$\psi _ { b _ { i } } . \psi _ { b _ { i + 1 } } \dots \psi _ { b _ { j } }$$ F, G atomic 1-place predicates F b , G b propositions assigning F and G to object b , respectively ¯ F ¯ G b , ¯ FG b , F ¯ G b , FG b complete descriptions (of object b ) F → G b F b → G b ≡ ¬ F b ∨ G b ≡ ¬ F ¯ G b H General hypothesis: ∀ b ∈ U F → G b E evidence: F a .G a B,D typical (objective) background knowledge ρ a typical proposition I ρ set of all individuals described by ρ A ρ set of all (simple) predicates involved in ρ /latticetop tautologous proposition ∆ set of all propositions in form of relation (1.3) (on universe U ) ∆ υ set of all propositions in form of relation (1.3) (on universe U υ ) δ set of all complete descriptions that do not falsify H CDV complete description vector Ω set of all CDVs (w.r.t universe U ) Ω υ set of all CDVs (w.r.t. universe U υ ) Ω α : β union of Ω α to Ω β ω Ω υ ρ ⊆ Ω υ an event that corresponds proposition ρ (w.r.t. sample space Ω υ ) ω ρ ⊆ Ω α : β an event that corresponds proposition ρ (w.r.t. sample space Ω α : β ) pr probability (over sample space Ω) pr υ probability (over sample space Ω υ ) Pr probability (over sample space Ω α : β ) π , π ′ , π ′′ typical permutations (i.e. bijections) in U π ( b ) an object that b ∈ U is mapped to by bijection π ρ π a proposition obtained from ρ by replacing any b ∈ I ρ with π ( b ) C,C ′ , C ′′ ⊆ U typical subsets of U C π { π ( b ) : b ∈ C } C U,k set of all subsets of U with cardinality k C π U,k { C π : C ∈ C U,k } Z ( C,F ) ∧ a ∈ C F a . ∧ b /negationslash∈ C ¬ F b Exact ( k, U, F ) a proposition representing: 'exactly k members of U are F '