Copiae, relationes et fvnctiones

Svmmarivm

Haec lectio sermonem constitvit qvo cvrsvs de nvmeris et fvnctionibvs loqvitvr, vna cvm eo qvod ex logica qvantificatorvm necessarivm est. Inclvsionem et operationes copiarvm definit, aeqvalitatem per inclvsionem dvplicem et leges De Morgani demonstrat, par ordinatvm cvm proprietate eivs characteristica constrvit et prodvctvm Cartesianvm relationesqve cvm earvm proprietatibvs definit. Demonstrat classes aeqvivalentiae partitionem efficere et omnem partitionem aeqvivalentiam definire, constrvctionem nvmerorvm integrorvm anticipans; ordines cvm elementis extremis et marginibvs svis perscrvtatvr; et fvnctiones vt relationes tractat, demonstrans compositionem associativam esse et iniectivitatem svperiectivitatemqve servare, fvnctionemqve biiectivam esse si et solvm si inversam habeat, qvae vnica est. Problemata aeqvivalentias nvmerant, nvmeros natvrales cvm nvmeris paribvs copvlant, diem hebdomadis cvivsdam diei invenivnt et omnem fvnctionem in svperiectionem, biiectionem et iniectionem resolvvnt.

Proposita discendi

Envntiata cvm qvantificatoribvs sermone symbolico scribere, ea recte negare et rationem demonstrandi eligere qvam forma eorvm logica postvlat.
Aeqvalitates et inclvsiones inter copias per inclvsionem dvplicem demonstrare, et vniones, intersectiones, differentias, prodvcta Cartesiana copiasqve partivm copiarvm finitarvm compvtare.
Diivdicare vtrvm relatio reflexiva, symmetrica, antisymmetrica an transitiva sit, et relationes aeqvivalentiae relationesqve ordinis agnoscere.
Classes et copiam qvotientem relationis aeqvivalentiae constrvere, et ab aeqvivalentia ad partitionem qvam definit transire, et vice versa.
Minimvm, maximvm, elementa minimalia et maximalia marginesqve svbcopiae copiae ordinatae determinare.
Imagines, praeimagines, compositiones et inversas compvtare, diivdicare vtrvm fvnctio iniectiva, svperiectiva an biiectiva sit, et proprietates compositionis demonstrare.

Sermo cvrsvs

Lectio seqvens nvmeros natvrales per fvnctionem definit, svccessorem, qvae iniectiva est et ad $1$ non pervenit. Pars seqvens nvmeros integros et rationales vt classes relationis aeqvivalentiae constrvit; lectio de combinatoria nvmervm elementorvm per biiectiones definit; ordo nvmerorvm natvralivm relatio ordinis est; et pars tertia fvnctiones reales componit et invertit. Omnia haec verba ad vnvm evndemqve sermonem pertinent, qvem constitvere expedit anteqvam adhibeatvr, vna cvm primis theorematibvs qvae cvrsvs postea invocabit.

Monere expedit qvid anticipetvr. Exempla nvmeros natvrales parvos adhibent cvm ordine, additione, mvltiplicatione, divisibilitate et residvo divisionis, sicvt in schola discvntvr. Lectio seqvens nvmeros natvrales per axiomata Peani definit, et lectiones partis has operationes definivnt earvmqve proprietates demonstrant nvllo hvivs lectionis exemplo adhibito, ita vt nvllvs circvlvs sit. Nvllvm hvivs lectionis theorema ex exemplis pendet: nvmeri tantvm eo valent vt theoremata in actv videantvr.

Qvae admittvntvr

Copia est collectio obiectorvm, qvae eivs elementa svnt; scribitvr $a \in A$ vt dicatvr $a$ ad $A$ pertinere, et $a \notin A$ vt id negetvr. Copia et pertinentia non definivntvr: notiones primitivae svnt, sicvt $1$ et svccessor in arithmetica. Atqvi non omnis proprietas copiam definit. Si exsisteret copia $R$ omnivm copiarvm qvae ad se ipsas non pertinent, qvaestio vtrvm $R$ ad $R$ pertineat responsvm non haberet, qvia ex definitione ipsivs $R$ esset $R \in R \leftrightarrow R \notin R$ . Haec contradictio, a Rvssell anno 1901 reperta, cogit formationem copiarvm restringere: proprietas nonnisi elementa copiae iam datae seligit.

Factvm admissvm (regvlae theoriae copiarvm intvitivae). Sine demonstratione admittvntvr regvlae theoriae copiarvm intvitivae qvibvs haec lectio vtitvr: dvae copiae eadem elementa habentes aeqvales svnt; ex copia data $A$ et proprietate $P$ formatvr copia $\{ x \in A : P(x) \}$ elementorvm ipsivs $A$ qvae eam habent; et exsistvnt copia vacva, copia $\{a, b\}$ cvivs sola elementa svnt $a$ et $b$ , vnio elementorvm copiae copiarvm et copia svbcopiarvm copiae. Exsistentia copiae proprietates copiae nvmerorvm natvralivm habentis in lectione seqventi admittitvr.

Hae regvlae ad axiomata Zermeli et Fraenkelii pertinent, qvorvm stvdivm ad theoriam copiarvm spectat et hvnc cvrsvm excedit; ideo admittvntvr, et declarantvr vt accvrate sciatvr qvid adhibeatvr.

Logica qvantificatorvm

Demonstrationes envntiata connectivis $\neg$ , $\wedge$ , $\vee$ , $\rightarrow$ et $\leftrightarrow$ ivngvnt, qvorvm leges in cvrsv complementario Logica Mathematica I: Logica Propositionalis perscrvtantvr, ab eivs lingva incipiendo; hic satis est meminisse implicationem $p \rightarrow q$ falsam esse tantvm cvm $p$ vera et $q$ falsa est, eam contrapositioni svae $\neg q \rightarrow \neg p$ aeqvivalere, et leges De Morgani conivnctionem vel disivnctionem negare:

\neg \left( p \wedge q \right) \leftrightarrow \left( \neg p \vee \neg q \right), \qquad \neg \left( p \vee q \right) \leftrightarrow \left( \neg p \wedge \neg q \right)

Vt de copiis loqvamvr, praeterea envntiatis opvs est de omnibvs elementis vel de aliqvo. Si $P(x)$ proprietas est elementorvm ipsivs $A$ , envntiatvm $(\forall x \in A)\,P(x)$ , qvod legitvr «pro omni $x$ ex $A$ , $P(x)$ », affirmat omnia elementa ipsivs $A$ eam habere; envntiatvm $(\exists x \in A)\,P(x)$ , «exsistit $x$ ex $A$ tale vt $P(x)$ », affirmat saltem vnvm eam habere; et $(\exists! x \in A)\,P(x)$ affirmat vnvm prorsvs eam habere. Signa $\forall$ et $\exists$ qvantificatores appellantvr, vniversalis et exsistentialis.

Factvm admissvm (negatio qvantificatorvm). Negare omnia elementa proprietatem habere est affirmare aliqvod eam non habere, et negare aliqvod eam habere est affirmare nvllvm eam habere:

\neg (\forall x \in A)\,P(x) \leftrightarrow (\exists x \in A)\,\neg P(x), \qquad \neg (\exists x \in A)\,P(x) \leftrightarrow (\forall x \in A)\,\neg P(x)

Hae regvlae, logicae primi ordinis propriae, admittvntvr; leges De Morgani extendvnt, qvia si $A = \{a, b\}$ envntiatvm vniversale est $P(a) \wedge P(b)$ et exsistentiale est $P(a) \vee P(b)$ . Ordo qvantificatorvm refert: envntiatvm $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ dicit omnem nvmervm natvralem alivm maiorem habere, et vervm est; envntiatvm $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ dicit esse nvmervm natvralem omnibvs maiorem, etiam se ipso, et falsvm est.

Forma logica envntiati modvm eivs demonstrandi praescribit. Rationes qvibvs haec lectio vtitvr hae svnt; earvm ivstificatio logica in lectione de artibvs dedvctionis perscrvtatvr.

Vt $(\forall x \in A)\,P(x)$ demonstretvr, svmitvr elementvm $x$ ipsivs $A$ qvodlibet, de qvo nihil praeter pertinentiam ad $A$ svpponitvr, et demonstratvr $P(x)$ .
Vt $(\exists x \in A)\,P(x)$ demonstretvr, exhibetvr elementvm certvm ipsivs $A$ qvod $P$ habet; vt $(\forall x \in A)\,P(x)$ refvtetvr, satis est exemplvm contrarivm, elementvm qvod eam non habet.
Vt $p \rightarrow q$ demonstretvr, svpponitvr $p$ et dedvcitvr $q$ ; vel demonstratvr contrapositio $\neg q \rightarrow \neg p$ ; vel svpponitvr $p \wedge \neg q$ et ad contradictionem pervenitvr.
Vt $p \leftrightarrow q$ demonstretvr, demonstrantvr ambae implicationes $p \rightarrow q$ et $q \rightarrow p$ .

ExemplvmNegare copiam circvmscriptam esse

Copia $X$ nvmerorvm natvralivm svpra circvmscripta est cvm exsistit nvmervs natvralis $c$ maior vel aeqvalis omnibvs eivs elementis. Definitionem cvm qvantificatoribvs scribere eamqve gradatim negare.

Demonstratio

$\dato{acot}{(\exists c \in \mathbb{N})(\forall x \in X)(x \leq c)}$
Definitio qvantificatorem exsistentialem habet qvem vniversalis seqvitvr: idem $c$ omnibvs elementis convenire debet.
$\resaltar{\neg} (\exists c \in \mathbb{N})(\forall x \in X)(x \leq c)$
Envntiatvm totvm negamvs.
$(\resaltar{\forall} c \in \mathbb{N})\,\resaltar{\neg} (\forall x \in X)(x \leq c)$
Negatio envntiati exsistentialis est envntiatvm vniversale negationis.
$(\forall c \in \mathbb{N})(\resaltar{\exists} x \in X)\,\resaltar{\neg} (x \leq c)$
Negatio envntiati vniversalis est envntiatvm exsistentiale negationis.
$(\forall c \in \mathbb{N})(\exists x \in X)(\resaltar{x > c})$
Per trichotomiam ordinis nvmerorvm natvralivm, negare $x \leq c$ est affirmare $x > c$ : copia svpra circvmscripta non est cvm nvllvs nvmervs natvralis margo est, qvia qvemqve candidatvm aliqvod elementvm svperat.

Copiae

Pertinentia, aeqvalitas et inclvsio

Copia describitvr per envmerationem, elementis eivs inter vncos envmeratis, vt $\{1, 2, 3\}$ , vel per comprehensionem, per proprietatem, vt $\{ n \in \mathbb{N} : n \leq 3 \}$ , qvae eadem copia est. Regvla extensionalitatis dicit copiam elementis svis determinari:

A = B \leftrightarrow (\forall x)(x \in A \leftrightarrow x \in B)

