Gödelization of a Pathology Database.

NEXT PAGE.
RETURN TO TABLE OF CONTENTS.
G. William Moore, MD, PhD [1,2,3],
Lawrence A. Brown, MD [1,2],
Robert E. Miller, MD [3].

From: Pathology and Laboratory Medicine Service (113), Baltimore VA Maryland Health Care System [1], Baltimore, MD.
Department of Pathology, University of Maryland School of Medicine [2], Baltimore, MD.
Department of Pathology, The Johns Hopkins Medical Institutions [3], Baltimore, MD.

Background. U. S. Federal regulations have become stricter regarding the transmission and publication of individually identifiable medical information. Some de-identification methods employed by major institutional medical dataholders are ineffective when another public information source re-identifies the patient with complementary data. This report proposes a mathematical model for patient re-identification by inference, based upon Gödelization, a formalism for mathematical logic.

Design. The data model is a flat database, where each row is a single patient-record and each column is a single, binary field. A Gödel quotient is a product of prime numbers, raised to power¹ if the field corresponding to a particular primary number is true; power^-1 if the field is false; or power ⁰ if the field is missingvalue. Inferences are obtained by multiplying Gödel quotients.

Results. It is proved that Gödel multiplication obtains all and only true statements for observed data and absolute inferences. Weaker inferences, based upon missing values, are consistent if they conform to a medical ontology, ordered in layers of increasing uncertainty.

Conclusion. A major flaw in current de-identification models is their failure to prevent patient re-identification by inference. Dataholders in the future may be held responsible for filtering de-identified data through available medical ontologies, in order to prevent re-identification.

