Sets

\( % cbs-katex.sty % \newcommand{\STYLE}[2]{\htmlClass{cbs-#1}{#2}} \newcommand{\DECL}[3]{\htmlId{#1:#2}{#3}} \newcommand{\REF}[3]{\href{###1:#2}{#3}} \newcommand{\HYPER}[5]{\href{#1/#2/index.html###3:#4}{#5}} % \SHADE{MATH} can be defined to produce a shaded background to highlight % inline MATH in running text: \newcommand{\SHADE}[1]{#1} % \KEY{TEXT}, \STRING{TEXT}, \ATOM{TEXT}, \LEX{TEXT} can be used in math mode: \newcommand{\KEY}[1]{\textsf{\textit{\STYLE{Key}{#1}}}} \newcommand{\STRING}[1]{\textsf{``\texttt{#1}''}} \newcommand{\ATOM}[1]{\textsf{`\texttt{#1}'}} \newcommand{\LEX}[1]{\textsf{\STYLE{Key}{`}\texttt{#1}\STYLE{Key}{'}}} % The following commands produce ASCII characters that are treated specially by LaTeX: \newcommand{\HASH}{\char`\#} \newcommand{\DOLLAR}{\char`\$} \newcommand{\PERCENT}{\char`\%} \newcommand{\AMPERSAND}{\char`\&} \newcommand{\APOSTROPHE}{\char`\'} \newcommand{\BACKSLASH}{\char`\\} \newcommand{\CARET}{\char`\^} \newcommand{\UNDERSCORE}{\char`\_} \newcommand{\GRAVE}{\char`\`} \newcommand{\LEFTBRACE}{\char`\{} \newcommand{\RIGHTBRACE}{\char`\}} \newcommand{\TILDE}{\textasciitilde} % {\char`\~} % \NAME{name} highlights the name; % \NAMEDECL{name} declares Name.name as the target of links to name; % \NAMEREF{name} links name to the target Name.name in the current file; % \NAMEHYPER{url}{file}{name} links name to Name.name at url/file/file.pdf. % Similarly for \VAR{partvariable}, \SYN{syntaxname}, \SEM{semanticsName}, % and \SECT{sectionnumber} % The kerns in \SUB and \VAR avoid overlaps with primes: \newcommand{\SUB}[1]{_{\kern-2mu\STYLE{PartVariable}{\textsf{#1}}}} % PLAIN \newcommand{\VAR}[1]{\STYLE{PartVariable}{\textsf{\textit{#1}\kern2mu}}} \newcommand{\NAME}[1]{\STYLE{Name}{\textsf{#1}}} \newcommand{\SYN}[1]{\STYLE{SyntaxName}{\textsf{#1}}} \newcommand{\SEM}[1]{\STYLE{SemanticsName}{\textsf{#1}}} \newcommand{\SECT}[1]{\STYLE{SectionNumber}{\textsf{#1}}} % DECL \newcommand{\VARDECL}[1]{\DECL{PartVariable}{#1}{\VAR{#1}}} \newcommand{\NAMEDECL}[1]{\DECL{Name}{#1}{\NAME{#1}}} \newcommand{\SYNDECL}[1]{\DECL{SyntaxName}{#1}{\SYN{#1}}} \newcommand{\SEMDECL}[1]{\DECL{SemanticsName}{#1}{\SEM{#1}}} \newcommand{\SECTDECL}[1]{\DECL{SectionNumber}{#1}{\textsf{#1}}} % REF \newcommand{\VARREF}[1]{\REF{PartVariable}{#1}{\VAR{#1}}} \newcommand{\NAMEREF}[1]{\REF{Name}{#1}{\NAME{#1}}} \newcommand{\SYNREF}[1]{\REF{SyntaxName}{#1}{\SYN{#1}}} \newcommand{\SEMREF}[1]{\REF{SemanticsName}{#1}{\SEM{#1}}} \newcommand{\SECTREF}[1]{\REF{SectionNumber}{#1}{\SECT{#1}}} % HYPER \newcommand{\VARHYPER}[3]{\HYPER{#1}{#2}{PartVariable}{#3}{\VAR{#3}}} \newcommand{\NAMEHYPER}[3]{\HYPER{#1}{#2}{Name}{#3}{\NAME{#3}}} \newcommand{\SYNHYPER}[3]{\HYPER{#1}{#2}{SyntaxName}{#3}{\SYN{#3}}} \newcommand{\SEMHYPER}[3]{\HYPER{#1}{#2}{SemanticsName}{#3}{\SEM{#3}}} \newcommand{\SECTHYPER}[3]{\HYPER{#1}{#2}{SectionNumber}{#3}{\SECT{#3}}} % \LEFTPHRASE MATH \RIGHTPHRASE produces [[ MATH ]] with proper brackets: \newcommand{\LEFTPHRASE}{\llbracket} \newcommand{\RIGHTPHRASE}{\rrbracket} % \LEFTGROUP MATH \RIGHTGROUP produces ( MATH ) where the parentheses are % highlighted the same as keywords: \newcommand{\LEFTGROUP}{\STYLE{Key}{(}} \newcommand{\RIGHTGROUP}{\STYLE{Key}{)}} % MATH\PLUS produces a superscript + % MATH\STAR produces a superscript * % MATH\QUERY produces a superscript ? \newcommand{\PLUS}{{}^{\texttt{+}}} \newcommand{\STAR}{{}^{\texttt{*}}} \newcommand{\QUERY}{{}^{\texttt{?}}} % \RULE{& PREMISE \\ & ...}{& FORMULA ... \\ & ...} produces an inference rule % with separately aligned premises and conclusion % PREMISE % ... % ----------- % FORMULA ... % ... \newcommand{\RULE}[2] {\frac{\begin{aligned}#1\end{aligned}}{\begin{aligned}#2\end{aligned}}} % \AXIOM{& FORMULA ... \\ & ...} produces an aligned formula % % FORMULA ... % ... \newcommand{\AXIOM}[1]{\begin{aligned}#1\end{aligned}} % \TO TYPE produces => TYPE \newcommand{\TO}{\mathop{\Rightarrow}} % TERM \TRANS TERM produces TERM ---> TERM \newcommand{\TRANS}{\longrightarrow} % TERM \xrightarrow{LABEL} TERM puts the label above the long arrow % \)

Funcons-beta : Sets.cbs | PLAIN | PDF

\[\begin{align*} [ \ \KEY{Type} \quad & \NAMEREF{sets} \\ \KEY{Funcon} \quad & \NAMEREF{set} \\ \KEY{Funcon} \quad & \NAMEREF{set-elements} \\ \KEY{Funcon} \quad & \NAMEREF{is-in-set} \\ \KEY{Funcon} \quad & \NAMEREF{is-subset} \\ \KEY{Funcon} \quad & \NAMEREF{set-insert} \\ \KEY{Funcon} \quad & \NAMEREF{set-unite} \\ \KEY{Funcon} \quad & \NAMEREF{set-intersect} \\ \KEY{Funcon} \quad & \NAMEREF{set-difference} \\ \KEY{Funcon} \quad & \NAMEREF{set-size} \\ \KEY{Funcon} \quad & \NAMEREF{some-element} \\ \KEY{Funcon} \quad & \NAMEREF{element-not-in} \ ] \end{align*}\] \[\begin{align*} \KEY{Meta-variables} \quad & \VAR{GT} <: \NAMEHYPER{../..}{Value-Types}{ground-values} \end{align*}\] \[\begin{align*} \KEY{Built-in Type} \quad & \NAMEDECL{sets}( \VAR{GT} ) \end{align*}\]

$\SHADE{\NAMEREF{sets} ( \VAR{GT} )}$ is the type of possibly-empty finite sets $\SHADE{\{ \VAR{V}\SUB{1}, \cdots, \VAR{V}\SUB{n} \}}$ where $\SHADE{\VAR{V}\SUB{1} : \VAR{GT}}$, …, $\SHADE{\VAR{V}\SUB{n} : \VAR{GT}}$.

\[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set}( \_ : ( \VAR{GT} )\STAR) : \TO \NAMEREF{sets} ( \VAR{GT} ) \end{align*}\]

The notation $\SHADE{\{ \VAR{V}\SUB{1}, \cdots, \VAR{V}\SUB{n} \}}$ for $\SHADE{\NAMEREF{set} ( \VAR{V}\SUB{1}, \cdots, \VAR{V}\SUB{n} )}$ is built-in.

\[\begin{align*} \KEY{Assert} \quad & \{ \VAR{V}\STAR : ( \VAR{GT} )\STAR \} == \NAMEREF{set} ( \VAR{V}\STAR ) \end{align*}\]

Note that $\SHADE{\NAMEREF{set} ( \cdots )}$ is not a constructor operation. The order and duplicates of argument values are ignored (e.g., $\SHADE{\{ 1, 2, 1 \}}$ denotes the same set as $\SHADE{\{ 1, 2 \}}$ and $\SHADE{\{ 2, 1 \}}$).

\[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set-elements}( \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO ( \VAR{GT} )\STAR \end{align*}\]

For each set $\SHADE{\VAR{S}}$, the sequence of values $\SHADE{\VAR{V}\STAR}$ returned by $\SHADE{\NAMEREF{set-elements} ( \VAR{S} )}$ contains each element of $\SHADE{\VAR{S}}$ just once. The order of the values in $\SHADE{\VAR{V}\STAR}$ is unspecified, and may vary between sets (e.g., $\SHADE{\NAMEREF{set-elements} \ \{ 1, 2 \}}$ could be $\SHADE{( 1, 2 )}$ and $\SHADE{\NAMEREF{set-elements} \ \{ 1, 2, 3 \}}$ could be $\SHADE{( 3, 2, 1 )}$).

\[\begin{align*} \KEY{Assert} \quad & \NAMEREF{set} ( \NAMEREF{set-elements} ( \VAR{S} ) ) == \VAR{S} \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{is-in-set}( \_ : \VAR{GT}, \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO \NAMEHYPER{../../Primitive}{Booleans}{booleans} \end{align*}\]

$\SHADE{\NAMEREF{is-in-set} ( \VAR{GV}, \VAR{S} )}$ tests whether $\SHADE{\VAR{GV}}$ is in the set $\SHADE{\VAR{S}}$.

\[\begin{align*} \KEY{Assert} \quad & \NAMEREF{is-in-set} ( \VAR{GV} : \VAR{GT}, \{ \ \} ) == \NAMEHYPER{../../Primitive}{Booleans}{false} \\ \KEY{Assert} \quad & \NAMEREF{is-in-set} ( \VAR{GV} : \VAR{GT}, \{ \VAR{GV} \} : \NAMEREF{sets} ( \VAR{GT} ) ) == \NAMEHYPER{../../Primitive}{Booleans}{true} \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{is-subset}( \_ : \NAMEREF{sets} ( \VAR{GT} ), \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO \NAMEHYPER{../../Primitive}{Booleans}{booleans} \end{align*}\]

$\SHADE{\NAMEREF{is-subset} ( \VAR{S}\SUB{1}, \VAR{S}\SUB{2} )}$ tests whether $\SHADE{\VAR{S}\SUB{1}}$ is a subset of $\SHADE{\VAR{S}\SUB{2}}$.

\[\begin{align*} \KEY{Assert} \quad & \NAMEREF{is-subset} ( \{ \ \}, \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ) ) == \NAMEHYPER{../../Primitive}{Booleans}{true} \\ \KEY{Assert} \quad & \NAMEREF{is-subset} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S} ) == \NAMEHYPER{../../Primitive}{Booleans}{true} \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set-insert}( \_ : \VAR{GT}, \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO \NAMEREF{sets} ( \VAR{GT} ) \end{align*}\]

$\SHADE{\NAMEREF{set-insert} ( \VAR{GV}, \VAR{S} )}$ returns the set union of $\SHADE{\{ \VAR{GV} \}}$ and $\SHADE{\VAR{S}}$.

\[\begin{align*} \KEY{Assert} \quad & \NAMEREF{is-in-set} ( \VAR{GV} : \VAR{GT}, \NAMEREF{set-insert} ( \VAR{GV} : \VAR{GT}, \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ) ) ) == \NAMEHYPER{../../Primitive}{Booleans}{true} \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set-unite}( \_ : ( \NAMEREF{sets} ( \VAR{GT} ) )\STAR) : \TO \NAMEREF{sets} ( \VAR{GT} ) \end{align*}\]