Inde seqvitvr in descriptione per envmerationem nec ordinem nec repetitiones referre: $\{1, 2, 2\}$ et $\{2, 1\}$ eadem copia svnt, qvia eadem elementa habent. Seqvitvr etiam vnam tantvm copiam sine elementis esse, copiam vacvam $\emptyset$ : dvae copiae sine elementis eadem elementa habent, scilicet nvlla.

Definitio (inclvsio). Copia $A$ in copia $B$ contenta est, sive svbcopia est ipsivs $B$ , cvm omne elementvm ipsivs $A$ elementvm est ipsivs $B$ :

A \subseteq B \leftrightarrow (\forall x)(x \in A \rightarrow x \in B)

Si praeterea $A \neq B$ , dicitvr $A$ svbcopia propria esse ipsivs $B$ .

Copia vacva in omni copia $A$ continetvr, qvia implicatio $x \in \emptyset \rightarrow x \in A$ semper antecedens falsvm habet et ideo vera est. Pertinentiam ab inclvsione distingvere oportet: $1 \in \{1, 2\}$ et $\{1\} \subseteq \{1, 2\}$ vera svnt, at $\{1\} \in \{1, 2\}$ falsvm est, qvia sola elementa ipsivs $\{1, 2\}$ svnt $1$ et $2$ , et copia $\{1\}$ nevtri eorvm aeqvalis est: $\{1\} \neq 1$ , qvia copia cvivs solvm elementvm est $1$ cvm ipso $1$ non confvnditvr, et $\{1\} \neq 2$ .

TheoremaProprietates inclvsionis

Pro omnibvs copiis $A$ , $B$ et $C$ inclvsio est reflexiva, $A \subseteq A$ ; transitiva, si $A \subseteq B$ et $B \subseteq C$ , tvm $A \subseteq C$ ; et antisymmetrica, si $A \subseteq B$ et $B \subseteq A$ , tvm $A = B$ . Vltima proprietas, vna cvm conversa sva, qvae statim patet, est methodvs inclvsionis dvplicis: vt demonstretvr dvas copias aeqvales esse, demonstratvr vtramqve in altera contineri.

A = B \leftrightarrow \left( A \subseteq B \wedge B \subseteq A \right)

Qvaeqve proprietas ad legem implicationis redvcitvr, qvolibet elemento adhibito. Figvra copias vt regiones plani repraesentat.

Demonstratio

$(\forall x)(x \in A \rightarrow x \in A)$
Reflexivitas: pro omni $x$ implicatio $x \in A \rightarrow x \in A$ vera est, qvia conseqvens eivs est antecedens eivs.
$x \in A \rightarrow \dato{xb}{x \in B}$
Transitivitas: sit $x$ elementvm qvodlibet ipsivs $A$ . Per primam hypothesim $x$ ad $B$ pertinet.
$\resaltar{x \in B} \rightarrow x \in C$
Per secvndam hypothesim $x$ ad $C$ pertinet. Cvm $x$ qvodlibet esset, $A \subseteq C$ .
$(x \in A \rightarrow x \in B) \wedge (x \in B \rightarrow x \in A) \leftrightarrow \resaltar{(x \in A \leftrightarrow x \in B)}$
Antisymmetria: dvae hypotheses pro qvoqve $x$ praebent ambas implicationes inter $x \in A$ et $x \in B$ , id est earvm aeqvivalentiam.
$A = B$
Per extensionalitatem $A$ et $B$ aeqvales svnt. Vice versa, si $A = B$ , vtraqve in altera per reflexivitatem continetvr.

Vnio, intersectio et differentia

Definitio (operationes copiarvm). Vnio ipsarvm $A$ et $B$ est copia elementorvm qvae ad aliqvam earvm pertinent; intersectio, copia eorvm qvae ad ambas pertinent; et differentia $A \setminus B$ , copia eorvm qvae ad $A$ pertinent et non ad $B$ :

x \in A \cup B \leftrightarrow x \in A \vee x \in B, \qquad x \in A \cap B \leftrightarrow x \in A \wedge x \in B, \qquad x \in A \setminus B \leftrightarrow x \in A \wedge x \notin B

Si $B \subseteq A$ , differentia $A \setminus B$ complementvm ipsivs $B$ relativvm ad $A$ appellatvr. Dvae copiae disivnctae svnt cvm earvm intersectio vacva est.

Qvaeqve operatio connectivvm reddit: vnio disivnctionem; intersectio conivnctionem; differentia conivnctionem cvm negatione. Si hoc ita est, qvaeqve lex logica legem copiarvm gignit: vnio et intersectio commvtativae, associativae et altera respectv alterivs distribvtivae svnt qvia connectiva talia svnt, et omnes hae leges sicvt theorema seqvens demonstrantvr. Complementvm semper respectv copiae referentiae svmitvr, qvia copia omnivm qvae in $B$ non svnt paradoxvm Rvssellianvm restitveret.

ExemplvmDivisores nvmerorvm 12 et 18

Sint $A = \{1, 2, 3, 4, 6, 12\}$ copia divisorvm nvmeri $12$ et $B = \{1, 2, 3, 6, 9, 18\}$ copia divisorvm nvmeri $18$ . Earvm vnionem, intersectionem et dvas differentias compvtare.

Demonstratio

$A \cap B = \dato{c}{\{1, 2, 3, 6\}}$
Elementa commvnia svnt divisores vtrivsqve nvmeri, id est divisores nvmeri $6$ .
$A \setminus B = \{1, 2, 3, 4, 6, 12\} \setminus \resaltar{\{1, 2, 3, 6\}} = \{4, 12\}$
Elementa ipsivs $A$ qvae divisores nvmeri $18$ non svnt ea svnt qvae manent commvnibvs ex $A$ remotis.
$B \setminus A = \{9, 18\}$
Eodem modo, divisores nvmeri $18$ qvi divisores nvmeri $12$ non svnt.
$A \cup B = \left( A \setminus B \right) \cup \left( A \cap B \right) \cup \left( B \setminus A \right) = \{1, 2, 3, 4, 6, 9, 12, 18\}$
Vnio tres copias complectitvr, qvae binae disivnctae svnt: qvodqve elementvm semel tantvm apparet, et $4 + 2 + 2 = 8$ .

TheoremaLeges De Morgani pro copiis

Pro omnibvs copiis $A$ , $B$ et $C$ complementvm relativvm ad $A$ vnionis est intersectio complementorvm, et complementvm intersectionis est vnio complementorvm:

A \setminus \left( B \cup C \right) = \left( A \setminus B \right) \cap \left( A \setminus C \right), \qquad A \setminus \left( B \cap C \right) = \left( A \setminus B \right) \cup \left( A \setminus C \right)

Ostenditvr elementvm qvodlibet ad primvm membrvm aeqvationis pertinere si et solvm si ad secvndvm pertinet, qvaqve operatione in connectivvm svvm conversa. Figvra in diagrammate Venniano regiones qvae intervenivnt obvmbrat.

Demonstratio

$x \in A \setminus \left( B \cup C \right) \leftrightarrow x \in A \wedge \resaltar{\neg} \left( x \in B \cup C \right)$
Sit $x$ qvodlibet. Per definitionem differentiae, ad primvm membrvm pertinere est in $A$ esse et in $B \cup C$ non esse.
$\leftrightarrow x \in A \wedge \neg \left( x \in B \resaltar{\vee} x \in C \right)$
Per definitionem vnionis.
$\leftrightarrow x \in A \wedge \left( x \resaltar{\notin} B \resaltar{\wedge} x \resaltar{\notin} C \right)$
Per legem De Morgani logicae, negatio disivnctionis est conivnctio negationvm.
$\leftrightarrow \left( \resaltar{x \in A} \wedge x \notin B \right) \wedge \left( \resaltar{x \in A} \wedge x \notin C \right)$
Cvm $p$ aeqvivaleat ipsi $p \wedge p$ , condicionem $x \in A$ iteramvs et itervm consociamvs, per associativitatem et commvtativitatem conivnctionis.
$\leftrightarrow x \in \left( A \setminus B \right) \resaltar{\cap} \left( A \setminus C \right)$
Per definitiones differentiae et intersectionis, hoc est ad secvndvm membrvm pertinere. Per extensionalitatem prima lex demonstrata est.
$x \in A \setminus \left( B \cap C \right) \leftrightarrow x \in A \wedge \left( x \notin B \resaltar{\vee} x \notin C \right) \leftrightarrow x \in \left( A \setminus B \right) \resaltar{\cup} \left( A \setminus C \right)$
Altera lex eadem catena demonstratvr, vnione cvm intersectione et disivnctione cvm conivnctione permvtatis; lex logica qvae tvm intervenit est altera lex De Morgani.

Copia partivm

Svbcopiae copiae ipsae copiam efficivnt, cvivs exsistentia initio admissa est. Copia partivm ipsivs $A$ , qvae $\mathcal{P}(A)$ notatvr, est copia cvivs elementa svnt svbcopiae ipsivs $A$ :

X \in \mathcal{P}(A) \leftrightarrow X \subseteq A

Exempli gratia, copia partivm ipsivs $\{1, 2, 3\}$ octo elementa habet: copiam vacvam, tres copias vnivs elementi, tres dvorvm elementorvm et ipsam $\{1, 2, 3\}$ .

\mathcal{P}(\{1, 2, 3\}) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}

Pro omni copia $A$ , copia vacva et ipsa $A$ elementa svnt ipsivs $\mathcal{P}(A)$ , et pro qvoqve $a$ ex $A$ habetvr $\{a\} \in \mathcal{P}(A)$ , at $a$ generaliter elementvm ipsivs $\mathcal{P}(A)$ non est. In lectione de combinatoria demonstrabitvr copiam $n$ elementorvm habere $2^n$ svbcopias.

Paria ordinata et prodvctvm Cartesianvm

Pvnctvm plani, fractio vel svbtractio nondvm peracta dvobvs obiectis ordine certo describvntvr: par $(3, 5)$ non est par $(5, 3)$ . Copia $\{3, 5\}$ ad id repraesentandvm non valet, qvia aeqvalis est ipsi $\{5, 3\}$ . Ab pari ordinato nihil alivd postvlatvr qvam eivs proprietas characteristica: dvo paria aeqvalia svnt si et solvm si eandem primam componentem et eandem secvndam componentem habent. Kvratowski anno 1921 animadvertit notionem copiae svfficere ad obiectvm hac proprietate praeditvm constrvendvm.

Definitio (par ordinatvm). Par ordinatvm cvivs prima componens est $a$ et secvnda componens $b$ est copia

(a, b) = \{ \{a\}, \{a, b\} \}

TheoremaProprietas characteristica paris ordinati

Pro omnibvs $a$ , $b$ , $c$ et $d$ , paria $(a, b)$ et $(c, d)$ aeqvalia svnt si et solvm si $a = c$ et $b = d$ .

(a, b) = (c, d) \leftrightarrow a = c \wedge b = d

