(*header{*Header Chapter Title Test*}*) (*section{*The Axiom of Extension*}*) (*--"\<^bold>I\<^bold>S\<^bold>A\<^bold>R \<^bold>(Theory name, imports, and begin.\<^bold>)"*) theory sTs01 imports Complex_Main "i" begin --"\<^bold>[\<^bold>\\<^bold>]" subsection{*Test of inline, equation, multline, eqnarray, label, ref, cite*} --"\<^isub>'I start off with the bibliography citations \\<^isub>`seGol.59\<^isub>`\ and \\<^isub>`seJec, loBil\<^isub>`\. Next is an index \<^isub>\entry\<^isub>\ on the word \entry\, and an index entry where \\<^isub>\markup\!entry\\<^isub>\\ is sub-indexed by using the option \<^isub>*!entry\<^isub>* in the \<^isub>*\index\<^isub>* command. Footnotes? What I really want to say can only be said below. \\<^isub>*Some people could be annoyed by all of this.\<^isub>*\ I now go on to those very important inline equations and equation environments, so please consider the difficulty of the inline equation \<^isub>`x\<^isup>1+\1.2\=1\<^isub>`, and now the equation \<^isub>\\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2),\<^isub>\ \aaaa60a\ along with the very ugly \<^isub>*multline\<^isub>* environment, .\<^isub>\(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)) \ P x \ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4)),\<^isub>\. \aaaa60b\ at least when I stick that middle line in there. The \<^isub>*eqnarray\<^isub>* environment with 3 columns specified by \<^isub>*[rcl]\<^isub>* is frequently used: \<^isub>\a \<^isub>\=\<^isub>\ b \<^isub>\=\<^isub>\ c \<^isub>\=\<^isub>\ d.\<^isub>\ Having to tweak LaTeX raises its ugly head, so I replace Equation \aaaa60b\ with a two column \<^isub>*eqnarray\<^isub>*, and change the default column alignment from \<^isub>*[rcl]\<^isub>* to \<^isub>*[rl]\<^isub>*. I do that with my equation array environment prefix \<^isub>*\rl\\<^isub>*. The \<^isub>*\rl\\<^isub>* is a prefix instead of a suffix, because the suffix position is taken up by the optional reference label. \rl\ \<^isub>\(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2))\<^isub>\\ P x \<^isub>\\ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4))\<^isub>\.\<^isub>\ I could have used the three column default, and left one column empty, but this is for demonstration. Here, I ask the question, \Are what I've been calling equations really equations?\ If we consider that the HOL \ operator is merely notation for \<^isub>`=\<^isub>`, then I suppose they are equations, but as a matter of style, I would rather use \Formula\, and I have set it up to where \Formula\ is a synonym for \Equation\ when used with \<^isub>*\label\<^isub>* and \<^isub>*\eqref\<^isub>*. After experimenting, I decided I can get rid of the \<^isub>*multline\<^isub>* environment. The environment \<^isub>*eqnarray\<^isub>*, from the \<^isub>*mathenv\<^isub>* package, replaces the standard \<^isub>*eqnarray\<^isub>* and it is a very versatile equation environment which can be used in place of many other environments. Here's the \<^isub>*multline\<^isub>* environment: .\<^isub>\(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)) \ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4)).\<^isub>\. \lkr23j\ And here's the same equation using the \<^isub>*eqnarray\<^isub>* environment, set for one right justified column: \r\ \<^isub>\(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)) \ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4)).\<^isub>\ \lkr23k\ Personally, I think Formula \lkr23k\ is formatted better than Formula \lkr23j\. And there are others ways to format Formula \lkr23j\ with \<^isub>*eqnarray\<^isub>*, like \<^isub>\(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2)\<^isub>\\\<^isub>\(q\<^isub>1 = q\<^isub>2)) \ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4)\<^isub>\\\<^isub>\(q\<^isub>3 = q\<^isub>4)),\<^isub>\ or \<^isub>\(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2))\<^isub>\\\<^isub>\ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4)\<^isub>\\\<^isub>\(q\<^isub>3 = q\<^isub>4)),\<^isub>\ This is why LaTeX can be a bad thing. I can spend way too much time tweaking the formatting of equations." subsection{*The primitive set type and membership predicate*} --"\<^isub>'ZF sets is a first-order language which requires an infinite set of variables, and it generally goes unsaid in the formalization of a first-order language that the variables provided are of a single type. However, in HOL there are a multitude of variable types, and additionally, we are allowed to define a new type of variable so we can have a new variable type that exists in its own domain. For ZF sets, I define the primitive variable type \<^isub>*sT\<^isub>*, where the non-ASCII notation for \<^isub>*sT\<^isub>* is \\<^isub>\. The subscripted character for \\<^isub>\ is the Greek letter iota." --"\<^bold>T\<^bold>Y\<^bold>P\<^bold>E \<^bold>(The primitive set type \<^isub>*sT\<^isub>*: everything is a set.\<^bold>)" typedecl sT ("\\<^isub>\") --"\<^bold>[\<^bold>\\<^bold>]" --"\<^isub>'ZF sets is specified to have one predicate, which is membership. The ASCII and non-ASCII notation for membership are \<^isub>*inS\<^isub>* and \\<^isub>\, along with negation of membership, which is notated by \<^isub>*niS\<^isub>* and \\<^isub>\." --"\<^bold>O\<^bold>P\<^bold>E\<^bold>R\<^bold>A\<^bold>T\<^bold>O\<^bold>R \<^bold>(Membership predicate \<^isub>*inS\<^isub>*: axiomatized by subsequent axioms.\<^bold>)" consts inS :: "\\<^isub>\ \ \\<^isub>\ \ bool" (infixl "inS" 55) notation inS (infixl "\\<^isub>\" 55) abbreviation niS :: "\\<^isub>\ \ \\<^isub>\ \ bool" (infixl "niS" 55) where "x niS y == \(x \\<^isub>\ y)" notation niS (infixl "\\<^isub>\" 55) --"\<^bold>[\<^bold>\\<^bold>]" subsection{*Axiomatizing the two forms of the Axiom of Extension*} --"\<^isub>'The standard Axiom of Extension is the formula \<^isub>\\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2).\<^isub>\ The question is whether in Isabelle/HOL, this standard formula is equivalent to the free variable form \<^isub>\(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2),\<^isub>\ where \<^isub>`q\<^isub>1\<^isub>` and \<^isub>`q\<^isub>2\<^isub>`, because they are not in the scope of any quantifier, are free variables. Naively, the following counterexample seems to indicate that they are not equivalent." --"\<^bold>C\<^bold>O\<^bold>U\<^bold>N\<^bold>T\<^bold>E\<^bold>R\<^bold>X \<^bold>(A counterexample is found for the naive equivalence.\<^bold>)" theorem "(\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)) \ ((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4))" --"nitpick[sat_solver=SAT4J,timeout=60,verbose,user_axioms]" --"Nitpick found a counterexample for card \\<^isub>\ = 2: Free variables: (q\<^isub>3\\\<^isub>\) = s1 (q\<^isub>4\\\<^isub>\) = s2" oops --"\<^bold>[\<^bold>\\<^bold>]" --"\<^isub>'The problem is that the prover engine implicitly quantifies all free variables in the statement of a theorem, so the formula in the above counterexample is not the equivalence that we need to prove or disprove. This quantification is done at the outermost level with universal quantifiers. For example, the formula \<^isub>\(\q\<^isub>1.\q\<^isub>2.\<^isub>\\<^isub>\(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)) \\<^isub>\\<^isub>\((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4))\<^isub>\ can be considered to be equivalent to the quantified formula \<^isub>\\q\<^isub>3.\q\<^isub>4.(\q\<^isub>1.\q\<^isub>2.\<^isub>\\<^isub>\(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)) \\<^isub>\\<^isub>\((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \(q\<^isub>3 = q\<^isub>4)).\<^isub>\ I say \considered\ because the quantification is actually being done at the meta-logic level. To see that free variables are quantified by the meta-logic quantifier \, we can look at the output of \<^isub>*thm\<^isub>* in the following example." --"\<^bold>E\<^bold>X\<^bold>A\<^bold>M\<^bold>P\<^bold>L\<^bold>E \<^bold>(Free variables are quantified at the meta-logic level.\<^bold>)\lkzv08a\" theorem free\<^isub>'variable\<^isub>'conjecture: "(\x\'a. P x) \ (P x)" sorry theorem And\<^isub>'quantified\<^isub>'conjecture: "\x.(\x\'a. P x) \ (P x)" sorry thm free\<^isub>'variable\<^isub>'conjecture And\<^isub>'quantified\<^isub>'conjecture --"thm output for both: (\(x\?'a). ?P\(?'a \ bool) x) = (?P (?x\?'a))." theorem forall\<^isub>'quantified\<^isub>'conjecture: "\x.(\x\'a. P x) \ (P x)" sorry thm forall\<^isub>'quantified\<^isub>'conjecture --"thm output: \(x\?'a). (\(x\?'a). ?P\(?'a \ bool) x) = (?P x)." --"\<^bold>[\<^bold>\\<^bold>]" --"\<^isub>'If we were to prove the first two conjectures in the above example, then the resulting theorems would be the same, as shown by the output of \<^isub>*thm\<^isub>*. (Example \lkzv08a\ also shows how free variables and \ quantified variables are tied together by means of schematic variables.) As shown by Example \lkzv08a\, free variables are quantified by \, and so I use the fact that because free variable Formula \lkzv39a\, shown here, \<^isub>\(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2),\<^isub>\ \lkzv39a\ is equivalent to Formula \lkzv39b\, \<^isub>\\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2),\<^isub>\ \lkzv39b\ then it is equivalent to this fully quantified Formula \lkzv39c\, \<^isub>\\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2).\<^isub>\ \lkzv39c\ This is the desired equivalence, that is, that the standard form of the Axiom of Extension is equivalent to the free variable form. To prove this, because \ is a meta-logic operator, we must resort to meta-logic, which I now do in the proof of Theorem \lkBh38a\." --"\<^bold>T\<^bold>H\<^bold>E\<^bold>O\<^bold>R\<^bold>E\<^bold>M \<^bold>(Standard and free variable Axiom of Extension equivalence.\<^bold>)\lkBh38a\" theorem extension\<^isub>'equivalence: "(Trueprop (\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2))) \ (\q\<^isub>3.\q\<^isub>4.((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4)))" --"\<^bold>[\<^bold>\\<^bold>]" --"\<^bold>P\<^bold>R\<^bold>O\<^bold>O\<^bold>F\lkBg41a\" proof assume "\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)" then show "\q\<^isub>3.\q\<^isub>4.(\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4)" by simp next assume "\q\<^isub>3.\q\<^isub>4.((\x. x \\<^isub>\ q\<^isub>3 \ x \\<^isub>\ q\<^isub>4) \ (q\<^isub>3 = q\<^isub>4))" then show "\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)" by simp qed --"\<^bold>[\<^bold>\\<^bold>]" --"\<^isub>'The use of \<^isub>*simp\<^isub>* in Proof \lkBg41a\ \\<^isub>`pipSte121029\<^isub>`\ shows that the proof of Theorem \lkBh38a\ is trivial, which is not surprising, since we would expect meta-logic \ and the HOL operator \ to both produce the same result. But though the proof is trivial, the theorem is not unimportant, since Formula \lkzv39a\ will be stated as an axiom, and when it comes to extending HOL with axioms, due diligence should be exercised, although what is \due diligence\ to one may be \belaboring the point\ to another. Of note is that Theorem \lkBh38a\ has been resorted to out of necessity, and it is tempting to also want to formally prove that Formula \lkzv39a\ is equivalent to Formula \lkzv39b\, but we would end up in the same situation, that because there are free variables in Formula \lkzv39a\, those variables would get quantified by \ if we tried to state, in a single formula, that Formula \lkzv39a\ and Formula \lkzv39b\ are equivalent. (In a single Isar hypothesis, there may be a way to state that two formulas are equivalent without using \, \, or \<^isub>`=\<^isub>`, but if there is, I am not aware of it.) Now, because it has been shown that the two forms of the Axiom of Extension are equivalent, then we can axiomatize either form and get the other. However, rather than just axiomatize one of the formulas, I axiomatize both. The \<^isub>*Nu\<^isub>* form of \<^isub>*Ax\<^isub>'x\<^isub>* axiom will be used, whenever possible, for theorems with no free variables. The \<^isub>*Nf\<^isub>* form will be used for theorems which contain free variables. This allows the possibility of separating the axioms and theorems with free variables from the axioms and theorems which contain no free variables." --"\<^bold>A\<^bold>X\<^bold>I\<^bold>O\<^bold>M \<^bold>(The Axiom of Extension: set equality.\<^bold>)\lkBh07a\" axiomatization where Ax\<^isub>'x\<^isup>N\<^isup>u: "\q\<^isub>1.\q\<^isub>2.(\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)" and Ax\<^isub>'x\<^isup>N\<^isup>f: " (\x. x \\<^isub>\ q\<^isub>1 \ x \\<^isub>\ q\<^isub>2) \ (q\<^isub>1 = q\<^isub>2)" --"\<^bold>[\<^bold>\\<^bold>]" section{*Rough LaTeX markup notes and documentation*} --"\<^isub>'My rough notes and documentation on how I'm marking things up. They're commented out and don't show up in the PDF. There's no fool proof method behind my selection of what character to use to create a markup delimiter. I think a little, and then I start using a character until I think of something better or find out why a certain character is not going to work." subsection{* Guidelines *} (* GUIDELINES FOR CHOOSING SUBSCRIPTED CHARACTERS FOR CREATING MARKUP DELIMITERS 0) With four characters and one type of delimiter, such as \...\, by using the characters subscripted either on the inside or outside, you can create 8 different delimiters. 1) Don't use subscripting or super scripting on two different characters that will look the same after subscripted. For example, a subscripted period looks about the same as a period: \<^isub>. and . 2) Don't subscript both an ASCII character and \ that will look the same. For example, subscripted ' and look about the same: \<^isub>' and \<^isub>\ 3) Preferably, use the following four subscripted and superscripted characters to create delimiters, since, after being subscripted they are fairly well centered, discrete, and recognizable (recognizable if we know that a subscripted or superscripted character used in a delimiter has to be one of these): * \<^isub>* subscript asterisk \<^isub>*example\<^isub>* \<^isub>*\example\\<^isub>* ' \<^isub>' subscript tick \<^isub>'example\<^isub>' ` \<^isub>` subscript reverse tick \<^isub>`example\<^isub>` ^ \<^isub>^ subscript caret \<^isub>^example\<^isub>^ 4) Other subscripted and superscripted characters that are fairly recognizable: , \<^isub>, subscript comma \<^isub>,example\<^isub>, \<^isub>,\example\\<^isub>, : \<^isub>: subscript colon \<^isub>:example\<^isub>: + \<^isub>+ subscript plus \<^isub>+example\<^isub>+ x \<^isub>x subscript x \<^isub>xexample\<^isub>x , \<^isup>, superscript comma \<^isup>,example\<^isup>, + \<^isup>+ superscript plus \<^isup>+example\<^isup>+ x \<^isup>x superscript x \<^isup>xexample\<^isup>x 5) Non-subscripted characters to create delimiters that are somewhat discrete: . period .example. .\example\. , comma ,example, 6) Subscripted \<...> commands WILL IT BE SUBSCRIPTED IN EQUATIONS? \<^isub>\ \<^isub>\ stileturn, turnstile \<^isub>\ \<^isub>\ lhd, rhd \<^isub>\ \<^isub>\ unlhd, unrhd \<^isub>\ \<^isub>\ \<^isub>\ \<^isub>\ lless, ggreater \<^isub>\ \<^isub>\ lesssim, greatersim \<^isub>\ \<^isub>\ lessapprox, greaterapprox \<^isub>\ \<^isub>\ box \<^isub>\ \<^isub>\ circ \<^isub>\ \<^isub>\ oplus \<^isub>\ \<^isub>\ ominus \<^isub>\ \<^isub>\ oslash \<^isub>\ \<^isub>\ otimes \<^isub>\ \<^isub>\ Oplus \<^isub>\ \<^isub>\ Odot \<^isub>\ \<^isub>\ Otimes \<^isub>\ \<^isub>\ infinity \<^isub>\ \<^isub>\ bar \<^isub>\ \<^isub>\ plusminus \<^isub>\ \<^isub>\ minusplus \<^isub>\ \<^isub>\ bullet \<^isub>\ \<^isub>\ prec, succ \<^isub>\ \<^isub>\ lfloor, rfloor Probably, as greatest integer \<^isub>\ \<^isub>\ lceil, rceil Probably, as least integer *) subsection{* Text and text formatting *} (* WHAT IT IS THE MARKUP EXAMPLE text{*...*} --"<^isub>'text" --"\<^isub>'text" double quotes text \quoted text\ italic <^isub>^text^<^isub> \<^isub>^a\<^isub>^ \textt <^isub>*text*<^isub> \<^isub>*text\<^isub>* *) subsection{* Equations *} (* \ensuremath{math} <^isub>`math<^isub>` \begin{eqnarray}[c] <^isub>equation<^isub> \begin{eqnarray}[rcl] <^isub>equation<^isub> a) "&" will be substituted for <^isub> b) "\\" will be inserted at newlines. *) subsection{* cite, index, footnote ref, label *} (* \cite \\<^isub>`seGol.59, seJec, loBil.20\<^isub>`\ \index \<^isub>\anRud \59\\<^isub>\ \footnote \\<^isub>*footnote\<^isub>*\ \ref Reference_type \abcd59a\ a) "Reference_type" must exactly match a word which corresponds to a command for which a \label can be assigned, which are: Chapter Section Equation \label \ymdhMMs\ a) Chars: a-z A-Z period (I could make it any characters \label will accept) b) Append reference labels on an as needed basis. c) Example equ.: \equation\ \ymdhMMs\ d) Example sec: section{ * a title * } --"\ymdhMMs\" e) Abbreviations: y year a-z means 1 to 26 m month a-l means 1 to 12 d day a-z-A-E means 1 to 31 h hour a-w means 1 to 23, 0 means the zero hour MM minutes 0-59 minutes s seconds a-l means 1 to 12, so s = floor(second/5) When making notes on a textbook, it means [page.pagePart.characterRef]. a=1 b=2 c=3 d=4 e=5 f=6 g=7 h=8 i=9 j=10 k=11 l=12 m=13 n=14 o=15 p=16 q=17 r=18 s=19 t=20 u=21 v=22 w=23 x=24 y=25 z=26 A=27 B=28 C=29 D=30 E=31 *) --"\<^bold>I\<^bold>S\<^bold>A\<^bold>R \<^bold>(Theory end.\<^bold>)" end --"\<^bold>[\<^bold>\\<^bold>]"