Proving Cardinality of P(S) > S

  • Thread starter Mr Davis 97
  • Start date
  • Tags
    Cardinality
In summary, the conversation is about proving that the cardinality of the powerset of any set S is greater than the cardinality of S itself. The attempt at a solution involves defining a function that is an injection, leading to the suspicion that something may be missing in the proof. It is suggested that the task is to prove that there is no bijection between S and its powerset.
  • #1
Mr Davis 97
1,462
44

Homework Statement


Prove that the cardinality of ##P(S)## is greater than the cardinality of S, where S is any set.

Homework Equations

The Attempt at a Solution


It would seem that we could simply define ##T: S \rightarrow P(S)## such that ##T(s) = \{s \}##. This is clearly an injection, so ##|S| \le |P(S)|##. That seemed too easy though, so I feel like I am doing something wrong.
 
Physics news on Phys.org
  • #2
Mr Davis 97 said:
That seemed too easy though, so I feel like I am doing something wrong.
I think you are asked to prove strict inequality of cardinalities.
 
  • #3
Krylov said:
I think you are asked to prove strict inequality of cardinalities.
So I have to show that there exists no bijection between ##S## and its powerset?
 

1. How do you define cardinality?

Cardinality is a mathematical concept that refers to the number of elements in a set. It is a measure of the size or "count" of a set.

2. What is the power set of a set?

The power set of a set, denoted by P(S), is the set of all possible subsets of that set. This includes the empty set and the set itself. For example, if S = {1,2}, then P(S) = {∅, {1}, {2}, {1,2}}.

3. How can you prove that the cardinality of P(S) is greater than the cardinality of S?

One way to prove this is by using the Cantor's diagonal argument. This argument states that for any set, the cardinality of its power set is always greater than the cardinality of the original set. This can be shown by constructing a one-to-one correspondence between the elements of the original set and the power set.

4. Can you provide an example to illustrate the proof of P(S) > S?

Sure, let's consider the set S = {a, b}. The power set of S, P(S), would be {∅, {a}, {b}, {a,b}}. To prove that P(S) > S, we can construct a one-to-one correspondence between the elements of S and the elements of P(S) as follows: a ↔ {a}, b ↔ {b}, ∅ ↔ ∅, and {a,b} ↔ {a,b}. This shows that every element in S has a corresponding element in P(S), and there are no elements in P(S) that do not have a corresponding element in S, thus proving that P(S) > S.

5. What are the implications of proving that P(S) > S?

Proving that P(S) > S has several implications in mathematics. It shows that the power set of any set is always larger than the original set, regardless of its size. This also means that there are infinitely many subsets of a set, even if the set itself is finite. This concept is important in various fields of mathematics, such as set theory, combinatorics, and topology.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
5
Views
849
  • Calculus and Beyond Homework Help
Replies
3
Views
761
  • Calculus and Beyond Homework Help
Replies
1
Views
449
  • Calculus and Beyond Homework Help
Replies
2
Views
150
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
3
Views
465
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
981
  • Calculus and Beyond Homework Help
Replies
25
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
Back
Top