Si componentes aeqvales svnt, paria eadem copia svnt. Ad conversvm distingvitvr vtrvm $a$ et $b$ aeqvales an diversi sint, et nvmeratvr qvot elementa qvaeqve copia qvae intervenit habeat. Figvra qvodqve par vt copiam dvarvm copiarvm depingit.

Demonstratio

$\dato{ig}{\{ \{a\}, \{a, b\} \} = \{ \{c\}, \{c, d\} \}}$
Ponamvs paria aeqvalia esse. Per extensionalitatem eadem elementa habent.
$\{c\} = \{a\}, \quad \{c, d\} = \{a\} \rightarrow c = a, \quad d = a = b$
Casvs primvs, $a = b$ . Tvm $\{a, b\} = \{a\}$ et primvm membrvm vnvm tantvm elementvm habet, $\{a\}$ ; dvo igitvr elementa secvndi membri ei aeqvalia svnt.
$\{c\} = \{a\} \rightarrow \dato{ca}{c = a}$
Casvs secvndvs, $a \neq b$ . Copia $\{c\}$ ad primvm membrvm pertinet, ita vt sit $\{a\}$ vel $\{a, b\}$ ; esse non potest $\{a, b\}$ , qvae dvo elementa habet, et ideo est $\{a\}$ .
$\{c, d\} = \{a, b\}$
Etiam $\{c, d\}$ ad primvm membrvm pertinet. Si esset $\{a\}$ , esset $d = a = c$ , et secvndvm membrvm vnvm tantvm elementvm haberet, $\{a\}$ , cvm primvm dvo habeat: id fieri non potest. Ergo $\{c, d\}$ est $\{a, b\}$ .
$\{a, \resaltar{d}\} = \{a, \resaltar{b}\} \rightarrow b = d$
Cvm $c = a$ , elementvm $b$ ipsivs $\{a, b\} = \{a, d\}$ est $a$ vel $d$ ; non est $a$ , qvia $a \neq b$ , et ideo est $d$ .
$(a, b) = (c, d) \rightarrow a = c \wedge b = d$
In vtroqve casv componentes congrvvnt.

Proprietate characteristica demonstrata, constrvctio Kvratowskiana oblivioni dari potest: qvidqvid cvrsvs de paribvs dicit ex ea dedvcitvr.

Definitio (prodvctvm Cartesianvm). Prodvctvm Cartesianvm ipsarvm $A$ et $B$ est copia parivm qvorvm prima componens ad $A$ et secvnda componens ad $B$ pertinet:

A \times B = \{ (a, b) : a \in A \wedge b \in B \}

Scriptvra $\{ (a, b) : a \in A \wedge b \in B \}$ per se non est vna ex regvlis admissis, qvae tantvm elementa ex copia iam formata separare sinvnt. Atqvi haec copia exsistit: si $a \in A$ et $b \in B$ , copiae $\{a\}$ et $\{a, b\}$ in $A \cup B$ continentvr, ideoqve elementa svnt ipsivs $\mathcal{P}(A \cup B)$ ; inde seqvitvr par $(a, b) = \{ \{a\}, \{a, b\} \}$ in $\mathcal{P}(A \cup B)$ contineri, id est elementvm esse ipsivs $\mathcal{P}(\mathcal{P}(A \cup B))$ . Ergo prodvctvm Cartesianvm per separationem intra hanc copiam formatvr, qvae per regvlas admissas exsistit: $A \cup B$ est vnio elementorvm ipsivs $\{A, B\}$ , et copia partivm bis svmitvr.

A \times B = \{ z \in \mathcal{P}(\mathcal{P}(A \cup B)) : (\exists a \in A)(\exists b \in B)\,(z = (a, b)) \}

Nomen Cartesivm in memoriam revocat: planvm geometriae analyticae est $\mathbb{R} \times \mathbb{R}$ . Prodvctvm commvtativvm non est: $\{1\} \times \{2\}$ solvm $(1, 2)$ continet, et $\{2\} \times \{1\}$ solvm $(2, 1)$ , qvod per proprietatem characteristicam diversvm est.

ExemplvmProdvctvm Cartesianvm vt reticvlvm

Prodvctvm $A \times B$ pro $A = \{1, 2, 3\}$ et $B = \{1, 2\}$ scribere, et nvmervm eivs elementorvm cvm nvmeris elementorvm factorvm comparare.

Demonstratio

$A = \{1, 2, 3\}, \quad B = \{1, 2\}$
Elementa ipsivs $A$ in axe horizontali disponimvs et elementa ipsivs $B$ in verticali: qvodqve par pvnctvm reticvli est.
$(1, 1), \ (2, 1), \ (3, 1)$
Paria qvorvm secvnda componens est $1$ primvm versvm efficivnt.
$(1, 2), \ (2, 2), \ (3, 2)$
Paria qvorvm secvnda componens est $2$ secvndvm versvm efficivnt.
$A \times B = \{ (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2) \}$
Prodvctvm $3 \cdot 2 = 6$ elementa habet: tot versvs qvot elementa ipsivs $B$ , singvlas cvm tot paribvs qvot elementa ipsivs $A$ . Principivm mvltiplicativvm combinatoriae hanc nvmerationem generalem reddit.

Relationes

Dicere $2$ dividere $6$ , $3$ minorem esse qvam $5$ , vel dvos dies in evndem diem hebdomadis incidere est affirmare qvaedam paria obiectorvm inter se referri. Si hoc ita est, relatio paribvs qvae refert determinatvr, et vt copia parivm definiri potest.

Definitio (relatio). Relatio ex $A$ in $B$ est svbcopia $R$ prodvcti $A \times B$ ; relatio in $A$ est relatio ex $A$ in $A$ . Si $(a, b) \in R$ , dicitvr $a$ cvm $b$ per $R$ referri.

Exempli gratia, relatio «minor vel aeqvalis» in $\{1, 2, 3\}$ est copia parivm $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$ . In relationibvs qvae saepe adhibentvr signvm inter terminos scribitvr, vt $a \leq b$ vel $a \mid b$ , loco $(a, b) \in R$ . Qvattvor proprietates relationis in copia per totvm cvrsvm redevnt.

Definitio (proprietates relationvm). Relatio $R$ in $A$ reflexiva, symmetrica, antisymmetrica vel transitiva est cvm condiciones seqventes respective explet.

Est reflexiva si omne elementvm cvm se ipso refertvr: $(\forall a \in A)\,((a, a) \in R)$ ;
Est symmetrica si relatio ipsivs $a$ cvm $b$ relationem ipsivs $b$ cvm $a$ implicat: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$ ;
Est antisymmetrica si dvo elementa vtroqve sensv relata aeqvalia svnt: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$ ;
Est transitiva si relatio ipsivs $a$ cvm $b$ et relatio ipsivs $b$ cvm $c$ relationem ipsivs $a$ cvm $c$ implicant: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$ .

In reticvlo ipsivs $A \times A$ relatio est copia pvnctorvm. Reflexiva est cvm totam diagonalem continet, scilicet parivm $(a, a)$ ; symmetrica est cvm pictvra eivs respectv diagonalis symmetrica est; et antisymmetrica est cvm nvllvm pvnctvm extra diagonalem symmetricvm svvm in relatione habet. Antisymmetrica non significat «non symmetrica»: aeqvalitas vtrvmqve est, et problema propositvm 1 relationem postvlat qvae nevtrvm sit.

ExemplvmDivisibilitas et paritas in copia ab 1 ad 6

In $A = \{1, 2, 3, 4, 5, 6\}$ considerantvr divisibilitas, $a \mid b$ , et relatio «eandem paritatem habere». Vtramqve in reticvlo ipsivs $A \times A$ depingere et diivdicare qvas ex qvattvor proprietatibvs vtraqve habeat.

Demonstratio

$\dato{div}{\{ (a, b) \in A \times A : a \mid b \}}$
Divisibilitas qvemqve nvmervm cvm svis mvltiplis intra $A$ refert: $1$ cvm omnibvs, $2$ cvm $2$ , $4$ et $6$ , $3$ cvm $3$ et $6$ , et qvemqve ceterorvm cvm se ipso. Paria svnt $14$ .
$a = 1 \cdot a \rightarrow \resaltar{a \mid a}$
Reflexiva est, qvia omnis nvmervs se ipsvm dividit: diagonalis completa est.
$2 \mid 4, \quad \neg (4 \mid 2)$
Symmetrica non est: vnvm exemplvm contrarivm svfficit. Contra antisymmetrica est, qvia si $a \mid b$ et $b \mid a$ , vterqve altero minor vel aeqvalis est.
$a \mid b \wedge b \mid c \rightarrow \resaltar{a \mid c}$
Transitiva est: si $b = ka$ et $c = lb$ , tvm $c = (lk)a$ . Exempli gratia, ex $1 \mid 2$ et $2 \mid 6$ seqvitvr $1 \mid 6$ .
$(1, 3) \in R \wedge (3, 1) \in R, \quad 1 \neq 3$
Eadem paritas nvmeros impares inter se et nvmeros pares inter se refert: paria svnt $9 + 9 = 18$ , qvae dvo membra respectv diagonalis symmetrica efficivnt. Reflexiva, symmetrica et transitiva est, sed non antisymmetrica, qvia $1$ et $3$ refert, qvi diversi svnt.

Relationes aeqvivalentiae

Relatio «eandem paritatem habere» se gerit vt aeqvalitas partialis: nvmeros qvi vna ratione congrvvnt, paritate, identificat, ceteras obliviscitvr. Tres proprietates qvae efficivnt vt sic se gerat nomen accipivnt.

Definitio (relatio aeqvivalentiae). Relatio in $A$ est relatio aeqvivalentiae cvm reflexiva, symmetrica et transitiva est. Tvm scribitvr $a \sim b$ , et dicitvr $a$ aeqvivalens esse ipsi $b$ . Classis ipsivs $a$ est copia elementorvm ipsi $a$ aeqvivalentivm, et qvodqve eorvm repraesentans classis est:

C(a) = \{ x \in A : x \sim a \}

Copia omnivm classivm copia qvotiens appellatvr et $A/{\sim}$ notatvr.

Relationes aeqvivalentiae svnt aeqvalitas, cvivs classes vnvm tantvm elementvm habent; eadem paritas, cvm dvabvs classibvs; idem residvvm in divisione per $3$ habere, cvm tribvs; et in evndem diem hebdomadis incidere, cvm septem, qvod est problema solvtvm 3. Generaliter, si $g$ fvnctio in $A$ definita est, relatio $g(x) = g(y)$ tres proprietates ab aeqvalitate hereditate accipit, et problema solvtvm 5 ostendit omnem aeqvivalentiam hvivs formae esse.

LemmaClasses aeqvivalentiae

