Questions tagged [relations]

This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric…), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

228 questions
13k 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$ ...
14k 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 ...
25k 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 ...
7k 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 ...
38k 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 ...
27k 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 ...
4k 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 ...
38k 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 ...
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 ...
35k views

How Many Symmetric Relations on a Finite Set?

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

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: ...
85k views

1k 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 ...
296 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 ...
37k views

Example of a relation that is symmetric and transitive, but not reflexive

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$ ...
201 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
392 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 ...
7k 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 ...
197 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!
58 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 ...
881 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 ...
375 views

Does $\neg(x > y)$ imply that $y \geq x$?
Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x)$$ In accordance ...