congruence Congruence3 2003-07-20 18:55:52 2003-08-02 16:14:08 Definition % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here \let \proves = \vdash \let \implies = \rightarrow \let \Implies = \Rightarrow \let \iff = \leftrightarrow \let \Iff = \Leftrightarrow \let \iso = \cong \newcommand{\eqclass}[1]{[\![#1]\!]} \newcommand{\set}[1]{\{#1\}} \newcommand{\tuple}[1]{\langle#1\rangle} \newcommand{\gen}[1]{\langle\!\langle #1 \rangle\!\rangle} \newcommand{\powerset}{\mathcal P} \DeclareMathOperator{\dom}{dom} \DeclareMathOperator{\range}{range} \DeclareMathOperator{\im}{im} \newcommand{\A}{\mathfrak{A}} \newcommand{\B}{\mathfrak{B}} Let $\Sigma$ be a fixed signature, and $\A$ a structure for $\Sigma$. A \emph{congruence} $\sim$ on $\A$ is an equivalence relation such that for every natural number $n$ and $n$-ary function symbol $F$ of $\Sigma$, if \(a_i \sim a_i'\) then \(F^\A(a_1, \ldots a_n) \sim F^\A(a_1', \ldots a_n').\)