$\SHADE{\NAMEREF{set-unite} ( \cdots )}$ unites a sequence of sets.

\[\begin{align*} \KEY{Assert} \quad & \NAMEREF{set-unite} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S} ) == \VAR{S} \\ \KEY{Assert} \quad & \NAMEREF{set-unite} ( \VAR{S}\SUB{1} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{2} : \NAMEREF{sets} ( \VAR{GT} ) ) == \NAMEREF{set-unite} ( \VAR{S}\SUB{2}, \VAR{S}\SUB{1} ) \\ \KEY{Assert} \quad & \NAMEREF{set-unite} ( \VAR{S}\SUB{1} : \NAMEREF{sets} ( \VAR{GT} ), \NAMEREF{set-unite} ( \VAR{S}\SUB{2} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{3} : \NAMEREF{sets} ( \VAR{GT} ) ) ) \\&\quad == \NAMEREF{set-unite} ( \NAMEREF{set-unite} ( \VAR{S}\SUB{1}, \VAR{S}\SUB{2} ), \VAR{S}\SUB{3} ) \\ \KEY{Assert} \quad & \NAMEREF{set-unite} ( \VAR{S}\SUB{1} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{2} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{3} : \NAMEREF{sets} ( \VAR{GT} ) ) \\&\quad == \NAMEREF{set-unite} ( \VAR{S}\SUB{1}, \NAMEREF{set-unite} ( \VAR{S}\SUB{2}, \VAR{S}\SUB{3} ) ) \\ \KEY{Assert} \quad & \NAMEREF{set-unite} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ) ) == \VAR{S} \\ \KEY{Assert} \quad & \NAMEREF{set-unite} ( \ ) == \{ \ \} \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set-intersect}( \_ : ( \NAMEREF{sets} ( \VAR{GT} ) )\PLUS) : \TO \NAMEREF{sets} ( \VAR{GT} ) \end{align*}\]

