Antisimmetric relations question

In summary, the number of anti-symmetrical relations on a set of ##n## elements, with ##p1## in relation with ##p3## and ##p2## in relation with ##p4## but not ##p1##, is ##2^n\cdot 3^{\binom{n}{2}}##. This is obtained by considering the diagonal possibilities and the upper triangle possibilities separately.
  • #1
doktorwho
181
6

Homework Statement


A set ##P=\left\{ \ p1,p2,p3,p4 \right\}## is given. Determine the number of antisimmetric relations of this set so that ##p1## is in relation with ##p3##, ##p2## is in relation with ##p4## but ##p2## is not in relation with ##p1##.

Homework Equations


3. The Attempt at a Solution [/B]
By drawing the table of relations i concluded that the total number of antisimmetrical relations without any constriction further implied in the problem is ##2^n3^{\frac{n^2-n}{2}}## with the first factor drawn from the diagonal possibilities and the second factpr being 3 possibilities on the upper part above the diagonal. I do not however know how to include these steps. Can you help?
 
Physics news on Phys.org
  • #2
This is the picture as I understand it.
[tex]
\begin{array}{ccc}x&x&1&x\\0&x&x&1\\x&x&x&x\\x&x&x&x\end{array}
[/tex]
You correctly deduce that there are a total of ##2^n\cdot 3^{\binom{n}{2}}## anti-symmetrical relations on a set of ##n ## elements. There's nothing special to this, you have fixed 2 components in the upper triangle bit. Keep in mind what an anti-symmetrical relation matrix has to look like and use the product rule.
 

1. What is an antisymmetric relation?

An antisymmetric relation is a type of binary relation in mathematics that is characterized by the property that if both elements x and y of the relation hold for a pair of elements, then x and y must be equal. In other words, if (x,y) and (y,x) are both in the relation, then x must be equal to y.

2. How is an antisymmetric relation different from a symmetric relation?

An antisymmetric relation differs from a symmetric relation in that it does not allow for both (x,y) and (y,x) to be in the relation unless x and y are equal. In a symmetric relation, both (x,y) and (y,x) can be in the relation regardless of whether x and y are equal or not.

3. Can an antisymmetric relation be reflexive?

Yes, an antisymmetric relation can be reflexive. This means that for every element x in the relation, (x,x) is also in the relation. However, the relation cannot be both antisymmetric and symmetric at the same time.

4. How is an antisymmetric relation represented?

An antisymmetric relation is typically represented using a directed graph or a matrix. In a directed graph, an arrow points from x to y if (x,y) is in the relation. In a matrix, the element at the intersection of row x and column y is 1 if (x,y) is in the relation and 0 otherwise.

5. What are some examples of antisymmetric relations?

Some examples of antisymmetric relations include the greater than or equal to relation (≥) on the set of integers, the divisibility relation (|) on the set of natural numbers, and the subset relation (⊆) on any set. In each of these examples, if both elements x and y hold for a pair, then x must be equal to y.

Similar threads

Replies
18
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
900
  • Precalculus Mathematics Homework Help
Replies
3
Views
639
  • General Math
Replies
6
Views
1K
  • Advanced Physics Homework Help
Replies
15
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • General Math
Replies
2
Views
1K
  • Biology and Chemistry Homework Help
Replies
5
Views
3K
  • Quantum Physics
Replies
1
Views
889
Back
Top