Department of Fundamentals of Computer Science

Wrocław University of Science and Technology

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.
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.
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.
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.
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$
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)$
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$
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\}$.
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
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|}$
Relation R is reflexive on a set $X$ if $(\forall x \in X)((x,x)\in R)$.
Any set of ordered pairs.
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)$.
The least upper bound of a set.
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)$.
Relation R jest symmetric if $(\forall x,y)(x R y \to y R x)$.
Any sentence of Propositional Calculus which is valid under any valuation.
Transcendental number
A number which is not algebraic.
Relation R jest transitive if $(\forall x,y,z)((x R y) \land (y R z) \to x R z)$
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.