$\SHADE{\NAMEREF{set-intersect} ( \VAR{GT}, \cdots )}$ intersects a non-empty sequence of sets.

\[\begin{align*} \KEY{Assert} \quad & \NAMEREF{set-intersect} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S} ) == \VAR{S} \\ \KEY{Assert} \quad & \NAMEREF{set-intersect} ( \VAR{S}\SUB{1} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{2} : \NAMEREF{sets} ( \VAR{GT} ) ) == \NAMEREF{set-intersect} ( \VAR{S}\SUB{2}, \VAR{S}\SUB{1} ) \\ \KEY{Assert} \quad & \NAMEREF{set-intersect} ( \VAR{S}\SUB{1} : \NAMEREF{sets} ( \VAR{GT} ), \NAMEREF{set-intersect} ( \VAR{S}\SUB{2} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{3} : \NAMEREF{sets} ( \VAR{GT} ) ) ) \\&\quad == \NAMEREF{set-intersect} ( \NAMEREF{set-intersect} ( \VAR{S}\SUB{1}, \VAR{S}\SUB{2} ), \VAR{S}\SUB{3} ) \\ \KEY{Assert} \quad & \NAMEREF{set-intersect} ( \VAR{S}\SUB{1} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{2} : \NAMEREF{sets} ( \VAR{GT} ), \VAR{S}\SUB{3} : \NAMEREF{sets} ( \VAR{GT} ) ) \\&\quad == \NAMEREF{set-intersect} ( \VAR{S}\SUB{1}, \NAMEREF{set-intersect} ( \VAR{S}\SUB{2}, \VAR{S}\SUB{3} ) ) \\ \KEY{Assert} \quad & \NAMEREF{set-intersect} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ) ) == \VAR{S} \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set-difference}( \_ : \NAMEREF{sets} ( \VAR{GT} ), \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO \NAMEREF{sets} ( \VAR{GT} ) \end{align*}\]

