Proving Set Theory Equation: Subsets of Size m = Subsets of Size n-m

In summary, the conversation discusses how to prove that the number of subsets of a set with n elements, of size m, is equal to the number of subsets of the same set with size n-m. The conversation mentions using combinations and finding a one-to-one correspondence between the subsets to prove this statement. The person is unsure of where to begin and is not familiar with combinations. They also mention using a google search for more information.
  • #1
TalonStriker
15
0

Homework Statement



Prove that, for all n, for all m with 0 <= m <= n, the number of subsets of {1, . . . , n} of size m is the same as the number of subsets of {1, . . . , n} of size n − m.


Homework Equations


n/a


The Attempt at a Solution


My problem is that I don't know where to begin. I have a vague notion that I should somehow find the powerset of all the sets of size m and n - m and compare their sizes. But I don't really know where to start.
 
Physics news on Phys.org
  • #2
Combinations?
 
  • #3
C(n,m)=C(n,n-m) since order of elements in a set is not important.
 
  • #4
EnumaElish said:
Combinations?

I am not familiar with combinations... what are they?

A google search doesn't net me any useful results.
 
Last edited:
  • #5
I want to choose m things. Therefore, I don't choose how many things?
 
  • #6
If A is a subset of S= {1, 2,... n} with m members, how many members does S\A have? Do you see an obvious one-to-one correspondence?
 

FAQ: Proving Set Theory Equation: Subsets of Size m = Subsets of Size n-m

What is the purpose of proving the set theory equation "Subsets of Size m = Subsets of Size n-m"?

The purpose of proving this set theory equation is to provide a mathematical proof for the relationship between subsets of different sizes within a larger set. By proving this equation, we can better understand the structure and properties of sets and their subsets.

Can you explain the meaning of "Subsets of Size m = Subsets of Size n-m" in simpler terms?

This equation means that the number of subsets of size m within a set is equal to the number of subsets of size n-m within the same set. In other words, if we have a set with n elements, the number of subsets with m elements will be the same as the number of subsets with n-m elements.

How does this equation relate to the concept of power sets?

Power sets are sets that contain all possible subsets of a given set. This equation is related to power sets because it shows that the number of subsets of a certain size within a set is equal to the number of subsets of a different size within the same set. This is important in understanding the structure and size of power sets.

Are there any real-life applications of this set theory equation?

Yes, this equation has many real-life applications in fields such as computer science, statistics, and economics. For example, in computer science, this equation can be used to analyze the complexity of algorithms and data structures. In statistics, it can be used to calculate probabilities and in economics, it can be used to analyze consumer preferences and market trends.

Is there any intuitive way to understand the proof of this set theory equation?

One intuitive way to understand the proof of this equation is by visualizing sets and their subsets. For example, if we have a set of 6 elements, there will be the same number of subsets with 3 elements as there are with 6-3 = 3 elements. This can be visualized by drawing out all the possible subsets and counting them. Another way to understand the proof is by using mathematical induction, which involves proving the equation for a base case and then showing that it holds true for all other cases.

Similar threads

Prove every subset of countable set is either finite or else countable
Replies
1
Views
1K
How many subsets of size three or less are in a n-object set
Replies
4
Views
1K
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
Replies
4
Views
901
Proving Completeness property of ##\mathbb{R}## using Dedekind cuts
Replies
20
Views
3K
Problem on a set which is a subset of a finite set
Replies
3
Views
1K
Every subset of a finite set is finite
Replies
1
Views
1K
Proving intersection of finitely many open sets is open
Replies
1
Views
1K
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
Replies
1
Views
1K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
Replies
1
Views
955
Possible Subsets of Even Numbers in a Set of Size n?
Replies
8
Views
1K

Hot Threads

Recent Insights

Back
Top