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.

learn more… | top users | synonyms

5
votes
2answers
189 views

On the Definition of Posets…

In my book, the author defines posets formally in the following way: Let $P$ be a set, and let $\le$ be a relationship on $P$ so that, $a$. $\le$ is reflective. $b$. $\le$ is transitive. $c$. ...
2
votes
5answers
76 views

A transitive relation $R$ such that $R\circ R\neq R$?

Find an example of a set $A$ and a transitive relation $R$ on $A$ such that $R\circ R\neq R$. $R\circ R$ is the relation such that $(a,c)\in R\circ R$ when $(a,b) \in R$ and $(b,c) \in R$. I know ...
2
votes
3answers
58 views

If $xy = u^2 $and $yz = w^2$, where each variable is a natural number, why is$ (\frac{uw}{y}) $a natural number?

I've just begun learning about equivalence relations, and this note was made in a worked example, but I'm unable to see why $(\frac{uw}{y}) $must also be a natural number. Could someone please ...
3
votes
1answer
64 views

Is there any correlation between $A^B$ and $B^A$?

So, we all know that exponentiation is non-commutative, but is there any relationship despite exponentiation's not being commutative? Is there any correlation between $A^B$ and $B^A$ where $A$ and $B$ ...
1
vote
1answer
101 views

Determining If A Relation Is A Function

I am given the simple relation $f(x)=\sqrt{x}$, where $f$ maps $R \rightarrow R$, and I am suppose to determine whether or not it is a function. I figured that it was a function, because in the ...
3
votes
3answers
2k views

Number of equivalence relations on a finite set

I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible ...
5
votes
3answers
412 views

Equivalence class of polynomials

$X$ is the set of all polynomials over $\mathbb{R}$. We define an equivalence relation on $X$ such that $p$~$q$ iff $p(0)=q(0)$. ($1$) What is the equivalence class of $p(x)=x$? ($2$) Give a ...
3
votes
1answer
426 views

For the relation $R = \emptyset$ on $\{1, 2, 3\}$, is it reflexive, symmetric, transitive?

In the case below, a relation on the set $\{1, 2, 3\}$ is given. Of the three properties, reflexivity, symmetry, and transitivity, determine which ones the relation has. Give reasons. $R = ...
4
votes
2answers
311 views

What is the correct notation for a multivariable function?

