Register to reply

Smallest set proofs

by gnome
Tags: proofs, smallest set
Share this thread:
gnome
#1
May1-06, 04:45 PM
P: 1,047
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.
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
NateTG
#2
May1-06, 04:52 PM
Sci Advisor
HW Helper
P: 2,538
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
#3
May1-06, 05:09 PM
Sci Advisor
HW Helper
P: 9,398
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
#4
May1-06, 05:19 PM
P: 1,047
Smallest set proofs

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
#5
May1-06, 05:34 PM
Sci Advisor
HW Helper
P: 9,398
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
#6
May1-06, 05:48 PM
P: 1,047
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.

[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 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
#7
May1-06, 06:09 PM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by gnome
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 thier 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.

[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 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
#8
May1-06, 06:32 PM
P: 1,047
Quote Quote by 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.

Quote Quote by matt grime
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
#9
May1-06, 07:01 PM
Sci Advisor
HW Helper
P: 9,398
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
#10
May1-06, 11:11 PM
P: 1,047
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