Department of Fundamentals of Computer Science

Wrocław University of Science and Technology

- 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
- $|A|+|B|$ = $|(A \times \{0\})$ + $(B \times \{1\})|$
- $|A|\cdot |B| = |A \times B|$
- $|A|^{|B|} = |A^B|$
- $\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^{\aleph_0}$ = $\mathfrak{c}^{\aleph_0}$ = $\mathfrak{c}$,
- $\mathfrak{c}+\mathfrak{c} = 2 \cdot \mathfrak{c} = 3 \cdot \mathfrak{c} = \ldots = \aleph_0 \cdot \mathfrak{c} = \mathfrak{c} \cdot \mathfrak{c}$
- $\mathfrak{c}^2 = \mathfrak{c}^3 = \ldots = \mathfrak{c}^{\aleph_0} = \mathfrak{c}$
- $\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:- $A \subseteq B$
- $A \cup B = B$
- $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.