# Questions tagged [relations]

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

318 questions
Filter by
Sorted by
Tagged with
20k views

### Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...
3k views

### Examples and Counterexamples of Relations which Satisfy Certain Properties

Definition: Given a set $X$, a relation $R$ on $X$ is any subset of $X\times X$. A relation $R$ on $X$ is said to be reflexive if $(x,x) \in R$ for all $x \in X$, irreflexive if $(x,x) \not\in R$ ...
21k views

### Understanding equivalence class, equivalence relation, partition

I'm having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
55k views

### Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . . For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have the ...
38k views

### Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
59k views

### Can a relation be both symmetric and antisymmetric; or neither? [closed]

Can some relation be at the same time symmetric and antisymmetric? And, can a relation be neither one nor the other? Please give me an example for your answer.
9k views

### Number of reflexive relations defined on a set A with n elements

Problem: If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it? My solution Is the answer ...
34k views

### If a relation is symmetric and transitive, will it be reflexive? [duplicate]

Possible Duplicate: Why isn't reflexivity redundant in the definition of equivalence relation? We had a heated discussion in class today and i still cant be sure if the professor was any good ...
14k views

### How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it? For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but ...
1k views

38k views

### Prove that the empty relation is Transitive, Symmetric but not Reflexive

Question: Let $R$ be a relation on a set $A$. Prove that if $A$ is non-empty, the empty relation is not reflexive on $A$. the empty relation is symmetric and transitive for every set $A$....
2k views

### Existence of the transitive closure for sets

How can I prove that the transitive close of an arbitrary set $X$ exists? A set $X$ is called transitive if $\in$ is transitiv on it. The transitive closure $\mathrm{tcl}(X)$ of an arbitrary set $X$...
19k views

### Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
28k views

4k views

### Proving this relation is transitive

Let $r$ be a relation on $A \times A$ such that $(a,b) r (c,d) \iff ad = bc.$ How can I show that this relation is transitive, ie. $(a, b)r(c,d)$ and $(c,d)r(e, f) \implies (a,b)r(e,f)$? I tried to ...
1 vote
131 views

### some relation $R$ is defined on $\mathbb{R}$ such that $xRy \iff x = 7^{k}y,$ for some $k\in \mathbb{Z}$. Prove that $R$ is an equivalence relation

some relation $R$ is defined on $\mathbb{R}$ such that $xRy \ \iff \ x = 7^{k}y,$ for some $k\in \mathbb{Z}$. Prove that $R$ is an equivalence relation I'm confused with proving that it is symmetric ...
1k views

### Reflexivity, Transitivity, Symmertry of the square of an relation

$\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$. If $p$ is reflexive/symmetric/transitive ...
70k views

### Is my understanding of antisymmetric and symmetric relations correct?

So I'm having a hard time grasping how a relation can be both antisymmetric and symmetric, or neither. Are my examples correct? symmetric & antisymmetric ...
40k views

### Is the relation $R = \emptyset$ is it reflexive, symmetric and transitive ? Why?

Can someone help me understand the properties of the relation $R = \emptyset$ ? It looks to me like it's not reflexive, since there is no element related to any element, so the elements are not ...
6k views

### Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
908 views

67k views

### Is an anti-symmetric and asymmetric relation the same? Are irreflexive and anti reflexive the same?

I don't understand the difference between an anti symmetric and asymmetric relation. From my understanding, it is asymmetric if there is not any element where: if (x,y) (y,x). But what if you have ...
1k views

### Can we extend the definition of a homomorphism to binary relations?

This is going to be quite a long post. The actual questions will be at the end of it in section "Questions." INTRODUCTION After receiving an answer to this question about extending the definition of ...  