# What is a mathematical or logical name for the process of proving a statement by exhausting the problem domain?

I am trying to understand logic and I came across a set of actions that I describe below that I can't get my head around.

```Suppose you have a bag of multiple colored balls.

Situation 1.
Argument: There are no red balls in the bag.
Action: Pick up balls at random until you find a red one.

Situation 2.
Action: Pickup a random ball from the bag.
Argument: All the balls in the bag are of same color as the ball you picked up.
```

I have some questions.

1. What is the correct conclusion in each situation?
2. Are these situation logic related?
3. Can one be converted to another?
4. Which is correct and which is flawed?
5. What are the names for the logic contained in these situations?
• What logic? I can't get my head around it either. What are the premise? What is the conclusion? Commented Feb 14, 2012 at 14:59
• I don't really understand how this question is posed, least of all the "situations". Could you elaborate on these? (Normally, arguments consist of premises and conclusions) Commented Feb 14, 2012 at 16:01
• Is there any chance I might be able to persuade you to clarify the headline here a bit? (They should ideally encapsulate or at least reflect some of the specific content of the question) Commented Feb 14, 2012 at 16:25
• @seamus , stoucfury I am sorry. I know there has to be a conclusion but I don't know what followed them and didn't want to post nonsense. May be I'll add it as another question.
– Dirt
Commented Feb 14, 2012 at 20:16
• @Joseph whether this is flawed was the main question and others were for better understanding, so I posted it that way. I didn't know how to frame a question that reflected what it described.
– Dirt
Commented Feb 14, 2012 at 20:20

The first situation is an exhaustive disproof of existence, and is (if I understand what you have written) sound in its logic. The second is perhaps reasonable, and (again if I understand your writing) is called inductive reasoning, it is however not logical- not a valid deduction, as was explosively pointed out by Hume in An Enquiry Concerning Human Understanding. As such, in 'the finite case' they are profoundly different, one being logically valid, the other not.

When the bag of balls becomes infinitely large, however, the situations become nearly identical in practice, as in finite time one can never check every ball to see that it is not red, and so some inductive reasoning is necessary in both cases.

In the latter case, however, they are not entirely the same- for the first situation is still slightly better than the second. In the first situation, we make a hypothesis 'there are no red balls in the bag' that we subsequently test in a way that could falsify it: in the second, since we do not repeat the experiment after we make our hypothesis, our hypothesis is not fallible (this is important for reasons articulated by Karl Popper amongst others).

• In your final comment, you said "our hypothesis is not fallible." Did you mean to say that "our hypothesis is fallible?" I do not understand the former. Commented Feb 14, 2012 at 12:16
• I did indeed mean not fallible! The reasoning is somewhat subtle- or at least the stuff of a mid sized essay- but fallibility is a very useful property for a proposition about the world to have- in fact it is the criterion by which a good scientific hypothesis can be judged. Read the link 'for reasons articulated...' and that should explain it to some extent. Commented Feb 14, 2012 at 12:29
• I should probably add a caveat that the second situation is not in principle unfalsifiable, but by the design of our methodology is unfalsifiable in practice. Commented Feb 14, 2012 at 12:32
• Ah, I understand now, thank you. I hadn't thought of it that way. Commented Feb 14, 2012 at 13:45

What is a mathematical or logical name for the process of proving a statement by exhausting the domain?

The general term is unsurprisingly proof by exhaustion. From WP:

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds.1 This is a method of direct proof. A proof by exhaustion typically contains two stages:

• A proof that the set of cases is exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases.
• A proof of each of the cases.

As for your scenarios and additional questions, it's best to see the two scenarios as using the same form of inductive logic to draw relatively certain conclusions about the contents of the bag by empirical means. In one case, you are trying to show no balls are a certain color, and in the second, all balls are a certain color; neither can be done with deductive, mathematical rigor. However, by conducting millions or billions of trials, one can gain an epistemologically sound confidence in an admittedly fallibilistic conclusion. One often see such confidence in mathematical conjectures, such as in Goldbach conjectures that are shy of proof, but may yet be shown to be false which was the fate of Fermat's primality test.

Situation 1.
Argument: There are no red balls in the bag. Action: Pick up balls at random until you find a red one.

Situation 2. Action: Pickup a random ball from the bag. Argument: All the balls in the bag are of same color as the ball you picked up.

If one is trying to prove there are all or no red balls, proof by exhaustion will provide, as noted in the other answer, an inductive proof, but not a deductive one in the scenarios above. This is because in a sense, one cannot truly exhaust the problem space. However, after drawing a billion times from the bag, an inductively cogent (not a deductively sound) proof, can be said to exist. Of course, scientists accept inductive proofs, whereas mathematicians tend to reject them. There are exceptions, of course. Computer scientists are quite comfortable with probabilistic primality tests such as the Miller-Rabin test.