Set Theory and Logical Derivation Rules

Vocabulary flashcards covering quantification derivation rules, formal set definitions, and set validation properties.

$$\forall\text{-introduction}$$

A proof rule where assuming $(k)\ \text{var } x; P(x)$ and deriving $(m-1)\ Q(x)$ allows concluding $(m)\ \forall_x [P(x) : Q(x)]$.

$$\forall\text{-elimination}$$

$$\exists^*\text{-introduction}$$

A derivation rule where given $(k)\ P(a)$ and $(l)\ Q(a)$ for an available object $a$, one concludes $(m)\ \exists_x [P(x) : Q(x)]$.

$$\exists^*\text{-elimination}$$

A derivation rule where given $(k)\ \exists_x [P(x) : Q(x)]$, one can pick an $x$ satisfying $P(x)$ and $Q(x)$, provided that $x$ is a new variable.

Subset ($\subseteq$)

Defined as $A \subseteq B \overset{\text{def}}{=} \forall_x [x \in A : x \in B]$.

Set Equality ($=$)

Defined as $A = B \overset{\text{def}}{=} A \subseteq B \land B \subseteq A$.

Set Intersection ($\cap$)

Defined as $A \cap B \overset{\text{def}}{=} \{x \in \mathbf{U} \mid x \in A \land x \in B\}$.

Set Union ($\cup$)

Defined as $A \cup B \overset{\text{def}}{=} \{x \in \mathbf{U} \mid x \in A \lor x \in B\}$.

Set Complement ($^c$)

Defined as $A^c \overset{\text{def}}{=} \{x \in \mathbf{U} \mid \neg(x \in A)\}$.

Set Difference ($\setminus$)

Defined as $A \setminus B \overset{\text{def}}{=} \{x \in \mathbf{U} \mid x \in A \land \neg(x \in B)\}$.

Universal Set ($\mathbf{U}$)

Defined as $\mathbf{U} = \{x \in \mathbf{U} \mid \text{True}\}$.

Empty Set ($\emptyset$)

Defined as $\emptyset = \{x \in \mathbf{U} \mid \text{False}\}$.

Property of $\in$

Validation rule $t \in \{x \in \mathbf{D} \mid P(x)\} \overset{\text{val}}{=} t \in \mathbf{D} \land P(t)$.

Property of $\subseteq$

Validation rule $A \subseteq B \land t \in A \overset{\text{val}}{=} t \in B$.

Properties of $=$

Validation rules $A = B \overset{\text{val}}{=} \forall_x [x \in A \Leftrightarrow x \in B]$, $A = B \land t \in A \overset{\text{val}}{=} t \in B$, and $A = B \land t \in B \overset{\text{val}}{=} t \in A$.

Property of $\cap$

Validation rule $t \in A \cap B \overset{\text{val}}{=} t \in A \land t \in B$.

Property of $\cup$

Validation rule $t \in A \cup B \overset{\text{val}}{=} t \in A \lor t \in B$.

Property of $^c$

Validation rule $t \in A^c \overset{\text{val}}{=} \neg(t \in A)$.

Property of $\setminus$

Validation rule $t \in A \setminus B \overset{\text{val}}{=} t \in A \land \neg(t \in B)$.

Properties of $\mathbf{U}$

Validation rules $t \in \mathbf{U} \overset{\text{val}}{=} \text{True}$ and $A = \mathbf{U} \overset{\text{val}}{=} \forall_x [x \in A : \text{True}]$.

Properties of $\emptyset$

Validation rules $t \in \emptyset \overset{\text{val}}{=} \text{False}$ and $A = \emptyset \overset{\text{val}}{=} \forall_x [x \in A : \text{False}]$.

Property of $\mathcal{P}$

Validation rule $C \in \mathcal{P}(A) \overset{\text{val}}{=} C \subseteq A$.

Properties of $\times$

Validation rules $(a, b) \in A \times B \overset{\text{val}}{=} a \in A \land b \in B$ and $(a, b) = (a', b') \overset{\text{val}}{=} a = a' \land b = b'$.