UGC NET Core: Sets, relations, logic, graph theory, combinatorics, number theory basics.
// Set Theory
Universal set U: All elements under consideration
Subset: A ⊆ B if every element of A in B
Power set P(A): All subsets, |P(A)| = 2^|A|
Operations:
Union: A ∪ B = {x | x ∈ A or x ∈ B}
Intersection: A ∩ B = {x | x ∈ A and x ∈ B}
Complement: A' = {x ∈ U | x ∉ A}
Difference: A - B = A ∩ B'
De Morgan's Laws:
(A ∪ B)' = A' ∩ B'
(A ∩ B)' = A' ∪ B'
Cardinality: |A ∪ B| = |A| + |B| - |A ∩ B|
// Relations
Relation R: Subset of A × B
Domain: All first elements
Range: All second elements
Properties:
- Reflexive: (a,a) ∈ R for all a
- Symmetric: (a,b) ∈ R ⟹ (b,a) ∈ R
- Transitive: (a,b),(b,c) ∈ R ⟹ (a,c) ∈ R
- Antisymmetric: (a,b),(b,a) ∈ R ⟹ a=b
Equivalence: Reflexive + Symmetric + Transitive
Partial order: Reflexive + Antisymmetric + Transitive
// Functions
f: A → B (function from A to B)
Domain: A, Codomain: B
Image: f(A) = {f(a) | a ∈ A}
Injective (one-to-one): f(a₁) = f(a₂) ⟹ a₁ = a₂
Surjective (onto): f(A) = B
Bijective: Both injective and surjective
// Combinatorics
Permutations: P(n,r) = n!/(n-r)! (order matters)
Combinations: C(n,r) = n!/(r!(n-r)!) (order doesn't matter)
Binomial: (a+b)^n = Σ C(n,k)a^(n-k)b^k
Pigeonhole principle: n+1 items in n boxes ⟹ one box has ≥2
Inclusion-Exclusion: |A ∪ B ∪ C| = |A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|
// Number Theory
GCD (Greatest Common Divisor): Largest number dividing both
LCM (Least Common Multiple): Smallest multiple of both
Euclidean algorithm: GCD(a,b) = GCD(b, a mod b)
Modular arithmetic: a ≡ b (mod m) if m | (a-b)
Properties: (a+b) mod m = ((a mod m)+(b mod m)) mod m
Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) if p prime
Euler's Theorem: a^φ(m) ≡ 1 (mod m) if gcd(a,m)=1
Prime numbers: No divisors except 1 and self
Sieve of Eratosthenes: O(n log log n) to find primes ≤ n
// Propositional Logic
Tautology: Always true
Contradiction: Always false
Contingency: Sometimes true
Logical equivalence: Same truth table
Modus ponens: p, p→q ⟹ q
Modus tollens: ¬q, p→q ⟹ ¬p
Contrapositive: p→q ≡ ¬q→¬p
// First-Order Logic
Predicates: P(x) true for some x
Quantifiers:
∀x P(x): For all x, P(x) is true
∃x P(x): There exists x such that P(x) is true
¬(∀x P(x)) ≡ ∃x ¬P(x) (De Morgan for quantifiers)
¬(∃x P(x)) ≡ ∀x ¬P(x)
// Proof Techniques
Direct proof: Assume premise, derive conclusion
Proof by contradiction: Assume opposite, derive falsehood
Proof by induction: Base case + inductive step
Proof by contrapositive: Prove ¬q→¬p instead of p→q
Proof by exhaustion: Check all cases