CD001A

finite_bit_union_intersection_values

Alpha v34 independently verified · alpha_closed; checked-use authorized; not Stable

The exact finite Boolean union/intersection truth table preserves the sum of the two input bits.

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved. Exact original first-admission records.

Exact expanded first-order arithmetic statement

forall a b u v. (a=0 \/ a=1) -> (b=0 \/ b=1) -> (u=0 \/ u=1) -> (v=0 \/ v=1) -> ((((u=1) -> (a=1 \/ b=1)) /\ ((a=1 \/ b=1) -> (u=1)))) -> ((((v=1) -> (a=1 /\ b=1)) /\ ((a=1 /\ b=1) -> (v=1)))) -> u+v=a+b

Constructive proof overview

Generated structural guide

The exact finite Boolean union/intersection truth table preserves the sum of the two input bits.

The unchanged tactic script uses 1 declared prerequisite and contains 166 exact native proof lines.

Alpha v34 checked-use · first admitted v27 · independently kernel and Lean verified; not Stable

Proof neighborhood

Direct dependencies

CD0017 finite_bit_zero_one_conflict

Direct dependents

CD001B finite_bit_union_intersection_count_balance

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Local theorem links identify exact declared prerequisites. This exact body belongs to a complete independently kernel-checked constructive proof bundle and has Alpha checked-use authority; it does not imply Stable membership.

Read the argument

Proof checkpoints

166 script commands · 67 reading checkpoints · 12 local claims

This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.

Named ingredients (1)
finite bit zero one conflict
01Fix variables and assumptionsL1–10

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro a
  2. L2
    intro b
  3. L3
    intro u
  4. L4
    intro v
  5. L5
    intro hA
  6. L6
    intro hB
  7. L7
    intro hU
  8. L8
    intro hI
  9. L9
    intro hOr
  10. L10
    intro hAnd
02Separate the logical casesL11–16

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L11
    cases hOr
  2. L12
    cases hAnd
  3. L13
    cases hA
  4. L14
    cases hB
  5. L15
    cases hU
  6. L16
    cases hI
03Calculate and transport equalitiesL17–21

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L17
    rewrite hU_left
  2. L18
    rewrite hI_left
  3. L19
    rewrite hA_left
  4. L20
    rewrite hB_left
  5. L21
    simp
04Establish habL22–24

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hAnd left.

  1. L22
    have hab : a=1 /\ b=1
  2. L23
    apply hAnd_left
  3. L24
    exact hI_right
05Separate the logical casesL25–26

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L25
    cases hab
  2. L26
    exfalso
06Use earlier factsL27–30

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L27
    specialize finite_bit_zero_one_conflict a
  2. L28
    apply finite_bit_zero_one_conflict
  3. L29
    exact hA_left
  4. L30
    exact hab_left
07Separate the logical casesL31–31

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L31
    cases hI
08Establish habL32–34

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr left.

  1. L32
    have hab : a=1 \/ b=1
  2. L33
    apply hOr_left
  3. L34
    exact hU_right
09Separate the logical casesL35–36

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L35
    cases hab
  2. L36
    exfalso
10Use earlier factsL37–40

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L37
    specialize finite_bit_zero_one_conflict a
  2. L38
    apply finite_bit_zero_one_conflict
  3. L39
    exact hA_left
  4. L40
    exact hab_left
11Separate the logical casesL41–41

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L41
    exfalso
12Use earlier factsL42–45

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L42
    specialize finite_bit_zero_one_conflict b
  2. L43
    apply finite_bit_zero_one_conflict
  3. L44
    exact hB_left
  4. L45
    exact hab_right
13Establish habL46–48

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr left.

  1. L46
    have hab : a=1 \/ b=1
  2. L47
    apply hOr_left
  3. L48
    exact hU_right
14Separate the logical casesL49–50

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L49
    cases hab
  2. L50
    exfalso
15Use earlier factsL51–54

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L51
    specialize finite_bit_zero_one_conflict a
  2. L52
    apply finite_bit_zero_one_conflict
  3. L53
    exact hA_left
  4. L54
    exact hab_left
16Separate the logical casesL55–55

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L55
    exfalso
17Use earlier factsL56–59

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L56
    specialize finite_bit_zero_one_conflict b
  2. L57
    apply finite_bit_zero_one_conflict
  3. L58
    exact hB_left
  4. L59
    exact hab_right
18Separate the logical casesL60–61

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L60
    cases hU
  2. L61
    cases hI
19Establish huL62–63

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr right.

  1. L62
    have hu : u=1
  2. L63
    apply hOr_right
20Separate the logical casesL64–64

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L64
    right
21Use earlier factsL65–65

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L65
    exact hB_right
22Separate the logical casesL66–66

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L66
    exfalso
23Use earlier factsL67–70

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L67
    specialize finite_bit_zero_one_conflict u
  2. L68
    apply finite_bit_zero_one_conflict
  3. L69
    exact hU_left
  4. L70
    exact hu
24Establish huL71–72

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr right.

  1. L71
    have hu : u=1
  2. L72
    apply hOr_right
25Separate the logical casesL73–73

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L73
    right
26Use earlier factsL74–74

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L74
    exact hB_right
27Separate the logical casesL75–75

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L75
    exfalso
28Use earlier factsL76–79

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L76
    specialize finite_bit_zero_one_conflict u
  2. L77
    apply finite_bit_zero_one_conflict
  3. L78
    exact hU_left
  4. L79
    exact hu
29Separate the logical casesL80–80

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L80
    cases hI
30Calculate and transport equalitiesL81–85

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L81
    rewrite hU_right
  2. L82
    rewrite hI_left
  3. L83
    rewrite hA_left
  4. L84
    rewrite hB_right
  5. L85
    simp
31Establish habL86–88

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hAnd left.

  1. L86
    have hab : a=1 /\ b=1
  2. L87
    apply hAnd_left
  3. L88
    exact hI_right
32Separate the logical casesL89–90

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L89
    cases hab
  2. L90
    exfalso
33Use earlier factsL91–94

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L91
    specialize finite_bit_zero_one_conflict a
  2. L92
    apply finite_bit_zero_one_conflict
  3. L93
    exact hA_left
  4. L94
    exact hab_left
34Separate the logical casesL95–97

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L95
    cases hB
  2. L96
    cases hU
  3. L97
    cases hI
35Establish huL98–99

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr right.

  1. L98
    have hu : u=1
  2. L99
    apply hOr_right
36Separate the logical casesL100–100

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L100
    left
37Use earlier factsL101–101

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L101
    exact hA_right
38Separate the logical casesL102–102

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L102
    exfalso
39Use earlier factsL103–106

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L103
    specialize finite_bit_zero_one_conflict u
  2. L104
    apply finite_bit_zero_one_conflict
  3. L105
    exact hU_left
  4. L106
    exact hu
40Establish huL107–108

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr right.

  1. L107
    have hu : u=1
  2. L108
    apply hOr_right
41Separate the logical casesL109–109

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L109
    left
42Use earlier factsL110–110

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L110
    exact hA_right
43Separate the logical casesL111–111

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L111
    exfalso
44Use earlier factsL112–115

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L112
    specialize finite_bit_zero_one_conflict u
  2. L113
    apply finite_bit_zero_one_conflict
  3. L114
    exact hU_left
  4. L115
    exact hu
45Separate the logical casesL116–116

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L116
    cases hI
46Calculate and transport equalitiesL117–121

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L117
    rewrite hU_right
  2. L118
    rewrite hI_left
  3. L119
    rewrite hA_right
  4. L120
    rewrite hB_left
  5. L121
    simp
47Establish habL122–124

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hAnd left.

  1. L122
    have hab : a=1 /\ b=1
  2. L123
    apply hAnd_left
  3. L124
    exact hI_right
48Separate the logical casesL125–126

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L125
    cases hab
  2. L126
    exfalso
49Use earlier factsL127–130

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L127
    specialize finite_bit_zero_one_conflict b
  2. L128
    apply finite_bit_zero_one_conflict
  3. L129
    exact hB_left
  4. L130
    exact hab_right
