Register to reply 
Smallest set proofs 
Share this thread: 
#1
May106, 04:45 PM

P: 1,046

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 n1 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. 


#2
May106, 04:52 PM

Sci Advisor
HW Helper
P: 2,537

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



#3
May106, 05:09 PM

Sci Advisor
HW Helper
P: 9,396

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. 


#4
May106, 05:19 PM

P: 1,046

Smallest set proofs
I'm comfortable with induction when it starts by proving P(k) is true for some nonnegative 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 ANTIreflexive, antisymmetric and transitive? Any ideas as to where I can find some thorough analysis of this sort of proof? 


#5
May106, 05:34 PM

Sci Advisor
HW Helper
P: 9,396

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(k1) is true as k1 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. 


#6
May106, 05:48 PM

P: 1,046

Hmm... wellordering 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. [tex](\forall{x}) (\exists{y})(R\, x,y)[/tex] [tex]\sim(\exists{x})R\, x,x[/tex] [tex](\forall{x})(\forall{y})(\forall{z})[(R\,x,y \wedge R\,y,z) \supset R\, x,z][/tex] 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 n1, 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? 


#7
May106, 06:09 PM

Sci Advisor
HW Helper
P: 9,396




#8
May106, 06:32 PM

P: 1,046

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. 


#9
May106, 07:01 PM

Sci Advisor
HW Helper
P: 9,396

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.



#10
May106, 11:11 PM

P: 1,046

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.



Register to reply 
Related Discussions  
Difference between Identical , Equal , Equivalent  Calculus & Beyond Homework  9  
Anyone familiar with centrifugal potential and brachistochrone in polar coords?  Advanced Physics Homework  7  
Do Androids Dream of Electric Sheep vs Blade Runner  General Discussion  0 