# Set theoretical dictionary

Aleph zero
The cardinality of natural numbers, denoted by $\aleph_0$.
Algebraic number
A real number which is a root of some non-zero polynomial with rational coefficients.
Antitautology
A sentence of Propositional Calculus whose negation is a tautology. Other name: contradictory sentence.
Axiom of Choice (AC)
Sentence: "every partition has a selector, i.e. such a set which has precisely one element with every set from the partition".
Axiom of extensionality
Two sets are equal if they have the same elements.
Bijection
A function which is injection and surjection.
Composition of bijections is a bijection.
Cantor theorem
$|A| \lt |P(A)|$.
Cantora-Bernsteina Theorem
$(|A| \le |B| \land |B| \le |A|) \to |A|=|B|$.
Cardinal arithmetic
1. $|A|+|B|$ = $|(A \times \{0\})$ + $(B \times \{1\})|$
2. $|A|\cdot |B| = |A \times B|$
3. $|A|^{|B|} = |A^B|$
1. $\aleph_0+\aleph_0 = 2 \cdot \aleph_0 = 3 \cdot \aleph_0 = \ldots = \aleph_0 \cdot \aleph_0 = \aleph_0^2= \aleph_0^3 = \ldots = \aleph_0$
2. $2^{\aleph_0}$ = $\mathfrak{c}^{\aleph_0}$ = $\mathfrak{c}$,
3. $\mathfrak{c}+\mathfrak{c} = 2 \cdot \mathfrak{c} = 3 \cdot \mathfrak{c} = \ldots = \aleph_0 \cdot \mathfrak{c} = \mathfrak{c} \cdot \mathfrak{c}$
4. $\mathfrak{c}^2 = \mathfrak{c}^3 = \ldots = \mathfrak{c}^{\aleph_0} = \mathfrak{c}$
5. $\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \ldots$
Cartesian product
Cartesian product of sets A and B is the set of all ordered pairs $(a,b)$ such that $a \in A$ and $b \in B$.
Complete lattice
A partial ordering (X,R) such that every nonempty subset of X has a supremum and infimum.
Composition of relations
A composition of relations $R$ and $S$ is the relation $R \circ S$ such that for each pair $(x,z)$ we have $$(x,z)\in R \circ S \equiv (\exists y)((x,y)\in S) \land (y,z)\in R))$$
Złożenie relacji jest łączne. Nie jest przemienne.
Continuum
The cardinality of real numbers.
Continuum Hypothesis(CH)
Sentence: "if $A \subseteq \mathbf{R}$ then $|A| =|\mathbf{R}|$ or $|A| \leq |\mathbf{N}|" Countable set$A$is countable if$A$is empty or there exists a surjection from natural numbers onto$A$. Examples: finite sets, natural numbers, rational numbers, algebraic numbers, set of all finite sequences of natural numbers. De Morgans laws Some basic laws of Propositional Calculs, set-theoretic operations, and first order logic: Dirichlett Principle If m, n are natural numbers, n<m and f:{1,...,m} → {1,...,n} then f is not an injection. Empty set. Oznaczenie:$\emptyset$The set with no elements, denoted by$\emptyset$. Axiom of Extensionality implies that there exists only one empty set. Equinumerosity Two sets$A$and$B$are equinumeros ($|A|=|B|$) if there exists a bijection between$A$i$B$. Equivalence class An equivalence class of element$a$under equivalence relation$R$is the set$[a]_R = \{x : a R x\}$. Equivalence relation A relation which is reflexive, symmetric and transitive. Family of sets Set of sets. In axiomatic set theory ZF every set is a family of sets. Finite set A set equinumerous with$\{0,...,n-1\}$for some natural number$n$. Fix-point of a mapping A fix point of a mapping$f:X \to X$is an element$a \in X$such that$f(a) = a$Function A set$f$is a function if$f$is a relation such that$(\forall x,a,b)((x,a)\in f \land (x,b) \in f) \to a=b)$. Greatest element Let ($X,R)$be a partial ordering. An element$a\in X$is$R$-greatest if$(\forall x \in X)(x R a)$. Image of a set If$R$is a relation and$A$is a set then$R[A]$is the set of all$y$such that$(\exists x \in A)(xRy)$Inclusion A set A is contained in B if every element of A is an member of B. The following sentences are equivalent: 1.$A \subseteq B$2.$A \cup B = B$3.$A \cap B = A$Injection A function$f: X \to Y$is injection if$f(x)=f(y) \to x=y$for each$x,y$. Inverse relation The inverse of relation$R$is$R^{-1} = \{(x,y): (y,x)\in R\}$. Isomorphizm Two partial orders$(X,R)$and$(Y,Q)$are isomorphic if there exists a bijection$f$from X to Y s.t. (x R y) iff (f(x) Q f(y)) Kuratowski-Tarski Theorem If$L$is a complete lattice and$f:L \to L$is monotonic then$f$has a fixed point. Kuratowski-Zorn Lemma (LKZ) Sentence: every partial ordering satisfiyng "every chain has an uppe bound" has a maximal element. KLZ is equivalent to AC Lattice A partial ordering$(X,R)$such that every nonempty finite subset of$X$has a supremum and infimum. Linear ordering A partial ordering$(X,R)$such that$(\forall x,y \in X)( (x R y) \lor (x=y) \lor (y R x))$. Logical values In classical Propositional Calculus it is the set {FALSE,TRUE}. Mathematical Induction Principle The following property of natural numbers: if$A$is a subset of natural numbers$\mathbf{N}$such that $$0\in A \land (\forall n \in \mathbf{N})(n \in A \to n+1 \in A)~,$$ then A is equal to the set of natural numbers. Maximal element If$(X,R)$is a partial ordering then the element$a\in X$is$R$-maximal if$(\forall x\in X)(a R x \to x=a)$. Minimal element Let$(X,R)$be a partial ordering. An element$a\in X$is R-minimal if$(\forall x \in X)(x R a \to x=a)$. Modus ponens The following deduction rule:$\{p, p \to q\} \models q$Newtons Symbol${n \choose k}$= the number of subsets of$\{1,\ldots,n\}$of cardinality$k$. Ordered pair Kuratowski's definition:$(x,y) = \{\{x\},\{x,y\}\}$. Its basic property:$(a,b)=(c,d)$if and only if$(a=c) \land (b=d)$Pair of elements A pair of$x$i$y$is the set$\{x,y\}$whose only elements are$x$and$y$. Partial ordering A pair$(X,R)$such that$R$is reflexive on$X$, transitive and weakly anti-symmetric. A restriction of a partial ordering to its subset is also a partial ordering. Partition of a set A family of sets P is a partition of X if P consists of non-empty, pairwise disjoints sets and the union of P is X. Power set Power set of$A$is the set$P(A)$of all subsets of$A$.$P(0) = \{0\}$;$P(P(0)) = \{0,\{0\}\}$;$|P(A)| = 2^{|A|}$Reflexivity Relation R is reflexive on a set$X$if$(\forall x \in X)((x,x)\in R)$. Relation Any set of ordered pairs. Resolution The following deduction rule: {p ∨ Q, ¬p ∨ R} |= Q ∨ R Russell's Theorem There is no set of all sets. Set of cardinality continuum A set equinumerous with real numbers. Smallest element If$(X,R)$is a partial ordering then the element$a\in X$is$R$-smallest if$(\forall x \in X)(a R x)$. Supremum The least upper bound of a set. Surjekcja A function$f: X \to Y$is surjection if$rng(f) = Y$. Symmetric difference Binary operation on sets defined by formula$(A\setminus B) \cup (B\setminus A)$. Symmetry Relation R jest symmetric if$(\forall x,y)(x R y \to y R x)$. Tautology Any sentence of Propositional Calculus which is valid under any valuation. Transcendental number A number which is not algebraic. Transitivity Relation R jest transitive if$(\forall x,y,z)((x R y) \land (y R z) \to x R z)$Valuation Any assignment of logical values to propositional variables. Weakly antysymmetric Relation R is weakly antysymmetric if$(\forall x,y\in X)((x R y \land y R x) \to x=y)\$.
Well ordering
A linear ordering such that each its nonempty subset has a minimal element.
Well-ordering principle (WO)
Sentence: "each set can be well-ordered".
WO is equivalent to Axiom of Choice.