مجموعهها و رابطهها
Sets and Relations
مباحث مجموعهها و رابطهها.
ریاضیات گسسته کنکور ارشد علوم کامپیوتر
کارتها · 12
On subsets of N, A is equivalent to B iff A delta B is finite: each class is countable, but there are continuum-many classes.
For nested indexed intervals, a union takes the largest member and an intersection takes the smallest.
Infinite unions of closed intervals can be open and infinite intersections of open intervals can be closed, so always compute the actual set.
Zorn's Lemma, the Hausdorff Maximal Principle, well-ordering, and cardinal comparability are all logically equivalent to the Axiom of Choice.
A poset is a set with a reflexive, antisymmetric, transitive order; under divisibility x preceq y ⇔ x y the integers form a lattice where gcd is the meet and lcm is the join.
A reflexive, symmetric, transitive relation slices a set into disjoint equivalence classes that partition it; count the distinct classes, not the elements.
∏_(i∈ I) X_i is the set of choice functions f:I→bigcup_i X_i with f(i)∈ X_i — one element picked from each X_i .
Interior is the largest open set inside A, closure the smallest closed set containing A, and boundary what is left over; complementing swaps interior and closure via two duality identities.
Composition distributes fully over UNION (both sides, always equality), but only ONE-WAY (subset, not equality) over intersection and difference — because it is built from an existential quantifier.
Count relations by splitting the n^2 pairs into independent diagonal loops and off-diagonal blocks, multiplying the choices each property allows. Handle 'not P' constraints by complementary counting: (all) minus (those with P).
Symmetric closes every pair under swapping; antisymmetric forbids two-way arrows between distinct points. The only relations that are both are subsets of the diagonal I = (x,x) .
The transitive closure R^(+) is the smallest transitive relation containing R : it adds (x,y) whenever a directed path of length ≥ 1 runs from x to y .