# 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.

268 questions
Filter by
Sorted by
Tagged with
17k 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$ ...
426 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$ ...
18k 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 ...
30k 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 ...
46k 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 ...
30k 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 ...
8k 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 ...
36k 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.
278 views

### $x\sim y\iff x^2\equiv y^2\pmod{\!6}$ is an equivalence relation.

Question 1: Let $x,y \in S$ such that $x\sim y$ if $x^2 =y^2\pmod6$. Show that $\sim$ is an equivalence relation. This is what I tried: Reflexive: $x^2\pmod6 = x^2$ implying $x\sim x$ Symmetry: ...
2k views

### The “Empty Tuple” or “0-Tuple”: Its Definition and Properties

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)) In axiomatic (ZFC) set theory, we define ...
5k 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 ...
50k views

### How to check whether a relation is transitive from the matrix representation?

$$\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}$$ This is a matrix representation of a relation on the set $\{1, 2, 3\}$. I have to determine if this relation matrix is ...
62k views

### Example of a relation that is symmetric and transitive, but not reflexive [duplicate]

Can you give an example of a relation that is symmetric and transitive, but not reflexive? By definition, $R$, a relation in a set $X$, is reflexive if and only if $\forall x\in X$, $x\,R\,x$. $R$ ...
41k views

### How Many Symmetric Relations on a Finite Set?

How many symmetric relations are there for an $n$-element set? Thank you.
107k views

10k views

### Finding all posets on a set

Suppose I have a set $A$ such that $A$ = $\{1, 2, 3, 4, 5\}$ (or $A$ = $\{1, 2, 3, 4\}$ or $A$ = $\{1, 2, 3\}$ or any other finite small set). How can I find the total number of partial order ...
2k views

### Distinguishing equality and isomorphism as relations

Is this relational characterization of equality in Wikipedia accepted? The identity relation is the archetype of the more general concept of an equivalence relation on a set: those binary ...
355 views

### How to prove reflexivity, symmetry and transitivity for the following relation? [closed]

I would like to know how to prove reflexivity, symmetry and transitivity for $\sim$ according to the following definition: Suppose $\sim$ is defined on the set of the integers as follows : $a\sim b$...
1k views

### Branch of math studying relations

There are many branches of mathematics (analysis, algebra, group theory, logic, ...). Now, I'm interested in relations and their special kinds (like equivalence relation) and their properties. I'd ...
226 views

### Equivalence relations on classes instead of sets

Can someone please explain to me how to deal with equivalence relations on classes instead of sets? Is there some sort of generalisation of relations? Thank you
473 views

### How to prove partition into $A_k=\{2^kn | n \in \mathbb N \text{ and }n\text{ is odd}\}$

I am having trouble showing that this is a partition: $\{A_k|k\in \mathbb N \cup \{0\}\}$ where each $A_k=\{2^kn | n \in \mathbb N \text{ and n - odd}\}$ is a partition of the natural numbers. I ...
2k views

### Cardinality of relations set

I was thinking about cardinality of all symmetric relations, for example in $\mathbb{Z}$. I know, that if I have finite set (which contains $n$ elements), there are $2^{\frac{n(n+1)}{2}}$ symmetric ...
1k 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$...
208 views

### What's the name for the equivalence induced by a function on its domain?

Any function $f$ with domain $X$ induces an equivalence relation on $X$, with classes $$\{f^{-1}(\{y\})\,:\, y \in \operatorname{im}f\;\} .$$ Is there a name for this equivalence? Thanks!
64 views

### How many functions are possible to create in this example?

Let $A = \{ 1,2,3,4 \}$ Let $F$ be a set of all functions from $A \to A$. Let $S$ be a relation defined by : $\forall f,g \in F$ $fSg \iff f(i) = g(i)$ for some $i \in A$ Let $h: A \to A$ be the ...
56k 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 ...
4k views

### Why is belonging not transitive?

From Halmos's Naive Set Theory, section 1: Observe, along the same lines, that inclusion is transitive, whereas belonging is not. Everyday examples, involving, for instance, super-organizations ...
2k views

It seems to me that Russell's paradox rather is a "paradox" concerning relations. Suppose we want to construct a graph (with finite or infinite number of nodes) and want some node to be adjacent ...
384 views

5k views

665 views

### Direct products in the category Rel

Please describe direct products in the category Rel.
On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...