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.
 
I believe there is a significant gap in the availability of resources that emphasize the underlying logic of abstract mathematical concepts. While tools such as Desmos and GeoGebra are valuable for graphical visualization, they often fall short in fostering a deeper, intuitive understanding. Visualisation, in this sense, should go beyond plotting functions and instead aim to reveal the reasoning and common-sense foundations of the concept. For example, on YouTube one can find an excellent...

Similar threads

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