Using Membership, Subset, and Cardinality Notation

Membership and Cardinality: Is it in there, and how many?

The two most basic questions we can ask about a set are: "Is this specific item in the set?" and "How many items are in the set?". Let's formalize the notation for these questions.

• Membership: To state that an element x is in a set A, we write $x\in A$. To state that it is not, we write $x\notin A$.
• Cardinality: The number of distinct elements in a finite set A is called its cardinality, written as $|A|$.

The following video from TrevTutor provides an excellent introduction to these concepts. It clearly explains the notation and walks through some important examples that can be tricky for newcomers, such as the distinction between the empty set $\varnothing$ and a set that contains the empty set, $\{\varnothing \}$.

As a quick check, consider the set $S=\{1,2,\{3,4\}\}$.

• Is it true that $1\in S$? Yes.
• Is it true that $3\in S$? No. The element is the set $\{3,4\}$, not the number 3 itself. So, $\{3,4\}\in S$ is true.
• What is the cardinality, $|S|$? The set has three distinct elements: the number 1, the number 2, and the set $\{3,4\}$. Therefore, $|S|=3$.

This distinction between an element and a set containing that element is a crucial point that trips up many beginners. Your experience with nested data structures in programming, like a Python list containing other lists, should give you a good mental model for this. [1, 2, [3, 4]] is a list of length 3, and 3 is not a direct element of it.

Subsets: Containing and Being Contained

Now let's move from the relationship between an element and a set to the relationship between two sets.

A set $A$ is a subset of a set $B$ if every element of $A$ is also an element of $B$. We denote this by $A\subseteq B$.

A set $A$ is a proper subset of a set $B$ if $A$ is a subset of $B$ and $A$ is not equal to $B$ (i.e., $B$ contains at least one element not in $A$). We denote this by $A\subset B$.

Let's clarify two important rules that follow from these definitions:

1. Every set is a subset of itself. For any set $A$, $A\subseteq A$.
2. The empty set is a subset of every set. For any set $A$, $\varnothing \subseteq A$.

The following video, also from TrevTutor, explains these concepts visually and works through several true/false examples that will help solidify your understanding.

The Power Set: Putting It All Together

The concept of a power set is a perfect way to practice using all the notation we've just learned. The power set of a set $A$, written $\mathcal{P}(A)$, is the set of all possible subsets of $A$.

Let's take $A=\{1,2\}$. What are its subsets?

• The empty set: $\varnothing$
• Subsets with one element: $\{1\}$, $\{2\}$
• Subsets with two elements: $\{1,2\}$

So, the power set is $\mathcal{P}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$.

Notice the interplay of our new symbols here:

• Subsets: $\{1\}\subseteq A$, but $\{1\}\in \mathcal{P}(A)$. This is the critical distinction: a subset of $A$ is an element of the power set of $A$.
• Cardinality: The set $A$ has cardinality $|A|=2$. The power set $\mathcal{P}(A)$ has cardinality $|\mathcal{P}(A)|=4$. There's a wonderful relationship here: if $|A|=n$, then $|\mathcal{P}(A)|=2^n$. This formula is incredibly useful in combinatorics and computer science, for example when considering all possible configurations of a set of n binary flags.

The TrevTutor video you started continues by explaining power sets and this cardinality formula.

Practice and Application

Let's put this notation to work. Use the definitions we've covered to determine if the following statements are true or false.

Let $S=\{a,b,\{c,d\}\}$ and $T=\{a,b\}$.

1. $T\subset S$
2. $T\in S$
3. $|\mathcal{P}(T)|=4$
4. $\{a,b\}\subseteq T$
5. $\{\{c,d\}\}\subseteq S$

For more practice on systematically finding and counting subsets, the OpenStax textbook provides a clear, step-by-step example.

A Python Perspective

Your practical programming background gives you a great advantage here, as these mathematical concepts have direct analogues in Python.

Let's define two sets:

A = {1, 2}
B = {1, 2, 3}

• Membership: The in keyword checks for membership.

  >>> 2 in A
  True
  >>> 3 in A
  False
  

• Cardinality: The built-in len() function gives the cardinality.

  >>> len(A)
  2
  

• Subsets: The <= operator checks for a subset relationship, and < checks for a proper subset.

  >>> A <= B  # Is A a subset of B?
  True
  >>> A < B   # Is A a proper subset of B?
  True
  >>> B <= A  # Is B a subset of A?
  False
  >>> A <= A  # Is A a subset of itself?
  True
  >>> A < A   # Is A a proper subset of itself?
  False
  

Thinking about these mathematical ideas in terms of the code you already know can be a powerful way to solidify your understanding.

Conclusion

In this lesson, you've acquired the essential notation for describing sets and their contents. Mastering this vocabulary is non-negotiable for further study in discrete mathematics and theoretical computer science.

Key Takeaways:

• Membership: $x\in A$ means x is an element of set A.
• Cardinality: $|A|$ is the number of distinct elements in set A.
• Subset: $A\subseteq B$ means every element of A is also in B.
• Proper Subset: $A\subset B$ means $A\subseteq B$ and $A\ne B$.
• The Power Set $\mathcal{P}(A)$ is the set of all subsets of $A$, and its cardinality is $|\mathcal{P}(A)|=2^{|A|}$.
• There is a critical difference between membership ($\in$) and being a subset ($\subseteq$).

So far, we have built up a language for logic (propositions and quantifiers) and a language for collections (sets and their properties). In the next lesson, we will combine these tools to study relations, which are formal ways to describe how elements within a set relate to each other. Concepts like the Cartesian product, which defines the universe of all possible pairings, and subsets, which select specific pairings with interesting properties, will be central to our discussion.