Problem 6 - Applied Discrete Structures

Question

Let \(C=\\{1,2,3,4,6,8,12,24\\}\) and define \(t\) on \(C\) by atb if and only if \(a\) and \(b\) share a common divisor greater than 1. Draw a digraph for \(t\).

Step-by-Step Solution

Answer

Draw nodes for each element in \( C \) and connect nodes if they share a common divisor greater than 1.

Step 1: Identify Elements of C

The set \( C \) is defined as \( C=\{1,2,3,4,6,8,12,24\} \). These are the elements we have to consider for the relation \( t \).

Step 2: Define Relation Condition

The relation \( t \) on set \( C \) is defined such that \( a \) is related to \( b \) (i.e., \( a t b \)) if and only if \( a \) and \( b \) share a common divisor greater than 1.

Step 3: Analyze Each Pair

Consider each pair of elements from \( C \). We need to check for each pair \( (a, b) \), whether they have a common divisor greater than 1. For instance, check \( a = 2 \) and \( b = 4 \) (common divisor is 2), so \( 2t4 \).

Step 4: List Related Pairs

After checking all pairs, the ones that meet the condition of having a common divisor greater than 1 are: \((2,4), (2,6), (2,8), (2,12), (2,24), (3,6), (3,12), (3,24), (4,6), (4,8), (4,12), (4,24), (6,8), (6,12), (6,24), (8,12), (8,24), (12,24)\) and the corresponding symmetric pairs.

Step 5: Draw the Directed Graph

To draw the digraph, represent each element of \( C \) as a node. Draw a directed edge from node \( a \) to node \( b \) if \( (a, b) \) is a related pair. Make sure to include all pairs as listed in Step 4. Since they are undirected pairs in terms of condition, draw bidirectional edges between nodes.

Key Concepts

Directed Graph

A directed graph, often called a digraph, is a set of nodes connected by edges, where the edges have a direction. This means each edge goes from one node to another specific node, indicating a relationship or connection.
A practical example of a directed graph is a one-way street map, where streets have direction and connect one point to another.

• **Nodes**: In our exercise, the nodes are the elements of set \( C \), i.e., \( \{1, 2, 3, 4, 6, 8, 12, 24\} \).
• **Edges**: The edges connect nodes based on the relationship defined by a common divisor greater than 1. These edges are bidirectional because the relationship is symmetric.

Understanding the concept of a directed graph helps in visualizing and analyzing how different elements relate in terms of their shared properties, like divisors in this case. The arrows depict the direction of the relation between pairs of nodes.

Relations

In mathematics, a relation is basically a rule that connects two or more objects together. It tells us how certain elements relate to one another in a structured way.
In this exercise, we’ve defined a specific relation \( t \) on the set \( C \). It states that an element \( a \) is related to \( b \) if they share a common divisor greater than 1. For example, \( 2 \) is related to \( 4 \) because they share \( 2 \) as a divisor, which is greater than 1.

• **Reflection**: Some relations like equality are reflexive, but in our example, not every element relates to itself unless it shares a divisor with itself like \( 8 \) does with \( 4 \).
• **Symmetry**: Our relation is symmetric, meaning if \( a \) is related to \( b \), then \( b \) is also related to \( a \).
• **Transitivity**: This would imply if \( a \) relates to \( b \) and \( b \) relates to \( c \), then \( a \) should relate to \( c \). Not all relations sustain this property naturally.

The usefulness of understanding these relationships is fundamental in fields such as computer science, network management, and discrete mathematics.

Divisors

A divisor is a number that divides another number completely without leaving a remainder. Common divisors are numbers that can divide two or more numbers fully. For example, the common divisors of \( 8 \) and \( 12 \) include \( 1, 2, \) and \( 4 \), with \( 1 \) usually being the trivial divisor.
Looking into our exercise, we have defined a relationship based on whether numbers share a divisor greater than 1. This helps in categorizing numbers by their shared properties.

• **Identifying Divisors**: To find if \( a \) and \( b \) are related by \( t \), we check if they have any common divisors above 1, such as \( 2 \) or \( 3 \).
• **Importance**: Understanding divisors is crucial for solving problems in number theory and has implications for cryptography, computer algorithms, and more.

Set Theory

Set theory is a fundamental part of modern mathematics and deals with collections of objects, known as sets. In the context of our exercise, the set \( C = \{1, 2, 3, 4, 6, 8, 12, 24\} \) is a collection of numbers, each considered as an element of the set.
Within set theory:

• **Elements**: These are individual objects within a set. For example, \( 1 \) or \( 12 \) are elements of the set \( C \).
• **Subsets**: A subset is any set containing elements that are all members of another set. All elements related by \( t \) form a subset of the larger set \( C \).
• **Intersection**: The intersection of two sets is where both sets contain the same elements. In our case, the common elements (divisors) could be seen where relationships overlap.

Set theory provides a framework for analyzing collections and their interrelations, offering insights that are vital for computer science, logic, and probability.