Sets, functions and relations

Learning objectives and scope

Distinguish membership from inclusion, compute set operations, read a function's domain and codomain, classify injective/surjective/bijective functions, and test basic properties of a relation on a finite set. Prerequisites: elementary arithmetic and propositional conditions. This is a foundation lesson, not complete coverage of sets or relations. Partial orders, Hasse diagrams, lattices, algebraic structures and infinite-cardinality arguments are outside this lesson.

1. Sets are collections without order or repetition

A set is determined by its elements. Thus {1,2,2} = {2,1} = {1,2}. The notation x ∈ A means x is an element of A. The notation A ⊆ B means every element of A belongs to B. The empty set ∅ has no elements and is a subset of every set: there is no element that could violate the subset condition. The set {∅} is not empty; its one element is the empty set.

For A = {1,2}, we have 1 ∈ A and {1} ⊆ A, but {1} ∉ A. A proper subset A ⊊ B satisfies A ⊆ B and A ≠ B. Equal sets are subsets of each other. The cardinality |A| counts distinct elements, so |{1,1,2}| = 2 and |{∅}| = 1.

The power set P(A) is the set of all subsets of A. For A = {a,b}, P(A) = {∅,{a},{b},{a,b}}. Each of n elements has two independent choices, included or omitted, so a finite n-element set has 2^n subsets. The empty subset and the full set must both be counted.

2. Worked set operations

Let the universe U = {1,2,3,4,5,6}, A = {1,2,4}, and B = {2,3,4}.

• A ∪ B = {1,2,3,4}: in at least one set.
• A ∩ B = {2,4}: in both.
• A \ B = {1}: in A but not B.
• B \ A = {3}: difference is not commutative.
• Aᶜ = U \ A = {3,5,6}: complement needs a stated universe.

|A ∪ B| = |A| + |B| − |A ∩ B| = 3 + 3 − 2 = 4. The subtraction removes the second count of each shared element; it does not remove those elements entirely. Set versions of De Morgan's laws are (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ, with all complements relative to the same U.

A Cartesian product contains ordered pairs: A × B = {(a,b): a ∈ A, b ∈ B}. For X = {1,2}, Y = {u,v,w}, X × Y has six pairs, with |X × Y| = 2×3. In general X × Y differs from Y × X; (1,u) is not (u,1).

3. A function is a restricted kind of relation

A relation from A to B is any subset of A × B. A function f:A→B must assign each element of A exactly one output in B. It may send different inputs to the same output. Missing an input or giving one input two different outputs makes the relation not a function on that domain.

The domain is A, the codomain is the specified target B, and the image f(A) is the set of outputs actually reached. A function is injective (one-to-one) if distinct inputs always have distinct outputs. It is surjective (onto B) if its image equals its codomain. It is bijective if both conditions hold. An injective function cannot merge inputs; a surjective function cannot miss a target.

Example: f:{1,2,3}→{a,b,c,d}, with f(1)=a, f(2)=c, f(3)=d, is injective but not surjective, because b is missed. If we change only the codomain to {a,c,d}, the same assignments define a bijection. Therefore “onto” cannot be judged from arrows alone without knowing the codomain. For finite sets an injection requires |A|≤|B| and a surjection requires |A|≥|B|; these size tests are necessary, not sufficient descriptions of a particular function.

4. Worked composition and inverse

Let f:{1,2}→{a,b} map 1 to b and 2 to a. Let g:{a,b}→{0,1} map a to 0 and b to 1. Composition g∘f applies f first: (g∘f)(1)=g(b)=1 and (g∘f)(2)=g(a)=0. Its domain is {1,2}, codomain {0,1}. The intermediate outputs must be valid inputs to g. Here f∘g is not defined on g's domain because g produces 0 and 1, which are not both inputs to f.

A bijection f:A→B has an inverse function f⁻¹:B→A that reverses every assignment. The example gives f⁻¹(a)=2 and f⁻¹(b)=1. If f merges two inputs, reversing arrows gives two outputs for one input, so no inverse function exists. If f misses a codomain element, reversal is undefined there. Thus an inverse on the entire stated codomain needs bijectivity.

5. Relations on one set: test each property separately

A relation R on A is a subset of A × A. Write aRb when (a,b) ∈ R.

• Reflexive: every (a,a) is included for a ∈ A.
• Symmetric: whenever (a,b) is included, (b,a) is also included.
• Antisymmetric: if both (a,b) and (b,a) are included, then a=b. It forbids two-way links between distinct elements; diagonal pairs are allowed.
• Transitive: whenever (a,b) and (b,c) are included, (a,c) must also be included.

Antisymmetric does not mean “not symmetric.” Equality is both symmetric and antisymmetric. Also, a relation with no applicable two-step chains satisfies transitivity vacuously. Always test against all elements of the specified underlying set; changing that set can change reflexivity.

6. Worked relation tests

On A={1,2,3}, take R={(1,1),(2,2),(3,3),(1,2),(2,1)}. All diagonal pairs are present, so R is reflexive. Every off-diagonal pair has its reverse, so it is symmetric. It is not antisymmetric because 1≠2 but both directions occur. It is transitive: within {1,2} every pair is present, within {3} the loop is present, and no link crosses the two groups. Every two-step chain therefore has its required shortcut.

