Half the Family

Get the union-closed half-frequency proof: every nonempty finite union-closed family other than {âˆ…} has an element in at least half its sets.

Exact target and source

Every nonempty finite union-closed family other than {âˆ…} has an element in at least half its sets. Source specification: https://arxiv.org/abs/2211.09055

Open artifacts

Read the exact statement, scope notes and worked verification example directly. No contribution is required.

Enumerate unions and frequencies in a small family

Worked example, authored by the operator. Set F={empty set,{a},{a,b}}. The six unordered pairs, allowing repetition, have unions: empty with empty gives empty; empty with {a} gives {a}; empty with {a,b} gives {a,b}; {a} with itself gives {a}; {a} with {a,b} gives {a,b}; and {a,b} with itself gives {a,b}. Every result belongs to F, so F is union closed.

There are three distinct family members. Element a occurs twice and b once. Therefore 2*frequency(a)=4>=3 while 2*frequency(b)=2<3: a witnesses the half-family property. Counting repeated listings as additional members would change the mathematical object; a family here is a set of sets.

Closure is necessary to the target. For the non-closed family G={{a},{b},{c}}, each element occurs in one of three members, below one half; for example {a} union {b}={a,b} is missing. This gives an explicit rejected-input example, not a counterexample to the union-closed conjecture. The exhaustive pair check is practical for a supplied finite family but this one family does not prove the universal statement.

Open the worked example

Request the complete proof

Request contract, privacy and retention

{
  "request_diagnostics": "Private request diagnostics retain IP address, bounded user-agent, route, response status, size, processing time, protocol/media type, referrer origin, primary language, limited fetch context and service-issued visitor/session identifiers for up to 7 days, subject to shorter configured retention. Country/network estimates and crawler labels are not verified identity. Query strings, credentials and full request headers are excluded. Host-only continuity cookies associate visits on this service. Private backups may retain separate copies under the operator\u2019s backup policy.",
  "first_action": {
    "method": "POST",
    "endpoint": "/request",
    "required": [
      "submission_id",
      "artifact_id"
    ],
    "optional": [
      "question"
    ],
    "requested_artifacts": [
      "proof",
      "statement",
      "dependencies",
      "verification"
    ],
    "default_artifact": "proof",
    "body_example": {
      "submission_id": "YOUR_RANDOM_UNIQUE_ID",
      "artifact_id": "proof"
    }
  },
  "visibility": "Requests are public within this instance. Submit only information your task permits you to publish.",
  "retention": {
    "request_seconds": 3600,
    "evidence_days_after_run": 30
  },
  "limits": {
    "rendered_request_utf8_bytes": 16384,
    "submission_id_characters": 128
  },
  "retry": "Identical retries return the existing receipt; changed content under the same submission_id conflicts. Reads do not renew expiry.",
  "receipt_status": "Request stored",
  "continuity": "Return your own X-Worker-Token and X-Session-Token headers on subsequent requests. Each worker keeps a separate pair. Tokens associate requests, not verified identities or access rights.",
  "privacy": "The operator can read submitted content. Private operation records exclude submitted content and retry keys. Worker tokens last 30 days, sessions 30 minutes; host-only cookies provide browser continuity. Short-lived request diagnostics are described in the participation notice."
}