Does a refl/anti-symm relation on a set A have this property?

In summary, the conversation discusses the theorem that states if an ordered relation on a set is both reflexive and anti-symmetric, then all elements sandwiched between two equal elements in a chain are also equal to each other. The conversation includes examples to support this theorem and discusses different approaches to proving it. The proof may involve showing that if x R y R x, then x=y, using the reflexive and anti-symmetric properties of the relation.
  • #1
pandaBee
23
0

Homework Statement


Let ##R## be an ordered relation on a set ##A## that is reflexive and anti-symmetric.
If there is a chain of elements in ##R## that begins and ends with the same element, say the element ##x \in A## is it true that all the elements of ##R## sandwiched in between the ones beginning and ending in ##x## are equal to each other?

Homework Equations


For clarification Let the 'chain' of elements in ##R## be the following:
##(x,b_0), (b_0,b_1), ..., (b_n, x)##
let ##Z = \{b_0, b_1, ..., b_n\}##
If ##R## is a reflexive and anti-symmetric ordered relation are all elements of ##Z## equivalent?

The Attempt at a Solution


I came up with a few antisymmetric, reflexive ordered relations and tested the validity of this argument and it passed in each one so I am guessing that the theorem above may be true since I have not found a counter-example yet. I just have no idea how to express it in a proof. The examples I came up with were:

The set ##G=\{(x,y) \in P\text{ x }P~ |~ x \ \text{genes come from}\ y\}## where ##P## is the set of all people,
The set ##D=\{(x,y) \in ℤ\text{ x }ℤ ~|~x \ \text{divides}\ y\}##
And also the standard less than or equal to ordered relation.

In every case it was implied that if a element of the set under which the relation is ordered under begins and ends a chain of ordered pairs in the ordered relation, then all of the elements are equivalent to one another, as a consequence of anti-symmetry and reflexivity.

I'm unsure of how to start this proof. I've tried defining a set containing all the intermediate elements (in this case being the ##b_j##'s in the set ##Z## and assuming that there is at least two elements that are not equal to one another in the set and trying to find a contradiction, but I ran into a dead end there as well. Any suggestions? Or perhaps someone can think of a counter example ruling out the theorem completely?
 
Last edited:
Physics news on Phys.org
  • #2
I think in general, you only need to show that it is true for any element y such that x R y R x implies that x=y.
I do not have a clear mental image of a rigorous proof, but I would start with the basics:

reflexive means that x R x for all x.
anti-symmetric means that x R y implies y ~R x.
So, x ~R x. If y R x and y ~R x, does this mean y = x?

Also, I think ordering is useful since there should not be anything between x and x in an ordered relation other than more x.
 

1. What is a refl/anti-symm relation on a set A?

A refl/anti-symm relation on a set A is a relation between elements of set A where every element is related to itself (reflexive property) and if two elements are related, their reverse relation is also present (anti-symmetric property).

2. What is the reflexive property of a refl/anti-symm relation?

The reflexive property of a refl/anti-symm relation means that every element in the set is related to itself.

3. What is the anti-symmetric property of a refl/anti-symm relation?

The anti-symmetric property of a refl/anti-symm relation means that if two elements are related, their reverse relation is also present. In other words, if a is related to b, then b is also related to a.

4. Does every refl/anti-symm relation have the same properties?

No, not all refl/anti-symm relations have the same properties. Some may have additional properties, such as transitivity, while others may only have the reflexive and anti-symmetric properties.

5. Can a relation on a set be both reflexive and anti-symmetric but not transitive?

Yes, a relation on a set can be both reflexive and anti-symmetric but not transitive. For example, the "is equal to" relation on the set of integers is reflexive and anti-symmetric, but it is not transitive as not all integers are equal to each other.

Similar threads

  • Calculus and Beyond Homework Help
Replies
24
Views
2K
  • Set Theory, Logic, Probability, Statistics
2
Replies
35
Views
498
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
876
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
2K
Back
Top