A relation that is reflexive, symmetric and transitive is an equivalence relation. R partitions A into equivalence classes {1,2} and {3}: each element belongs to exactly one class. Reflexivity includes the element itself; symmetry makes relatedness mutual; transitivity makes linked elements stay in the same class.

For contrast, S={(1,2),(2,3)} on A is not transitive: the two given pairs require (1,3), which is absent. S is antisymmetric because no distinct pair occurs both ways. Properties are separate tests, not competing labels.

Quick reference and common errors

• Element: x∈A. Subset: X⊆A. ∅ differs from {∅}.
• |P(A)|=2^|A|; |A×B|=|A||B| for finite sets.
• Function: exactly one output for every domain element.
• Injection: no collisions. Surjection: no missed codomain elements. Bijection: both.
• g∘f means f first; an inverse function on the full codomain needs a bijection.
• Equivalence relation: reflexive + symmetric + transitive.

Do not discard duplicate counting only after a cardinality calculation; sets already contain each element once. Do not confuse image and codomain, or assume equal finite sizes make every function bijective. To reject transitivity, exhibit an actual pair of links and the missing shortcut. A lone missing pair is insufficient without the two-link premise.

7. Counting functions and testing edge cases

Let A have m elements and B have n elements, with m,n positive integers. There are n^m functions A→B: each input independently chooses one of n outputs. There are 2^(mn) relations from A to B, because each of the mn ordered pairs may be included or omitted. These counts differ because an arbitrary relation need not give each input exactly one output.

For A={1,2} and B={a,b,c}, there are 3²=9 functions and 2⁶=64 relations. Exactly 3×2=6 functions are injective. No function is surjective onto B because two inputs cannot reach three distinct targets. Equal finite domain and codomain sizes do not make every function bijective; however, for a function between such sets, injective and surjective are equivalent conditions. A collision leaves some target unreached, and an unreached target forces a collision.

On a nonempty set, the empty relation is symmetric, antisymmetric and transitive: there is no pair or chain that violates those conditions. It is not reflexive, because required diagonal pairs are missing. On the empty underlying set, it is also reflexive. State the underlying set before judging a relation.

Original practice: six single-correct MCQs

Original questions, not previous-year questions. Choose exactly one option.

C01. For A={1,2}, which statement is false?

A. ∅⊆A B. {1}⊆A C. {1}∈A D. 1∈A

Answer: C

A: The empty set is a subset of every set, so this statement is true.

B: Every element of {1} is in A, so this statement is true.

C: The elements of A are the numbers 1 and 2, not the set {1}; this is false.

D: The number 1 is explicitly an element of A, so this is true.

C02. If A={a,b,c}, what is |P(A)|?

A. 3 B. 6 C. 9 D. 8

Answer: D

A: Three counts elements of A, not its subsets.

B: Six is 3!, which counts orderings, not subsets.

C: Nine is 3^2, the number of ordered pairs in A×A.

D: Each of three elements is included or excluded independently; 2^3=8 subsets.

C03. Let f:{1,2,3}→{a,b,c,d} have values a,c,d, respectively. How is f classified?

A. Injective, not surjective B. Surjective, not injective C. Bijective D. Neither injective nor surjective

Answer: A

A: All outputs are distinct, but b in the codomain is missed; hence injective only.

B: There is no collision and b is missed, so both parts of this description fail.

C: A bijection must reach b as well; surjectivity fails.

D: Injection does hold because no two inputs share an output.

C04. Let f(1)=b, f(2)=a and g(a)=0, g(b)=1. What is (g∘f)(2)?

A. a B. 0 C. 1 D. b

Answer: B

A: a is the intermediate result f(2), not the final output after g.

B: Apply f first: f(2)=a, then g(a)=0.

C: One is g(b), but f(2) is a, not b.

D: b is f(1); the input here is 2 and the composition also applies g.

C05. On {1,2}, let R={(1,1),(2,2)}. Which description is correct?

A. Symmetric but not antisymmetric B. Antisymmetric but not symmetric C. Neither symmetric nor antisymmetric D. Both symmetric and antisymmetric

Answer: D

A: Every pair reverses to itself, but there is also no two-way pair of distinct elements, so antisymmetry holds.

B: Antisymmetry holds, but reversing each loop also proves symmetry.

C: Both properties hold; the relation contains only diagonal pairs.

D: Loops reverse to themselves, giving symmetry; there are no two-way links between distinct elements, giving antisymmetry.

C06. For S={(1,2),(2,3)} on {1,2,3}, which missing pair directly witnesses failure of transitivity?

A. (1,3) B. (3,1) C. (2,1) D. (1,1)

Answer: A

A: The existing chain 1→2→3 requires 1→3, which is absent.

B: There is no existing chain from 3 to 1 requiring this pair.

C: Its absence shows a symmetry issue, not the shortcut required by the given chain.

D: A missing diagonal disproves reflexivity, but no existing two-step chain here requires (1,1).

Source and scope

This introductory lesson aligns with Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. It is not full-topic or full-syllabus coverage. The source establishes syllabus relevance; teaching examples and questions are original.

Official GATE 2027 CS syllabus (verified 2026-10-14).