Set size of a cartesian product

In summary, the conversation discusses the concept of sets, specifically a set S with n elements. The size of the set is determined by the number of elements in its subsets, as shown in the equation X union Y = S. The individual in the conversation is seeking hints for solving a related problem, and it is determined that Y has n-k to n-k elements at most, with a minimum value of 1 and a maximum of n-1. The conversation also mentions considering the combinations for n = 2 and n = 3, and the number of possibilities for X and Y based on the number of elements in the set and its subsets. The conversation concludes with the individual expressing their gratitude for the hints received.
  • #1
guropalica
8
0
Set S with n elements!
Set size of
{<x,y> | (X,Y are proper subsets of S), (X union Y = S)!
I tried doing something, but I'm stuck staring at a closed door, so I need a fresh start!
Any hints would be appreciated!
 
Physics news on Phys.org
  • #2
If X has k elements, then how many elements does Y have?
What is the minimum and maximum value for k?

Maybe you can try writing out all the combinations for n = 2 and n = 3 to get some feeling for the problem.
 
  • #3
If x has k elements, than Y has n-k to n-k elements at most!
Minimum value for k is 1, and max is n-1
It's pretty much pointless to write about 2 elements since that way I'd have only 2 cartesian products only since by the condition sets are not subsets so they can't be equal to the parent ie we get two sets of 1 element!
The same with 3 :/
 
  • #4
guropalica said:
If x has k elements, than Y has n-k to n-k elements at most!
/

X union Y = S is a big clue.
 
  • #5
Is there a typo, or did you just mean "n - k elements exactly"? :-)

OK, here's another hint: how many different subsets of k elements can you choose from a set of n? In other words, how many possibilities are there for X?
 
  • #6
n-1 a typo...There are k^2 possibilities for X, and C of k from n for Y I think!
PS.Can we go more direct with hints I'm deadline's due 02:15 GMT :)
 
  • #7
You're almost there, just take a moment to think it through.

C(n, k) is the number of k-element subsets you can make for X.

Then Y has to contain all the other elements (and, if X and Y don't need to be disjoint, any subset of X. How many of those are there?)
 
  • #8
C(n,k), n-k the number of elements of Y, 2^(n-k) the number of subsets...by binomial I got 3^n!
Thanks a lot guys
 
  • #9
C(n,k), n-k the number of elements of Y, 2^(n-k) the number of subsets...by binomial I got 3^n!
Thanks a lot guys
 

FAQ: Set size of a cartesian product

1. What is the definition of "cartesian product"?

The cartesian product is a mathematical operation that takes two sets and produces a new set containing all possible ordered pairs of elements from the original sets. It is denoted by the symbol x.

2. How do you calculate the set size of a cartesian product?

The set size of a cartesian product is equal to the product of the sizes of the two original sets. For example, if set A has 3 elements and set B has 4 elements, then the set size of A x B is 3 x 4 = 12.

3. Can the set size of a cartesian product be infinite?

Yes, the set size of a cartesian product can be infinite if one or both of the original sets are infinite. For example, the set of all real numbers x the set of all real numbers would have an infinite set size.

4. What is the relationship between the set size of a cartesian product and the power set?

The set size of a cartesian product is equal to the cardinality (number of elements) of the power set of the two original sets. This is because the power set contains all possible subsets of a set, and for each element in the cartesian product, there is a corresponding subset in the power set.

5. How is the set size of a cartesian product affected by the number of elements in the original sets?

The set size of a cartesian product increases exponentially as the number of elements in the original sets increases. This means that as the size of the original sets grows, the set size of the cartesian product grows at a much faster rate.

Similar threads

MHB Sets so that the cartesian product is commutative
Replies
2
Views
1K
I Construction of sigma-algebras: a counterexample
Replies
5
Views
222
I How Are Infinite Cartesian Products Interpreted in Set Theory?
Replies
4
Views
2K
MHB ZFC and the Axiom of Power Sets ....
Replies
2
Views
1K
A Probability distributions in an ordered set of extracted elements
Replies
2
Views
1K
I When does ## { n \choose k } ## represent set of lists?
Replies
20
Views
2K
MHB Describing Sets: A Comprehensive Guide
Replies
5
Views
2K
MHB How Many Elements Are Found in Each Mathematical Set?
Replies
5
Views
1K
Cartesian product of (possible infinite) family of sets
Replies
5
Views
4K
I Bloch Analysis proof of Theorem 2.5.5 (Definition by recursion)
Replies
2
Views
976

Hot Threads

Recent Insights

Back
Top