Sit $\sim$ relatio aeqvivalentiae in $A$ . Pro omnibvs $a$ et $b$ ex $A$ : qvodqve elementvm ad classem svam pertinet; dvo elementa aeqvivalentia svnt si et solvm si classes eorvm aeqvales svnt; et dvae classes aliqvod elementvm commvne habentes aeqvales svnt. Qvaeqve assertio ex vna trivm proprietatvm aeqvivalentiae obtinetvr, ad elementvm qvodlibet classis adhibita.

Demonstratio

$a \sim a \rightarrow \resaltar{a \in C(a)}$
Per reflexivitatem $a \sim a$ ; per definitionem classis $a$ ad $C(a)$ pertinet, et nvlla classis vacva est.
$x \sim a \wedge a \sim b \rightarrow \resaltar{x \sim b}$
Ponamvs $a \sim b$ et sit $x$ ex $C(a)$ . Per transitivitatem ex $x \sim a$ et $a \sim b$ seqvitvr $x \sim b$ ; ergo $C(a) \subseteq C(b)$ .
$a \sim b \rightarrow \dato{eq}{C(a) = C(b)}$
Per symmetriam etiam $b \sim a$ , et idem argvmentvm praebet $C(b) \subseteq C(a)$ . Per inclvsionem dvplicem classes aeqvales svnt.
$a \in C(a) = C(b) \rightarrow a \sim b$
Vice versa, si $C(a) = C(b)$ , elementvm $a$ , qvod ad $C(a)$ pertinet, ad $C(b)$ pertinet, id est $a \sim b$ .
$x \in C(a) \cap C(b) \rightarrow C(a) = C(b)$
Si $x$ ad $C(a)$ et ad $C(b)$ pertinet, per symmetriam et transitivitatem $a \sim x$ et $x \sim b$ praebent $a \sim b$ , et per ea qvae praecedvnt classes aeqvales svnt.

Classes igitvr copiam in membra dividvnt qvae sibi invicem non svperponvntvr. Hic modvs copiam dividendi definitionem propriam meretvr.

Definitio (partitio). Partitio copiae $A$ est copia svbcopiarvm ipsivs $A$ , qvae membra appellantvr, qvae vacvae non svnt, qvae binae disivnctae svnt et qvarvm vnio est $A$ ; aeqvivalenter, qvodqve elementvm ipsivs $A$ ad vnvm prorsvs membrvm pertinet.

TheoremaAeqvivalentiae et partitiones

Classes relationis aeqvivalentiae in $A$ partitionem ipsivs $A$ efficivnt. Vice versa, si $\Pi$ partitio est ipsivs $A$ , relatio «ad idem membrvm pertinere» est relatio aeqvivalentiae cvivs classes svnt prorsvs membra ipsivs $\Pi$ . Prior assertio est lemma svperivs; altera tres proprietates verificat condicione adhibita vt qvodqve elementvm in vno tantvm membro sit. Figvra relationem «idem residvvm in divisione per $3$ habere» in copia ab $1$ ad $9$ seqvitvr.

Demonstratio

$(\forall a \in A)\,(a \in \resaltar{C(a)})$
Per lemma nvlla classis vacva est et qvodqve elementvm ad classem svam pertinet, ita vt vnio classivm sit $A$ .
$C(a) \neq C(b) \rightarrow C(a) \cap C(b) = \resaltar{\emptyset}$
Per lemma dvae classes diversae nvlla elementa commvnia habent. Ergo classes partitionem efficivnt.
$a \sim b \leftrightarrow (\exists X \in \Pi)(a \in X \wedge b \in X)$
Vice versa, sit $\Pi$ partitio et scribamvs $a \sim b$ cvm $a$ et $b$ in eodem membro svnt. Qvodqve elementvm in aliqvo membro est, ideoqve in eodem membro ac se ipsvm: relatio reflexiva est. Symmetria statim patet, qvia condicio non pendet ex ordine qvo $a$ et $b$ nominantvr.
$b \in X \cap Y \rightarrow X = Y \rightarrow a \sim c$
Transitivitas: si $a$ et $b$ in membro $X$ svnt, et $b$ et $c$ in membro $Y$ , tvm $b$ in $X$ et in $Y$ est; cvm qvodqve elementvm in vno tantvm membro sit, $X = Y$ , et $a$ et $c$ in eodem membro svnt.
$a \in X \rightarrow C(a) = \resaltar{X}$
Deniqve, si $a$ in membro $X$ est, classis ipsivs $a$ constat ex elementis qvae membrvm cvm $a$ commvnicant, qvae svnt elementa ipsivs $X$ : classes svnt membra.

Aeqvivalentiam in $A$ dare et partitionem ipsivs $A$ dare svnt igitvr dvo modi idem dicendi; problema solvtvm 4 hoc vtitvr ad aeqvivalentias nvmerandas. Copia qvotiens est partitio vt copia nova spectata: transevndo ab $A$ ad $A/{\sim}$ , elementa aeqvivalentia in vnvm conflvvnt.

ExemplvmRelatio qvae nvmeros integros constrvet

In copia $\mathbb{N} \times \mathbb{N}$ parivm nvmerorvm natvralivm definitvr $(a, b) \sim (c, d)$ cvm $a + d = b + c$ . Relatio aeqvivalentiae est, vt in lectione de nvmeris integris demonstratvr. Qvosdam repraesentantes classivm ipsorvm $(5, 2)$ , $(1, 1)$ et $(2, 5)$ compvtare, et classes in reticvlo parivm describere.

Demonstratio

$(a, b) \sim (c, d) \leftrightarrow \resaltar{a + d = b + c}$
Par $(a, b)$ svbtractionem nondvm peractam $a - b$ repraesentat, qvae inter nvmeros natvrales fortasse non exsistit; condicio $a + d = b + c$ dicit dvo paria eandem svbtractionem repraesentare nvlla svbtractione scripta.
$C(5, 2) = \{ (4, 1), (5, 2), (6, 3), (7, 4), \ldots \}$
Classis ipsivs $(5, 2)$ paria continet qvae differentiam $3$ describvnt. Exempli gratia $(4, 1)$ , qvia $5 + 1 = 2 + 4$ .
$C(1, 1) = \{ (1, 1), (2, 2), (3, 3), \ldots \}$
Classis ipsivs $(1, 1)$ est classis parivm componentivm aeqvalivm, qvia $1 + b = 1 + a$ postvlat $a = b$ : est diagonalis reticvli.
$C(2, 5) = \{ (1, 4), (2, 5), (3, 6), \ldots \}$
Classis ipsivs $(2, 5)$ differentiam describit qvae nondvm exsistit, eam qvae erit $-3$ .
$\mathbb{Z} = \left( \mathbb{N} \times \mathbb{N} \right) / {\sim}$
Qvaeqve classis est copia parivm rectae diagonali parallelae, et per theorema hae rectae partitionem reticvli efficivnt. Nvmervs integer per definitionem vna ex his classibvs erit: $\mathbb{Z}$ est copia qvotiens.

Eodem modo, in lectione de nvmeris rationalibvs dvae fractiones $(p, q)$ et $(r, s)$ aeqvivalentes svnt cvm $ps = qr$ , et nvmervs rationalis classis est; et in lectione de congrventiis residva modvlo $n$ svnt classes aeqvivalentiae inter nvmeros integros.

Relationes ordinis

Divisibilitas exempli svperioris non symmetrica sed antisymmetrica est: loco elementorvm identificandorvm ea ordinat. Relationes hvivs generis nomen proprivm accipivnt.

Definitio (ordo). Relatio in $A$ est relatio ordinis, sive ordo partialis, cvm reflexiva, antisymmetrica et transitiva est; tvm scribitvr $a \preceq b$ , et dicitvr $a$ praecedere ipsvm $b$ . Ordo est totalis cvm dvo qvaelibet elementa comparabilia svnt, id est cvm pro omnibvs $a$ et $b$ habetvr $a \preceq b$ vel $b \preceq a$ .

Ordines svnt relatio $\leq$ inter nvmeros natvrales, qvae totalis est per trichotomiam in lectione de operationibvs nvmerorvm natvralivm demonstratam; inclvsio, per theorema de proprietatibvs eivs, qvae totalis non est, qvia $\{1\}$ et $\{2\}$ comparabiles non svnt; et divisibilitas inter nvmeros natvrales, cvivs antisymmetria in lectione de divisibilitate demonstratvr, qvae totalis non est, qvia nec $2 \mid 3$ nec $3 \mid 2$ . Ordo finitvs diagrammate Hassiano depingitvr: pvnctvm pro qvoqve elemento, $b$ altivs qvam $a$ cvm $a$ praecedit ipsvm $b$ , et segmentvm cvm inter ambo nvllvm alivd elementvm est; transitivitas cetera segmenta omittere sinit.

Definitio (margines et elementa extrema). Sint $\preceq$ ordo in $A$ et $X$ svbcopia ipsivs $A$ . Margines et elementa extrema ipsivs $X$ sic definivntvr.

Elementvm $c$ ipsivs $A$ est margo inferior ipsivs $X$ si omnia elementa ipsivs $X$ praecedit, et margo svperior si omnia elementa ipsivs $X$ id praecedvnt.
Minimvm ipsivs $X$ est margo inferior ipsivs $X$ qvi ad $X$ pertinet, et maximvm est margo svperior qvi ad $X$ pertinet.
Elementvm $m$ ipsivs $X$ est minimale si nvllvm elementvm ipsivs $X$ ab eo diversvm id praecedit, et maximale si ipsvm nvllvm elementvm ipsivs $X$ a se diversvm praecedit.
Infimvm ipsivs $X$ est maximvm copiae marginvm eivs inferiorvm, et svpremvm est minimvm copiae marginvm eivs svperiorvm, si exsistvnt.

PropositioMinimvm vnicvm est et solvm minimale

Si svbcopia $X$ copiae ordinatae minimvm habet, hoc minimvm vnicvm est, et solvm elementvm minimale ipsivs $X$ est. Si ordo totalis est, omne elementvm minimale ipsivs $X$ minimvm eivs est. Idem de maximo et elementis maximalibvs valet. Vnicitas in antisymmetria nititvr, et vltima assertio in comparabilitate.

Demonstratio

$m \preceq n \wedge n \preceq m \rightarrow \resaltar{m = n}$
Si $m$ et $n$ minima svnt ipsivs $X$ , vtrvmqve ad $X$ pertinet et omnia eivs elementa praecedit; praesertim vtrvmqve altervm praecedit, et per antisymmetriam aeqvalia svnt.
$x \preceq m \wedge m \preceq x \rightarrow x = m$
Minimvm $m$ minimale est: si $x$ ex $X$ praecedit ipsvm $m$ , cvm etiam $m \preceq x$ , antisymmetria praebet $x = m$ .
$m \preceq n \rightarrow m = n$
Si $n$ minimale est, cvm $m$ praecedat ipsvm $n$ et ad $X$ pertineat, definitio minimalis cogit $m = n$ : alia minimalia non svnt.
$(\forall x \in X)\,(\resaltar{m \preceq x})$
Si ordo totalis est et $m$ minimale, pro qvoqve $x$ ex $X$ habetvr $m \preceq x$ vel $x \preceq m$ ; in secvndo casv, cvm minimale sit, $x = m$ . In vtroqve casv $m \preceq x$ , et $m$ minimvm est.

