every congruence is the kernel of a homomorphism

Let $\Sigma$ be a fixed signature, and $\mathfrak{A}$ a structure for $\Sigma$ . If $\sim$ is a congruence on $\mathfrak{A}$ , then there is a homomorphism $f$ such that $\sim$ is the kernel of $f$ .

Proof.

Define a homomorphism $f\colon\mathfrak{A}\to\mathfrak{A}/\!\sim\ :a\mapsto[\![a]\!]$ . Observe that $a\sim b$ if and only if $f(a)=f(b)$ , so $\sim$ is the kernel of $f$ . To verify that $f$ is a homomorphism, observe that

1.

For each constant symbol $c$ of $\Sigma$ , $f(c^{\mathfrak{A}})=[\![c^{\mathfrak{A}}]\!]=c^{\mathfrak{A}/\!\sim}$ .
2.

For each $n\in\mathbb{N}$ and each $n$ -ary function symbol $F$ of $\Sigma$ ,

$\displaystyle f(F^{\mathfrak{A}}(a_{1},\ldots a_{n}))$ $\displaystyle=[\![F^{\mathfrak{A}}(a_{1},\ldots a_{n})]\!]$

$\displaystyle=F^{\mathfrak{A}/\!\sim}([\![a_{1}]\!],\ldots[\![a_{n}]\!])$

$\displaystyle=F^{\mathfrak{A}/\!\sim}(f(a_{1}),\ldots f(a_{n})).\qed$
3.

For each $n\in\mathbb{N}$ and each $n$ -ary relation symbol $R$ of $\Sigma$ , if $R^{\mathfrak{A}}(a_{1},\ldots,a_{n})$ then $R^{\mathfrak{A}/\!\sim}([\![a_{1}]\!],\ldots,[\![a_{n}]\!])$ , so $R^{\mathfrak{A}/\!\sim}(f(a_{1}),\ldots,f(a_{n}))$ .

Title	every congruence is the kernel of a homomorphism
Canonical name	EveryCongruenceIsTheKernelOfAHomomorphism
Date of creation	2013-03-22 13:48:59
Last modified on	2013-03-22 13:48:59
Owner	almann (2526)
Last modified by	almann (2526)
Numerical id	11
Author	almann (2526)
Entry type	Theorem
Classification	msc 03C07
Classification	msc 03C05

	$\displaystyle f(F^{\mathfrak{A}}(a_{1},\ldots a_{n}))$	$\displaystyle=[\![F^{\mathfrak{A}}(a_{1},\ldots a_{n})]\!]$
		$\displaystyle=F^{\mathfrak{A}/\!\sim}([\![a_{1}]\!],\ldots[\![a_{n}]\!])$
		$\displaystyle=F^{\mathfrak{A}/\!\sim}(f(a_{1}),\ldots f(a_{n})).\qed$