Math proof about relations

In summary: Here's the summary:In summary, the problem at hand involves determining the number of relations on a set X={1,2,3,4,5,6} that are both reflexive and anti-symmetric. The first step is to consider what can happen with a pair, such as {1,2}, and determine the possibilities for including (1,2) and/or (2,1) in a relation while keeping it anti-symmetric. Once this is done, the number of available pairs can be determined. The misconception that a relation is reflexive if for all a in a set A, a R (to some element) then aRa was addressed, and the correct solution was determined to be 3^(n choose
  • #1
21
0

Homework Statement


Let X = {1, 2, 3, 4, 5, 6}. Determine the number of relations on X which are reflexive and anti-symmetric

Homework Equations

The Attempt at a Solution


This problem looks a little bit hard.

Approach:
consider R={(x,x),... }
If there is just one pair in the relation in the form (x,x), there is no way we can come up with something that is reflexive and anti-symmetric hence we are just allowed to include pairs that start with x. If add another pair that starts with x then automatically the relation becomes transitive. There is no way to destroy the transitivity hence for the same reason we are just allowed to add pairs that start with x.

consider R={(x,x),(y,y),...}
If this is the case then we can come up with something like this R={(1,1),(2,2),(1,2),(2,3)}. Here the relation is reflexive and antisymmetric. The pattern that I see here is when we have two pairs in R in the form (x,x), if we add another pair that starts with x, we have to find a way to destroy the transitivity by adding another pair. This is too hard. How can you count that by using a pattern?
 
Physics news on Phys.org
  • #2
Danielm said:

Homework Statement


Let X = {1, 2, 3, 4, 5, 6}. Determine the number of relations on X which are reflexive and anti-symmetric

Homework Equations

The Attempt at a Solution


This problem looks a little bit hard.

Approach:
consider R={(x,x),... }
If there is just one pair in the relation in the form (x,x), there is no way we can come up with something that is reflexive and anti-symmetric hence we are just allowed to include pairs that start with x. If add another pair that starts with x then automatically the relation becomes transitive. There is no way to destroy the transitivity hence for the same reason we are just allowed to add pairs that start with x.

consider R={(x,x),(y,y),...}
If this is the case then we can come up with something like this R={(1,1),(2,2),(1,2),(2,3)}. Here the relation is reflexive and antisymmetric. The pattern that I see here is when we have two pairs in R in the form (x,x), if we add another pair that starts with x, we have to find a way to destroy the transitivity by adding another pair. This is too hard. How can you count that by using a pattern?
Transitivity is irrelevant to this exercise.

For example, the following relation is reflexive and anti-symmetric:
R = {(1,1), (2,2),(3,3), (4,4), (5,5), (6,6), (1,2), (2,3)}

This relation is reflexive, but not anti-symmetric:
R' = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,3), (3,2)}

To determine how many reflexive and anti-symmetric relations there are on X, the first task is to determine what can happen with a pair.
Say {1,2}. We can form two tuples: (1,2), (2,1). How many of these can be in an anti-symmetric relation? How many possibilities does that give?
Once you have that, how many pairs do you have to consider?
 
  • #3
Samy_A said:
Transitivity is irrelevant to this exercise.

To determine how many reflexive and anti-symmetric relations there are on X, the first task is to determine what can happen with a pair.
Say {1,2}. We can form two tuples: (1,2), (2,1). How many of these can be in an anti-symmetric relation? How many possibilities does that give?
Once you have that, how many pairs do you have to consider?

(1,2),(2,1) can't be in the same relation because (1,1) and (2,2) have to be as well in the relation and this creates transitivity. That's why I am saying that we have add other pairs to destroy the transitivity.
 
  • #4
Danielm said:
(1,2),(2,1) can't be in the same relation because (1,1) and (2,2) have to be as well in the relation and this creates transitivity. That's why I am saying that we have add other pairs to destroy the transitivity.
(1,2),(2,1) can't be in the relation because you are asked to count reflexive and anti-symmetric relations. Transitivity has nothing to do with it. Transitivity plays no role in this exercise.

The reflexive part of the question is easy. A relation is reflexive if it includes (1,1), (2,2), ..., (6,6). Not much to count here.
The anti-symmetric part is a little more difficult. That's why I suggested you look at a pair, {1, 2}, and see what the possibilities are for including (1,2) and/or (2,1) in a relation, while keeping the relation anti-symmetric.
Once that is done, determine the number of available pairs.
 
  • #5
