A question for order in sets

  • Thread starter Shing
  • Start date
  • #1
144
1

Main Question or Discussion Point

I am reading a book named sets & groups,
I would like to ask:
What exactly is a finite set of order n? [itex]A_1\times A_2\times A_3...A_n[/itex] ?
is pair [itex](x_1,x_2,x_3...x_m)[/itex] counted as a single element? or a set? or an order?
also how should I prove that the number of subsets, including empty set, of a finite set of order n is [itex]2^n[/itex]?


Thanks!
 

Answers and Replies

  • #2
CompuChip
Science Advisor
Homework Helper
4,302
47
The order of a set is just the number of elements in a set. So a finite set of order n is a set with n elements.

You can also look at Cartesian products of set, and then the elements of that set will be pairs / triples / (n-)tuples of elements from those sets. You can prove that the order of the product [itex]A = A_1 \times A_2 \times \cdots \times A_n[/itex] is [itex]|A| = |A_1| \times |A_2| \times \cdots \times |A_n|[/itex] where |X| denotes the order of set X.

For your last question: note that if you have finitely many elements you can list them all. One way to proceed is to write down a one or zero for each of them, indicating whether they are in a given subset or not. You can put all of these in an n-tuple. Then show that each such n-tuple corresponds to one particular subset and that each subset can be written as one particular n-tuple; finally count then number of n-tuples you can make.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,792
920
I am reading a book named sets & groups,
I would like to ask:
What exactly is a finite set of order n?
A set containing exactly n members.

[itex]A_1\times A_2\times A_3...A_n[/itex] ?
Since you haven't said what A1 etc. are, I can't say!

is pair [itex](x_1,x_2,x_3...x_m)[/itex] counted as a single element? or a set? or an order?
Well, that's not a "pair" of course, but the "ordered m-tuplet" is a member of
[itex]A_1\times A_2\times A_3...A_n[/itex].

also how should I prove that the number of subsets, including empty set, of a finite set of order n is [itex]2^n[/itex]?Thanks!

By induction on n. If A is of order 1, it contains the single element {a} and so has 21= 2 subsets, {} and {a}.

Now, suppose A has k+1 members. Choose one of them, call it z, and note that any subset of A either contains z or doesn't. If it doesn't contain z, it is a subset of A-{z} which has k members. If it does contain z, it can be written as [itex]C\union {z}[/itex]
and C is a subset of A-{z}.
 

Related Threads for: A question for order in sets

  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
5K
Replies
0
Views
803
Replies
1
Views
2K
Replies
2
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
4
Views
3K
Top