Relation Practice

The inverse of a relation $R: A \rightarrow B, G \subseteq A \times B$ is defined by reversing all the arrows: $$ R^{-1}: B \rightarrow A, G^{-1} \subseteq B \times A $$

$$ (b, a) \in G^{-1} \iff \fillin\fillin\fillin\fillin $$

What does it mean if $R \equiv R^{-1}$?

Set Cardinality

Finite Cardinality. If $A$ is a finite set, the cardinality of $A$, written $|A|$, is the number of elements in $A$.

Does this definition require adding a new fundamental set operation?

#

Alternate definition: The cardinality of the set $$ N_k = { n | n \in \mathbb{N} \wedge n < k } $$ is $k$. If there is a bijection between two sets, they have the same cardinality.

#

If there is a surjective relation between $A$ and $B$ what do we know about their cardinalities?

##

If there is a surjective function between $A$ and $B$ what do we know about their cardinalities?

If there is a total surjective function between $A$ and $B$ what do we know about their cardinalities?

##

If there is a total surjective injective function between $A$ and $B$ what do we know about their cardinalities?

##

What is the cardinality of $A \cup B$?

#

Power Sets

The power set of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$: $$ B \in \textrm{pow}(A) \iff B \subseteq A. $$

Prove that the size of the power set of a set $S$ with $|S| = N$ is $2^N$ using the well-ordering principle. (See MCS 4.5.1 for an alternate proof.)

#

#