Operations and Structures

Subjects: Set Theory
Links: Natural Numbers, Stronger recursion Theorem, Alephs

Def: A binary operation on $S$ is a function from $S^2$ into $S$. Nonletter symbols such as $+,\cdot {,}_{,}\mathrm{△}$, etc. are often used to denote operations. The output of the function is dented as $x\ast y$ instead of $\ast (x,y)$.

Def: A unary operation on $S$ is a function mapping a subset of $S$ into $S$. A ternary operation on $S$ is a function on a subset $S^3$ into $S$.

Def: A structure consists of a set $A$ and of several relations and operations on $A$, usually denoted as an $n$ -tuple.

$n$-Tuples and Sequences of length $n$

The ordered pair such that

We called $a_0$ the first coordinate of $(a_0,a_1)$, and $a_1$ its second coordinate. In analogy, an $n$-tuple $(a_0,\dots ,a_{n-1})$ should be a set that uniquely determines its $n$ , we want

Using sequences, we find that the ****************sequence of length $n$, $⟨a_0,\dots ,a_{n-1}⟩$. The statement that

since it is a comparison of functions. Then we define $n$-tuples as sequences of length $n$.

If $⟨A_i\mid i\in n⟩$ is a finite sequence of sets, then the $n$-fold Cartesian product $\prod _{i\in n}{A}_i$, as defined in when talking about the Cartesian product, is the set of $n$ -tuples $a=⟨a_0,\dots ,a_{n-1}⟩$, where $a_i\in A_i$ for $i\in n$. If $A_i=A$ for all $i\in n$, then $\prod _{i\in n}{A}_i=A^n$ is the set of all $n$-tuples with all coordinates from $A$.

We note $A^0=\{⟨⟩\}$, and $A^1$ can be identified with $A$.

An $n$-ary relation $R$ in $A$ is a subset of $A^n$. We then write $R(a_0,\dots ,a_{n-1})$ instead of $⟨a_0,\dots ,a_{n-1}⟩\in R$. Similarly an $n$-ary operation $F$ on $A$ is a function from $A^n$ into $A$; we write $F(a_0,\dots ,a_{n-1})$ instead of $F(⟨a_0,\dots ,a_{n-1}⟩)$. If $P(x_0,\dots ,x_{n-1})$ is a property with parameters $x_0,x_1,\dots ,x_{n-1}$, we write

to denote the set

A special case is the $0$-ary operation, since it is of the form $\{(⟨⟩,a)\}$ where $a\in A$. We call them constants, and we don’t distinguish them with elements of $A$.

There are problems if we want to define $n$-tuples with recursion as:$$ (a_0) = a_0 $$$$\forall n \in \Bbb N^+[(a_i){i\in n}=(a_0, a_1, \dots, a_n) = ((a_0, a_1, \dots, a), a_n)=((a_i)_{i\in n-1}, a_n)]

where $R_i$ is an $r_i$-ary relation on $A$ for each $i\in m$ and $F_j$ is an $f_j$-ary operation on $A$ for each $j\in n$, in addition we require $F_j\ne \varnothing$ if $f_j=0$. We call $A$ the universe of the structure $\mathfrak{U}$.

Def: An isomorphism between structures $\mathfrak{U}$ and ${\mathfrak{U}}^{\prime }\mathfrak{=}\mathfrak{(}{\mathfrak{A}}^{\prime }\mathfrak{,}⟨{\mathfrak{R}}_{\mathfrak{0}}^{\prime }\mathfrak{,}\dots \mathfrak{,}{\mathfrak{R}}_{\mathfrak{m}\mathfrak{-}\mathfrak{1}}^{\prime }⟩\mathfrak{,}⟨{\mathfrak{F}}_{\mathfrak{0}}^{\prime }\mathfrak{,}\dots \mathfrak{,}{\mathfrak{F}}_{\mathfrak{n}\mathfrak{-}\mathfrak{1}}^{\prime }⟩\mathfrak{)}$ of the same type $\tau$ is a bijection from $A$ into $A^{\prime }$ such that

