User:Ascii/Prose Test/Set Theory

From ProofWiki
Jump to navigation Jump to search

Sets and Elements

Every set is a subset of itself: $\forall S: S \subseteq S$

The singleton of an element of a set is a subset of that set: $x \in S \iff \{x\} \subseteq S$

The subset relation $\subseteq$ is transitive: $\paren {R \subseteq S} \land \paren {S \subseteq T} \implies R \subseteq T$

There are equivalent definitions of set equality: $S = T \iff \paren {\forall x: x \in S \iff x \in T}$ and $S = T \iff S \subseteq T \land T \subseteq S$

A set is equal to itself: $S = S$

Sets are unequal if neither is a subset of the other: $S \ne T \iff \left({S \nsubseteq T}\right) \lor \left({T \nsubseteq S}\right)$

The empty set $\O$ is unique

and a subset of all sets: $\forall S: \O \subseteq S$
and an element of every power set: $\forall S: \O \in \mathcal P (S)$

A set is an element of its power set: $S \in \powerset S$

The power set of the empty is the singleton of the empty set: $P \left({\varnothing}\right) = \left\{{\varnothing}\right\}$


Union

Union is idempotent: $S \cup S = S$

commutative: $S \cup T = T \cup S$
and associative: $(S \cup T) \cup R = S \cup (T \cup R)$

The union of a set with the empty set is itself: $S \cup \O = S$

A set is a subset of a union of itself with another: $S \subseteq S \cup T$

Union preserves subsets: $A \subseteq B, \ S \subseteq T \implies A \cup S \subseteq B \cup T$

A union of a pair of sets is the smallest set containing them: $\paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T} \iff \paren {S_1 \cup S_2} \subseteq T$

A set unioned with a superset is the superset: $S \subseteq T \iff S \cup T = T$

Union distributes over itself: $\forall A, B, C: \left({A \cup B}\right) \cup \left({A \cup C}\right) = A \cup B \cup C = \left({A \cup C}\right) \cup \left({B \cup C}\right)$

Every power set is closed under union: $\forall A, B \in \powerset S: A \cup B \in \powerset S$


Intersection

Set Intersection is Idempotent: $S \cap S = S$

commutative: $S \cap T = T \cap S$
and associative: $A \cap \paren {B \cap C} = \paren {A \cap B} \cap C$

A set intersected with another is a subset of itself: $S \cap T \subseteq S$

Intersection with the empty set is the empty set: $S \cap \O = \O$

Intersection of Subsets is Subset/Set of Sets

  1. Let $T$ be a set and $\mathbb S$ be a non-empty set of sets.
    Suppose that for each $S \in \mathbb S$: $S \subseteq T$
    Then $\bigcap \mathbb S \subseteq T$
  2. Intersection with Subset is Subset‎
    $S \subseteq T \iff S \cap T = S$

Intersection is self-distributive: $\forall A, B, C: \left({A \cap B}\right) \cap \left({A \cap C}\right) = A \cap B \cap C = \left({A \cap C}\right) \cap \left({B \cap C}\right)$

Every power set is closed under intersection: $\forall A, B \in \powerset S: A \cap B \in \powerset S$