Many mathematical texts define a multivariable function $f$ in the following way $$f := f(x,y)$$ However, if we focus on the fact that a function is really a binary relation on two sets, (say the ...
3
votes
1answer
181 views

Diagrammatic (Postfix) Composition of Functions

Consider the functions $f : X \to Y$ and $g : Y \to Z$. According to the Wikipedia articles on Function Composition, the application of $f$ to an input $x$ can be written as $xf$ (as opposed to the ...
1
vote
1answer
90 views

Is this a correct proof for this relation?

I feel like I am being too brief and maybe incorrect on my proof by contradiction for transitivity/antisymmetry. So is this proof flawed in any way? A relation R on the set of positive integers is ...
1
vote
1answer
573 views

Is the relation on the positive integers defined by $(x,y) \in R$ if $x = y^2$ only antisymmetric?

The question in my book says: Determine whether the relation defined on the set of positive integers is reflexive, symmetric, antisymmetric, transitive, and/or a partial order. $x = y^2 ...
5
votes
3answers
211 views

Determine if the following is a partial order, and if so, is it a total order?

I'm having trouble figuring out how I can solve this... I've never been good with formal proofs. $$(\mathbb{R},\preceq), a\preceq b\iff a^{2}\leq b^{2}$$ I can easily see that it's Reflexive: ...
3
votes
2answers
272 views

Properties of Equivalence Relation Compared with Equality

I'm reading about congruences in number theory and my textbook states the following: The congruence relation on $\mathbb{Z}$ enjoys many (but not all!) of the properties satisfied by the usual ...
4
votes
1answer
114 views

What are the usual definitions of minimality and maximality with respect to an arbitrary relation?

Let $\mathcal R$ be a relation on $S$ and let $T \subseteq S$. It seems there are two notions floating around of an $\mathcal R$-minimal element of $T$: $x$ is an $\mathcal R$-minimal element of ...
1
vote
1answer
51 views

Does there exist any elements which I can add to a Relation such that the Relation remains Sym/Anti, Trans, and Reflexive?

Given some set $X$ and relation $R$ If $R = \{(x,x) | x \in X\}$ then we have a relation which is reflexive, transitive, symmetric, and anti-symmetric. Now can I add any elements to the relation ...
2
votes
2answers
101 views

Is there an infinite sequence AB, BC, CD, DX, …, YZ

Is it possible to construct an infinite set of ordered pairs of form S = {(A, B), (B, C), (C, D), (D, x), ..., (y, Z)}? Every element (B, C...) must appear only once as the first object in one of the ...
0
votes
1answer
52 views

Do nets have subsequence?

Let $(P,\leq)$ be a directed set. Is there a cofinal and increasing function $\theta:\mathbb{N}\to P$. if $P$ has any maximal elements it can be proved easily. So I suppose $(P,\leq)$ none of it's ...
0
votes
1answer
72 views

Is $(\prod R_i)\circ (\prod R_i)$ the same as $\prod R_i\circ R_i$?

For each $i\in I$, $R_i$ is a (binary) relation (on a set $X_i$). Is $(\prod R_i)\circ (\prod R_i)$ the same as $\prod R_i\circ R_i$ as relations on $\prod_{i\in I}X_i$?
0
votes
2answers
48 views

Why am I getting that minimal elements are equivalent to the minimum?

I have these two definitions, about minimals and minimums in an order relation: $b$ is minimal in $B<=>¬\exists:(x \in B \land x \prec b)$ and also equivalent to $ \forall x,[(x \in B \land x ...
2
votes
1answer
113 views

Total Ordering and relation

Consider the relation $<$ on $\mathbb{Q}$ defined by: $(m, n) < (j, k) \iff jn-mk \in \mathbb{N}.$ Where $m, j \in \mathbb{N}$ and $n, k\in\mathbb{Z}$ I want to show that $<$ is a total ...
1
vote
4answers
130 views

“Differs in only finitely many terms” an equivalence relation on sequences?

Consider sequences $a : \mathbb{Z}^+ \rightarrow A$ on a set $A$. Define the relation $\sim$ over sequences by $a \sim b$ iff there are only finitely many indices $i$ at which $a_i \neq b_i$. Clearly ...
0
votes
1answer
96 views

Question about relation on rational numbers

Define the relation on $\mathbb{Q}$ by $$[m,n]<[j,k]$$ if and only if $jn-mk$ belongs to $\mathbb{N}$, $j$ and $m$ belong to $\mathbb{Z}$, $n$ and $k$ belong to $\mathbb{N}$. (a) Show that ...
2
votes
4answers
283 views

Showing that $R$ is an equivalence relation on $X \times X$

Let $X = \{1,2,3,..,10\}$ define a relation $R$ on $X \times X$ by $(a,b)R(c,d)$ if $ad=bc$. Show that R is an equivalence relation on $X \times X$. I know that the $R$ have to be reflexive (because ...
10
votes
4answers
362 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
3
votes
4answers
197 views

Are $4ab\pm 1 $ and $(4a^2\pm 1)^2$ coprime?

Let $a\ne b$ be two positive integers. Are $4ab+1$ and $(4a^2+1)^2$ coprime always? Can you find $a$ and $b$ such that they are not coprime? Edit: It has been proved that $4ab-1$ is not a divisor ...
0
votes
1answer
33 views

How do I say mathematically that a binary relation is reflexive?

[Symmetry is easy enough for me (assuming I'm even correct)... $$(\forall(a,b)\in\mathcal{R})[(b,a)\in\mathcal{R}]$$ but I don't know how to say it similarly for transitivity and reflexivity.. ...
1
vote
0answers
86 views

Function on equivalence relation on functions

Let $E$ be the set of all functions from a set $X$ into a set $Y$. Let $b \in X$ and let $R$ be the subset of $E \times E$ consisting of those pairs $(f,g)$ such that $f(b) = g(b)$. Prove that $R$ is ...
2
votes
1answer
219 views

Equivalence relation function

Let $f:X \to X$ be an injective function from a set $X$ into itself. Define a sequence of functions $f^0 , f^1, f^2, \dots : X \to X$ by letting $f^0 = \mathrm{id}$, $f^1 = f$ and $f^n = ...
3
votes
1answer
100 views

Function on equivalence relation

Let $f:X \to Y$ be a surjective function from a set $X$ onto a set $Y$. Let $R$ be the subset of $X \times X$ consisting of those pairs $(x,x')$ such that $f(x) =f(x')$. Prove that $R$ is an ...
2
votes
2answers
101 views

Question about relation on real numbers

Let $R$ be the relation on the set of real numbers such that, $$R = \{(x, y): y = x2\}$$ Is $R$ an equivalence relation? Sorry I'm quite new to discrete maths. What does the $| \;\;|$ mean ...
2
votes
1answer
71 views

Question about relation on certain sets of integers

I'm new to discrete maths and I have a few questions. Let $C = \{x \in\mathbb{Z}: 0 < x < 10\}$ and let $D = \{ y \in\mathbb{Z}: 1 < y < 9\}$, and define a binary relation $S$ from ...
0
votes
1answer
141 views

The Transitive Property. Same relation or not?

Consider $\mathbf{u}, \mathbf{v}, \mathbf{w}$ vectors. If $\mathbf{u}$ and $\mathbf{v}$ are orthogonal, that is $\mathbf{u} \cdot \mathbf{v} = 0$, and the vectors $\mathbf{v}$ and $\mathbf{w}$ are ...
1
vote
2answers
469 views

Is cancellation of Cartesian product possible? I think so, but am having trouble with the proof…

So, Is a cancellation possible for the Cartesian product? ex. if you have two Cartesian products that are equal to eachother, do the 2nd sets for each product equal eachother? Lets say you have ...
0
votes
4answers
101 views

Is this a transitive relation?

$$A = \{foo, bar\}$$ $$R_1 = \{(foo, foo)\}$$ $$R_2 = \{(foo, bar)\}$$ Is $R_1$ transitive on $A$? My gut tells me yes, but I'm not sure if transitivity requires $3$ elements. What about $R_2$? ...
2
votes
1answer
267 views

Help showing this is an equivalence relation

I need help with question as following: $X= \mathbb{Z}\times \mathbb{Z}$ I need to define the relation $R$ on $X$ as follows: $(X_1,X_2)R(Y_1,Y_2) \longleftrightarrow ...
0
votes
3answers
386 views

Domain of a function is all the elements of the first set?

I am reading about functions in the textbook "Discrete Mathematical Structures" by Kolman et.al. They have given in an example that \begin{equation} A=\{1,2,3\} \quad\text{and}\quad B=\{x,y,z\} ...
0
votes
1answer
65 views

an infinite queue preserving equality.

Is there any well-ordered set $(A,\leq)$ such that: $(A,\leq^{-1})$ is well-ordered. $A$ is infinite. there's exactly one function $\theta:A\rightarrow \{0,1\}$ such that 1) for each $a < M$, ...
3
votes
2answers
2k views

Reflexive , symmetric and transitive closure of a given relation

Given a relation $R = \{(x,y)\mid y=x+1\}$ and I have to find the reflexive, transitive and symmetric closure. For reflexive, I added $y=x$ with given condition so now the relation becomes $R = ...
3
votes
2answers
268 views

Would this relation be an equivalence relation?

I am a bit stuck on this one question from my homework and for some reason it isn't making any sense to me. I would really appreciate it if somebody could explain it to me how I can go about to ...
3
votes
1answer
760 views

Modus Ponens: implication versus entailment

Would it be inconsistent to write Modus Ponens using only implication, not entailment? $(p \wedge (p \to q)) \to q$ The way I understand is that implication ($ \to$) is an operator that yields a new ...
-2
votes
1answer
1k views

Proof that mutual statistical independence implies pairwise independence

This question about pairwise vs. mutual relations is related some extant questions: here and here. Kobayashi, Mark & Turin's Probability, Random Processes and Statistical Analysis, 2012, states ...
0
votes
1answer
40 views

Collection of Equivalence relations

I'm lazy about retyping the question so I put a screenshot of it here: Munkres, Topology, Chapter 1, section 3, problem 5(b). Let $\{R_i\}_{i \in I}$ be a collection of equivalence relations with ...
2
votes
2answers
555 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 ...
3
votes
1answer
160 views

Prove transitivity of $\forall X( X\subseteq A\setminus\{a, b\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{b\}\in\mathcal{F}))$

This one is from Velleman's "How to Prove It, 2nd Ed.", exercise 4.3.23. Suppose $A$ is set, and $\mathcal{F}\subseteq\mathcal{P}(A)$. Let $$R=\{(a,b)\in A\times A : \text{for every } X\subseteq ...
0
votes
1answer
198 views

Equivalence Relation? Column-equivalence on the set of all $m\times n$ matrices.

How do I show that column equivalence on the set of all $m\times n$ matrices is an equivalence relation? I know that to show it is an equivalence relation, I need to show that column equivalence is ...
4
votes
3answers
1k 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 ...
1
vote
0answers
144 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 • ...
1
vote
1answer
52 views

Finding a mistake in the incorrect proof for $(S\setminus T)\circ R\subseteq (S\circ R)\setminus(T\circ R)$

This is from Velleman's "How to Prove It", exercise 4.2.11.b). The exercise requires finding a mistake in the proof, but everything looks good to me. Must be that I'm missing some important fact, but ...
2
votes
1answer
104 views

Categories of $n$-ary relations?

Arrows in the category $\bf Rel$ are binary (2-valued) relations between set objects. Do ternary, 4-term, $n$-term and variadic (2-valued) relations form categories? (Or perhaps one category?). It ...