Changing the Statement Combinatorial proofs & Contraposition

CGandC
Messages
326
Reaction score
34
I have a question regarding to combinatorial proofs and predicate logic. It seems to me that in some combinatorial proofs there is a use of contraposition ( although not explicitly stated in the books where I've read so far ), for example If we to prove that ## C(n,k) = C(n,n-k) ## combinatorically, the explanation is:

" (1) we have ## C(n,k) ## ways to create k subsets
(2) we have ## C(n,n-k) ## ways to not create k subsets
And since both ways of counting are equivalent, we finished. "


However, why these two statements ( statements (1) and (2) ) are equivalent? is it because "## C(n,n-k) ## ways to not create k subsets" is the contrapositive of " ## C(n,k) ## ways to create k subsets " ?
But how do you even find the contrapositive of a sentence like " ## C(n,k) ## ways to create k subsets "? ( it doesn't seem like an implication to me )
 
Physics news on Phys.org
The easiest way is probably to show that the formulas are identical.

The way the argument above uses is: Whenever I choose ##k## elements out of ##n##, then I have simultaneously chosen ##n-k## elements, which do not belong to the set. Hence if I pick ##k## or ##n-k## elements does not matter.

I simply label the resulting bowls of ##C(k,n)## as chosen and not chosen. Of course, I can exchange the labels that I have put on my selections afterwards anyway without even repeating the process. So both results depend on a sign I used to mark them, not the process of selection. But that was deliberate.
 
##C(n,k)## is the number of ways to choose ##k## elements out of ##n##. That is the same as to choose ##n-k##, because whether you choose ##k## and leave ##n-k## behind or you choose ##n-k## and leave ##k## behind is the same.
 
In terms of predicate and quantificational logic, is" ## C(n,k) ## ways to create k subsets" can be considered as a predicate? does it have a True/False value? I'm having hard time to interpret the logic behind this phrase and what to classify it as ( maybe there's advanced logic behind that's discussed in a course about Logic ).
 
I tried to write it with logical symbols, but it is quite a bit troublesome for such an obvious result. One has to define subsets with ##k## elements and make a statement about the size of the set of such sets, and sets of sets is always a bit clumsy.

Why don't you think of partitioning a set of ##n## elements into two sets, one with ##k## the other one with ##n-k## elements. This demonstrates the symmetry in the argument.
 
Ok I understand, thanks. I tried looking at combinatorial proofs as statements with quantifiers and such like when I was learning predicate and quantificational logic. But I think I'll have to exercise such proofs to get an idea of what's going on.
 

Similar threads

Replies
10
Views
3K
Replies
5
Views
2K
3
Replies
100
Views
11K
Replies
51
Views
10K
Back
Top