ExemplvmDivisores nvmeri 12 per divisibilitatem ordinati

In copia $A = \{1, 2, 3, 4, 6, 12\}$ divisorvm nvmeri $12$ , per divisibilitatem ordinata, consideratvr svbcopia $X = \{2, 3, 4, 6\}$ . Diagramma Hassianvm depingere et determinare elementa minimalia et maximalia, minimvm, maximvm, margines, infimvm et svpremvm ipsivs $X$ .

Demonstratio

$1 \mid 2 \mid 4 \mid 12, \qquad 1 \mid 3 \mid 6 \mid 12$
In diagrammate $1$ infra est, qvia omnes dividit; svper evm $2$ et $3$ ; svper eos $4$ et $6$ ; svmmo loco $12$ . Ivngvntvr $1$ cvm $2$ et cvm $3$ ; $2$ cvm $4$ et cvm $6$ ; $3$ cvm $6$ ; et $4$ et $6$ cvm $12$ .
$\neg (2 \mid 3), \quad \neg (3 \mid 2)$
Minimalia ipsivs $X$ svnt $2$ et $3$ : nvllvm alivd elementvm ipsivs $X$ ea dividit. Cvm dvo sint, per propositionem $X$ minimvm non habet; ordo totalis non est, qvia $2$ et $3$ comparabiles non svnt.
$\neg (4 \mid 6), \quad \neg (6 \mid 4)$
Maximalia svnt $4$ et $6$ , qvi nvllvm alivd elementvm ipsivs $X$ dividvnt; neqve maximvm est.
$(\forall x \in X)\,(\resaltar{1} \mid x \wedge x \mid \resaltar{12})$
Solvs margo inferior ipsivs $X$ in $A$ est $1$ , qvi ideo infimvm est; solvs margo svperior est $12$ , qvi svpremvm est. Nevter eorvm ad $X$ pertinet.

Infimvm igitvr et svpremvm exsistere possvnt etsi minimvm et maximvm non exsistvnt. Haec differentia nvmeros reales distingvit: in lectione de generibvs nvmerorvm admittitvr, vt axioma completvdinis, omnem copiam non vacvam nvmerorvm realivm svpra circvmscriptam svpremvm habere, qvod nvmeri rationales non explent. Nvmeri natvrales contra principivm bonae ordinationis explent, in lectione de svmmationibvs et indvctione demonstratvm: omnis copia non vacva nvmerorvm natvralivm minimvm habet.

Fvnctiones

Fvnctiones vt relationes

Fvnctio cviqve elemento vnivs copiae vnvm prorsvs elementvm alterivs assignat. Si hoc ita est, fvnctio paribvs determinatvr qvae ex qvoqve elemento et eo qvod ei assignatvr constant, et vt relatio proprietate speciali praedita definiri potest.

Definitio (fvnctio). Fvnctio $f$ ex $A$ in $B$ est relatio ex $A$ in $B$ qvae qvodqve elementvm ipsivs $A$ cvm vno prorsvs elemento ipsivs $B$ refert:

(\forall a \in A)(\exists! b \in B)\,((a, b) \in f)

Hoc vnicvm elementvm imago ipsivs $a$ appellatvr et $f(a)$ scribitvr; scribitvr $f : A \to B$ , et dicitvr $A$ esse dominivm ipsivs $f$ et $B$ eivs codominivm.

Dvae fvnctiones aeqvales svnt cvm idem dominivm, idem codominivm et eandem imaginem in qvoqve elemento habent. Fvnctio identica ipsivs $A$ , qvae $I_A$ notatvr, qvodqve elementvm vbi est relinqvit: est diagonalis ipsivs $A \times A$ , et $I_A(x) = x$ pro omni $x$ ex $A$ .

Definitio (imago et praeimago). Sit $f : A \to B$ . Imago svbcopiae $X$ ipsivs $A$ est copia qvae ex imaginibvs elementorvm eivs constat, et praeimago svbcopiae $Y$ ipsivs $B$ est copia elementorvm ipsivs $A$ qvorvm imago in $Y$ est:

f(X) = \{ f(x) : x \in X \}, \qquad f^{-1}(Y) = \{ x \in A : f(x) \in Y \}

Imago totivs dominii, $f(A)$ , copia imaginvm ipsivs $f$ appellatvr et $\operatorname{Rec}(f)$ notatvr.

Notatio praeimaginis non svpponit $f$ inversam habere: praeimago pro qvalibet fvnctione exsistit.

ExemplvmFvnctio nvmeri divisorvm

Sit $f : \{1, 2, 3, 4, 5, 6\} \to \{1, 2, 3, 4\}$ fvnctio qvae cviqve nvmero mvltitvdinem divisorvm eivs assignat. Valores eivs, copiam imaginvm, praeimaginem ipsivs $\{2\}$ compvtare, et $f(X \cap Y)$ cvm $f(X) \cap f(Y)$ comparare pro $X = \{2, 4\}$ et $Y = \{3, 4\}$ .

Demonstratio

$f(1) = 1, \ f(2) = f(3) = f(5) = 2, \ f(4) = 3, \ f(6) = 4$
Nvmervs $1$ vnvm divisorem habet; $2$ , $3$ et $5$ dvos; $4$ tres habet, $1$ , $2$ et $4$ ; et $6$ qvattvor habet, $1$ , $2$ , $3$ et $6$ .
$\operatorname{Rec}(f) = \{1, 2, 3, 4\}$
Qvodqve elementvm codominii imago alicvivs est: copia imaginvm totvm codominivm est.
$f^{-1}(\{2\}) = \{2, 3, 5\}$
Nvmeri qvi dvos prorsvs divisores habent svnt nvmeri primi dominii.
$f(X \resaltar{\cap} Y) = f(\{4\}) = \{3\}$
Intersectio ipsarvm $X$ et $Y$ est $\{4\}$ , cvivs imago est $\{3\}$ .
$f(X) \resaltar{\cap} f(Y) = \{2, 3\} \neq \{3\}$
Contra, $f(X) = f(Y) = \{2, 3\}$ , qvia $2$ et $3$ eandem imaginem habent. Generaliter sola inclvsio $f(X \cap Y) \subseteq f(X) \cap f(Y)$ valet, qvia $x$ ex $X \cap Y$ testis vtrivsqve imaginis est; aeqvalitas deficit cvm testes diversi svnt, vt hic $2$ et $3$ .

Compositio

Si $f : A \to B$ et $g : B \to C$ , qvodqve $x$ ex $A$ imaginem $f(x)$ in $B$ habet, qvae ipsa imaginem in $C$ habet. Compositio ipsivs $g$ cvm $f$ est fvnctio $g \circ f : A \to C$ qvae primvm $f$ deinde $g$ adhibet:

\left( g \circ f \right)(x) = g(f(x))

Fvnctio est, qvia cviqve $x$ vnvm tantvm $f(x)$ respondet et hvic vnvm tantvm $g(f(x))$ . Ordo scribendi ordini adhibendi contrarivs est: in $g \circ f$ fvnctio dextera prior agit. Compositio commvtativa non est: si $f(n) = 2n$ et $g(n) = n + 1$ in nvmeris natvralibvs, tvm $(g \circ f)(n) = 2n + 1$ , qvi impar est, et $(f \circ g)(n) = 2n + 2$ , qvi par est. Fvnctio identica vtrimqve nevtra est, qvia $f(I_A(x)) = f(x)$ et $I_B(f(x)) = f(x)$ :

f \circ I_A = f, \qquad I_B \circ f = f

TheoremaAssociativitas compositionis

Si $f : A \to B$ , $g : B \to C$ et $h : C \to D$ , fvnctiones $h \circ (g \circ f)$ et $(h \circ g) \circ f$ aeqvales svnt. Ambae ex $A$ in $D$ evnt; satis est verificare eas evndem valorem in qvoqve elemento svmere, definitione compositionis bis adhibita. Figvra fvnctiones vt sagittas inter qvattvor colvmnas repraesentat.

Demonstratio

$\left( h \circ \left( g \circ f \right) \right)(x) = h\left( \resaltar{\left( g \circ f \right)(x)} \right)$
Sit $x$ elementvm qvodlibet ipsivs $A$ . Per definitionem compositionis, ad $h$ et ad $g \circ f$ adhibitam.
$= h\left( \resaltar{g(f(x))} \right)$
Itervm per definitionem, nvnc ad $g \circ f$ adhibitam.
$\left( \left( h \circ g \right) \circ f \right)(x) = \left( h \circ g \right)\left( \resaltar{f(x)} \right)$
Altera via, per definitionem ad $h \circ g$ et ad $f$ adhibitam.
$= \resaltar{h(g(f(x)))}$
Et per definitionem ad $h \circ g$ adhibitam, in elemento $f(x)$ .
$h \circ \left( g \circ f \right) = \left( h \circ g \right) \circ f$
Dvae fvnctiones idem dominivm, idem codominivm et eosdem valores habent: aeqvales svnt. Ideo sine parenthesibvs scribitvr $h \circ g \circ f$ .

Fvnctiones iniectivae, svperiectivae et biiectivae

Definitio. Fvnctio $f : A \to B$ iniectiva est cvm elementa diversa imagines diversas habent, vel, per contrapositionem, cvm aeqvalitas imaginvm aeqvalitatem elementorvm implicat; svperiectiva est cvm omne elementvm ipsivs $B$ imago est alicvivs elementi ipsivs $A$ , id est cvm $\operatorname{Rec}(f) = B$ ; et biiectiva, sive biiectio, est cvm iniectiva et svperiectiva est:

(\forall x, y \in A)\,(f(x) = f(y) \rightarrow x = y), \qquad (\forall b \in B)(\exists x \in A)\,(f(x) = b)

Fvnctio nvmeri divisorvm exempli svperiectiva est et iniectiva non est. Fvnctio $n \mapsto 2n$ ex nvmeris natvralibvs in nvmeros natvrales iniectiva est et svperiectiva non est, qvia $1$ nvllivs nvmeri natvralis dvplvm est. Svccessor lectionis seqventis est, per qvartvm axioma Peani, fvnctio iniectiva ex $\mathbb{N}$ in $\mathbb{N}$ , et per tertivm svperiectiva non est, qvia $1$ nvllivs nvmeri natvralis imago est. Svperiectivitas ex codominio declarato pendet. Biiectio elementa dvarvm copiarvm copvlat nvllo repetito neqve omisso; ideo lectio de combinatoria definit $A$ habere $n$ elementa cvm exsistit biiectio ex $\{1, 2, \ldots, n\}$ in $A$ .

TheoremaCompositio iniectivitatem et svperiectivitatem servat

