I am currently stuck on a set theory problem. Suppose we have set S = $ \{1, 2, 3, 4, 5 \}$ and set A $\subseteq S * S$ given by $A = \{ (1, 1), (1, 4), (2, 1), (2, 2), (2, 4), (3, 5), (4, 3), (4, 4), (5, 2) \} $.
Now, suppose $B \subseteq S * S$ and is a transitive relation such that $A \subseteq B$. What is the smallest cardinality of $B$?
My working was as follows: For $B$ to be transitive, for every $(a, b) \in B$ and $(b, c) \in B$ there must be $(a, c) \in B$.
As $A \subseteq B$, we can get the smallest set if we consider the elements in $A$ which already hold a transitive relation and simply add any 'missing' elements to fulfil the remaining elements that lack this relation.
There's an issue though. Once we add those 'missing' elements, they become part of the set and so need to hold the transitive relation for themselves. For example, we have from $A$, $(1,4)$ and $(4,3)$. Therefore we need to add $(1, 3)$ to complete the transitive relation between those two. However, this creates another issue - $(1, 3)$ (the added 'missing' element) and $(3, 5)$ (from set $A$) do not satisfy the transitive relation (i.e. there is a missing $(1, 5)$).
Once I got this impression, it made me believe that manually determining all the pairs to add to $B$ in order to satisfy the transitive requirement for the set may take a while.
The given solution says the answer is '25' (i.e. the entirety of the elements of $S * S$). Is this verifiable without manually crunching all the pairs required to satisfy the requirement? If so, it would be funny that the 'smallest' possible cardinality is the entire set.
The question was basically solved in the comments by Paul Tanenbaum and Gerry Myerson
It is enough to notice that there is a cycle going through all elements of $S$, namely $1\to 4\to 3\to 5\to 2\to 1$.
Using the arrows in this cycle one can get from any of the numbers $1$, $2$, $3$, $4$, $5$ to all remaining numbers.