• $R_i(a_0,\dots a_{r_i-1})$ iff $R_i^{\prime }(h(a_0),\dots ,h(a_{r_i-1}))$ holds for all $a_0,\dots ,a_{r_i-1}\in A$ and $i\in m$
• $h(F_j(a_0,\dots ,a_{f_j-1}))=F_j(h(a_0),\dots ,h(a_{f_j-1}))$ for all $a_0,\dots ,a_{f_j-1}\in A$ and $j\in n$, provided that either side is defined.

An isomorphism between $\mathfrak{U}$ and $\mathfrak{U}$ is called an automorphism. The trivial automorphism is the identity.

Given a structure $\mathfrak{U}$, we can consider the automorphism group.

Def: Consider a fixed structure $\mathfrak{U}=(A,⟨R_0,\dots ,R_{m-1}⟩,⟨F_0,\dots ,F_{n-1}⟩)$. A set $B\subseteq A$ is called closed if the result of applying any operation to elements of $B$ is again in $B$. Let $C\subseteq A$; the closure of $C$, to be denoted $\bar{C}$, is the least closed set containing all elements of $C$:

Th: Let $\mathfrak{U}=(A,⟨R_0,\dots ,R_{m-1}⟩,⟨F_0,\dots ,F_{n-1}⟩)$ be a structure and $C\subseteq A$. If the sequence $⟨C_i\mid i\in \mathbb{N}⟩$ is defined recursively

then $\bar{C}=\bigcup _{i\in \mathbb{N}}{C}_i$.

Th: Let $P(x)$ be a property. Assume that

• $P(a)$ holds for all $a\in C$
• For each $j\in n$ if $P(a_0),\dots P(a_{f_j-1})$ hold and $F(a_0,\dots ,a_{f_j-1})$ is well defined then $P(F(a_0,\dots ,a_{f_j-1}))$ holds

Then $P(x)$ holds for all $x\in \bar{C}$.

Infinitary Operations

We define $F$ is a (countably) infinitary operation on $A$ if $F$ is a function on a subset of $A^{\mathbb{N}}$ (the set of all infinite sequences of elements of $A$) into $A$, and introduce structures with infinitary operations. This can be done formally by extending the definition of type by allowing $f\in \mathbb{N}\cup \{\mathbb{N}\}$ and postulating that $F_j$ is an infinitary operation whenever $f_j=\mathbb{N}$. The definition of a set $B\subseteq A$ being closed remains unchanged; if $f_j=\mathbb{N}$ we require $F_j(⟨a_i\mid i\in \mathbb{N}⟩)\in B$ for all $⟨a_i\mid i\in \mathbb{N}⟩$ such that $a_i\in B$ for all $i\in \mathbb{N}$, and $F_j$ is defined. The closure $\bar{C}$ of $C\subseteq A$ is still the least closed containing all elements of $C$.

Th: Let $\mathfrak{U}=(A,⟨R_0,\dots ,R_{m-1}⟩,⟨F_0,\dots ,F_{n-1}⟩)$ be a structure and let $C\subseteq A$. Let $\bar{C}$ be the closure of $C$. If $C$ is finite, the $\bar{C}$ is at most countable; if $C$ is infinite, then $|\bar{C}|=|C|$.

Th: Let $\mathfrak{U}=(A,F)$ be a structure where $F$ is a function on a subset of $A^{\omega }$ into $A$, and let $C\subseteq A$. Let $\bar{C}$ be the closure of $C$ in $\mathfrak{U}$, i.e., $$ \overline C = \bigcap {X \subset A \mid F[X^\omega]\subseteq X \land C\subseteq X}$$
If $C$ has at least two elements, then $|\bar{C}|\le |C{|}^{{\mathrm{\aleph }}_0}$

We also prove in the same proof that if we define

And $$\overline C = \bigcup_{\alpha< \omega_1} C_\alpha$$