Sint $f : A \to B$ et $g : B \to C$ . Si $f$ et $g$ iniectivae svnt, $g \circ f$ iniectiva est; si $f$ et $g$ svperiectivae svnt, $g \circ f$ svperiectiva est; et ideo, si ambae biiectivae svnt, $g \circ f$ biiectiva est. Ad iniectivitatem catena retrorsvm percvrritvr, ab $C$ ad $A$ ; ad svperiectivitatem item, sed praeimaginibvs qvaesitis. Figvra tres colvmnas ostendit.

Demonstratio

$g(f(x)) = g(f(y))$
Iniectivitas: sint $x$ et $y$ ex $A$ eandem imaginem per $g \circ f$ habentia.
$\dato{fa}{f(x) = f(y)}$
Cvm $g$ iniectiva sit, elementa $f(x)$ et $f(y)$ , qvae eandem imaginem per $g$ habent, aeqvalia svnt.
$\resaltar{f(x) = f(y)} \rightarrow x = y$
Cvm $f$ iniectiva sit, $x = y$ . Ergo $g \circ f$ iniectiva est.
$\dato{b}{g(b) = c}, \quad \dato{a}{f(a) = b}$
Svperiectivitas: sit $c$ ex $C$ . Cvm $g$ svperiectiva sit, exsistit $b$ ex $B$ cvm $g(b) = c$ ; cvm $f$ svperiectiva sit, exsistit $a$ ex $A$ cvm $f(a) = b$ .
$\left( g \circ f \right)(a) = g(\resaltar{f(a)}) = g(\resaltar{b}) = c$
Hoc $a$ praeimago est ipsivs $c$ per compositionem. Ergo $g \circ f$ svperiectiva est, et si ambae fvnctiones biiectivae svnt, etiam compositio est.

Fvnctio inversa

Fvnctio $g : B \to A$ retexit ipsam $f : A \to B$ cvm, post $f$ adhibita, qvodqve elementvm ad pvnctvm vnde profectvm est redvcit, id est cvm $g \circ f = I_A$ ; et $f$ vicissim retexit ipsam $g$ cvm $f \circ g = I_B$ . Fvnctio qvae ambas aeqvalitates explet inversa ipsivs $f$ appellatvr. Theorema seqvens dicit qvae fvnctiones eam habeant.

TheoremaFvnctio biiectiva est si et solvm si inversam habet, et inversa vnica est

Fvnctio $f : A \to B$ biiectiva est si et solvm si exsistit fvnctio $g : B \to A$ talis vt $g \circ f = I_A$ et $f \circ g = I_B$ . Haec fvnctio $g$ vnica est; fvnctio inversa ipsivs $f$ appellatvr et $f^{-1}$ notatvr. Praeterea $f^{-1}$ biiectiva est et eivs inversa est $f$ . Ad inversam constrvendam paria ipsivs $f$ invertvntvr; ad vnicitatem associativitas compositionis adhibetvr. Figvra biiectionem inter dvas copias qvattvor elementorvm seqvitvr.

Demonstratio

$g = \{ (b, a) : (a, b) \in f \}, \quad \dato{g}{g(b) = a \leftrightarrow f(a) = b}$
Ponamvs $f$ biiectivam esse. Pro qvoqve $b$ ex $B$ exsistit $a$ cvm $f(a) = b$ , qvia $f$ svperiectiva est, et vnvm tantvm, qvia $f$ iniectiva est. Relatio qvae paribvs ipsivs $f$ invertendis obtinetvr ideo fvnctio est ex $B$ in $A$ .
$g(f(a)) = \resaltar{a}, \qquad f(g(b)) = \resaltar{b}$
Per definitionem ipsivs $g$ , adhibere $f$ deinde $g$ qvodqve $a$ reddit, et adhibere $g$ deinde $f$ qvodqve $b$ reddit.
$x = g(f(x)) = g(\resaltar{f(y)}) = y$
Vice versa, ponamvs $g$ exsistere. Si $f(x) = f(y)$ , adhibita $g$ fit $x = y$ : fvnctio $f$ iniectiva est.
$f(\resaltar{g(b)}) = b$
Pro qvoqve $b$ ex $B$ elementvm $g(b)$ praeimago est ipsivs $b$ : fvnctio $f$ svperiectiva est ideoqve biiectiva.
$g = g \circ I_B = g \circ \resaltar{\left( f \circ h \right)} = \resaltar{\left( g \circ f \right)} \circ h = I_A \circ h = h$
Vnicitas: si $g$ et $h$ ambas aeqvalitates explent, fvnctio identica interponitvr et per associativitatem itervm consociatvr.
$f^{-1} \circ f = I_A, \qquad f \circ f^{-1} = I_B$
Dvae aeqvalitates definitionis symmetricae svnt in $f$ et $f^{-1}$ : $f$ retexit ipsam $f^{-1}$ vtroqve sensv. Per id qvod iam demonstratvm est $f^{-1}$ biiectiva est, et eivs inversa est $f$ .

CorollarivmBiiectionem habere est aeqvivalentia inter copias

Pro omnibvs copiis $A$ , $B$ et $C$ : exsistit biiectio ex $A$ in $A$ ; si exsistit biiectio ex $A$ in $B$ , exsistit vna ex $B$ in $A$ ; et si exsistvnt biiectiones ex $A$ in $B$ et ex $B$ in $C$ , exsistit vna ex $A$ in $C$ . Praesertim, si $A$ habet $n$ elementa et exsistit biiectio ex $A$ in $B$ , tvm $B$ habet $n$ elementa. Qvaeqve assertio vnvm ex theorematibvs svperioribvs est.

Demonstratio

$I_A \circ I_A = I_A$
Fvnctio identica biiectio est, qvia sibi ipsi inversa est.
$f : A \to B \rightarrow f^{-1} : B \to A$
Inversa biiectionis biiectio est, per theorema fvnctionis inversae.
$f : A \to B, \ g : B \to C \rightarrow g \circ f : A \to C$
Compositio dvarvm biiectionvm biiectio est, per theorema svperivs.
$f \circ h : \{1, \ldots, n\} \to B$
Si $h$ biiectio est ex $\{1, \ldots, n\}$ in $A$ et $f$ biiectio ex $A$ in $B$ , compositio biiectio est ex $\{1, \ldots, n\}$ in $B$ .

Relatio aeqvivalentiae non appellatvr qvia non exsistit copia omnivm copiarvm in qva definiatvr. Lectio de operationibvs fvnctionvm haec ad fvnctiones reales adhibebit, et ibi delineatio inversae delineationi fvnctionis respectv diagonalis symmetrica erit, pictvra geometrica parivm inversorvm.

Problemata solvta

Problemata a dvabvs exercitationibvs de fvnctionibvs ad tres applicationes aeqvivalentiarvm progredivntvr. Secvndvm mvltiplicatione nvmerorvm natvralivm eivsqve lege cancellationis vtitvr, qvae in lectione de operationibvs nvmerorvm natvralivm demonstratvr; tertivm divisione cvm residvo, qvae in lectione de divisibilitate demonstratvr. Nvllvm ex his eventis ex hac lectione pendet.

Problema solvtvm 1Qvid compositio de factoribvs svis doceat

Sint $f : A \to B$ et $g : B \to C$ . Demonstrare, si $g \circ f$ iniectiva est, tvm $f$ iniectivam esse, et, si $g \circ f$ svperiectiva est, tvm $g$ svperiectivam esse. Exemplo ostendere $g \circ f$ biiectivam esse posse etsi neqve $g$ iniectiva neqve $f$ svperiectiva est.

Solvtio

$f(x) = f(y) \rightarrow \resaltar{g(f(x)) = g(f(y))}$
Sint $x$ et $y$ ex $A$ cvm $f(x) = f(y)$ . Cvm $g$ fvnctio sit, elementis aeqvalibvs imagines aeqvales assignat.
$\left( g \circ f \right)(x) = \left( g \circ f \right)(y) \rightarrow x = y$
Haec aeqvalitas est aeqvalitas imaginvm per $g \circ f$ , qvae iniectiva est: ergo $x = y$ , et $f$ iniectiva est.
$c = g(\resaltar{f(a)}) = g(b)$
Sit $c$ ex $C$ . Cvm $g \circ f$ svperiectiva sit, exsistit $a$ cvm $g(f(a)) = c$ ; elementvm $b = f(a)$ ipsivs $B$ praeimago est ipsivs $c$ per $g$ .
$\left( g \circ f \right)(1) = g(1) = 1$
Ad exemplvm, sint $A = C = \{1\}$ et $B = \{1, 2\}$ , cvm $f(1) = 1$ et $g(1) = g(2) = 1$ . Compositio est fvnctio identica ipsivs $\{1\}$ , qvae biiectiva est.
$g(1) = g(2), \quad 2 \notin \operatorname{Rec}(f)$
Attamen $g$ iniectiva non est, qvia $g(1) = g(2)$ , et $f$ svperiectiva non est, qvia $2$ nvllivs rei imago est. Qvod compositio transmittit est iniectivitas prioris factoris et svperiectivitas posterioris, nec qvicqvam amplivs.

Problema solvtvm 2Tot nvmeri pares qvot natvrales

Sit $P = \{ m \in \mathbb{N} : (\exists k \in \mathbb{N})(m = 2k) \}$ copia nvmerorvm parivm. Biiectionem ex $\mathbb{N}$ in $P$ cvm eivs inversa constrvere, et animadvertere $P$ svbcopiam propriam esse ipsivs $\mathbb{N}$ .

Solvtio

$\dato{f}{f(n) = 2n} \in P$
Dvplicare proponimvs: $f(n) = 2n$ . Fvnctio est ex $\mathbb{N}$ in $P$ , qvia $2n$ par est, teste $k = n$ .
$2n = 2m \rightarrow \resaltar{n = m}$
Iniectivitas: si $2n = 2m$ , per legem cancellationis mvltiplicationis nvmerorvm natvralivm, $n = m$ .
$m = 2k = f(\resaltar{k})$
Svperiectivitas: omnis $m$ ex $P$ formam $2k$ habet cvm $k$ natvrali, ideoqve imago est ipsivs $k$ .
$f^{-1}(m) = \frac{m}{2}, \qquad f^{-1}(f(n)) = \frac{2n}{2} = n$
Per theorema fvnctionis inversae $f$ inversam habet: eam qvae cviqve nvmero pari dimidivm eivs assignat, qvod est nvmervs natvralis $k$ illationis svperioris, per legem cancellationis vnicvs.
$1 \notin P, \qquad P \subseteq \mathbb{N}, \quad P \neq \mathbb{N}$
Attamen $P$ svbcopia propria est ipsivs $\mathbb{N}$ : $1$ par non est, qvia $2k = k + k \geq 1 + 1 = 2$ pro omni nvmero natvrali $k$ .

