◀ ▲ ▶Branches / Combinatorics / Proof

Proof

(related to Proposition: Indicator Function and Set Operations)

• By hypothesis, $S$ is a set with some subsets $A,B\subseteq S$ and the corresponding indicator functions $\chi_A$ and $\chi_B.$

Set Union

• By definition, the carrier of $\max(\chi_A,\chi_B)$ is the set $\{x\mid x\in S,\max(\chi_A,\chi_B)=1\}.$
• This set equals obviously the set $\{x\mid x\in S,\chi_A(x)=1\vee \chi_B(x)=1\}.$
• But it carrier is the set union $A\cup B.$
• Therefore, $\chi_{A\cup B}=\max(\chi_A,\chi_B).$

Set Intersection

• By definition, the carrier of $\min(\chi_A,\chi_B)$ is the set $\{x\mid x\in S,\min(\chi_A,\chi_B)=1\}.$
• This set equals obviously the set $\{x\mid x\in S,\chi_A(x)=1\wedge \chi_B(x)=1\}.$
• But it carrier is the set intersection $A\cap B.$
• Therefore, $\chi_{A\cap B}=\min(\chi_A,\chi_B).$

Other

• The reader is invited to verify the other identities for set complement and set difference as an exercise.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github: