OCMEBilingual mathematics & derivations繁體中文

Explore related knowledge and questions →

Question 20960: Three-Set Inclusion-Exclusion Needs the Triple Intersection

On this page
  1. Original question and givens
  2. Definition and scope
  3. Step-by-step derivation
  4. Reverse checks
  5. Result
  6. This question review and source binding

Return to catalogue page 105

← Question derivation index · Original question batch

R0040-20960 · q-20261014-advance-20261108-r05-inclusion-exclusion-principle-0035

Original question and givens

Use the complete indexed finite integer-set family sets=[[9, 10, 11], [9, 11, 12], [9, 11, 13]] in supplied index order. Each set has distinct elements; equal sets at different indices remain separate indexed entries. Every nonempty index subset contributes its intersection cardinality, with positive odd-order and negative even-order sign. Keep zero-size intersections and source increasing-bitmask term order. Give (terms, union_size, alternating_sum, equal, certificate).

  • G001 — Use the complete indexed finite integer-set family sets=[[9, 10, 11], [9, 11, 12], [9, 11, 13]] in supplied index order. Each set has distinct elements; equal sets at different indices remain separate indexed entries. Every nonempty index subset contributes its intersection cardinality, with positive odd-order and negative even-order sign. Keep zero-size intersections and source increasing-bitmask term order. Give (terms, union_size, alternating_sum, equal, certificate).

Definition and scope

Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.

Step-by-step derivation

S001 · implies

Before

source operation=incexc-three-set-formula;original snapshot and mathematics retained

After

explicit ordered source output fields=[terms, union_size, alternating_sum, equal, certificate]

Conditions: none

Keep the historical interface marker in the original snapshot while listing source fields here without JavaScript or external lookup.Labels are not mathematical evidence,and No retains its source claim scope.

Step identifiers and dependencies

Rule: source_ordered_interface_explicit_without_javascript · Uses: G001

S002 · implies

Before

ORIGINAL indexed finite set family in SUPPLIED outer index order=[[9, 10, 11], [9, 11, 12], [9, 11, 13]]

After

within-set numeric normalization=[[9, 10, 11], [9, 11, 12], [9, 11, 13]];duplicates INSIDE a set rejected;EQUAL sets at DIFFERENT indices RETAINED;integer labels may be negative

Conditions: none

Normalize elements within each set only.Outer family positions are inclusion-exclusion indices and must not be semantically reordered or deduplicated.Empty sets are legitimate indexed members,and element labels are not cardinalities.

Step identifiers and dependencies

Rule: incexc_indexed_family_not_deduplicated_or_semantic_reordered · Uses: G001, S001

S003 · calculation

Before

inclusion mask1 signed intersection cardinality := mul(1, 3)

After

inclusion mask1 signed intersection cardinality = 3

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S002

S004 · calculation

Before

inclusion mask1 alternating prefix sum := sum(0, 3)

After

inclusion mask1 alternating prefix sum = 3

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S003

S005 · implies

Before

next NONEMPTY NUMERIC bitmask=1;ORIGINAL family indices=[0];actual selected original sets=[[9, 10, 11]]

After

FULL intersection members=[9, 10, 11];size=3;ODD order sign=1;alternating prefix=3;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S004

S006 · calculation

Before

inclusion mask2 signed intersection cardinality := mul(1, 3)

After

inclusion mask2 signed intersection cardinality = 3

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S005

S007 · calculation

Before

inclusion mask2 alternating prefix sum := sum(3, 3)

After

inclusion mask2 alternating prefix sum = 6

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S006

S008 · implies

Before

next NONEMPTY NUMERIC bitmask=2;ORIGINAL family indices=[1];actual selected original sets=[[9, 11, 12]]

After

FULL intersection members=[9, 11, 12];size=3;ODD order sign=1;alternating prefix=6;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S007

S009 · calculation

Before

inclusion mask3 signed intersection cardinality := mul(-1, 2)

After

inclusion mask3 signed intersection cardinality = -2

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S008

S010 · calculation

Before

inclusion mask3 alternating prefix sum := sum(6, -2)

After

inclusion mask3 alternating prefix sum = 4

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S009

S011 · implies

Before

next NONEMPTY NUMERIC bitmask=3;ORIGINAL family indices=[0, 1];actual selected original sets=[[9, 10, 11], [9, 11, 12]]

After

FULL intersection members=[9, 11];size=2;EVEN order sign=-1;alternating prefix=4;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S010

S012 · calculation

Before

inclusion mask4 signed intersection cardinality := mul(1, 3)

After

inclusion mask4 signed intersection cardinality = 3

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S011

S013 · calculation

Before

inclusion mask4 alternating prefix sum := sum(4, 3)

After

inclusion mask4 alternating prefix sum = 7

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S012

S014 · implies

Before

next NONEMPTY NUMERIC bitmask=4;ORIGINAL family indices=[2];actual selected original sets=[[9, 11, 13]]

After

FULL intersection members=[9, 11, 13];size=3;ODD order sign=1;alternating prefix=7;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S013

S015 · calculation

Before

inclusion mask5 signed intersection cardinality := mul(-1, 2)

After

inclusion mask5 signed intersection cardinality = -2

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S014

S016 · calculation

Before

inclusion mask5 alternating prefix sum := sum(7, -2)

After

inclusion mask5 alternating prefix sum = 5

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S015

S017 · implies

Before

next NONEMPTY NUMERIC bitmask=5;ORIGINAL family indices=[0, 2];actual selected original sets=[[9, 10, 11], [9, 11, 13]]

After

FULL intersection members=[9, 11];size=2;EVEN order sign=-1;alternating prefix=5;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S016

S018 · calculation

Before

inclusion mask6 signed intersection cardinality := mul(-1, 2)

After

inclusion mask6 signed intersection cardinality = -2

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S017

S019 · calculation

Before

inclusion mask6 alternating prefix sum := sum(5, -2)

After

inclusion mask6 alternating prefix sum = 3

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S018

S020 · implies

Before

next NONEMPTY NUMERIC bitmask=6;ORIGINAL family indices=[1, 2];actual selected original sets=[[9, 11, 12], [9, 11, 13]]

After

FULL intersection members=[9, 11];size=2;EVEN order sign=-1;alternating prefix=3;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S019

S021 · calculation

Before

inclusion mask7 signed intersection cardinality := mul(1, 2)

After

inclusion mask7 signed intersection cardinality = 2

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S020

S022 · calculation

Before

inclusion mask7 alternating prefix sum := sum(3, 2)

After

inclusion mask7 alternating prefix sum = 5

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S021

S023 · implies

Before

next NONEMPTY NUMERIC bitmask=7;ORIGINAL family indices=[0, 1, 2];actual selected original sets=[[9, 10, 11], [9, 11, 12], [9, 11, 13]]

After

FULL intersection members=[9, 11];size=2;ODD order sign=1;alternating prefix=5;zero-size terms retained

Conditions: none

Every nonempty index subset appears once in numeric-mask order,not cardinality or lexicographic order.Odd intersections add and even ones subtract.Retain zero-size intersections;an intermediate alternating sum is not yet asserted to be a cardinality.

Step identifiers and dependencies

Rule: incexc_every_index_submask_intersection_parity_source_order · Uses: G001, S022

S024 · calculation

Before

inclusion COMPLETE actual union cardinality := sum(1, 1, 1, 1, 1)

After

inclusion COMPLETE actual union cardinality = 5

Conditions: none

Substitute original roles and established intermediates exactly,retaining indices,set positions,orientation,signs and applicability conditions.

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S023

S025 · implies

Before

ACTUAL union element=9;ALL containing ORIGINAL family indices=[0, 1, 2];indexed multiplicity r=3

After

only nonempty subsets of these containing indices contribute to this element;pair subsets not containing the first such index with subsets adding it:opposite signs cancel except its positive singleton;total coefficient1

Conditions: none

Fix one containing index.Pair each nonempty subset omitting it with the subset adding it;their signs cancel.The missing empty subset leaves its positive singleton unpaired,giving coefficient1.Equal sets at different indices increase r and must not be deduplicated.

Step identifiers and dependencies

Rule: incexc_each_element_full_coefficient_not_one_sum_coincidence · Uses: G001, S024

S026 · implies

Before

ACTUAL union element=10;ALL containing ORIGINAL family indices=[0];indexed multiplicity r=1

After

only nonempty subsets of these containing indices contribute to this element;pair subsets not containing the first such index with subsets adding it:opposite signs cancel except its positive singleton;total coefficient1

Conditions: none

Fix one containing index.Pair each nonempty subset omitting it with the subset adding it;their signs cancel.The missing empty subset leaves its positive singleton unpaired,giving coefficient1.Equal sets at different indices increase r and must not be deduplicated.

Step identifiers and dependencies

Rule: incexc_each_element_full_coefficient_not_one_sum_coincidence · Uses: G001, S025

S027 · implies

Before

ACTUAL union element=11;ALL containing ORIGINAL family indices=[0, 1, 2];indexed multiplicity r=3

After

only nonempty subsets of these containing indices contribute to this element;pair subsets not containing the first such index with subsets adding it:opposite signs cancel except its positive singleton;total coefficient1

Conditions: none

Fix one containing index.Pair each nonempty subset omitting it with the subset adding it;their signs cancel.The missing empty subset leaves its positive singleton unpaired,giving coefficient1.Equal sets at different indices increase r and must not be deduplicated.

Step identifiers and dependencies

Rule: incexc_each_element_full_coefficient_not_one_sum_coincidence · Uses: G001, S026

S028 · implies

Before

ACTUAL union element=12;ALL containing ORIGINAL family indices=[1];indexed multiplicity r=1

After

only nonempty subsets of these containing indices contribute to this element;pair subsets not containing the first such index with subsets adding it:opposite signs cancel except its positive singleton;total coefficient1

Conditions: none

Fix one containing index.Pair each nonempty subset omitting it with the subset adding it;their signs cancel.The missing empty subset leaves its positive singleton unpaired,giving coefficient1.Equal sets at different indices increase r and must not be deduplicated.

Step identifiers and dependencies

Rule: incexc_each_element_full_coefficient_not_one_sum_coincidence · Uses: G001, S027

S029 · implies

Before

ACTUAL union element=13;ALL containing ORIGINAL family indices=[2];indexed multiplicity r=1

After

only nonempty subsets of these containing indices contribute to this element;pair subsets not containing the first such index with subsets adding it:opposite signs cancel except its positive singleton;total coefficient1

Conditions: none

Fix one containing index.Pair each nonempty subset omitting it with the subset adding it;their signs cancel.The missing empty subset leaves its positive singleton unpaired,giving coefficient1.Equal sets at different indices increase r and must not be deduplicated.

Step identifiers and dependencies

Rule: incexc_each_element_full_coefficient_not_one_sum_coincidence · Uses: G001, S028

S030 · implies

Before

COMPLETE indexed family size=3;ALL7 nonempty index subsets accounted for;ACTUAL union=[9, 10, 11, 12, 13]

After

each covered element has coefficient1 and any uncovered element coefficient0;FULL alternating sum=5=actual union size=5;empty family yields empty union/no terms/0

Conditions: none

Sum the pointwise coefficient certificates to get the entire finite union size,rather than inferring a theorem from one numerical coincidence.Uncovered points have no containing indices and contribute0;the empty family gives0 directly.

Step identifiers and dependencies

Rule: incexc_full_pointwise_identity_all_finite_indexed_sets · Uses: G001, S029

Reverse checks

  • S030 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S029 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S028 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S027 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S026 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S025 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S024 · premise_and_result_audit — Recompute inclusion COMPLETE actual union cardinality with exact rational arithmetic, not rounded decimals.
  • S023 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S022 · premise_and_result_audit — Recompute inclusion mask7 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S021 · premise_and_result_audit — Recompute inclusion mask7 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S019 · premise_and_result_audit — Recompute inclusion mask6 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S018 · premise_and_result_audit — Recompute inclusion mask6 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S016 · premise_and_result_audit — Recompute inclusion mask5 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S015 · premise_and_result_audit — Recompute inclusion mask5 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S013 · premise_and_result_audit — Recompute inclusion mask4 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S012 · premise_and_result_audit — Recompute inclusion mask4 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S010 · premise_and_result_audit — Recompute inclusion mask3 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S009 · premise_and_result_audit — Recompute inclusion mask3 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S007 · premise_and_result_audit — Recompute inclusion mask2 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S006 · premise_and_result_audit — Recompute inclusion mask2 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S004 · premise_and_result_audit — Recompute inclusion mask1 alternating prefix sum with exact rational arithmetic, not rounded decimals.
  • S003 · premise_and_result_audit — Recompute inclusion mask1 signed intersection cardinality with exact rational arithmetic, not rounded decimals.
  • S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.

Result

([[[0], 1, 3], [[1], 1, 3], [[0, 1], -1, 2], [[2], 1, 3], [[0, 2], -1, 2], [[1, 2], -1, 2], [[0, 1, 2], 1, 2]], 5, 5, Yes, odd_intersections_positive_even_intersections_negative)

The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.

This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.

Source hashes and review receipts
  • input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
  • original question SHA-256: 9a2f50174aea1a3e5106ecd4f80d027f4cca4ceded3f303602494b42b0d8bc93
  • candidate record SHA-256: 1f2be745888c2035e2656bcff5a7ecb39dbf875907bd7dc6363cd18b6703b22d
  • semantic review receipt SHA-256: c6483ed1229af9183fe5c704a2627b1558ad9a31bfbb0d2ee2d5c1a1c299ab4d
  • question-first witness SHA-256: e81f9a560d630fcb23441146f008c4feca7aceab3ebe4de2cf1997c061375ef7
  • Lean: NOT_RUN · human review: NOT_PERFORMED
Same-source full JSON