Metamath Proof Explorer


Table of Contents - 1.4. Predicate calculus with equality: Tarski's system S2 (1 rule, 6 schemes)

Here we extend the language of wffs with predicate calculus, which allows us to talk about individual objects in a domain of discourse (which for us will be the universe of all sets, so we call them "setvar variables") and make true/false statements about predicates, which are relationships between objects, such as whether or not two objects are equal. In addition, we introduce universal quantification ("for all", e.g. ax-4) in order to make statements about whether a wff holds for every object in the domain of discourse. Later we introduce existential quantification ("there exists", df-ex) which is defined in terms of universal quantification.

Our axioms are really axiom schemes, and our wff and setvar variables are metavariables ranging over expressions in an underlying "object language". This is explained here: mmset.html#axiomnote.

Our axiom system starts with the predicate calculus axiom schemes system S2 of Tarski defined in his 1965 paper, "A Simplified Formalization of Predicate Logic with Identity" [Tarski]. System S2 is defined in the last paragraph on p. 77, and repeated on p. 81 of [KalishMontague]. We do not include scheme B5 (our sp) of system S2 since [KalishMontague] shows it to be logically redundant (Lemma 9, p. 87, which we prove as theorem spw below).

Theorem spw can be used to prove any instance of sp having mutually distinct setvar variables and no wff metavariables. However, it seems that sp in its general form cannot be derived from only Tarski's schemes. We do not include B5 i.e. sp as part of what we call "Tarski's system" because we want it to be the smallest set of axioms that is logically complete with no redundancies. We later prove sp as theorem axc5 using the auxiliary axiom schemes that make our system metalogically complete.

Our version of Tarski's system S2 consists of propositional calculus (ax-mp, ax-1, ax-2, ax-3) plus ax-gen, ax-4, ax-5, ax-6, ax-7, ax-8, and ax-9. The last three are equality axioms that represent three sub-schemes of Tarski's scheme B8. Due to its side-condition ("where is an atomic formula and is obtained by replacing an occurrence of the variable by the variable "), we cannot represent his B8 directly without greatly complicating our scheme language, but the simpler schemes ax-7, ax-8, and ax-9 are sufficient for set theory and much easier to work with.

Tarski's system is exactly equivalent to the traditional axiom system in most logic textbooks but has the advantage of being easy to manipulate with a computer program, and its simpler metalogic (with no built-in notions of "free variable" and "proper substitution") is arguably easier for a non-logician human to follow step by step in a proof (where "follow" means being able to identify the substitutions that were made, without necessarily a higher-level understanding). In particular, it is logically complete in that it can derive all possible object-language theorems of predicate calculus with equality, i.e., the same theorems as the traditional system can derive.