$\SHADE{\NAMEREF{set-difference} ( \VAR{S}\SUB{1}, \VAR{S}\SUB{2} )}$ returns the set containing those elements of $\SHADE{\VAR{S}\SUB{1}}$ that are not in $\SHADE{\VAR{S}\SUB{2}}$.

\[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{set-size}( \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO \NAMEHYPER{../../Primitive}{Integers}{natural-numbers} \end{align*}\] \[\begin{align*} \KEY{Assert} \quad & \NAMEREF{set-size} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ) ) == \NAMEHYPER{../.}{Sequences}{length} ( \NAMEREF{set-elements} ( \VAR{S} ) ) \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{some-element}( \_ : \NAMEREF{sets} ( \VAR{GT} )) : \TO \VAR{GT}\QUERY \\ \KEY{Assert} \quad & \NAMEREF{some-element} ( \VAR{S} : \NAMEREF{sets} ( \VAR{GT} ) ) == \NAMEHYPER{../.}{Sequences}{index} ( 1, \NAMEREF{set-elements} ( \VAR{S} ) ) \\ \KEY{Assert} \quad & \NAMEREF{some-element} \ \{ \ \} == ( \ ) \end{align*}\] \[\begin{align*} \KEY{Built-in Funcon} \quad & \NAMEDECL{element-not-in}( \VAR{GT} : \NAMEHYPER{../..}{Value-Types}{types}, \_ : \NAMEREF{set} ( \VAR{GT} )) : \TO \VAR{GT}\QUERY \end{align*}\]

$\SHADE{\NAMEREF{element-not-in} ( \VAR{GT}, \VAR{S} )}$ gives an element of the type $\SHADE{\VAR{GT}}$ not in the set $\SHADE{\VAR{S}}$, or $\SHADE{( \ )}$ when $\SHADE{\VAR{S}}$ is empty. When the set of elements of $\SHADE{\VAR{GT}}$ is infinite, $\SHADE{\NAMEREF{element-not-in} ( \VAR{GT}, \VAR{S} )}$ never gives $\SHADE{( \ )}$.

From the PLanCompS Project

CBS-beta issues…

Suggest an improvement…

← ↑ →