2. INTRODUCTION.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. U. S. Federal regulations have become stricter regarding the transmission and publication of individually identifiable medical information, including pathology databases for research purposes (1,2,3).

      2. Two standards for concealing a patient's identity that qualify for expedited approval by an Institutional Review Board (IRB) are ANONYMIZATION (breaking all linkages to the patient's exact identifiers) and DE-IDENTIFICATION (making secure linkages to the patient's identifiers) (4).

      3. Sweeney has shown that several popular methods for de-identification, employed by major institutional medical dataholders, are ineffective because patients can be re-identified from information in other publicly available databases (5,6,7).

      4. In principle, NO public information source should suffice to re-identify a patient, either DIRECTLY OR BY INFERENCE.

      5. This report proposes a mathematical model for pathology inferences, based upon GödELIZATION, a fundamental formalism for mathematical logic (8,9,10,11), as a method for predicting inferential breakins into a pathology database.

      6. Patient data and inferential relationships are organized as a MEDICAL ONTOLOGY (12,13,14,15,16), into LAYERS OF UNCERTAINTY (17,18,19,20,21,2,23,24,25,26,27,28).

3. DATABASE STRUCTURE.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. Sweeney has introduced a de-identification model, called DATAFLY (7), consisting of a FLAT (rectangular) database, in which EACH ROW is a SINGLE RECORD (patient); and EACH COLUMN is a SINGLE FIELD (feature). As shown in Appendix A, essentially all pathology data, including text diagnoses, can be expressed as binary fields. Binary fields are not computationally efficient, but they make the mathematical argument more transparent for didactic purposes, and reflect the underlying yes/no structure of decision-making processes in medical diagnosis and prognosis.

      2. Pathology fields in our model may assume values TRUE, FALSE, or MISSINGVALUE, where it is understood that every missingvalue could, in principle, always be true or false. All statements in which a true or false response is not always possible are DISALLOWED. These include statements like: "you have stopped beating your spouse, true or false," such as might be asked by hostile journalists (see Appendix A).

      3. The following are hypothetical binary data on ten patient-records, named ABNER, BILL, CHARLIE, DAVID, EDWARD, FRANK, GEORGE, HARRY, IKE, and JOHN, where T=true, F=false, and MV=missingvalue. It is convenient to employ abbreviations, as follows (29,30): ___________________________________________________________________________ FIELD => | AGE | AGE | PSA>4 | URINARY | BIOPSY PROVEN | |RECORD | >30 YRS | >60 YRS | mEq/dL | COMPLAINT | PROSTATE CANCER | V | | | | | | ___________________________________________________________________________ ABBREV | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | ___________________________________________________________________________ ABNER | F | F | MV | F | MV | *F ___________________________________________________________________________ BILL | F | F | F | F | MV | *F ___________________________________________________________________________ CHARLIE | MV | F | MV | F | MV | *MV ___________________________________________________________________________ DAVID | T | F | MV | T | MV | *MV ___________________________________________________________________________ EDWARD | T | F | F | T | MV | *F ___________________________________________________________________________ FRANK | T | F | T | T | MV | *T ___________________________________________________________________________ GEORGE | MV | T | MV | F | MV | *MV ___________________________________________________________________________ HARRY | T | T | MV | T | MV | *T ___________________________________________________________________________ IKE | T | T | F | T | MV | *F ___________________________________________________________________________ JOHN | T | T | T | T | MV | *T ___________________________________________________________________________

In the final column, the asterisk-value is the inferred status of of the PROCA field, i.e., *T=inferred-true and *F=inferred-false. The inference calculations are shown in Appendix D.

      4. In principle, if the inferred value for a field represented a highly patient-specific result, then the patient could be re-identified. For example, it might be possible to INFER that a particular patient-record belongs to a 6'2" blond-haired Baltimore VA Medical Center pathologist, and that this pathologist has a socially undesirable disease. By additional inferences, the patient could be re-identified.

      5. We say that OBSERVED DATA for an individual patient are at LAYER ZERO, L₀. Thus:

ABNER L₀ = {NOT-AGE30, NOT-AGE60, NOT-URCOM} = {2^-1, 3^-1, 7^-1}
BILL L₀ = {NOT-AGE30, NOT-AGE60, NOT-PSAG4, NOT-URCOM} = {2^-1, 3^-1, 5^-1, 7^-1}
CHARLIE L₀ = {AGE60, NOT-URCOM} = {3¹, 7^-1}
DAVID L₀ = {AGE30, NOT-AGE60, URCOM} = {2¹, 3^-1, 7¹}
EDWARD L₀ = {AGE30, NOT-AGE60, PSAG4, URCOM} = {2¹, 3^-1, 5¹, 7¹}
FRANK L₀ = {AGE30, NOT-AGE60, PSAG4, URCOM} = {2¹, 3^-1, 5¹, 7¹}
GEORGE L₀ = {AGE60, NOT-URCOM} = {3¹, 7^-1}
HARRY L₀ = {AGE30, AGE60, URCOM} = {2¹, 3¹, 7¹}
IKE L₀ = {AGE30, AGE60, NOT-PSAG4, URCOM} = {2¹, 3¹, 5^-1, 7¹}
JOHN L₀ = {AGE30, AGE60, PSAG4, URCOM} = {2¹, 3¹, 5¹, 7¹}

6. For a review of SET THEORY NOTATION (31,32,33), see Appendix B.

4. CLASSICAL GÖDELIZATION.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. GÖDELIZATION, GÖDEL ENUMERATION, or GÖDEL PRODUCT, is a formalism for representing all possible mathematical phrases, statements, conjectures, proofs, etc., as unique whole numbers. The method was introduced by GÖDEL in 1931 (8), and serves as the basis for Turing (theoretical) computers and von Neumann (non-parallel) computers. Von Neumann, an early supporter of Gödel, designed the first functioning computer (ENIAC) at Princeton in the 1940s. Most personal computers in use today are von Neumann computers.

      2. The original purpose of Gödelization was to reduce all statements in mathematics to numerical form (arithmetic), in order to prove META-THEOREMS about statements in mathematics, just as one would prove ordinary theorems about numbers using number theory. Gödel used this enumeration method to prove that NOT EVERY TRUE STATEMENT IN MATHEMATICS IS PROVABLE.

      3. A PRIME NUMBER is a whole number greater than one, divisible without remainder only by itself and one (34,35,36,37). For example, the first few prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 57, 59, 61, 67, 71,....

Prime numbers form a natural ordering: the first prime number is always 2, the second prime number is always 3,.... the last prime number given above is: N=71, which is the mth (=21st) prime number. The fixed ordering of prime numbers can be used to keep track of the order of words in a mathematical statement, or the order of fields in a pathology database.

4. In CLASSICAL GÖDELIZATION, the basic concept-names of mathematics (e.g., "for every", "there exists", "a unique", "X", "Y", "NOT", "AND", "OR", etc.) are arbitrarily assigned whole-number labels, as for example:
__________________________ | MATHEMATICAL | NUMERIC | | CONCEPT | LABEL | |__________________________| | FOR EVERY | 1 | |__________________________| | THERE EXISTS | 2 | |__________________________| | A UNIQUE | 3 | |__________________________| | X | 4 | |__________________________| | Y | 5 | |__________________________| | NOT | 6 | |__________________________| | AND | 7 | |__________________________| | OR | 8 | |__________________________| | ( | 9 | |__________________________| | ) | 10 | |__________________________|

Then, a mathematical phrase such as "for every X there exists a unique Y...." would be Gödelized as:

2^{for every} × 3^X × 5^{there exists} × 7^{a unique} × 11^Y = 2¹ × 3⁴ × 5² × 7³ × 11⁵
= 223,723,996,650.

5. In a theorem known to EUCLID, every whole number can be uniquely reduced (FACTORED) down to its component primes and powers (34,35). In this example, 223,723,996,650 can always be uniquely factored obtain its prime-number components, namely:

223,723,996,650 = 2¹ × 3⁴ × 5² × 7³ × 11⁵

The lookup table can, in turn, be used to reconstitute the original mathematical phrase:

2^{for every} × 3^X × 5^{there exists} × 7^{a unique} × 11^Y

This powerful property of prime number multiplication is used in mathematical arguments, but does not lend itself immediately to practical applications, because it involves arithmetic on huge numbers, and because factoring such numbers, while easy in principle, is computationally intense (so-called NP-complete and beyond (5,36,37).

5. GÖDEL QUOTIENTS.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. We introduce the concept of GÖDEL QUOTIENTS for discussing a flat (rectangular) pathology database with binary fields. These fields (columns) in the pathology database can be enumerated as consecutive prime numbers (N=11, m=5):

__________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________| | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|

      2. The observed values for a particular patient are initially represented as powers of single prime numbers in a Gödel quotient, where: TRUE=1, FALSE=-1, MISSINGVALUE=0. Thus, for example, 2¹ means that the patient is greater than 30 years old; and 2^-1 means that the patient is at most 30 years old.

      3. Then, for example:

__________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________| | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________| | ABNER | F | F | MV | F | MV | |__________________________________________________|

ABNER has the following Gödel quotientset as observed (Layer 0)data: ABNER L₀ = {2^-1, 3^-1, 7^-1}. That is, Abner is at most 30 years old; Abner is at most 60 years old (a redundant statement); and Abner has no urinary complaints.

      4. Similarly: __________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________| | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________| | JOHN | T | T | T | T | MV | |__________________________________________________|
JOHN has the following Gödel quotientset as observed data: JOHN L₀ = {2¹, 3¹, 5¹, 7¹}. That is, John is greater than 30 years old; John is greater than 60 years old; John has PSA greater than 4; and John has urinary complaints.

      5. A Gödel quotient consisting of a SINGLE PRIME FACTOR initially represents an observed truth about a patient, such as age, PSA value, physical complaints, laboratory tests, etc. A Gödel quotient consisting of a PRODUCT OF MULTIPLE PRIME FACTORS represents those factors in INCLUSIVE-OR RELATION to one another (vide infra). Observed data belong to LAYER ZERO, L₀. Inclusive-or relations belong to LAYER ONE, L₁. One may combine Gödel quotients in order to discover additional true statements about the patient. Observed data belong to LAYER ZERO, L₀. Inferences belong to progressive layers of uncertainty: L₁, L₂, L₃, L₄,.... In the worst case, a publicly posted ontology might served to re-identify a patient.

      6. In classical FIRST ORDER PROPOSITIONAL LOGIC, inferences are obtained by classical methods, especially, MODUS PONENS. In modus ponens, if A is an observed truth, and A IMPLIES B, then B is an inferred truth.

      7. In the Gödel quotient method, inferences are made by FLAT-MULTIPLICATION. Layer-zero Gödel quotients are combined with higher-layer Gödel quotients, and placed through a computer algorithm driven by FLAT-MULTIPLICATION (vide infra). This flat-multiplication mirrors the processes of FIRST ORDER PROPOSITIONAL LOGIC, a method for inferring additional truths from observed data. Observed data belong to LAYER ZERO, L₀. Inferences belong to progressive layers of uncertainty: L₁, L₂, L₃, L₄,....

6. INFERENCES IN CLASSICAL LOGIC.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. Classical FIRST ORDER PROPOSITIONAL LOGIC is a method of reasoning based upon certainties (17,18) The usual operators of classical logic include: NOT, AND, IOR (inclusive-or), XOR (exclusive-or), IMPLIES (if..then), etc. The weakness of classical logic is its inability to handle uncertainties efficiently, first formalized by Lukasiewicz (founder of "Polish logic"(25)).

      2. For example, one can INFER AGE30 from AGE60. We write: AGE60 => AGE30. That is, if the patient is greater than 60 years old, then the patient is greater than 30 years old.

      3. The contrapositive, which is equivalently true, is: NOT-AGE30 => NOT-AGE60. That is, if the patient is not greater than 30 years old, then the patient is not greater than 60 years old.

      4. Another useful equivalence is: NOT-AGE60 IOR AGE30. That is, the patient is either not greater than 60 years old, or the patient is greater than 30 years old (or both). In this report, the Gödel quotient method exploits this IOR RELATION. A product of prime factors in a Gödel quotient corresponds to the different statements in the IOR relation to one another. For example, "2^-1 3^-1" is equivalent to NOT-AGE60 IOR AGE30.

      5. All inference models in logic appeal to a MODEL OF TRUTH (23). One popular model of truth is a TRUTH TABLE, T, which contains every possible combination of every variable in a completely-described record. Then, one must demonstrate that a particular computing algorithm returns answers that are consistent with the model of truth.

      6. In the present model, each TRUTH TABLE ELEMENT, tC T, is either true or false for each prime factor, in a Gödel quotient (IOR relation). The IOR relation has the powerful property that, for every statement B, if statement A is true for the patient, then statement A-IOR-B is true for the patient. We say that A SUPPORTS A-IOR-B, because if A is true, then A-IOR-B is true. In the example, the truth table for five fields has 32 = 2⁵ possible truth table elements, as follows: #1. 2^-1 3^-1 5^-1 7^-1 11^-1 #2. 2^-1 3^-1 5^-1 7^-1 11¹ #3. 2^-1 3^-1 5^-1 7¹ 11^-1 #4. 2^-1 3^-1 5^-1 7¹ 11¹ #5. 2^-1 3^-1 5¹ 7^-1 11^-1 #6. 2^-1 3^-1 5¹ 7^-1 11¹ ........ #32. 2¹ 3¹ 5¹ 7¹ 11¹
For example:

Truth-table-element-#1 is: NOT-2 IOR NOT-3 IOR NOT-5 IOR NOT-7 IOR NOT-11.
Truth-table-element-#2 is: NOT-2 IOR NOT-3 IOR NOT-5 IOR NOT-7 IOR 11.
Truth-table-element-#3 is: NOT-2 IOR NOT-3 IOR NOT-5 IOR 7 IOR NOT-11, etc.

      7. An initial set of Gödel quotients, Q, consists of USER-SUPPLIED TRUTHS in layers L₀, L₁, L₂, L₃, L₄,.... Then there is a larger set of Gödel quotients that are DEEMED TRUE FOR Q, denoted ðQ; and a set of Gödel quotients that are COMPUTED FOR Q, denoted ¢Q. In this report, we demonstrate that ðQ = ¢Q. That is, DEEMED TRUTH and TRUTH COMPUTED BY ALGORITHM should generate the same set. The reason for having a computer algorithm separate from the truth-model itself is that the truth model typically is mathemically clean and didactically transparent, but requires intense computational effort to solve. By contrast, a computer algorithm typically lends itself to shortcuts and heuristics. In the present algorithm, Step 2 may essentially be dispensed with in the actual calculations, which substantially lessens the computation-cycle and storage consumption.

      8. The set of Gödel quotients that are DEEMED TRUE FOR Q, denoted ðQ, is the set of every Gödel quotient, r, where for every truth table element that r supports, there exists a user-supplied truth that also supports that truth table element. That is, for every truth table element, tC T, such that r « t, there exists a qC Q, such that q « t.

      9. The algorithm computes inferences in four steps, as follows:

Step 1. All user-suppled truths are computed Gödel quotients. Every qC Q is computed for Q, i.e., Q C ¢Q.

Step 2. All IOR covers are computed Gödel quotients. If q is computed for Q, then every cover of q is computed for Q, i.e., if q C ¢Q and q « r, then r C ¢Q.

Step 3. All flat-products are computed Gödel quotients. If q, r are computed for Q, then every FLAT-PRODUCT, q×r, is computed for Q, i.e., if q, r C ¢Q, then q×r C ¢Q.

Step 4. Ontology Layering Theorem. If p is uncertain in Q and p « q, then Q U {q} is consistent.

10. The major process of the computer algorithm is FLAT-MULTIPLICATION, which amounts to CANCELLATION OF PRIME FACTORS for exactly one pair of computed Gödel quotients. This amounts to the inference that if B is true and A-IOR-NOT-B is true, then A is true. Here, 3¹ and 3^-1, then these Gödel quotients may be FLAT-MULTIPLIED to obtain another computed Gödel quotient, here, 2^-1.
3¹ 2¹ 3^-1 ______________________ 2¹

Then, for CHARLIE:

__________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________| | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________| | CHARLIE | MV | T | F | F | MV | |__________________________________________________|

In Gödel quotient notation: Charlie: 3¹ Ontology: 2¹ 3^-1 ______________________ 2¹
We can make the (obvious) inference that AGE30 is true, since AGE60 is true.

7. REASONING UNDER UNCERTAINTY.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. The most important difference between classical mathematical logic and medical logic is the need to reason under uncertainty, so-called SUTTON'S LAW (24,25,26). Under Sutton's Law, if required data are missing for a certain inference, then one "goes where the money is", that is, one selects the most likely solution, and proceeds with the management of the patient.

      2. A system of medical inferences is called an ONTOLOGY (12,13). Inference formulas in an ontology may be ABSOLUTE or UNCERTAIN. For example, patient ABNER is less than 30 years old, with no urinary complaints, so it is PRESUMED that ABNER has no prostate cancer. It is further presumed that his serum PSA is below 4 mEq/dL (normal), and there is no need to test it. From this, one might draw the UNCERTAIN INFERENCE that (NOT-AGE30 AND NOT-URCOM) IMPLIES NOT-PROCA, and therefore ABNER has no prostate cancer, and doesn't need to be tested for it. This inference formula in IOR-prime-factor format is: 2¹ 7¹ 11^-1

      3. In Gödel quotient notation, ABNER has two relevant layer-zero data elements, namely, 2^-1 (= NOT-AGE30) and 7^-1 (= NOT-URCOM).
ABNER: 2^-1 ABNER: 7^-1 ONTOLOGY: 2¹ 7¹ 11^-1 __________________________ 11^-1

If the three Gödel quotients are FLAT-MULTIPLIED, then the flat-product is 11^-1, i.e., NOT-PROCA. Therefore one concludes that ABNER has no prostate cancer.

      4. However, suppose that ABNER receives a digital rectal examination for an unrelated reason (say, a gastrointestinal complaint), and a rock-hard prostate nodule is palpated, followed by a serum prostate specific antigen determination of 12 mEq/dL, and a prostate biopsy positive for cancer. In classical logic, there would be a contradiction (a Gödel quotient of 1), an inconsistent system, and no conclusions whatsoever could be drawn.

      5. There are various suggested remedies, including: modal logic, fuzzy set theory, certainty logic (12,13,25,26,27,28,29).

8. MEDICAL ONTOLOGIES.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. An ONTOLOGY is a (Platonic) description of essential reality, i.e., what actually is, as opposed to what one can see (observation, accident), or what one can know (epistemiology) (12). The term ontology was coined by two German philosophers, Göckel and Lorhard, in 1613, and first appeared in English in 1721. Quine (13) views ontology as the metaphysical commitments or presuppositions embodied in the different natural sciences. For example, the belief that a cancer can metastasize would be an ONTOLOGICAL COMMITMENT. In the philosophy and practice of science, ontology goes under various names: essence, reality, Mind of God, nature, gold standard, or mathiverse (14). In medical informatics, ontology has come to mean a structured list of concepts, typically prepared by an expert or panel of experts.

      2. With the ease of posting structured lists on the Internet, and with EXTENDED MARKUP LANGUAGE (XML) (38,39) as an emerging standard for such lists, it is likely that the next decade will witness an explosion of public medical ontologies, both amateur and professional.

      3. The importance of ontologies has been recognized by the U. S. Defense Advanced Research Projects Agency (DARPA), the original sponsor of the Internet, which has proposed guidelines for a formal ontology AGENT MARKUP LANGUAGE, that employs the ONTOLOGY INFERENCE LAYER (15,16).

      4. A simple ontology is illustrated by the observation at autopsy that CHRONIC-PASSIVE-CONGESTION-LIVER (CPCL = C0700148-C0721399 in UMLS codes) (40,41). often accompanies HEART HYPERTROPHY (HH = C0795691-C0333959). In an approximate sense, HH causes CPCL (42). Thus, one might expect a hypothetical collection, say, of 10,000 cases to distribute as follows: HEART HYPERTROPHY (HH=C0795691-C0333959) ____________________________________________ | | NOT-HH | HH | Total | |___________________________________________| | NOT-CPCL | 7,000 | 1,000 | 8,000 | |___________________________________________| | CPCL | 0 | 2,000 | 2,000 | |___________________________________________| | Total | 7,000 | 3,000 | 10,000 | |___________________________________________| CHRONIC-PASSIVE -CONGESTION-LIVER (CPCL=C0700148-C0721399).

      5. That is, most cases are negative for both features; HH anticipates CPCL in some cases; but there should be only rare cases with CPCL but without HH. Therefore, in the language of first-order propositional logic, CPCL IMPLIES HH, or NOT-CPCL IOR HH.

      6. Such correlations (2x2 CONTINGENCY TABLES), could be edited for redundancy and nonsense correlations (43).

      7. As necessary, a collection of such 2x2 contingency tables could be ORDERED BY IMPORTANCE, based upon the frequencies of cases appearing in the lower right corner of the table.

      8. Medical ontologies can be used to break into de-identified, public databases BY INFERENCE, which are otherwise well-protected. It will become the obligation of the data-holder to anticipate any inferential break-ins, and pre-empt them, by removing vulnerable data (5,44).

      9. In this report, we employ a medical ontology in progressive LAYERS OF UNCERTAINTY, L₀, L₁, L₂, L₃, ....

      10. LAYER ZERO, L₀, comprises observed data on a single record. LAYER ONE, L₁ are absolute inferences. LAYERS TWO OR MORE, L₂, L₃, L₄,... are progressively more uncertain inferences (26).

9. ONTOLOGY FOR UNCERTAIN LOGIC.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

1. The data for the individual patient-record is placed in layer-zero:

ABNER L₀ = {NOT-AGE30, NOT-AGE60, NOT-URCOM} = {2^-1, 3^-1, 7^-1}
BILL L₀ = {NOT-AGE30, NOT-AGE60, NOT-PSAG4, NOT-URCOM} = {2^-1, 3^-1, 5^-1, 7^-1}
CHARLIE L₀ = {AGE60, NOT-URCOM} = {3¹, 7^-1}
DAVID L₀ = {AGE30, NOT-AGE60, URCOM} = {2¹, 3^-1, 7¹}
EDWARD L₀ = {AGE30, NOT-AGE60, PSAG4, URCOM} = {2¹, 3^-1, 5¹, 7¹}
FRANK L₀ = {AGE30, NOT-AGE60, PSAG4, URCOM} = {2¹, 3^-1, 5¹, 7¹}
GEORGE L₀ = {AGE60, NOT-URCOM} = {3¹, 7^-1}
HARRY L₀ = {AGE30, AGE60, URCOM} = {2¹, 3¹, 7¹}
IKE L₀ = {AGE30, AGE60, NOT-PSAG4, URCOM} = {2¹, 3¹, 5^-1, 7¹}
JOHN L₀ = {AGE30, AGE60, PSAG4, URCOM} = {2¹, 3¹, 5¹, 7¹}

2. For the prostate example in this report, there is one ABSOLUTE INFERENCE, placed at LAYER ONE, L₁, namely, that:

L₁: AGE60 IMPLIES AGE30

This relationship may be expressed as an IOR relation, or as a Gödel quotient, as follows, where 2=AGE30 and 3=AGE60 IMPLICATION INCLUSIVE-OR GÖDEL QUOTIENT L₁: AGE60 IMPLIES AGE30 NOT-AGE60 IOR AGE30 2¹ 3^-1

3. The IMPLICATION FORMAT is easiest to understand. The INCLUSIVE-OR FORMAT is a simple transition format. The GÖDEL QUOTIENT FORMAT is unintuitive, but most suitable for mathematical arguments. Medical professional organizations should prepare ontologies in IMPLICATION FORMAT; information technology professionals can complete the translation to Gödel quotients, and execute the algorithm.

4. Remaining inferences in the example are UNCERTAIN, but this uncertainty can be ORDERED. Successive layers, L₂, L₃, L₄, L₅,... correspond to increasing uncertainty. Here are some proposed uncertain inferences:

L₂: PROCA IMPLIES PSAG4
L₃: (NOT-AGE30 AND NOT-URCOM) IMPLIES NOT-PROCA.
L₄: PSAG4 IMPLIES PROCA
L₅: (AGE60 AND URCOM) IMPLIES PROCA.
L₆: (AGE30 AND URCOM) IMPLIES PSAG4.

For example, PROCA IMPLIES PSAG4 is considered more certain than PSAG4 IMPLIES PROCA, since PSAG4 is a measure of high turnover of prostate glandular epithelium, and many pathologic processes (infection, infarction, hyperplasia) can lead to this potentially non-specific result. Conversion to Gödel quotients yields: �RM120� IMPLICATION INCLUSIVE-OR GÖDEL QUOTIENT L₁: AGE60 IMPLIES AGE30. NOT-AGE60 IOR AGE30 2¹ 3^-1 L₂: PROCA IMPLIES PSAG4. NOT-PROCA IOR PSAG4 5¹ 11^-1 L₃: (NOT-AGE30 AND NOT-URCOM) AGE30 IOR URCOM 2¹ 7¹ 11^-1 IMPLIES NOT-PROCA. IOR NOT-PROCA L₄: PSAG4 IMPLIES PROCA NOT-PSAG4 IOR PROCA 5^-1 11¹ L₅: (AGE60 AND URCOM) NOT-AGE60 IOR NOT-URCOM 3^-1 7^-1 11¹ IMPLIES PROCA IOR PROCA L₆: (AGE30 AND URCOM) NOT-AGE30 IOR NOT-URCOM 2^-1 5¹ 7^-1 IMPLIES PSAG4 IOR PSAG4
�RM80�

6. This method for displaying and calculating ontologies does NOT require that exact probability numbers be assigned to each layer, merely that the layers be ORDERED. This is an extremely simple ontology structure, which could be set up by various hostile attackers. The ONTOLOGY LAYERING THEOREM constrains the ordering in order to guarantee consistency.

7. The ONTOLOGY LAYERING THEOREM guarantees that if every layer contains a common prime factor that is uncertain from previous layers, then the solution is CONSISTENT. In the algorithm, this means that, in solving a particular layer, if the common prime factor is already certain, then the contents of that layer are DISCARDED by the algorithm (Step 4).

10. ONTOLOGY LAYERING THEOREM.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

1. A PRIME NUMBER is a whole number greater than one, divisible without remainder only by itself and one. A PRIME FACTOR is defined here as a prime number raised to power¹ or power^-1.
DEFINITION 1. PRIME FACTORS. The set of PRIME FACTORS is P = { 2, 2^-1, 3, 3^-1, 5, 5^-1, 7, 7^-1, 11, 11^-1, ..., N }, where N is the maximum prime number for the database, and m is the number of primes (=columns in the database).

In the example, there are m=5 fields (columns) in the database, numbered 2, 3, 5, 7, 11=N.

A GÖDEL QUOTIENT, q, is any product of prime factors, where each prime factor appears at most once.
DEFINITION 2. A GÖDEL QUOTIENT, q, is a product of prime factors, where each prime factor appears at most once in the product. The WORLD, W, is a set of all possible Gödel quotients.

A GÖDEL QUOTIENTSET, Q, is any set of Gödel quotients. For every GÖDEL QUOTIENTSET, Q, QC W.

2. We can regard the possible Gödel quotients as a TREE, in which the ROOT of the tree is called the SUPPORT and the LEAVES of the tree are called the COVER, as shown in the diagram. The ultimate leaves are truth table elements. The penultimate roots are unambiguous solutions for particular prime factors. The ultimate root is the World, W, and is inconsistent.

 COVER 
 z   z        z   z
 |   |        |   |
 |   |        |   |
 |   |        |   |
 | y |        | y |
 |   |        |   |
                |            |                
                |            |                
                |            |                
                |      x     |                
 |            |
      |    
      |    
      |    
      |    
      |    
 SUPPORT

We say that a single prime factor, pC P, SUPPORTS the Gödel quotient, q, denoted p « q. if and only if p is a factor of q. The prime factors of q correspond to binary variables in IOR relation to one another.
DEFINITION 3. p-SUPPORT. For every prime factor, p C P, and Gödel quotient, q, we say that p supports q, denoted p « q, if and only if p is a factor of q.

We say that a Gödel quotient, q, supports another Gödel quotient, r, denoted q « r, if and only if every prime factor of q is also a prime factor of r. If q « r, then all the prime factors in IOR relation in q are also prime factors in IOR relation in r (but not necessarily vice versa). In particular, if q is true for the record and q « r, then r is true for the record. The assertion that q « r (q supports r) is equivalent to r » q (r covers q).
DEFINITION 4. SUPPORT, COVER. For any pair of Gödel quotients, q, r C W, q, r, we say that q SUPPORTS r, denoted q « r, if and only if for every prime factor, p C P, such that p « q, it is true that p « r.
We say that r covers q, denoted r » q, if and only if q « r.

Corollary 1 states that every Gödel quotient supports itself.
COROLLARY 1. For every q C W, q « q.
PROOF.

Corollary 2 states that if a pair of Gödel quotients support each other, then these Gödel quotients are equal.
COROLLARY 2. For every q,r C W, such that q « r and r « q, then q = r
PROOF.

Corollary 3 states that the support operation, «, is transitive.
COROLLARY 3. If q « r and r « s, then q « s.
PROOF. By Definition 4, consider any prime factor, p, such that p « q; then p « r. By Definition 4, p « s. Then by Definition 4, q « s. Q.E.D.

3. A TRUTH TABLE ELEMENT is a Gödel quotient where every prime factor is present, either at power¹ or at power^-1. That is, there are no missingvalues in a truth table element.
DEFINITION 5. TRUTH TABLE, T. The TRUTH TABLE, T C W, is the set of t C T, such that t is a Gödel quotient, and for every p C P, either p « t or p^-1 « t.

For a set of user-supplied-truths, Q C W, the set of Gödel quotients that are DEEMED TRUE FOR Q consist of every Gödel quotient, r, such that for every truth table element, t, that r supports, there is some user-supplied Gödel quotient belonging to Q that also supports t.
DEFINITION 6. DEEMED TRUE FOR Q, ðQ. For any set of Gödel quotients, Q C W, the set of Gödel quotients that are DEEMED TRUE FOR Q, denoted ðQ, is the set of every r where for every truth table element, tC T, such that r « t, there exists a qC Q, such that q « t.

By Corollary 4, every user-supplied truth is a deemed truth.
COROLLARY 4. For every Q C W, Q C ðQ.
PROOF. Consider any qC Q, and any truth table element, tC T, such that q « t. By Definition 6, qC ðQ. Q.E.D.

By Corollary 5, every cover of a user-supplied truth is a deemed truth.
COROLLARY 5. For every Q C W, and for every r » q C ðQ, rC ðQ.
PROOF. Consider any qC ðQ, any r » q, and any truth table element, tC T such that r « t. By Corollary 3, the transitivity of «, q « r « t. By Definition 6, rC ðQ. Q.E.D.

4. The FLAT-PRODUCT for a pair of Gödel quotients, is an ordinary product (multiplication), subject to the condition that no power of a prime number is allowed to exceed 1 nor be less than -1.
DEFINITION 7. FLAT-PRODUCT. For Gödel quotients, q, r C W, we say that s = q × r is ALLOWED if and only if there exists exactly one prime factor, p C P, such that:

(1) p « q, p^-1 « r;
(2) for every p' C P-{p,p^-1} such that p' « q, p'^-1 ~« r.
(3) for every p' C P-{p,p^-1} such that p' « r, p'^-1 ~« q.

Then: s is the FLAT-PRODUCT, q × r, if and only if:

(1) p ~« s, p^-1 ~« s; .
(2) for every p' C P-{p,p^-1} such that p' « q, p' « s;
(3) for every p' C P-{p,p^-1} such that p' « r, p' « s.

The exactly one prime factor described above permits an EXACT CANCELLATION. Consider the example:

q = 2 3 5¹ r = 3 5^-1 7 _____________________________ s = 2 3 5⁰ 7

In this example, there is exactly one p C P, namely p=5, such that: 5 « q and 5^-1 « r. On the other hand, for every p' C P-{p,p^-1} such that p' « q, namely, p'=2 or p'=3, p'^-1 ~« r; That is, for p'=2, 2^-1 is not a prime factor of r at all; whereas for p'=3, 3¹ is the prime factor of r. Likewise for p' « r, p'=3 or p'=7.

We call this operation FLAT-PRODUCT, because no power is allowed to exceed 1 nor be less than -1. Thus 2×1=2, 5¹×5^-1=1, and 7×1=7; however, 3×3=3.

5. For a set of user-supplied truths, Q, the set of Gödel quotients that are COMPUTED FOR Q consist of all user-supplied truths, all IOR inferences, and all flat-products.
DEFINITION 8. COMPUTED FOR Q, ¢Q. For any set of Gödel quotients, Q C W, the set of Gödel quotients that are COMPUTED FOR Q, denoted ¢Q, is:

(1) the set of every q C Q (USER-SUPPLIED TRUTHS);
(2) the set of every r » q such that q C ¢Q (IOR INFERENCES);
and (3) the set of every s = q × r such that q, r C ¢Q (FLAT-PRODUCTS).

For a set of user-supplied truths, Q C W, we say that a prime factor, p, is UNCERTAIN IN Q if and only if there are truth table elements, t, u, where p supports t, p^-1 supports u, and neither t nor u are deemed truths for Q.
DEFINITION 9. UNCERTAIN IN Q. For any set of Gödel quotients, Q C W, p C P is UNCERTAIN IN Q if and only if there exist t, u C T such that p « t, p^-1 « u, and t, u ~C ðQ.

A set of user-supplied truths, Q, is consistent if and only if 1 is not a deemed truth for Q.
DEFINITION 10. CONSISTENT. Quotientset Q is CONSISTENT if and only if 1 ~C ðQ.

COROLLARY 4. For any set of Gödel quotients, Q C W, if p C P is uncertain in Q, then Q is consistent.
PROOF. By Definition 9 of uncertain, there exist t, u C T such that p « t, p^-1 « u, and t, u ~C ðQ. Suppose that Q is not consistent. Then 1 C ðQ, 1 « t, and 1 « u, so that t, u C ðQ. CONTRADICTION.

COROLLARY 5. For any set of Gödel quotients, Q C W, Q is consistent if and only if there exists a p C P and a q » p such that q ~C ðQ.
PROOF.

COROLLARY 6. For any set of Gödel quotients, Q C W, 1 C ðQ if and only if W C Q, respectively, W = Q.
PROOF.

      6. THEOREM 1 states that every computed quotient is a deemed quotient, i.e., ¢Q C ðQ.
THEOREM 1. For any set of Gödel quotients, Q C W, ¢Q C ðQ.
PROOF. Suppose that the theorem is false, and consider the first s C (¢Q - ðQ). By Corollary 5, s ~C Q. By Corollary 6, there exists no r C ðQ such that r « s. Therefore, s = q × r, and q, r C ðQ. Without loss of generality, consider the following flat-product (Definition 6):

q = 2 3 5¹ r = 3 5^-1 7 _____________________________ s = 2 3 5⁰ 7

Consider any t C T such that s « t. If 5¹ « t, then q « t. If 5^-1 « t, then r « t. In either case, s C ðQ. CONTRADICTION.

      7. THEOREM 2 states that every deemed quotient is a computed quotient, i.e., ðQ C ¢Q.
THEOREM 2. For any set of Gödel quotients, Q C W, ðQ C ¢Q.
PROOF. Suppose that the theorem is false, and consider the first s C (ðQ - ¢Q). Without loss of generality, let s = 2¹×3^-1, N=11, and consider the following subset of the truth table that supports s: 2¹3^-15^-17^-111^-1 2¹3^-15^-17^-111¹ 2¹3^-15^-17¹ 11^-1 2¹3^-15^-17¹ 11¹ 2¹3^-15¹ 7^-111^-1 2¹3^-15¹ 7^-111¹ 2¹3^-15¹ 7¹ 11^-1 2¹3^-15¹ 7¹ 11¹
All the above truth table elements belong to ðQ (Corollary 6). Furthermore, the following belong to ¢Q (Definition 8(3)): 2¹3^-15^-17^-1 2¹3^-15^-17¹ 2¹3^-15¹ 7^-1 2¹3^-15¹ 7¹
Likewise, the following belong to ðQ: 2¹3^-15^-1 2¹3^-15¹
Likewise, s belongs to ðQ. CONTRADICTION.

      8. THEOREM 3, the Ontology Layering Theorem, states that if a prime factor, p, is uncertain in Q, and p « r, then QU{r} is consistent.
THEOREM 3. ONTOLOGY LAYERING THEOREM. For any set of Gödel quotients, Q C W, if p C P is uncertain in Q and p « r, then (QU{r}) is consistent.
PROOF. Consider t, u C T such that p « t, p^-1 « u, and t, u ~C ðQ. Then p ~« u. Since u ~C ðQ, there exists no q C Q such that q « u. Since p « r, it follows that r ~« u. Therefore, there exists no q C {r} such that q « u. Hence, u ~C ðQU{r}, and by Corollary 5, (QU{r}) is consistent. Q.E.D.

11. RESULTS.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. Theorems 1 and 2 demonstrate that the computer algorithm, ¢Q, obtains all and only true statements for a set of user-supplied truths, Q C W.

      2. Weaker inferences, based upon missingvalues, are possible if there is a medical ontology, ordered in layers corresponding to increasing uncertainty.

      3. Observed data for the individual patient-record is placed in layer-zero, L₀. Layer-one, L₁, consists of absolute inferences. The remaining inferences are uncertain, but this uncertainty can be ordered in layers corresponding to increasing uncertainty in a medical ontology.

      4. Theorem 3, the Ontology Layering Theorem guarantees that if every layer in the medical ontology is uncertain with respect to some prime factor, then the solution at that layer is consistent.

12. DISCUSSION.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. U. S. Federal regulations have become much stricter regarding exchange and publication of individually identifiable medical information, including pathology databases for research purposes. Two standards for masking a patient's identity that qualify for exemption by an Institutional Review Board (IRB), namely anonymization and de-identification, are not achieved by methods currently in use.

      2. A pathology database can be characterized in general as a flat database, where each row is a single patient-record, and each column is a binary field (attribute). Sweeney has recently published a mathematical description of de-identification algorithms using this model, and has shown that many available computer systems either fail to protect the patient's identity, or perturb the data so substantially that the data are effectively useless for research investigations.

      3. Gödelization is a fundamental form for meta-discussions in mathematical logic, which is adapted in this report to handle true/false/missingvalue variables in a pathology database. The Gödelization in this report is mathematically akin to fuzzy set theory and multivalued (modal) logic.

      4. There are two flaws in Sweeney's model. First is the assumption that one always knows what database information is publicly posted, or ever will be posted. This forms a subset of KNOWN EXTERNAL LISTS (30).

      5. The second flaw in Sweeney's model is the fact that effective de-identification includes not only removal of the exact identifiers, but also a demonstration that the patient's identity cannot be determined by inference.

      6. Three theorems prove that a proposed algorithm infers all and only true statements. Weaker inferences, based upon missing values, are possible if there is a published medical ontology.

      7. Inferential determinations could be made by attackers from published medical ontologies, and may involve missingvalues and reasoning-from-uncertainty.

      8. Dataholders will be held responsible for filtering published data through a medical ontology, in order to guarantee effective de-identification.

      9. The Johns Hopkins Autopsy Resource (JHAR) demographics are k-anonymous, where k=4, with a single exception (45,46).

13. REFERENCES.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

      1. U. S. Code of Federal Regulations. 1995. 45 CFR Subtitle A (10-1-95 Edition), part 46.101 (b) (4).
U. S. Department of Health and Human Services. Office of the Secretary.
The complete Common Rule document (45CFR46), at URL:
http://www.uaf.edu/oar/irb/45cfr46.html
or at URL:
http://ohrp.osophs.dhhs.gov/humansubjects/guidance/45cfr46.htm

      2. U. S. Code of Federal Regulations. 1999. 45 CFR Parts 160 - 164. Standards for Privacy of Individually Identifiable Health Information; Proposed Rule.
Department of Health and Human Services. Office of the Secretary.
Fed Regist. 1999 Nov 3;64(212):59917-59966. http://aspe.hhs.gov/admnsimp/

      3. National Cancer Institute's Confidentiality Brochure, at URL:
http://www-cdp.ims.nci.nih.gov/policy.html

      4. Moore GW, Berman JJ.
Anatomic Pathology Data Mining.
In: Cios KJ, ed. Medical Data Mining and Knowledge Discovery.
2001. XVIII, 502 pp. 98 figs., 98 tabs. Hardcover.
ISBN: 3-7908-1340-0.
Copyright Springer-Verlag: Berlin/Heidelberg 1999.

      5. Sweeney L.
Computational Disclosure Control: A Primer on Data Privacy Protection.
PhD Thesis. Massachusetts Institute of Technology. Spring, 2001. Draft.
http://www.swiss.ai.mit.edu/classes/6.805/articles/privacy/sweeney-thesis-draft.pdf

      6. Sweeney L.
Privacy and medical-records research.
N Engl J Med. 1998 Apr 9;338(15):1077.
PMID: 9537887; UI: 98181820.

      7. Sweeney L.
Guaranteeing anonymity when sharing medical data, the Datafly System.
Proc AMIA Annu Fall Symp. 1997;:51-55.
PMID: 9357587; UI: 98020458.

      8. Gödel K.
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.
Monatsh Math u Physik. 1931; 38: 173-198.
Translation: Gödel K. On formally undecidable propositions of Principia Mathematica and related systems. New York: Basic Books. 1962.

      9. Nagel E, Newman JR.
Gödel's Proof.
New York: New York University Press. 1958.
ISBN 0-8147-0325-9.

      10. Hofstadter DR.
Gödel, Escher, Bach. An Eternal Golden Braid.
New York: Basic Books. 1979.
ISBN 0-465-02656-7, 777 pages.

      11. Casti JL, DePauli W.
Gödel. A Life of Logic.
Cambridge, MA: Perseus Publishing. 2000.
ISBN 0-7382-0274-6, 210 pages.

      12. Smith B.
Mereotopology: A Theory of Parts and Boundaries.
Data and Knowledge Engineering. 1996;20:287-303.

      13. Quine WVO.
Ontological relative, and other essays.
New York: Columbia University Press. 1969;:.

      14. Stewart I.
Flatterland. Like Flatland. Only More So.
Cambridge, MA: Perseus Publishing. 2001.
ISBN 0-7382-0442-0, 301 pages.

      15. U. S. Defense Advanced Research Projects Agency (DARPA). Agent Markup Language.
http://www.daml.org

      16. U. S. Defense Advanced Research Projects Agency (DARPA). Ontology Inference Layer.
http://www.ontoknowledge.org/oil

      17. Boole G.
An Investigation of the Laws of Thought. On which are founded the Mathematical Theories of Logic and Probabilities.
New York: Dover Publications, Inc. 1954.

      18. Lewis CI, Langford CH.
Symbolic Logic. Second Edition.
New York: Dover Publications, Inc. 1932.

      19. Borkowski L.
Formale Logik.
Muenchen: C. H. Beck.

      20. Zeman J.
Modal Logic: The Lewis Modal Systems.
Oxford at the Clarendon Press. 1972;:.

      21. Haack S.
Deviant Logic, Fuzzy Logic: Beyond the Formalism.
Paperback - 292 pages (November 1996).
Chicago: University of Chicago Press, 1996.
ISBN: 0226311341 ;

      22. Nguyen HT, Walker EA.
A First Course in Fuzzy Logic.
Hardcover, 300 pages, 2 edition, July 1999.
New York: CRC Press.
ISBN: 0849316596.

      23. Quine WVO, Ullian JS.
The Web of Belief. Second Edition.
Paperback 2nd edition. February 1, 1978. McGraw-Hill Higher Education;
ISBN: 0075536099.

      24. Beeson P.
Sutton's Law Paper.
Am J Med. 1960.

      25. Sutton WF, with Linn E.
Where the money was.
Out of print.

      26. Moore GW, Hutchins GM, Bulkley BH.
Certainty levels in the nullity method of symbolic logic: application to the pathogenesis of congenital heart malformations.
J Theor Biol. 1979 Jan 7;76(1):53-81.

      27. Moore GW, Hutchins GM.
Effort and demand logic in medical decision making.
Metamedicine 1980;1:277-304.

      28. Cios KJ, Moore GW. 2000.
Medical Data Mining and Knowledge Discovery: An Overview.
In: Cios KJ, ed. Medical Data Mining and Knowledge Discovery.
2001. XVIII, 502 pp. 98 figs., 98 tabs. Hardcover.
ISBN: 3-7908-1340-0.
Copyright Springer-Verlag: Berlin/Heidelberg 1999.

      29. College of American Pathologists.
Surgical Pathology Case Summaries.
http://www.cap.org

      30. Collaborative Prostate Cancer Tissue Resource.
http://www.prostatehealth.org/cpctr

      31. Suppes P.
Introduction to Logic.
New York: Van Nostrand. 1957.

      32. Bernays P.
Axiomatic Set Theory.
New York: Dover Publications. 1968.

      33. Suppes P.
Axiomatic Set Theory.
New York: Dover Publications. 1972.
ISBN 0486616304.

      34. Davis M.
Computability and Unsolvability.
New York: Dover Publications, Inc. 1958.
ISBN 0-486-61471-9, 248 pages.

      35. Andrews GL.
Number Theory.
New York: Dover Publications, Inc. 1971.
ISBN 0-486-68252-8, 259 pages.

      36. Schneier B.
Applied Cryptography, Second Edition. Protocols, Algorithms, and Source Code in C.
New York: John Wiley & Sons, 1996.

      37. Tarjan RE.
Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics.
Paperback, December, 1983.
New York: Society for Industrial & Applied Mathematics.
ISBN: 0898711878.

      38. Worldwide Web Consortium.
http://www.w3.org

      39. Light R.
Presenting XML.
Sams.net Publishing. 1997.

      40. U.S. National Library of Medicine.
Unified Medical Language System.
http://www.nlm.nih.gov/research/umls/

      41. U. S. National Library of Medicine.
UMLS Knowledge Sources. Twelfth Edition. Unified Medical Language System.
U. S. Department of Health and Human Services. National Institutes of Health. National Library of Medicine. 2001.

      42. Vigorita VJ, Moore GW, Hutchins GM.
Absence of correlation between coronary arterial atherosclerosis and severity or duration of diabetes mellitus of adult onset.
Am J Cardiol. 1980;46:535-542.

      43. Moore GW, Hutchins GM.
Consistency versus completeness in medical decision making: Application to 155 patients autopsied after coronary artery bypass graft surgery.
Proc 6th Annu Symp Comput Appl Med Care. 1982;6:805-811.

      44. Moore GW, Brown LA, Miller RE.
Set Theory Definition and Algorithm for Medical De-Identification.
Arch Pathol Lab Med. 2001;:in press.
http://www.netautopsy.org/apep00st.htm

      45. Johns Hopkins Autopsy Resource.
http://www.netautopsy.org/

      46. Moore GW, Berman JJ, Hanzlick RL, Buchino JJ, Hutchins GM. 1996.
A prototype Internet autopsy database. 1625 consecutive fetal and neonatal autopsy facesheets spanning 20 years.
Arch Pathol Lab Med. 1996;120:782-785.

      47. Hornung J.
Kritik der Signifikanztests.
Metamed 1977;1:325-345.

      48. Moore GW, Hutchins GM.
The persistent importance of autopsies.
Mayo Clin Proc. 2000 Jun;75(6):557-8.

      49. Wilbur WJ.
Overview of Books at NCBI.
http://www.ncbi.nlm.nih.gov:80/books/mboc/bookshelp/bookover.html#link

      50. Shared Pathology Informatics Network.
http://grants.nih.gov/grants/guide/rfa-files/RFA-CA-01-006.html

      51. Nelson SJ, Cole WG, Tuttle MS, Olson NE, Sherertz DD.
Recognizing new medical knowledge computationally.
Proc Annu Symp Comput Appl Med Care. 1993;17:409-413.

      52. Moore GW, Polacsek RA, Erozan YS, de la Monte SM, Miller RE, Hutchins GM, Riede UN.
Multilingual translation techniques in the analysis of narrative medical text.
Comput Methods Programs Biomed. 1986 Mar;22(1):35-42.

      53. Chomsky N.
Aspects of the Theory of Syntax.
Cambridge, MA: The MIT Press. 1965.

14. APPENDIX A. CONVERSION TO BINARY DATA.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

       1. Essentially all pathology data, including text diagnoses, can be expressed as BINARY FIELDS. Binary fields are not computationally efficient, but they make the mathematical argument more transparent for didactic purposes, and reflect the inherently yes/no structure of decision-making processes in medical diagnosis and prognosis. Four data-types admit to database collection and statistical evaluation, as follows (33):
1. Binary data.
2. Numeric data.
3. Categorical data.
4. Text comment or explanatory note.

       2. BINARY DATA. True/false or yes/no data. These data are already in a form that can be used by the data-model in this report. All binary data must have a true/false response IN PRINCIPLE for every patient-record. This excludes so-called loaded statements, such as "you have stopped beating your spouse, true or false", that are so popular with the hostile news media. When such statements are posed (inadvertently) in a pathology database, then they can usually be rephrased as a statement that always has a meaningful true/false response. For example: You have a spouse; AND
you once beat your spouse; AND
you have stopped beating your spouse, true or false.
A FALSE response to this compound sentence only means that at least one of the conditions is false. The status of the other two conditions would be determined from separate true/false statements.

       3. NUMERIC DATA. All numeric data can, in principle, be pointed to a set of binary questions, at the level of roundoff error of the particular numeric variable. For example:

serum K < 1 mEq/dL. (T/F)
serum K > 1 mEq/dL. (T/F)
serum K > 1.1 mEq/dL. (T/F)
serum K > 1.2 mEq/dL. (T/F)
serum K > 1.3 mEq/dL. (T/F)
serum K > 1.4 mEq/dL. (T/F)
serum K > 1.5 mEq/dL. (T/F) .........

This conversion is not particularly efficient, but it suggests a method in which conversion from numeric to binary data is always possible. Various computer algorithms can make the conversion more efficient. One simplification is to set break-points (thresholds) at below-normal, normal, above-normal, as for example:

serum K < 3.3 mEq/dL. (T/F)
serum K > 3.3 AND < 5.1 mEq/dL. (T/F)
serum K > 5.1 mEq/dL. (T/F)

Another simplification is to set break-points at levels that would influence diagnostic or prognostic decisions.

One of the mathematical properties of a numerical scale is the set of rules that interrelate the binary variables, as for example:

>4.0 => >3.9.
>3.9 => >3.8.
>3.8 => >3.7.
>3.7 => >3.6.
>3.6 => >3.5. ........

Therefore:

NOT->4.0 IOR >3.9.
NOT->3.9 IOR >3.8.
NOT->3.8 IOR >3.7.
NOT->3.7 IOR >3.6.
NOT->3.6 IOR >3.5. ........

4. CATEGORICAL DATA. True/false data in mutually exclusive categories. For example, the class of prostate carcinomas listed in the College of American Pathologists Surgical Pathology Case Summaries (29) that can be interpreted as belonging to one of the following twelve, mutually exclusive categories: ADENOCAPR: Adenocarcinoma, not otherwise specified.
PRDCTPRCA: Prostatic duct adenocarcinoma.
COLLOPRCA: Mucinous (colloid) adenocarcinoma.
SGNRNPRCA: Signet ring cell carcinoma.
ADNSQPRCA: Adenosquamous carcinoma.
SQMCLPRCA: Squamous cell carcinoma.
BASLOPRCA: Basaloid and adenoid cystic carcinoma.
TRANSPRCA: Transitional cell carcinoma.
SMLCLPRCA: Small cell carcinoma.
SARCOPRCA: Sarcomatoid carcinoma,
LYMEPPRCA: Lymphoepithelioma-like carcinoma.
UNDIFPRCA: Undifferentiated carcinoma, not otherwise specified.
One of the mathematical properties of mutually exclusive categories is the set of rules that interrelate the corresponding binary variables, as for example: ADENOCAPR => NOT-PRDCTPRCA.
ADENOCAPR => NOT-COLLOPRCA.
ADENOCAPR => NOT-SGNRNPRCA.
ADENOCAPR => NOT-ADNSQPRCA.
ADENOCAPR => NOT-SQMCLPRCA.
ADENOCAPR => NOT-BASLOPRCA.
ADENOCAPR => NOT-TRANSPRCA.
ADENOCAPR => NOT-SMLCLPRCA.
ADENOCAPR => NOT-SARCOPRCA.
ADENOCAPR => NOT-LYMEPPRCA.
ADENOCAPR => NOT-UNDIFPRCA.
PRDCTPRCA => NOT-COLLOPRCA.
PRDCTPRCA => NOT-SGNRNPRCA. ........
In IOR-notation: NOT-ADENOCAPR IOR NOT-PRDCTPRCA.
NOT-ADENOCAPR IOR NOT-COLLOPRCA.
NOT-ADENOCAPR IOR NOT-SGNRNPRCA.
NOT-ADENOCAPR IOR NOT-ADNSQPRCA.
NOT-ADENOCAPR IOR NOT-SQMCLPRCA.
NOT-ADENOCAPR IOR NOT-BASLOPRCA.
NOT-ADENOCAPR IOR NOT-TRANSPRCA.
NOT-ADENOCAPR IOR NOT-SMLCLPRCA.
NOT-ADENOCAPR IOR NOT-SARCOPRCA.
NOT-ADENOCAPR IOR NOT-LYMEPPRCA.
NOT-ADENOCAPR IOR NOT-UNDIFPRCA.
NOT-PRDCTPRCA IOR NOT-COLLOPRCA.
NOT-PRDCTPRCA IOR NOT-SGNRNPRCA. ........

5. TEXT COMMENT, EXPLANATORY NOTE. These are "emergent" fields, that have not yet been assigned to categories, and which don't seem to fit anywhere else. The predominant field of a comment it that it only holds true for a single patient-record, and is missingvalue for every other patient-record. A comment is useless in a logic expression, and useless for posting in a public database (because it would uniquely identify a patient). Therefore, the main value of a comment its potential for generating rules or new data fields (columns in the database).

15. APPENDIX B. REVIEW OF SET THEORY.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

       1. MATHEMATICAL LOGIC has its roots in Aristotle and in the European Middle Ages, but assumed its modern form in the hands of George Boole (17), who is rightfully memorialized in the term BOOLEAN SEARCHES used for searching the computerized medical literature.

       2. The MATHEMATICAL THEORY OF SETS was invented in the late nineteenth century, based upon concepts from mathematical logic, as a means for addressing some pressing philosophical issues in mathematics, such as the meaning of limits in calculus, and different classes of infinity. It has been suggested that these mathematical disciplines have potential serious applications in medicine, but so far the published examples (including in this report) are fairly trivial.

       3. A MATHEMATICAL SET, S, is any collection of objects for which it can be said that a particular object, s, either BELONGS TO S, (s is a member of S), denoted s C S, or DOES NOT BELONG TO S, (s is not a member of S), denoted s ~C S. One cannot simply collect a set of just anything. In particular, the SET OF ALL SETS is a famous paradox, whose recognition by a young Bertrand Russell nearly demolished the celebrated magnum opus and career of Prof. Gottlob Frege. THERE CANNOT BE A SET OF ALL SETS.

       4. A set may be characterized either as a listing of its actual members within curly brackets, {}, so-called roster notation, or by the method of its creation. For example, {2,3,5,7,11,13,17,19} and the SET OF ALL PRIMES LESS THAN 20 are the same set.

       5. The most important set of all is the NULL SET or EMPTY SET, i.e., the set that contains no members, usually denoted Ø, or {}.

       6. There are two important things to remember about a mathematical set (32,33):

6a. A SET IS CHARACTERIZED entirely in terms of its members, i.e., EXTENSIONALLY. A set may NOT be uniquely characterized INTENSIONALLY, i.e., by the manner of its creation. If two sets are created differently, but end up with the same membership, then they are the same set. For example, the set of humans living on the moon in 1850 and the set of Chevrolets built during 1850 are the same set, namely, the null set, Ø.

6b. A SET IS DIFFERENT FROM WHAT IT CONTAINS. that is, s and {s} are different. This property of sets leads to the Russell-Frege paradox: does the set of all sets belong to itself or not? (Is Epimenides a liar or not? (see Appendix C)). The Russell-Frege paradox can be resolved by defining two types of sets: ordinary sets and classes. This double definition involves a lot of extra mathematical bookkeeping.

Smith (12) believes that this classical formulation for sets is fundamentally flawed for describing ontologies, and has proposed using an alternate formulation, known as MEREOLOGY.

7. There are six commonly used concepts in set theory:

1. Set membership, denoted C . We say that s is a member of S, denoted C S; or s is not a member of S, denoted ~C S;

2. The empty set, Ø, the set containing no members. There exists no s such that s C Ø.

3. Set Union, U. The set A U B is the set of all members that belong either to set A or to set B or to both. Set union is analogous to inclusive-or (IOR) in first order propositional logic.

4. Set Intersection, /\. The set A /\ B is the set of all members that belong both to set A and to set B. Set intersection is analogous to logical AND in first order propositional logic.

5. Set Subtraction, -. The set A - B is the set of all members that belong to set A but NOT to set B. Set intersection is analogous to logical NOT in first order propositional logic.

6. Subset. A C B. We say that the set A C B, if the set of all members that belong to set A also belong to set B. Set intersection is analogous to IMPLIES in first order propositional logic.

16. APPENDIX C. BRIEF BIOGRAPHY OF GÖDEL.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

       1. GÖDEL is arguably the greatest mathematician of the twentieth century (11). His seminal work was published in 1931 (8), but only mathematicians and philosophers had ever heard of him until Hofstadter's popular book covering his work appeared two decades ago (10). Few persons outside of the computer science community realize that the computer's basic design of pointing instructions to numbers was Gödel's.

       2. Gödel was raised in Brno, Czech Republic, in the early 1900s. This was a time and place of intellectual ferment and ethnic diversity. Gödel was fluent in four languages, with an amateur interest in several others. He was influenced by existential writers such as Kafka; by the Jewish Kabbalists, who associated letters and words in the Hebrew Bible with numerical values and spiritual relationships; and by the emerging doctrine of non-Euclidean geometry.

       3. Gödel came of age at a time of crisis in physics. The unintuitive conclusion that the speed of light in a vacuum is everywhere constant conflicted with Newton's Laws at high speeds, and the geometry of space did not satisfy the classical Euclidean model. Prof. David Hilbert issued a challenge to his colleagues to design a consistent set of axioms from which all true statements of mathematics could be proved. Such an achievement would stake out an irreducible core of true principles in mathematics, which would not blow away with each passing fad in physics.

       3. The fundamental tool of mathematical reasoning is Aristotle's SYLLOGISM. For example: (1) All men are mortal;
(2) Socrates is a man;
(3) Therefore, Socrates is mortal.
If one knows that assertions (1) and (2) are true, then one is entitled to INFER that assertion (3) is true. This stepwise derivation of additional true statements from known true statements is a MATHEMATICAL PROOF.

       4. Aristotle also proposed the paradox of Epimenides the Cretan, who asserted that all Cretans are liars (11). This so-called PARADOX OF SELF-REFERENCE has no truth-value, for if the assertion is true, then it is false; if the assertion is false, then it is true. There are many forms of this paradox, including: "this statement is false"; "the barber shaves everyone who doesn't shave himself"; and "the set of all sets" (FREGE-RUSSELL PARADOX, see Appendix B).

       5. Gödel demolished Hilbert's dream by proving that EVERY system of mathematics at least as rich as as arithmetic, geometry, or set theory, must necessarily contain true but unprovable statements. The method by which Gödel achieved this result was as stunning as the result itself. Gödel assigned a unique whole number to every grammatically well-formed statement in mathematics. He then constructed this true statement in his enumeration model: THIS STATEMENT IS UNPROVABLE.

       6. Gödel's place in the history of mathematics, science, and technology is secure. His ideas have influenced computer science, artificial intelligence, neural nets, and possible limits on human sentience and creativity. Prof. John von Neumann, an early supporter of Gödel's work, clearly had Gödel's enumeration model in mind when von Neumann designed the first modern computer in the 1940s. The initial philosophical pessimism over the impossibility of establishing a complete and consistent mathematical system has matured: the reverse of the argument is that there will always be future work for creative mathematicians. At the end of his career, Gödel speculated that biological and human cultural diversity could serve as an inexhaustible wellspring for mathematical creativity (11).

17. APPENDIX D. ANSWERS TO PROBLEM SET.

NEXT PAGE.
PREVIOUS PAGE.
RETURN TO TABLE OF CONTENTS.

1. INTRODUCTION TO PROBLEM SET. The ten hypothetical patients: ABNER, BILL, CHARLIE, DAVID, EDWARD, FRANK, GEORGE, HARRY, IKE, JOHN, are solved in this section. Since there are 5 fields, each with a possible three values apiece (true, false, missingvalue), there are 3⁵ = 243 possible, hypothetical patients. The solution for all 243 hypothetical patients is left as an exercise for the reader. You are welcome to make your own HTML pages, from which you can launch your own solutions of the Ontology Layering Theorem. All you have to do is follow the pattern for the HTML pages for the hypothetical patients below.

The computer script, written in Perl v.5, which solves these patients, is posted at URL:

http://www.netautopsy.org/cgi-bin/goedpath.cgi

The source code for this script is listed at URL:

http://www.netautopsy.org/goedpath.txt

An introduction to the Internet is given at URL:

http://www.netautopsy.org/whatnett.htm

An introduction to HTML and Perl is given at URL:

http://www.netautopsy.org/whatperl.htm

       2. SUMMARY OF ONTOLOGY. IMPLICATION INCLUSIVE-OR GÖDEL QUOTIENT L₁: AGE60 IMPLIES AGE30. NOT-AGE60 IOR AGE30 2¹ 3^-1 L₂: PROCA IMPLIES PSAG4. NOT-PROCA IOR PSAG4 5¹ 11^-1 L₃: (NOT-AGE30 AND NOT-URCOM) AGE30 IOR URCOM 2¹ 7¹ 11^-1 IMPLIES NOT-PROCA. IOR NOT-PROCA L₄: PSAG4 IMPLIES PROCA NOT-PSAG4 IOR PROCA 5^-1 11¹ L₅: (AGE60 AND URCOM) PROCA NOT-AGE60 IOR NOT-URCOM 3^-1 7^-1 11¹ IMPLIES IOR PROCA L₆: (AGE30 AND URCOM) PROCA NOT-AGE30 IOR NOT-URCOM 2^-1 5¹ 7^-1 IMPLIES IOR PSAG4

       3. ABNER is a typical 29-year-old man with no urinary complaints, seen for a routine physical examination. His general practitioner sees no reason to perform a serum PSA test. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | ABNER | F | F | MV | F | MV | *F |__________________________________________________|____
Abner (observed): 2^-1 L₃: 2¹ 7¹ 11^-1 ___________________________________________________________________ Abner (calculated): 7¹ 11^-1 Abner (observed): 7^-1 ___________________________________________________________________ Abner (calculated): 11^-1
Solution: ABNER has NOT-PROCA.

       The HTML page that solves the ABNER �20dataset is posted at URL: http://www.netautopsy.org/goedabne.htm

       2. BILL is a 29-year-old man complaining of urinary frequency, with a firm prostate by digital rectal examination. As a precaution, a serum PSA is drawn, and is normal. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | BILL | F | F | F | T | MV | *F |__________________________________________________|____
Bill (observed): 5^-1 L₂: 5¹ 11^-1 ___________________________________________________________________ Bill (calculated): 11^-1
Solution: BILL has NOT-PROCA.

       The HTML page that solves the BILL �20dataset is posted at URL: http://www.netautopsy.org/goedbill.htm

       3. CHARLIE is a 56-year old man being seen in a busy clinic. The hurried technician records Charlie's AGE60 field, but fails to fill out the AGE30 field (used by a pathology informatics research study), and fails to order a serum PSA test, although this test is routinely ordered when there are urinary complaints in this age group. For this group of observations, the user-supplied ontology does not return a value for PROCA. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | CHARLIE | MV | F | MV | T | MV | *MV |__________________________________________________|____

Solution: CHARLIE has missingvalue PROCA.

       The HTML page that solves the CHARLIE �20dataset is posted at URL: http://www.netautopsy.org/goedchar.htm

       4. DAVID is a 52 year old male with urinary complaints and a hard prostate by digital rectal examination. A serum PSA determination is indicated. The user-supplied ontology returns a value for PROCA as TRUE. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | DAVID | T | F | MV | T | MV | *T |__________________________________________________|____
David (observed): 2¹ L₆: 2^-1 5¹ 7^-1 ___________________________________________________________________ David (calculated): 5¹ 7^-1 David (observed): 7¹ ___________________________________________________________________ David (calculated): 5¹ L₄: 5^-1 11¹ ___________________________________________________________________ David (calculated): 5¹

Solution: DAVID has PROCA.

       The HTML page that solves the DAVID �20dataset is posted at URL: http://www.netautopsy.org/goeddavi.htm

       5. EDWARD is a 45 year old male with urinary obstructive complaints. Serum PSA is drawn, and is 2.3 mEq/dL. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | EDWARD | T | F | F | T | MV | *F |__________________________________________________|____
Edward (observed): 5^-1 L₂: 5¹ 11^-1 ___________________________________________________________________ Edward (calculated): 11^-1

Solution: EDWARD has NOT-PROCA.

       6. FRANK is a 57 year old male with urinary obstructive complaints. A PSA is taken and found to be 5.5 mEq/dL. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | FRANK | T | F | T | T | MV | *T |__________________________________________________|____
Frank (observed): 5¹ L₄: 5^-1 11¹ ___________________________________________________________________ Frank (calculated): 11¹

Solution: FRANK has PROCA.

       7. GEORGE is a 61-year old man seen in a clinic. The technician records GEORGE's AGE60 field, but fails to fill out the AGE30 field, and fails to order a serum PSA test. For this group of observations, the user-supplied ontology returns a value for PROCA as missingvalue. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | GEORGE | MV | T | MV | F | MV | *MV |__________________________________________________|____

Solution: GEORGE has missingvalue PROCA.

       8. HARRY is a 64 year old male with urinary complaints and a hard prostate by digital rectal examination. A prostate biopsy is indicated. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | HARRY | T | T | MV | T | MV | *T |__________________________________________________|____
Harry (observed): 3¹ L₅: 3^-1 7^-1 11¹ ___________________________________________________________________ Harry (calculated): 7^-1 11¹ Harry (observed): 7¹ ___________________________________________________________________ Harry (calculated): 11¹

Solution: HARRY has PROCA.

       9. IKE is a 77 year old male with urinary obstructive complaints. PSA is taken and is 2.3 mEq/dL. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | IKE | T | T | F | T | MV | *F |__________________________________________________|____
Ike (observed): 5^-1 L₆: 5¹ 11^-1 ___________________________________________________________________ Ike (calculated): 11^-1

Solution: IKE has NOT-PROCA.

       10. JOHN is a 53 year old male with urinary obstructive complaints. A PSA is taken and found to be 5.5 mEq/dL. _______________________________________________________ | FIELD | AGE30 | AGE60 | PSAG4 | URCOM | PROCA | |__________________________________________________|____ | PRIME | 2 | 3 | 5 | 7 | 11 | |__________________________________________________|____ | JOHN | T | T | T | T | MV | *T |__________________________________________________|____
John (observed): 5¹ L₆ : 5^-1 11¹ ___________________________________________________________________ John (calculated): 11¹

Solution: JOHN has PROCA.

Last Updated: October 7, 2001, by G. William Moore, MD, PhD.