Hic eventvs intvitioni repvgnat qva pars minor est qvam totvm, qvod iam Galilaevs anno 1638 animadverterat cvm nvmeros natvrales cvm qvadratis eorvm copvlaret. Nvllam copiam finitam in biiectione esse cvm svbcopia sva propria forma est principii locvlorvm, qvod lectio de combinatoria sine demonstratione admittit vna cvm vnicitate nvmeri elementorvm; hoc principio accepto, $\mathbb{N}$ finita non est. Dedekind hanc ipsam proprietatem pro definitione copiae infinitae svmpsit, et lectio de axiomatibvs Peani ostendit $\mathbb{N}$ eam habere.

Problema solvtvm 3Dies hebdomadis

Kalendae Ianvariae anni 2026 in diem Iovis incidervnt. Dies anni 2026 ab $1$ ad $365$ nvmeramvs et dicimvs dvos dies aeqvivalentes esse cvm nvmeri eorvm idem residvvm in divisione per $7$ relinqvvnt. Demonstrare hanc relationem aeqvivalentiae esse, classes eivs describere, et determinare in qvem diem hebdomadis incidat dies qvintvs mensis Octobris anni 2026 et in qvem incidet dies qvintvs mensis Octobris anni 2027.

Solvtio

$n \sim m \leftrightarrow \resaltar{g(n) = g(m)}$
Sit $g(n)$ residvvm divisionis ipsivs $n$ per $7$ , per theorema divisionis cvm residvo vnicvm. Relatio est $g(n) = g(m)$ , et tres proprietates svas ab aeqvalitate hereditate accipit: $g(n) = g(n)$ ; si $g(n) = g(m)$ , tvm $g(m) = g(n)$ ; et si $g(n) = g(m)$ et $g(m) = g(p)$ , tvm $g(n) = g(p)$ .
$C(1) = \{1, 8, 15, \ldots, 365\}, \quad \ldots, \quad C(7) = \{7, 14, \ldots, 364\}$
Residva possibilia svnt $0, 1, \ldots, 6$ , et qvodqve attingitvr, ita vt septem classes sint, colvmnae calendarii septem colvmnarvm. Cvm hebdomas septimo qvoqve die redeat, dvo dies aeqvivalentes in evndem diem hebdomadis incidvnt.
$31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 5 = \dato{n}{278}$
Dies qvintvs mensis Octobris est dies $278$ anni, qvia novem menses priores $273$ dies efficivnt.
$278 = 7 \cdot 39 + \resaltar{5} \rightarrow 278 \sim 5$
Per $7$ dividimvs: residvvm est $5$ , ita vt dies qvintvs mensis Octobris in classe diei $5$ sit, diei qvinti mensis Ianvarii.
$C(278) = C(5)$
Dies $1$ dies Iovis fvit, ideoqve dies $5$ , qvattvor diebvs post, dies Lvnae fvit: dies qvintvs mensis Octobris anni 2026 dies Lvnae est.
$365 = 7 \cdot 52 + \resaltar{1}$
Annvs 2026 $365$ dies habet, et $365 = 7 \cdot 52 + 1$ : eadem dies anni seqventis $365$ diebvs post incidit, id est vno die hebdomadis serivs. Dies qvintvs mensis Octobris anni 2027 dies Martis erit.

Problema solvtvm 4Relationes aeqvivalentiae copiae qvattvor elementorvm

Qvot relationes aeqvivalentiae svnt in copia $\{1, 2, 3, 4\}$ ?

Solvtio

$a \sim b \leftrightarrow (\exists X \in \Pi)(a \in X \wedge b \in X)$
Per theorema de aeqvivalentiis et partitionibvs, qvaeqve aeqvivalentia partitionem svam in classes determinat, et qvaeqve partitio $\Pi$ aeqvivalentiam «in eodem membro esse» determinat, cvivs classes svnt membra; dvae correspondentiae altera alteram retexvnt. Satis est igitvr partitiones nvmerare, qvas secvndvm magnitvdines membrorvm svorvm distribvimvs.
$\{1, 2, 3, 4\}$
Vnvm membrvm qvattvor elementorvm: vna partitio, ea qvae vnam tantvm classem habet.
$\{2, 3, 4\}, \{1\}; \quad \{1, 3, 4\}, \{2\}; \quad \{1, 2, 4\}, \{3\}; \quad \{1, 2, 3\}, \{4\}$
Membrvm trivm et membrvm vnivs: tot qvot modi svnt elementi solitarii eligendi, qvattvor.
$\{1, 2\}, \{3, 4\}; \quad \{1, 3\}, \{2, 4\}; \quad \{1, 4\}, \{2, 3\}$
Dvo membra binorvm: partitio socio ipsivs $1$ determinatvr, qvi esse potest $2$ , $3$ vel $4$ ; tres svnt.
$\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}$
Membrvm dvorvm et dvo membra singvlorvm: partitio pari determinatvr qvod membrvm dvorvm efficit, et sex paria svnt.
$1 + 4 + 3 + 6 + 1 = 15$
Qvattvor membra singvlorvm: vna partitio, ea aeqvalitatis. Qvinqve generibvs additis nvmervs aeqvivalentiarvm obtinetvr.

Nvmeri partitionvm copiae $1$ , $2$ , $3$ , $4$ , $5$ elementorvm svnt $1$ , $2$ , $5$ , $15$ , $52$ ; nvmeri Belliani appellantvr, et problema propositvm 2 qvintvm obtinet.

Problema solvtvm 5Omnis fvnctio classificatio est

Sit $f : A \to B$ fvnctio. Demonstrare relationem $x \sim y$ , per $f(x) = f(y)$ definitam, aeqvivalentiam esse, et $f$ compositionem esse trivm fvnctionvm: svperiectionis $g$ qvae qvodqve elementvm ad classem svam fert, biiectionis $h$ ex copia qvotiente in copiam imaginvm ipsivs $f$ , et iniectionis $J$ qvae qvodqve elementvm copiae imaginvm ad se ipsvm intra $B$ fert. Hoc ad fvnctionem nvmeri divisorvm exempli adhibere.

Solvtio

$C(x) = f^{-1}(\{ f(x) \})$
Relatio $f(x) = f(y)$ aeqvivalentia est, eodem argvmento ac in problemate solvto 3. Classes eivs svnt praeimagines elementorvm copiae imaginvm: classis ipsivs $x$ elementa eandem imaginem habentia colligit. In exemplo svnt $\{1\}$ , $\{2, 3, 5\}$ , $\{4\}$ et $\{6\}$ .
$g : A \to A/{\sim}, \quad g(x) = C(x)$
Fvnctio $g(x) = C(x)$ ex $A$ in $A/{\sim}$ it et svperiectiva est, qvia omnis classis est classis alicvivs elementorvm svorvm.
$C(x) = C(y) \rightarrow \resaltar{f(x) = f(y)}$
Definimvs $h(C(x)) = f(x)$ . Cvm classis mvltos repraesentantes habeat, verificandvm est valorem non pendere ex eo qvi electvs est: si $C(x) = C(y)$ , tvm $x \sim y$ , id est $f(x) = f(y)$ .
$h(C(x)) = h(C(y)) \rightarrow C(x) = C(y)$
Fvnctio $h$ iniectiva est, qvia implicatio svperior invertitvr: si $f(x) = f(y)$ , tvm $x \sim y$ et $C(x) = C(y)$ . Svperiectiva est in copiam imaginvm, qvia qvodqve $f(x)$ est $h(C(x))$ .
$\left( J \circ h \circ g \right)(x) = J(h(C(x))) = f(x)$
Inclvsio $J(b) = b$ copiae imaginvm in $B$ iniectiva est, et compositio $f$ reddit. In exemplo qvattvor classes ad $1$ , $2$ , $3$ et $4$ evnt; fvnctio iniectiva non est qvia classis $\{2, 3, 5\}$ tria elementa habet.

Problema ostendit omnem fvnctionem dominivm svvm classificare et, vice versa, per lemma de classibvs, omnem aeqvivalentiam esse relationem «eandem imaginem habere» per aliqvam fvnctionem, eam qvae qvodqve elementvm ad classem svam fert. Sic ratio censvrarvm discipvlos in classes secvndvm censvram svam dividit, nvmervs cvrsvalis inscriptiones secvndvm regionem svam, et fvnctio residvi nvmeros secvndvm residvvm svvm.

Problemata proposita

Qvodqve problema indicivm habet, qvod aperire expedit nonnisi postqvam id temptatvm est; responsvm finale post indicivm ostenditvr.

Problema propositvm 1Qvando copia e parenthesi extrahi possit

Demonstrare, pro omnibvs copiis $A$ , $B$ et $C$ ,

A \cap \left( B \cup C \right) = \left( A \cap B \right) \cup C \leftrightarrow C \subseteq A

Praeterea exemplvm dare relationis in $\{1, 2, 3\}$ qvae neqve symmetrica neqve antisymmetrica sit.

Indicivm

Ad implicationem dextrorsvm svme $x$ in $C$ : est in secvndo membro, ergo in primo, ergo in $A$ . Ad alteram demonstra inclvsionem dvplicem distingvendo, pro qvoqve $x$ , vtrvm in $B$ an in $C$ sit. Ad relationem ivnge par cvm symmetrico svo et alivd par sine eo.

Responsvm

Si aeqvalitas valet, $C$ in secvndo membro continetvr, qvod primo aeqvale est, in $A$ contento. Si $C \subseteq A$ , elementvm ipsivs $A$ qvod in $B$ vel in $C$ est in $A \cap B$ vel in $C$ est, et vice versa elementvm ipsivs $C$ in $A$ et in $B \cup C$ est. Exemplvm relationis qvae neqve symmetrica neqve antisymmetrica est praebet

\{ (1, 2), (2, 1), (2, 3) \}

Solvtio explicata

Solvtio

$x \in C \rightarrow x \in \left( A \cap B \right) \cup C = \resaltar{A} \cap \left( B \cup C \right) \rightarrow x \in A$
Si aeqvalitas valet et $x$ in $C$ est, tvm $x$ in secvndo membro est, qvod $C$ continet; per aeqvalitatem in primo est, et praesertim in $A$ . Ergo $C \subseteq A$ .
$x \in A \wedge \left( x \in B \vee x \in C \right) \rightarrow \resaltar{x \in A \cap B} \vee \resaltar{x \in C}$
Vice versa, ponamvs $C \subseteq A$ et sit $x$ ex primo membro: in $A$ est, et praeterea in $B$ vel in $C$ . In priore casv est in $A \cap B$ ; in altero, in $C$ . In vtroqve, in secvndo membro.
$x \in C \rightarrow x \in \resaltar{A} \cap \left( B \cup C \right)$
Sit nvnc $x$ ex secvndo membro. Si in $A \cap B$ est, in $A$ et in $B \cup C$ est; si in $C$ est, in $B \cup C$ est et, per hypothesim $C \subseteq A$ , etiam in $A$ .
$C \subseteq A \rightarrow A \cap \left( B \cup C \right) = \left( A \cap B \right) \cup C$
Per inclvsionem dvplicem dvo membra aeqvalia svnt cvm $C \subseteq A$ ; cvm prima illatione aeqvivalentia demonstrata est.
$(2, 3) \in R, \ (3, 2) \notin R; \qquad (1, 2), (2, 1) \in R$
In relatione proposita par $(2, 3)$ adest et symmetricvm eivs $(3, 2)$ non adest, ita vt symmetrica non sit; paria $(1, 2)$ et $(2, 1)$ adsvnt, cvm $1 \neq 2$ , ita vt antisymmetrica non sit.

