Set Definitions Flashcards
The 3 ways to write ∃!xP(x)
∃x (P(x) ∧ ∀y (P(y) → y = x) )
∃x ∀y (P(y) ↔ y = x)
∃x P(x) ∧ ∀y ∀z ( (P(y) ∧ P(z) ) → y = z)
A⊆B
∀x (x ∈ A → x ∈ B)
℘(A)
{x | x ⊆ A}
A×B
{(a,b) | a ∈ A ∧ b ∈ B}
Relation
R ⊆ A×B
∩F
{x | ∀A (A ∈ F → x ∈ A)}
∪F
{x | ∃A (A ∈ F ∧ x ∈ A)}
Dom(R)
{a ∈ A | ∃b ∈ B ( (a,b) ∈ R)}
Ran(R)
{b ∈ B | ∃a ∈ A ( (a,b) ∈ R)}
R-1
{(b,a) ∈ B×A | (a,b) ∈ R}
SoR
{(a,c) ∈ A×C | ∃b ∈ B ( (a,b) ∈ R ∧ (b,c) ∈ S)}
Reflexive
∀x ∈ A (xRx)
Symmetric
∀x ∈ A ∀y ∈ A (xRy → yRx)
Transitive
∀x ∈ A ∀y ∈ A ∀z ∈ A ( (xRy ∧ yRx) → xRz)
Antisymmetric
∀x ∈ A ∀y ∈ A ( (xRy ∧ yRx) → x = y)
Partial Order
Reflexive
Transitive
Antisymmetric
Total Order
Partial Order
∀x ∈ A ∀y ∈ A (xRy ∨ yRx)
R-smallest
∀x ∈ B (bRx)
R-largest
∀x ∈ B (xRb)
R-minimal
¬∃x ∈ B (xRb ∧ x ≠ b)
R-maximal
¬∃x ∈ B (bRx ∧ x ≠ b)
Equivalence Relation
Reflexive
Symmetric
Transitive
Pairwise Disjoint
∀X ∈ F ∀Y ∈ F (X ≠ Y → X∩Y = ∅)
Partition
∪F = A
Pairwise Disjoint (∀X ∈ F ∀Y ∈ F (X ≠ Y → X∩Y = ∅))
∀X ∈ F (x ≠ ∅)
Equivalence Class
[x]R = {y ∈ A | yRx}
A/R
{[x]R | x ∈ A}
x is congruent to y (mod m)
(modulo)
∃k ∈ Z (x - y = km)
f: A → B
∀a ∈ A ∃!b ∈ B ( (a,b) ∈ f)
f: A → B is one-to-one.
¬∃a1 ∈ A ∃a2 ∈ A ( f(a1) = f(a2) ∧ a1 ≠ a2)
