
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Operators & Postulates
Group Theory is a branch of mathematics and abstract algebra that defines an algebraic structure named as group. Generally, a group comprises of a set of elements and an operation over any two elements on that set to form a third element also in that set.
In 1854, Arthur Cayley, the British Mathematician, gave the modern definition of group for the first time −
A set of symbols all of them different, and such that the product of any two of them (no matter in what order), or the product of any one of them into itself, belongs to the set, is said to be a group. These symbols are not in general convertible [commutative], but are associative.
In this chapter, we will know about operators and postulates that form the basics of set theory, group theory and Boolean algebra.
Any set of elements in a mathematical system may be defined with a set of operators and a number of postulates.
A binary operator defined on a set of elements is a rule that assigns to each pair of elements a unique element from that set. For example, given the set $ A = \lbrace 1, 2, 3, 4, 5 \rbrace $, we can say $\otimes$ is a binary operator for the operation $c = a \otimes b$, if it specifies a rule for finding c for the pair of $(a,b)$, such that $a,b,c \in A$.
The postulates of a mathematical system form the basic assumptions from which rules can be deduced. The postulates are −
Closure
A set is closed with respect to a binary operator if for every pair of elements in the set, the operator finds a unique element from that set.
Example
Let $A = \lbrace 0, 1, 2, 3, 4, 5, \dots \rbrace$
This set is closed under binary operator into $(\ast)$, because for the operation $c = a \ast b$, for any $a, b \in A$, the product $c \in A$.
The set is not closed under binary operator divide $(\div)$, because, for the operation $c = a \div b$, for any $a, b \in A$, the product c may not be in the set A. If $a = 7, b = 2$, then $c = 3.5$. Here $a,b \in A$ but $c \notin A$.
Associative Laws
A binary operator $\otimes$ on a set A is associative when it holds the following property −
$(x \otimes y) \otimes z = x \otimes (y \otimes z)$, where $x, y, z \in A $
Example
Let $A = \lbrace 1, 2, 3, 4 \rbrace$
The operator plus $( + )$ is associative because for any three elements, $x,y,z \in A$, the property $(x + y) + z = x + ( y + z )$ holds.
The operator minus $( - )$ is not associative since
$$( x - y ) - z \ne x - ( y - z )$$
Commutative Laws
A binary operator $\otimes$ on a set A is commutative when it holds the following property −
$x \otimes y = y \otimes x$, where $x, y \in A$
Example
Let $A = \lbrace 1, 2, 3, 4 \rbrace$
The operator plus $( + )$ is commutative because for any two elements, $x,y \in A$, the property $x + y = y + x$ holds.
The operator minus $( - )$ is not associative since
$$x - y \ne y - x$$
Distributive Laws
Two binary operators $\otimes$ and $\circledast$ on a set A, are distributive over operator $\circledast$ when the following property holds −
$x \otimes (y \circledast z) = (x \otimes y) \circledast (x \otimes z)$, where $x, y, z \in A $
Example
Let $A = \lbrace 1, 2, 3, 4 \rbrace$
The operators into $( * )$ and plus $( + )$ are distributive over operator + because for any three elements, $x,y,z \in A$, the property $x * ( y + z ) = ( x * y ) + ( x * z )$ holds.
However, these operators are not distributive over $*$ since
$$x + ( y * z ) \ne ( x + y ) * ( x + z )$$
Identity Element
A set A has an identity element with respect to a binary operation $\otimes$ on A, if there exists an element $e \in A$, such that the following property holds −
$e \otimes x = x \otimes e$, where $x \in A$
Example
Let $Z = \lbrace 0, 1, 2, 3, 4, 5, \dots \rbrace$
The element 1 is an identity element with respect to operation $*$ since for any element $x \in Z$,
$$1 * x = x * 1$$
On the other hand, there is no identity element for the operation minus $( - )$
Inverse
If a set A has an identity element $e$ with respect to a binary operator $\otimes $, it is said to have an inverse whenever for every element $x \in A$, there exists another element $y \in A$, such that the following property holds −
$$x \otimes y = e$$
Example
Let $A = \lbrace \dots -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, \dots \rbrace$
Given the operation plus $( + )$ and $e = 0$, the inverse of any element x is $(-x)$ since $x + (x) = 0$
De Morgan's Law
De Morgans Laws gives a pair of transformations between union and intersection of two (or more) sets in terms of their complements. The laws are −
$$(A \cup B)' = A' \cap B'$$
$$(A \cap B)' = A' \cup B'$$
Example
Let $A = \lbrace 1, 2, 3, 4 \rbrace ,B = \lbrace 1, 3, 5, 7 \rbrace$, and
Universal set $U = \lbrace 1, 2, 3, \dots, 9, 10 \rbrace$
$A' = \lbrace 5, 6, 7, 8, 9, 10 \rbrace$
$B' = \lbrace 2, 4, 6, 8, 9, 10 \rbrace$
$A \cup B = \lbrace 1, 2, 3, 4, 5, 7 \rbrace$
$A \cap B = \lbrace 1, 3 \rbrace $
$(A \cup B)' = \lbrace 6, 8, 9, 10 \rbrace$
$A' \cap B' = \lbrace 6, 8, 9, 10 \rbrace$
Thus, we see that $(A \cup B)' = A' \cap B'$
$(A \cap B)' = \lbrace 2, 4, 5, 6, 7, 8, 9, 10 \rbrace$
$A' \cup B' = \lbrace 2, 4, 5, 6, 7, 8, 9, 10 \rbrace$
Thus, we see that $(A \cap B)' = A' \cup B'$