Smallest Set Proofs: How to Construct?

[gnome]

"smallest set" proofs

From time to time I've seen proofs (to disprove some assertion) which are based on claiming that if the assertion P holds for some sets, there must be some set S which is the smallest set for which P holds, and then showing that if P holds for a set of size |n| it must hold for a set of size |n-1| thus contradicting the assumption that S is the smallest such set. (Or something along those lines.)

Unfortunately I can't seem to find one now, and even if I could, I'm not quite sure what is needed to make such a proof valid.

Would someone please point me to a valid example of this sort of proof, or better yet, an explanation as to how to construct one. In particular, what is needed to make a statement like "there must be a smallest set ... let S be that smallest set" a valid basis for proof by contradiction.

 

[NateTG]

That's a type of proof by induction, so you'll need to have some kind of useful well-ordering to make it work.

 

[matt grime]

For fullness: a set is well ordered if

1. it has an ordering (less than or equal to)
2 given any non empty set E, then there is a minimal element of E.

The natural numbers with their normal ordering are well ordered, the integers with their usual ordering are not.

It is an axiom of some set theories that all sets can be given an order that makes them well ordered. It is implied by the axiom of choice for instance.

 

[gnome]

I'm comfortable with induction when it starts by proving P(k) is true for some non-negative integer k, and then proving P(n) -> P(n+1) for all n>=k.

But this "smallest set" form just seems too "tricky". Is a partial ordering EXACTLY what is required to make it valid? i.e. is it only valid to prove (or disprove) relations that are reflexive, antisymmetric and transitive? For example, how about ANTI-reflexive, antisymmetric and transitive?

Any ideas as to where I can find some thorough analysis of this sort of proof?

 

[matt grime]

But they're exactly the same thing.Suppose P(0) is true, and let k be the smallest natural for which P(k) is false (k>0, then as P(0) is true), thus P(k-1) is true as k-1 is smaller than k, hence if the inductive hypothesis holds P(k) is true, which is a contradiction. This shows if you can do it by induction you can do it by picking a smallest counter example.Conversely, if you know you can't find a smallest counter example, suppose P(k) is true, but then P(k)=>P(k+1) is true, otherwise P(k+1) is false and there is some set of s for which P(s) is false (it contains k+1) and hence is non empty and has a minimal element, which is a contradiction), and P(0) must be true otherwise 0 is a minimal element for which it is false. Thus we have shown we can prove it by induction too.

And it is a well ordering, not a partial ordering that you use.

 

[gnome]

Hmm... well-ordering only applies to integers, is that correct?

Maybe this can't really be discussed in generalities. I want to prove that the conjunction (call it P) of these three sentences can't be satisfied in any finite domain.

$$(\forall{x}) (\exists{y})(R\, x,y)$$
$$\sim(\exists{x})R\, x,x$$
$$(\forall{x})(\forall{y})(\forall{z})[(R\,x,y \wedge R\,y,z) \supset R\, x,z]$$

I've already done so, using a directed graph argument. One of my classmates wants to argue along these lines: Assume (for contradiction) that P is satisfiable in some finite domains. Then there must be some smallest set S of n elements for which P is satisfied. Next, show that if P is satisfiable by a set of n elements, it must be satisfiable by a set of n-1, thus disproving the first assumption.

Ignore for the moment the question of whether that inductive step can actually be proven (I suspect that I can find a hole in that part of his argument as well). My question is, for these sentences is it even valid to assume some smallest set to begin with? And if so, why?

 

[matt grime]

Hmm... well-ordering only applies to integers, is that correct?

no, not at all. I did explain that every set can be equipped with an ordering that makes it well ordered if we assume the axiom of choice, and further the integers are not well ordered with their usual ordering: the set of integers less than 0 has no minimal element. The naturals are well ordered.

Maybe this can't really be discussed in generalities. I want to prove that the conjunction (call it P) of these three sentences can't be satisfied in any finite domain.

$$(\forall{x}) (\exists{y})(R\, x,y)$$
$$\sim(\exists{x})R\, x,x$$
$$(\forall{x})(\forall{y})(\forall{z})[(R\,x,y \wedge R\,y,z) \supset R\, x,z]$$

I've already done so, using a directed graph argument. One of my classmates wants to argue along these lines: Assume (for contradiction) that P is satisfiable in some finite domains. Then there must be some smallest set S of n elements for which P is satisfied. Next, show that if P is satisfiable by a set of n elements, it must be satisfiable by a set of n-1, thus disproving the first assumption.

Ignore for the moment the question of whether that inductive step can actually be proven (I suspect that I can find a hole in that part of his argument as well). My question is, for these sentences is it even valid to assume some smallest set to begin with? And if so, why?

Let S be the set of natural numbers for which the three statements are not satisfiable. It is a subset of the *natural numbers*. If it is non-empty it has a minimal element.

 

[gnome]

Hmm... well-ordering only applies to integers, is that correct?

Sorry, that was just sloppiness on my part. I had "natural numbers" in mind.

Let S be the set of natural numbers for which the three statements are not satisfiable. It is a subset of the *natural numbers*. If it is non-empty it has a minimal element.

I don't think that is the issue. This assertion has to be proven for ALL finite domains, so we're not dealing with a minimal element. We're dealing with a set of minimal cardinality.

I've become more or less convinced that his starting point is valid. It's his inductive step that needs more scrutiny. But I have to go to a class now so that'll have to wait. Thanks for your help.

 

[matt grime]

Let S be the set of cardinalities of finite sets for which they are satisfiable, then. It's still a subset of the natural numbers.

 

[gnome]

Yes, that's why I said I was "more or less convinced that his starting point was valid." In fact, now I'm more, rather than less, convinced that his entire proof is valid. I just needed to think out loud a bit. Thanks for listening to my babbling.