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 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. Nonfreeness 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. 3albii
    14. sylgt
    15. sylg
    16. alrimih
    17. hbxfrbi
    18. alex
    19. exnal
    20. 2nalexn
    21. 2exnaln
    22. 2nexaln
    23. alimex
    24. aleximi
    25. alexbii
    26. exim
    27. eximi
    28. 2eximi
    29. eximii
    30. exa1
    31. 19.38
    32. 19.38a
    33. 19.38b
    34. imnang
    35. alinexa
    36. exnalimn
    37. alexn
    38. 2exnexn
    39. exbi
    40. exbii
    41. 2exbii
    42. 3exbii
    43. nfbiit
    44. nfbii
    45. nfxfr
    46. nfxfrd
    47. nfnbi
    48. nfnt
    49. nfn
    50. nfnd
    51. exanali
    52. 2exanali
    53. exancom
    54. exan
    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. 3exdistr
    52. 4exdistr
  5. Equality predicate (continued)
    1. weq
    2. speimfw
    3. speimfwALT
    4. spimfw
    5. ax12i
  6. Axiom scheme ax-6 (Existence)
    1. ax-6
    2. ax6v
    3. ax6ev
    4. spimw
    5. spimew
    6. speiv
    7. speivw
    8. exgen
    9. extru
    10. 19.2
    11. 19.2d
    12. 19.8w
    13. spnfw
    14. spfalw
    15. spvw
    16. 19.3v
    17. 19.8v
    18. 19.9v
    19. spimevw
    20. spimvw
    21. spsv
    22. spvv
    23. chvarvv
    24. 19.39
    25. 19.24
    26. 19.34
    27. 19.36v
    28. 19.12vvv
    29. 19.27v
    30. 19.28v
    31. 19.37v
    32. 19.44v
    33. 19.45v
    34. equs4v
    35. alequexv
    36. exsbim
    37. equsv
    38. equsalvw
    39. equsexvw
    40. cbvaliw
    41. 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. alcomimw
    37. excomimw
    38. alcomw
    39. excomw
    40. hbn1fw
    41. hbn1w
    42. hba1w
    43. hbe1w
    44. hbalw
    45. 19.8aw
    46. exexw
    47. spaev
    48. cbvaev
    49. aevlem0
    50. aevlem
    51. aeveq
    52. aev
    53. aev2
    54. hbaev
    55. naev
    56. naev2
    57. hbnaev
  8. Define proper substitution
    1. sbjust
    2. wsb
    3. df-sb
    4. dfsb
    5. sbtlem
    6. sbt
    7. sbtru
    8. stdpc4
    9. sbtALT
    10. 2stdpc4
    11. sbi1
    12. spsbim
    13. spsbbi
    14. sbimi
    15. sb2imi
    16. sbbii
    17. 2sbbii
    18. sbimdv
    19. sbbidv
    20. sban
    21. sb3an
    22. spsbe
    23. sbequ
    24. sbequi
    25. sb6
    26. 2sb6
    27. sb1v
    28. sbv
    29. sbcom4
    30. pm11.07
    31. sbrimvw
    32. sbbiiev
    33. sbievw
    34. sbievwOLD
    35. sbiedvw
    36. 2sbievw
    37. sbcom3vv
    38. sbievw2
    39. sbco2vv
    40. cbvsbv
    41. sbco4lem
    42. sbco4
    43. equsb3
    44. equsb3r
    45. equsb1v
    46. nsb
    47. sbn1
  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. elsb1
    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. elequ2g
    8. elsb2
    9. elequ12
    10. ru0
  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