Binary relations and set projections

Mathematical statement

For sets A and B, a binary relation R from A to B is a subset of A×B; xRy means (x,y)∈R. Its domain is Dom(R)={x∈A:there exists y∈B with (x,y)∈R}; its image of C is R[C]={y∈B:there exists x∈C with (x,y)∈R}; its converse is R⁻¹={(y,x):(x,y)∈R}⊆B×A.

Representative formula (exact TeX)

R(x,y)

Assumptions

• The source A, target B, and relation R are explicit, and C is a subset of A.
• Ordered pairs retain their direction. The exercises use finite integer sets and explicit ordered-pair data.

Symbol scope

• R — specified binary relation
• x — first component
• y — second component

Intuition, definition, and misconceptions

R need not be a total function: a first component can have no second component or more than one. Identifying the declared source A in R⊆A×B with Dom(R) omits the actual first-projection distinction.

R[C] collects only outputs connected to elements of C, listing repeated values once. An empty relation or empty input subset has empty image.

The converse exchanges the direction of ordered pairs and swaps source and target. It is not automatically an inverse function and establishes no injectivity, surjectivity, or invertibility by itself.

Common errors include treating the declared source as the actual relational domain, or treating a converse relation as an established inverse function.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Set membership — Membership semantics identify relation and ordered-pair membership.
• Set — The source, target, projections, and images are sets.

Verification boundary

An explicit finite relation can be enumerated completely; general relation properties and specialization to functions await formalization.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind Set (A×B), the first projection, relational images, and converse; retain function conditions as additional constraints.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.