Friday, 24 May 2013

Quine Transform of a Model

Suppose that $\mathcal{A} = (A, \vec{R}, \vec{f})$ is a model, and let $\pi : A \rightarrow A$ be a bijection (permutation of $A$ to itself). Next, define the following notion:

Definition [Quine Transform]
The Quine transform of $\mathcal{A}$ under $\pi$, written $\mathcal{A}^{\pi}$, is given by:
$\mathcal{A}^{\pi}: = (A, \pi[\vec{R}], \pi[\vec{f}])$. 
For example, suppose the model $\mathcal{A} = (A,R)$ is specified as follows:
$A= \{0,1, 2\}$
$R= \{(0,1), (0,2), (1,2) \}$. 
Let $\pi: A \to A$ be the transposition that swaps $0$ to $1$. Then,
$\pi[R] = \{(1,0), (1,2),(0,2)\}$
Consequently, $R$ and $\pi[R]$ are extensionally distinct. However, $\mathcal{A}$ and $\mathcal{A}^{\pi}$ are isomorphic under $\pi$. More generally, one can see that:

Lemma ["Quine Transform Lemma"]
Let $\pi : A \to A$ be any bijection. Then: $\mathcal{A}^{\pi} \cong \mathcal{A}$.

This is all quite simple discrete mathematics. But it has interesting applications.