Samy_A said:
(1,2),(2,1) can't be in the relation because you are asked to count reflexive and anti-symmetric relations. Transitivity has nothing to do with it. Transitivity plays no role in this exercise.

The reflexive part of the question is easy. A relation is reflexive if it includes (1,1), (2,2), ..., (6,6). Not much to count here.
The anti-symmetric part is a little more difficult. That's why I suggested you look at a pair, {1, 2}, and see what the possibilities are for including (1,2) and/or (2,1) in a relation, while keeping the relation anti-symmetric.
Once that is done, determine the number of available pairs.
I don't know if I am misreading the question but I think that we have to count the relations
Samy_A said:
(1,2),(2,1) can't be in the relation because you are asked to count reflexive and anti-symmetric relations. Transitivity has nothing to do with it. Transitivity plays no role in this exercise.

The reflexive part of the question is easy. A relation is reflexive if it includes (1,1), (2,2), ..., (6,6). Not much to count here.
The anti-symmetric part is a little more difficult. That's why I suggested you look at a pair, {1, 2}, and see what the possibilities are for including (1,2) and/or (2,1) in a relation, while keeping the relation anti-symmetric.
Once that is done, determine the number of available pairs.
I got the problem already. I had a very big misconception about reflexivity. I thought that for all a in a set A, if a R (to some element) then aRa, so the relation is reflexive. We have to include every possible (a,a) in the set A, so it's reflexive. At the end I came up with 3^(n choose 2) is the right answer.
 
  • #6
It would have been nice for future readers of the thread to indicate how you got that result.

For a pair of elements, say {1,2}, there are three possibilities that keep the relation anti-symmetric.
1: (1,2) ∈ R and (2,1) ∉ R
2: (1,2) ∉ R and (2,1) ∈ R
3: (1,2) ∉ R and (2,1) ∉ R

There are ##\binom {6}{2}=15## pairs available.
There is only one way to make the relation reflexive, that is include all of (1,1), (2,2), ..., (6,6).

So the total number of reflexive and anti-symmetric relations is 315.
 
  • #7
Samy_A said:
It would have been nice for future readers of the thread to indicate how you got that result.

For a pair of elements, say {1,2}, there are three possibilities that keep the relation anti-symmetric.
1: (1,2) ∈ R and (2,1) ∉ R
2: (1,2) ∉ R and (2,1) ∈ R
3: (1,2) ∉ R and (2,1) ∉ R

There are ##\binom {6}{2}=15## pairs available.
There is only one way to make the relation reflexive, that is include all of (1,1), (2,2), ..., (6,6).

So the total number of reflexive and anti-symmetric relations is 315.
Ok, I will post my solution in future threads.
 

1. What is a math proof about relations?

A math proof about relations is a logical and rigorous method used to demonstrate the validity of a relationship between mathematical objects or concepts. It involves using known axioms, definitions, and previously proven theorems to arrive at a conclusive statement.

2. Why are math proofs about relations important?

Math proofs about relations are important because they provide a solid foundation for mathematical arguments and help to establish the truth of mathematical statements. They also allow for the discovery of new relationships and can lead to further advancements in mathematics.

3. What are the different types of relations that can be proven in math?

There are several types of relations that can be proven in math, including reflexive, symmetric, transitive, and equivalence relations. Other types of relations that can be proven include partial orders, total orders, and functions.

4. How are math proofs about relations constructed?

Math proofs about relations are constructed using a series of logical steps, starting from basic definitions and axioms and building upon them with the use of previously proven theorems. The proof must be clear, concise, and follow a logical flow to arrive at a conclusive statement.

5. Can math proofs about relations be applied to real-world problems?

Yes, math proofs about relations can be applied to real-world problems, particularly in fields such as computer science, engineering, and physics. By establishing the validity of relationships between mathematical objects or concepts, these proofs can be used to solve complex real-world problems and make accurate predictions.

Suggested for: Math proof about relations

Replies
14
Views
370
Replies
1
Views
699
Replies
32
Views
1K
Replies
12
Views
1K
Replies
3
Views
1K
Replies
5
Views
863
Replies
19
Views
1K
Replies
3
Views
965
Back
Top