1.3 Subsets

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-09-29 Teacher: Prof. Musacchio

Sets

Intro

• elements from one set can be found in another set
  • E.g. A = { 0,2,4 } is also an element of B = { 0,1,2,3,4 }. When A and B are related this way we say that A is a subset of B
  • A $\subseteq$ B
• the opposite is also true
  • E.g. A $⊈$ B

Proper Subset

• if $A\subseteq B$ and A $\ne$ B, we say A is a proper subset of B

Formal Definition

• Suppose A and B are sets. If every element of A is also an element of B, then we say A is a subset of B, and we denote this as A $\subseteq$ B. We write A $\subseteq$ B if A is not a subset of B, that is, if it is not true that every element of A is also an element of B. Thus A $⊈$ B means that there is at least one element of A that is not an element of B

Fact

• The Empty Set is a subset of all sets, that is, $\varnothing$ ⊆ B for any set B

Fact

• If a finite set has n elements, then it has 2${}^n$ subsets.