Problema propositvm 2Partitiones qvinqve elementorvm

Relationes aeqvivalentiae copiae $\{1, 2, 3, 4, 5\}$ nvmerare, et qvot earvm dvas prorsvs classes habeant.

Indicivm

Partitiones secvndvm magnitvdines membrorvm svorvm distribve, vt in problemate solvto 4: septem genera svnt, a $5$ ad $1 + 1 + 1 + 1 + 1$ . Ad membrvm trivm et membrvm dvorvm satis est membrvm dvorvm eligere; ad dvo membra binorvm et vnvm singvlorvm, primvm solitarivm elige.

Responsvm

Per genera, $1 + 5 + 10 + 10 + 15 + 10 + 1$ ; eae qvae dvas classes habent svnt genervm $4 + 1$ et $3 + 2$ , qvae simvl $5 + 10 = 15$ efficivnt:

1 + 5 + 10 + 10 + 15 + 10 + 1 = 52

Problema propositvm 3Inversa compositionis

Sint $f : A \to B$ et $g : B \to C$ biiectivae. Demonstrare inversam ipsivs $g \circ f$ esse $f^{-1} \circ g^{-1}$ , hoc ordine. Hoc ad vestes indvendas adhibere: si $f$ est tibialia indvere et $g$ calceos indvere, qvo ordine operatio retexitvr?

Indicivm

Per vnicitatem inversae satis est verificare $f^{-1} \circ g^{-1}$ cvm $g \circ f$ compositam, vtroqve ordine, fvnctionem identicam praebere; per associativitatem itervm consocia vt $g^{-1}$ cvm $g$ et $f$ cvm $f^{-1}$ concvrrant.

Responsvm

Per associativitatem factores medii se tollvnt; per vnicitatem inversae $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ . Ad vestes exvendas primvm calcei, deinde tibialia exvvntvr.

\left( f^{-1} \circ g^{-1} \right) \circ \left( g \circ f \right) = f^{-1} \circ \left( g^{-1} \circ g \right) \circ f = f^{-1} \circ f = I_A

Solvtio explicata

Solvtio

$f^{-1} \circ g^{-1} : C \to A$
Compositio dvarvm biiectionvm biiectiva est ideoqve vnam tantvm inversam habet. Satis est verificare $f^{-1} \circ g^{-1}$ , qvae ex $C$ in $A$ it, eam vtroqve ordine retexere.
$\left( f^{-1} \circ g^{-1} \right) \circ \left( g \circ f \right) = f^{-1} \circ \resaltar{\left( g^{-1} \circ g \right)} \circ f = f^{-1} \circ f = I_A$
Primvs ordo: per associativitatem compositionis $g^{-1}$ cvm $g$ concvrrit et eorvm compositio est fvnctio identica ipsivs $B$ , qvae ipsam $f$ non mvtat.
$\left( g \circ f \right) \circ \left( f^{-1} \circ g^{-1} \right) = g \circ \resaltar{\left( f \circ f^{-1} \right)} \circ g^{-1} = g \circ g^{-1} = I_C$
Secvndvs ordo: eodem modo $f$ cvm $f^{-1}$ concvrrit.
$\left( g \circ f \right)^{-1} = f^{-1} \circ g^{-1}$
Per vnicitatem inversae $f^{-1} \circ g^{-1}$ est inversa ipsivs $g \circ f$ : factores ordine contrario invertvntvr.
$\left( g \circ f \right)^{-1} = \resaltar{f^{-1}} \circ \resaltar{g^{-1}}$
Vestes indvere est $g \circ f$ : primvm tibialia, deinde calcei. Id retexere est primvm $g^{-1}$ adhibere, calceos exvere, deinde $f^{-1}$ , tibialia exvere.

Problema propositvm 4Tot paria nvmerorvm natvralivm qvot nvmeri natvrales

Demonstrare fvnctionem $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ definitam per

f(a, b) = 2^{a - 1} \left( 2b - 1 \right)

biiectionem esse.

Indicivm

Omnis nvmervs natvralis $n$ vno tantvm modo scribitvr vt potentia ipsivs $2$ nvmero impari mvltiplicata: divide per $2$ qvamdiv nvmervs par est; processvs finitvr qvia qvotientes decrescvnt. Ad vnicitatem, si $2^{j} u = 2^{k} v$ cvm $u$ et $v$ imparibvs et $j < k$ , tolle $2^{j}$ et paritatem dvorvm membrorvm compara.

Responsvm

Fvnctio biiectiva est: exponens ipsivs $2$ in $n$ praebet $a$ , et pars impar $2b - 1$ praebet $b$ . Primi valores svnt

f(1, 1) = 1, \quad f(2, 1) = 2, \quad f(1, 2) = 3, \quad f(3, 1) = 4, \quad f(1, 3) = 5, \quad f(2, 2) = 6

Solvtio explicata

Solvtio

$f(a, b) = 2^{a - 1} \left( 2b - 1 \right)$
Fvnctio bene definita est: $a - 1$ est $0$ vel nvmervs natvralis, et in priore casv $2^0 = 1$ per conventionem potentiae exponentis nihili, qvam lectio de operationibvs primis ivstificat; praeterea $2b - 1$ impar est. In tabvla versvs $a$ continet prodvcta ipsivs $2^{a - 1}$ per nvmeros impares.
$n = 2^{j} u = 2^{j} \left( 2b - 1 \right) = f(\resaltar{j + 1}, \resaltar{b})$
Svperiectivitas: dato $n$ , per $2$ dividitvr qvamdiv nvmervs par est. Qvotientes decrescvnt, et seqventia stricte decrescens nvmerorvm natvralivm infinita esse non potest (est principivm bonae ordinationis, in lectione de svmmationibvs et indvctione demonstratvm, qvod hic anticipatvr): processvs in nvmero impari $u$ post $j$ divisiones finitvr, et $u = 2b - 1$ cvm $b = \frac{u + 1}{2}$ .
$2^{j} u = 2^{k} v, \ j < k \rightarrow u = \resaltar{2^{k - j}} v$
Iniectivitas: ponamvs $f(a, b) = f(a', b')$ , id est $2^{j} u = 2^{k} v$ cvm $j = a - 1$ , $k = a' - 1$ , $u = 2b - 1$ et $v = 2b' - 1$ , vbi $u$ et $v$ impares svnt. Si esset $j < k$ , svblato $2^{j}$ maneret nvmervs impar pari aeqvalis, qvod fieri non potest; eodem modo si $k < j$ , et per trichotomiam $j = k$ , id est $a = a'$ .
$2^{j} u = 2^{j} v \rightarrow u = v \rightarrow 2b = 2b', \qquad a = a', \ b = b'$
Cvm $j = k$ , lex cancellationis mvltiplicationis praebet $u = v$ ; inde seqvitvr $2b = u + 1 = v + 1 = 2b'$ , et lex cancellationis mvltiplicationis praebet $b = b'$ : dvo paria in vtraqve coordinata congrvvnt.
$f(3, 2) = 2^{2} \cdot 3 = 12$
Fvnctio igitvr biiectio est ex $\mathbb{N} \times \mathbb{N}$ in $\mathbb{N}$ . Exempli gratia, $12 = 2^2 \cdot 3$ est imago paris $(3, 2)$ .

Problema propositvm 5Ordo cvrsvvm

Discipvla sex cvrsvs, $a$ , $b$ , $c$ , $d$ , $e$ et $f$ , disponit, qvos singvlos alivm post alivm freqventabit. Cvrsvs $a$ praevivs est cvrsibvs $b$ et $c$ ; cvrsvs $b$ et $c$ praevii svnt cvrsvi $d$ ; et $e$ praevivs est cvrsvi $f$ . Si $x \preceq y$ scribitvr cvm $x = y$ vel $x$ ante $y$ freqventandvs est, directe vel indirecte, demonstrare $\preceq$ ordinem partialem esse, elementa eivs minimalia et maximalia determinare, et nvmerare modos sex cvrsvs ordinandi cvrsibvs praeviis servatis.

Indicivm

Ordinatio valida est ordo totalis qvi $\preceq$ continet. Cvrsvs $a$ , $b$ , $c$ et $d$ dvobvs tantvm ordinibvs freqventari possvnt, provt $b$ vel $c$ prior venit; deinde $e$ et $f$ , hoc ordine, inter ceteros qvattvor interponendi svnt: elige qvos dvos ex sex locis occvpent.

Responsvm

Minimalia svnt $a$ et $e$ ; maximalia, $d$ et $f$ ; neqve minimvm neqve maximvm est. Svnt $15$ modi loca ipsorvm $e$ et $f$ inter sex eligendi, ideoqve

2 \cdot 15 = 30

Solvtio explicata

Solvtio

$x \preceq y \wedge y \preceq z \rightarrow \resaltar{x \preceq z}$
Relatio per definitionem reflexiva est, qvia prior alternativa definitionis, $x = y$ , valet cvm $y$ est ipse $x$ . Transitiva est: si $x$ ante $y$ venit et $y$ ante $z$ , directe vel indirecte, tvm $x$ ante $z$ venit.
$x \preceq y \wedge y \preceq x \rightarrow x = y$
Antisymmetrica est: si esset $x \preceq y$ et $y \preceq x$ cvm $x \neq y$ , cvrsvs praevii circvlvm efficerent, et nevter dvorvm cvrsvvm primvs freqventari posset. In figvra sagittae cvrsvvm praeviorvm semper deorsvm tendvnt, et nvlli circvli svnt.
$\{ a, e \}, \qquad \{ d, f \}$
Minimalia svnt cvrsvs sine cvrsibvs praeviis, $a$ et $e$ ; maximalia, ii qvi nvlli cvrsvi praevii svnt, $d$ et $f$ . Cvm $a$ et $e$ comparabiles non sint, neqve $d$ et $f$ , neqve minimvm neqve maximvm est.
$(a, b, c, d), \qquad (a, c, b, d)$
Cvrsvs $a$ , $b$ , $c$ et $d$ dvos tantvm ordines admittvnt: $a$ primvm, $d$ vltimvm, et $b$ et $c$ vtrovis ordine inter se.
$2 \cdot \resaltar{15} = 30$
Restat vt $e$ et $f$ , hoc ordine, interponantvr: satis est dvo loca eligere qvae inter sex occvpant, et $5 + 4 + 3 + 2 + 1 = 15$ modi svnt, secvndvm locvm ipsivs $e$ . Qvisqve ex dvobvs ordinibvs cvm qvalibet ex his electionibvs ivngitvr, et $30$ ordinationes svnt.