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.

Filter by
Sorted by
Tagged with
88 votes
6 answers
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$ ...
user avatar
  • 5,548
2 votes
2 answers
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$ ...
user avatar
  • 24.1k
21 votes
4 answers
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 ...
user avatar
  • 369
154 votes
15 answers
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 ...
user avatar
  • 5,582
18 votes
6 answers
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 ...
user avatar
  • 2,586
5 votes
4 answers
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.
user avatar
8 votes
1 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 ...
user avatar
  • 603
9 votes
2 answers
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 ...
user avatar
  • 603
8 votes
4 answers
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 ...
user avatar
  • 809
6 votes
3 answers
1k views

$ (a,b), (c,d) \in \mathbb{R} \times \mathbb{R}\ $ let us define a relation by $(a,b) \sim (c,d)$ if and only if $\ a + 2d = c+2b$

Question: For $ (a,b), (c,d) \in \mathbb{R} \times \mathbb{R}\ $ let us define a relation by $(a,b) \sim (c,d)$ if and only if $\ a + 2d = c+2b$ Is this an equivalence relation on $\mathbb{R} \...
user avatar
0 votes
3 answers
511 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: ...
user avatar
  • 141
7 votes
3 answers
3k 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 ...
user avatar
  • 3,119
14 votes
4 answers
66k 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 ...
user avatar
  • 4,339
16 votes
7 answers
89k 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$ ...
user avatar
  • 1,480
12 votes
4 answers
49k views

How Many Symmetric Relations on a Finite Set?

How many symmetric relations are there on an $n$-element set? Thank you.
user avatar
27 votes
5 answers
126k views

Antisymmetric Relations

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric? $$R = \{(1, 2), (2, 3), (3, 4)\}$$ Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then $...
user avatar
20 votes
1 answer
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$....
user avatar
6 votes
2 answers
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$...
user avatar
  • 28.1k
4 votes
5 answers
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 ...
user avatar
  • 769
12 votes
3 answers
28k views

How to find the number of anti-symmetric relations?

I know that given a set $A = \{1, 2, 3, ... , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 - n}$$ The number of symmetric relations is $$2^{{...
user avatar
  • 341
10 votes
3 answers
4k views

Is statistical dependence transitive?

Take any three random variables $X_1$, $X_2$, and $X_3$. Is it possible for $X_1$ and $X_2$ to be dependent, $X_2$ and $X_3$ to be dependent, but $X_1$ and $X_3$ to be independent? Is it possible ...
user avatar
  • 2,182
9 votes
3 answers
26k views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
user avatar
  • 193
9 votes
4 answers
47k views

Prove that the intersection of two equivalence relations is an equivalence relation. [closed]

I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows. Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R \cap ...
user avatar
4 votes
4 answers
13k views

Why is $y = \sqrt{x-4}$ a function? and $y = \sqrt{4 - x^2}$ should be a circle

So why is it a function, even though for example $x = 8$; you'll have $y = +2$ and $y = -2$. It'll fail the vertical line test. But every textbook considers it as a function. Did I misunderstand ...
user avatar
1 vote
0 answers
374 views

Example relations: pairwise versus mutual

There are by now several questions on math.se asking about pairwise versus mutual relations, eg: • When does “pairwise” strengthen and when does it weaken? • Relation: pairwise and mutually • ...
user avatar
  • 3,272
6 votes
2 answers
3k 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 ...
user avatar
  • 1,081
2 votes
1 answer
1k views

Define a relation and find its equivalence classes.

Define a relation $\sim$ on $\Bbb{N}$ as follows. For any $a,b∈\Bbb N$, $a\sim b$ if and only if $ab$ is a perfect square. Show that $\sim$ is an equivalence relation. What are the equivalence classes?...
user avatar
  • 21
14 votes
2 answers
2k views

How do I define exactly what a function is?

While it is easy to understand what a function is intuitively, I've been trying to wrap my head around how to precisely define what a function is using only mathematical notation. My attempt at this ...
user avatar
4 votes
7 answers
2k views

The map $f:\mathbb{Z}_3 \to \mathbb{Z}_6$ given by $f(x + 3\mathbb{Z}) = x + 6\mathbb{Z}$ is not well-defined

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is not a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ ...
user avatar
  • 1,858
2 votes
2 answers
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 ...
user avatar
  • 3,405
1 vote
3 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 675
19 votes
3 answers
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 ...
user avatar
17 votes
3 answers
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 ...
user avatar
  • 183
16 votes
3 answers
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 ...
user avatar
  • 322
14 votes
1 answer
908 views

Can we extend the definition of a continuous function to binary relations?

Let $X,Y$ be topological spaces. A function $\phi:X\to Y$ is continuous iff for any open subset $A\subseteq Y,$ the preimage $\phi^{-1}(A)$ is open in $X.$ We could similarly define a relation $\rho\...
user avatar
8 votes
3 answers
12k 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 ...
user avatar
11 votes
3 answers
3k views

Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
user avatar
4 votes
2 answers
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 ...
user avatar
  • 3,272
-2 votes
2 answers
525 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$...
user avatar
  • 325
5 votes
1 answer
866 views

The equivalence relation generated by a relation

Let $X$ be a non-empty set and let $r\subseteq X\times X$ be a relation on $X$. Let $R$ be the intersection of all equivalence relations on $X$ that contain $r$. Prove that if $xRy$, then one of the ...
user avatar
  • 4,865
5 votes
2 answers
267 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
user avatar
  • 51
4 votes
4 answers
2k views

Is an Anti-Symmetric Relation also Reflexive?

According to the definition of an Anti-Symmetric Relation if xRy and yRx then x = y Which means, effectively, x is in relation with itself. Does this mean that anti-symmetry implies reflexive ...
user avatar
  • 141
3 votes
1 answer
685 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 ...
user avatar
  • 1,018
4 votes
3 answers
252 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!
user avatar
  • 13.5k
0 votes
2 answers
81 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 ...
user avatar
18 votes
4 answers
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 ...
user avatar
12 votes
2 answers
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 ...
user avatar
23 votes
10 answers
5k 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 ...
user avatar
10 votes
3 answers
7k views

Is the empty set partially ordered ? Also, is it totally ordered?

I am not sure on how to go about this. Please provide clear explanations.
user avatar

1
2 3 4 5
7