50Separate the logical casesL131–132

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L131
    cases hU
  2. L132
    cases hI
51Establish huL133–134

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr right.

  1. L133
    have hu : u=1
  2. L134
    apply hOr_right
52Separate the logical casesL135–135

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L135
    left
53Use earlier factsL136–136

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L136
    exact hA_right
54Separate the logical casesL137–137

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L137
    exfalso
55Use earlier factsL138–141

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L138
    specialize finite_bit_zero_one_conflict u
  2. L139
    apply finite_bit_zero_one_conflict
  3. L140
    exact hU_left
  4. L141
    exact hu
56Establish huL142–143

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hOr right.

  1. L142
    have hu : u=1
  2. L143
    apply hOr_right
57Separate the logical casesL144–144

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L144
    left
58Use earlier factsL145–145

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L145
    exact hA_right
59Separate the logical casesL146–146

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L146
    exfalso
60Use earlier factsL147–150

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L147
    specialize finite_bit_zero_one_conflict u
  2. L148
    apply finite_bit_zero_one_conflict
  3. L149
    exact hU_left
  4. L150
    exact hu
61Separate the logical casesL151–151

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L151
    cases hI
62Establish hvL152–153

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hAnd right.

  1. L152
    have hv : v=1
  2. L153
    apply hAnd_right
63Separate the logical casesL154–154

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L154
    split
64Use earlier factsL155–156

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L155
    exact hA_right
  2. L156
    exact hB_right
65Separate the logical casesL157–157

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L157
    exfalso
66Use earlier factsL158–161

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L158
    specialize finite_bit_zero_one_conflict v
  2. L159
    apply finite_bit_zero_one_conflict
  3. L160
    exact hI_left
  4. L161
    exact hv
67Calculate and transport equalitiesL162–166

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L162
    rewrite hU_right
  2. L163
    rewrite hI_right
  3. L164
    rewrite hA_right
  4. L165
    rewrite hB_right
  5. L166
    simp

Library-wide reading audit