However, for efficiency (and indeed a key feature that makes Metamath successful), our system is designed to derive reusable theorem schemes (rather than object-language theorems) from other schemes. From this "metalogical" point of view, Tarski's S2 is not complete. For example, we cannot derive scheme sp, even though (using spw) we can derive all instances of it that do not involve wff metavariables or bundled setvar variables. (Two setvar variables are "bundled" if they can be substituted with the same setvar variable, i.e., do not have a "$d" disjoint variable condition.) Later we will introduce auxiliary axiom schemes ax-10, ax-11, ax-12, and ax-13 that are metatheorems of Tarski's system (i.e. are logically redundant) but which give our system the property of "scheme completeness", allowing us to prove directly (instead of, say, by induction on formula length) all possible schemes that can be expressed in our language.

  1. Universal quantifier (continued); define "exists" and "not free"
    1. Existential quantifier
    2. Non-freeness predicate
  2. Rule scheme ax-gen (Generalization)
    1. ax-gen
    2. gen2
    3. mpg
    4. mpgbi
    5. mpgbir
    6. nex
    7. nfth
    8. nfnth
    9. hbth
    10. nftru
    11. nffal
    12. sptruw
    13. altru
    14. alfal
  3. Axiom scheme ax-4 (Quantified Implication)
    1. ax-4
    2. alim
    3. alimi
    4. 2alimi
    5. ala1
    6. al2im
    7. al2imi
    8. alanimi
    9. alimdh
    10. albi
    11. albii
    12. 2albii
    13. sylgt
    14. sylg
    15. alrimih
    16. hbxfrbi
    17. alex
    18. exnal
    19. 2nalexn
    20. 2exnaln
    21. 2nexaln
    22. alimex
    23. aleximi
    24. alexbii
    25. exim
    26. eximi
    27. 2eximi
    28. eximii
    29. exa1
    30. 19.38
    31. 19.38a
    32. 19.38b
    33. imnang
    34. alinexa
    35. exnalimn
    36. alexn
    37. 2exnexn
    38. exbi
    39. exbii
    40. 2exbii
    41. 3exbii
    42. nfbiit
    43. nfbii
    44. nfxfr
    45. nfxfrd
    46. nfnbi
    47. nfnt
    48. nfn
    49. nfnd
    50. exanali
    51. 2exanali
    52. exancom
    53. exan
    54. exanOLD
    55. alrimdh
    56. eximdh
    57. nexdh
    58. albidh
    59. exbidh
    60. exsimpl
    61. exsimpr
    62. 19.26
    63. 19.26-2
    64. 19.26-3an
    65. 19.29
    66. 19.29r
    67. 19.29r2
    68. 19.29x
    69. 19.35
    70. 19.35i
    71. 19.35ri
    72. 19.25
    73. 19.30
    74. 19.43
    75. 19.43OLD
    76. 19.33
    77. 19.33b
    78. 19.40
    79. 19.40-2
    80. 19.40b
    81. albiim
    82. 2albiim
    83. exintrbi
    84. exintr
    85. alsyl
    86. nfimd
    87. nfimt
    88. nfim
    89. nfand
    90. nf3and
    91. nfan
    92. nfnan
    93. nf3an
    94. nfbid
    95. nfbi
    96. nfor
    97. nf3or
    98. The empty domain of discourse
  4. Axiom scheme ax-5 (Distinctness) - first use of $d
    1. ax-5
    2. ax5d
    3. ax5e
    4. ax5ea
    5. nfv
    6. nfvd
    7. alimdv
    8. eximdv
    9. 2alimdv
    10. 2eximdv
    11. albidv
    12. exbidv
    13. nfbidv
    14. 2albidv
    15. 2exbidv
    16. 3exbidv
    17. 4exbidv
    18. alrimiv
    19. alrimivv
    20. alrimdv
    21. exlimiv
    22. exlimiiv
    23. exlimivv
    24. exlimdv
    25. exlimdvv
    26. exlimddv
    27. nexdv
    28. 2ax5
    29. stdpc5v
    30. 19.21v
    31. 19.32v
    32. 19.31v
    33. 19.23v
    34. 19.23vv
    35. pm11.53v
    36. 19.36imv
    37. 19.36iv
    38. 19.37imv
    39. 19.37iv
    40. 19.41v
    41. 19.41vv
    42. 19.41vvv
    43. 19.41vvvv
    44. 19.42v
    45. exdistr
    46. exdistrv
    47. 4exdistrv
    48. 19.42vv
    49. exdistr2
    50. 19.42vvv
    51. 19.42vvvOLD
    52. 3exdistr
    53. 4exdistr
  5. Equality predicate (continued)
    1. weq
    2. equs3OLD
    3. speimfw
    4. speimfwALT
    5. spimfw
    6. ax12i
  6. Axiom scheme ax-6 (Existence)
    1. ax-6
    2. ax6v
    3. ax6ev
    4. spimw
    5. spimew
    6. spimehOLD
    7. speiv
    8. speivw
    9. exgen
    10. exgenOLD
    11. extru
    12. 19.2
    13. 19.2d
    14. 19.8w
    15. spnfw
    16. spvw
    17. 19.3v
    18. 19.8v
    19. 19.9v
    20. 19.3vOLD
    21. spvwOLD
    22. 19.39
    23. 19.24
    24. 19.34
    25. 19.36v
    26. 19.12vvv
    27. 19.27v
    28. 19.28v
    29. 19.37v
    30. 19.44v
    31. 19.45v
    32. spimevw
    33. spimvw
    34. spvv
    35. spfalw
    36. chvarvv
    37. equs4v
    38. alequexv
    39. exsbim
    40. equsv
    41. equsalvw
    42. equsexvw
    43. equsexvwOLD
    44. cbvaliw
    45. cbvalivw
  7. Axiom scheme ax-7 (Equality)
    1. ax-7
    2. ax7v
    3. ax7v1
    4. ax7v2
    5. equid
    6. nfequid
    7. equcomiv
    8. ax6evr
    9. ax7
    10. equcomi
    11. equcom
    12. equcomd
    13. equcoms
    14. equtr
    15. equtrr
    16. equeuclr
    17. equeucl
    18. equequ1
    19. equequ2
    20. equtr2
    21. stdpc6
    22. equvinv
    23. equvinva
    24. equvelv
    25. ax13b
    26. spfw
    27. spw
    28. cbvalw
    29. cbvalvw
    30. cbvexvw
    31. cbvaldvaw
    32. cbvexdvaw
    33. cbval2vw
    34. cbvex2vw
    35. cbvex4vw
    36. alcomiw
    37. alcomiwOLD
    38. hbn1fw
    39. hbn1w
    40. hba1w
    41. hbe1w
    42. hbalw
    43. spaev
    44. cbvaev
    45. aevlem0
    46. aevlem
    47. aeveq
    48. aev
    49. aev2
    50. hbaev
    51. naev
    52. naev2
    53. hbnaev
  8. Define proper substitution
    1. sbjust
    2. wsb
    3. df-sb
    4. sbt
    5. sbtru
    6. stdpc4
    7. sbtALT
    8. 2stdpc4
    9. sbi1
    10. spsbim
    11. spsbbi
    12. sbimi
    13. sb2imi
    14. sbbii
    15. 2sbbii
    16. sbimdv
    17. sbbidv
    18. sbbidvOLD
    19. sban
    20. sb3an
    21. spsbe
    22. spsbeOLD
    23. sbequ
    24. sbequi
    25. sbequOLD
    26. sb6
    27. 2sb6
    28. sb1v
    29. sb4vOLD
    30. sb2vOLD
    31. sbv
    32. sbcom4
    33. pm11.07
    34. sbrimvlem
    35. sbrimvw
    36. sbievw
    37. sbiedvw
    38. 2sbievw
    39. sbcom3vv
    40. sbievw2
    41. sbco2vv
    42. equsb3
    43. equsb3r
    44. equsb3rOLD
    45. equsb1v
    46. equsb1vOLD
  9. Membership predicate
    1. wcel
    2. wel
  10. Axiom scheme ax-8 (Left Equality for Binary Predicate)
    1. ax-8
    2. ax8v
    3. ax8v1
    4. ax8v2
    5. ax8
    6. elequ1
    7. elsb3
    8. cleljust
  11. Axiom scheme ax-9 (Right Equality for Binary Predicate)
    1. ax-9
    2. ax9v
    3. ax9v1
    4. ax9v2
    5. ax9
    6. elequ2
    7. elsb4
    8. elequ2g
  12. Logical redundancy of ax-10 , ax-11 , ax-12 , ax-13
    1. ax6dgen
    2. ax10w
    3. ax11w
    4. ax11dgen
    5. ax12wlem
    6. ax12w
    7. ax12dgen
    8. ax12wdemo
    9. ax13w
    10. ax13dgen1
    11. ax13dgen2
    12. ax13dgen3
    13. ax13dgen4