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

Click For Summary
SUMMARY

The discussion centers on the properties of reflexive and anti-symmetric relations in set theory, specifically whether all elements in a chain defined by a reflexive and anti-symmetric relation are equivalent. The relation R is defined on a set A, and the chain consists of elements (x, b0), (b0, b1), ..., (bn, x). The conclusion drawn is that if R is reflexive and anti-symmetric, all elements in the set Z = {b0, b1, ..., bn} must be equal, as demonstrated through various examples including the "divides" relation and the standard "less than or equal to" relation.

PREREQUISITES
  • Understanding of reflexive relations in set theory
  • Knowledge of anti-symmetric relations and their implications
  • Familiarity with ordered pairs and chains in relations
  • Basic proof techniques in mathematics, particularly proof by contradiction
NEXT STEPS
  • Study the properties of reflexive relations in depth
  • Explore anti-symmetric relations and their applications in set theory
  • Learn about proof techniques, especially proof by contradiction
  • Investigate specific examples of ordered relations, such as divisibility and order relations
USEFUL FOR

Mathematics students, particularly those studying set theory and relations, as well as educators looking to deepen their understanding of reflexive and anti-symmetric properties in mathematical proofs.

pandaBee
Messages
23
Reaction score
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
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.
 

Similar threads

  • · Replies 24 ·
Replies
24
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 7 ·
Replies
7
Views
1K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 35 ·
2
Replies
35
Views
5K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 5 ·
Replies
5
Views
4K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 7 ·
Replies
7
Views
3K