Original exact command ledger · 166 lines
  1. 0001intro a
  2. 0002intro b
  3. 0003intro u
  4. 0004intro v
  5. 0005intro hA
  6. 0006intro hB
  7. 0007intro hU
  8. 0008intro hI
  9. 0009intro hOr
  10. 0010intro hAnd
  11. 0011cases hOr
  12. 0012cases hAnd
  13. 0013cases hA
  14. 0014cases hB
  15. 0015cases hU
  16. 0016cases hI
  17. 0017rewrite hU_left
  18. 0018rewrite hI_left
  19. 0019rewrite hA_left
  20. 0020rewrite hB_left
  21. 0021simp
  22. 0022have hab : a=1 /\ b=1
  23. 0023apply hAnd_left
  24. 0024exact hI_right
  25. 0025cases hab
  26. 0026exfalso
  27. 0027specialize finite_bit_zero_one_conflict a
  28. 0028apply finite_bit_zero_one_conflict
  29. 0029exact hA_left
  30. 0030exact hab_left
  31. 0031cases hI
  32. 0032have hab : a=1 \/ b=1
  33. 0033apply hOr_left
  34. 0034exact hU_right
  35. 0035cases hab
  36. 0036exfalso
  37. 0037specialize finite_bit_zero_one_conflict a
  38. 0038apply finite_bit_zero_one_conflict
  39. 0039exact hA_left
  40. 0040exact hab_left
  41. 0041exfalso
  42. 0042specialize finite_bit_zero_one_conflict b
  43. 0043apply finite_bit_zero_one_conflict
  44. 0044exact hB_left
  45. 0045exact hab_right
  46. 0046have hab : a=1 \/ b=1
  47. 0047apply hOr_left
  48. 0048exact hU_right
  49. 0049cases hab
  50. 0050exfalso
  51. 0051specialize finite_bit_zero_one_conflict a
  52. 0052apply finite_bit_zero_one_conflict
  53. 0053exact hA_left
  54. 0054exact hab_left
  55. 0055exfalso
  56. 0056specialize finite_bit_zero_one_conflict b
  57. 0057apply finite_bit_zero_one_conflict
  58. 0058exact hB_left
  59. 0059exact hab_right
  60. 0060cases hU
  61. 0061cases hI
  62. 0062have hu : u=1
  63. 0063apply hOr_right
  64. 0064right
  65. 0065exact hB_right
  66. 0066exfalso
  67. 0067specialize finite_bit_zero_one_conflict u
  68. 0068apply finite_bit_zero_one_conflict
  69. 0069exact hU_left
  70. 0070exact hu
  71. 0071have hu : u=1
  72. 0072apply hOr_right
  73. 0073right
  74. 0074exact hB_right
  75. 0075exfalso
  76. 0076specialize finite_bit_zero_one_conflict u
  77. 0077apply finite_bit_zero_one_conflict
  78. 0078exact hU_left
  79. 0079exact hu
  80. 0080cases hI
  81. 0081rewrite hU_right
  82. 0082rewrite hI_left
  83. 0083rewrite hA_left
  84. 0084rewrite hB_right
  85. 0085simp
  86. 0086have hab : a=1 /\ b=1
  87. 0087apply hAnd_left
  88. 0088exact hI_right
  89. 0089cases hab
  90. 0090exfalso
  91. 0091specialize finite_bit_zero_one_conflict a
  92. 0092apply finite_bit_zero_one_conflict
  93. 0093exact hA_left
  94. 0094exact hab_left
  95. 0095cases hB
  96. 0096cases hU
  97. 0097cases hI
  98. 0098have hu : u=1
  99. 0099apply hOr_right
  100. 0100left
  101. 0101exact hA_right
  102. 0102exfalso
  103. 0103specialize finite_bit_zero_one_conflict u
  104. 0104apply finite_bit_zero_one_conflict
  105. 0105exact hU_left
  106. 0106exact hu
  107. 0107have hu : u=1
  108. 0108apply hOr_right
  109. 0109left
  110. 0110exact hA_right
  111. 0111exfalso
  112. 0112specialize finite_bit_zero_one_conflict u
  113. 0113apply finite_bit_zero_one_conflict
  114. 0114exact hU_left
  115. 0115exact hu
  116. 0116cases hI
  117. 0117rewrite hU_right
  118. 0118rewrite hI_left
  119. 0119rewrite hA_right
  120. 0120rewrite hB_left
  121. 0121simp
  122. 0122have hab : a=1 /\ b=1
  123. 0123apply hAnd_left
  124. 0124exact hI_right
  125. 0125cases hab
  126. 0126exfalso
  127. 0127specialize finite_bit_zero_one_conflict b
  128. 0128apply finite_bit_zero_one_conflict
  129. 0129exact hB_left
  130. 0130exact hab_right
  131. 0131cases hU
  132. 0132cases hI
  133. 0133have hu : u=1
  134. 0134apply hOr_right
  135. 0135left
  136. 0136exact hA_right
  137. 0137exfalso
  138. 0138specialize finite_bit_zero_one_conflict u
  139. 0139apply finite_bit_zero_one_conflict
  140. 0140exact hU_left
  141. 0141exact hu
  142. 0142have hu : u=1
  143. 0143apply hOr_right
  144. 0144left
  145. 0145exact hA_right
  146. 0146exfalso
  147. 0147specialize finite_bit_zero_one_conflict u
  148. 0148apply finite_bit_zero_one_conflict
  149. 0149exact hU_left
  150. 0150exact hu
  151. 0151cases hI
  152. 0152have hv : v=1
  153. 0153apply hAnd_right
  154. 0154split
  155. 0155exact hA_right
  156. 0156exact hB_right
  157. 0157exfalso
  158. 0158specialize finite_bit_zero_one_conflict v
  159. 0159apply finite_bit_zero_one_conflict
  160. 0160exact hI_left
  161. 0161exact hv
  162. 0162rewrite hU_right
  163. 0163rewrite hI_right
  164. 0164rewrite hA_right
  165. 0165rewrite hB_right
  166. 0166simp