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.
0
votes
1answer
45 views
I need help with relations
Let $S$ be the power set $P({1,2,...,10})$; that is, $S$ is the set of all subsets of $\{1,2,\dots,10\}$. define the relation $\mathcal R$ on $S$ by:
For all subsets $A,B$ of $\{1,2,\dots,10\}$, ...
0
votes
1answer
37 views
is this symmetric
A is the set of all functions $\mathbb{R}$ $\to$ $\mathbb{R}$
f is related to g if and only if f(x) $\le$ g(x) for all x $\in$ $\mathbb{R}$
I said its reflexive since it is less than OR equal, so ...
0
votes
3answers
55 views
I dont understand equivalence classes with relations
I am not quite understanding equivalence classes. For example I have this problem:
Let $A$ be the set of integers and
$\quad a\;R\;b\quad$ if and only if $\quad |a| = |b|$.
I have proved that this ...
0
votes
1answer
32 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 ...
0
votes
1answer
29 views
Symmetric, transitive and reflexive properties of a matrix
Say I had a relation A = matrix
| a b |
| c d |
where a,b,c,d elements of R (real numbers)
Where X is related to Y if and only if det(X) = det(Y) (where det(A) means ad-bc)
So I say its ...
-3
votes
2answers
32 views
general properties of equivalence relations
let ~1 and ~2 be distinct equivalence relations on A. Define ~3 by a ~3 b iff a ~1 b and a ~2 b. prove that ~3 is an equivalence relation on A. if [x]i denotes the equivalence class of x for ~i (i = 1 ...
0
votes
1answer
30 views
is a relation R total/linear/well-order
Let $\mathcal{R}$ be a relation on $\mathbb{N}\times \mathbb{N}$ i.e $\mathcal{R}\subseteq(\mathbb{N}\times \mathbb{N})\times (\mathbb{N}\times \mathbb{N})$ s.t $(x,y)\mathcal{R}(z,w)$ iff $x<z$ or ...
1
vote
0answers
18 views
Six notions of closure associated with every binary operation (more generally, with every ternary relation).
Let $X$ denote a set and consider a ternary relation $\phi \subseteq X^3.$ If you're more comfortable thinking of binary operations, just imagine that $\phi(x,y,z) \leftrightarrow x*y=z$ for some ...
7
votes
1answer
82 views
Is there a name for relations with this property?
Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
3
votes
1answer
29 views
Suppose $B_1 \subseteq A$, $B_2 \subseteq A$, $\sup(B_1)=x_1$ and $\sup(B_2)=x_2$. Prove that if $B_1 \subseteq B_2$, then $x_1 Rx_2$
I'm having trouble with the following proof:
Suppose $\mathcal{R}$ is a partial order on A, $B_1 \subseteq A$, $B_2 \subseteq A$, $\sup(B_1)=x_1$ and $\sup(B_2)=x_2$. Prove that if $B_1 \subseteq ...
2
votes
2answers
36 views
Let $A$ be a set, $R$ an empty relation on $A$, what is $A/R$?
Let $A=\{0,1,2\}$ be a set and $R=\{\}$. I know that $R$ is not an equivalence relation, but does it have to be? What is $A/R$ if $R$ is empty?
Examples:
$R_1=\{(0,0),(1,1),(2,2)\}$, $A/R_1=\{[0], ...
2
votes
2answers
83 views
Partitions of a Set
Is it true that only kind of relations that can completely and uniquely define a partition in a set is the equivalence relation ?
I'm having a hard problem believing that.
Given an ...
6
votes
4answers
170 views
Is it a Transitive Relation?
I need clarification.
Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$.
Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
1
vote
1answer
36 views
composite function with conditional IF
I've been wrapping my head around my Computer and Logic Essentials class, I can do most composite functions, however there is one question that I'm confused with.
It has an if statement inside it:
...
3
votes
1answer
33 views
Showing $(a,b) \sim (c,d) \implies (a+e,b+f)\sim(c+e,d+f)$
I have this equivalence relation (this one is proven already):
$(a,b) R (c,d) ⇔ a + d = b + c$
and now I need to show that for $(a,b),(c,d),(e,f) ∈ ℕ x ℕ$:
$(a,b)R(c,d) ⇒ (a+e,b+f)R(c+e,d+f)$
What I ...
0
votes
2answers
43 views
Elementary Set Theory - Relations
I'm not exactly sure what to search for this problem I'm having, as I don't know the keywords, so I figured the best action would be to ask a question.
I have this question:
...
1
vote
2answers
31 views
Functions and Relations 2
A relation R is defined on ordered pairs of integers as follows :
$(x,y) R(u,v)$ if $x<u$ and $y>v.$
Then R is
Neither a Partial Order nor an Equivalence relation
A Partial Order but not a ...
3
votes
2answers
45 views
transitivity of commutator
I remember a quantum mechanics lecture where my professor said "Two matrices $A, B$ which commute with a third matrix $C$, $[A,C]=[B,C]=0$, commute with each other: $[A,B]=0$." I pointed out the ...
2
votes
1answer
44 views
Proving this realtion is not a transitive relation
I have trouble proving how the following statement is false:
The relation $g = \{\,(x,y)\in \Bbb R\times\Bbb R\mid y = x^2\,\}$ is transitive.
I know you have to use $yRx$, $zRy$, and $xRz$, but I'm ...
2
votes
3answers
77 views
Proof of $\;\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$
The relation $\;\sqsubset\;\subseteq S\times S$ is asymmetric if
$$\forall a,b\in S:(a,b)\in\sqsubset\rightarrow (b,a)\notin\sqsubset$$
and it is antireflexive if
$$\forall a\in ...
1
vote
3answers
100 views
If a relation is reflexive is it symmetric and transitive?
If a relation is reflexive is it symmetric and transitive ?
let ~ means " in relation with "
if A is a set , ~ is a relation on $A$, prove that:
if $a$~$a$ for any $a$ $\in$ A then
1- $x$~$y$ ...
1
vote
1answer
47 views
what if geometric sequence + geometric sequence
I wrote a program that basicly can find the formula of the sequence that created with any-degree equation.
For example if you give my program that sequence:
[1926, 2811, 833240, 28778265, 398155842, ...
1
vote
1answer
34 views
Definition of correspondence
A one-to-one correspondence is an alternative name for a bijection between two sets, but to what does the term 'correspondence' alone refer? As far as I can see, it seems to be another term for ...
2
votes
1answer
23 views
Are these partially ordered set or equivalence relation?
I) {${((a,b),(c,d)) ∈ (\Bbb Q × \Bbb Q)² : (a<c) ∨ ( a = c ∧ b ≤ d)}$}
II) {${(f,g) ∈ \Bbb Q→\Bbb Q × \Bbb Q→\Bbb Q: ∀x ∈ \Bbb Q : f(x) ≤ g(x)}$}
III) {(a,b) ∈ $\Bbb Z$ × $\Bbb Z$ : n devides a - ...
4
votes
2answers
29 views
$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$ If R is symmetric, must S be symmetric?
I'm working on an exercise from How To Prove It by Velleman, and I'm having a hard time.
Suppose $R$ is a relation on $A$ and define a relation S on $\mathcal{P}(A)$ as follows: $$S=\{(X,Y) \in ...
0
votes
2answers
23 views
Domain of a Relation from A to B
The latest versions of Susanna S. Epp's Discrete Mathematics book (both the First Brief Edition, and the full Applications 4th edition) define a relation from $\mathcal{A}$ to $\mathcal{B}$ as a ...
1
vote
2answers
35 views
Integer proof equivalence class
I've been searching online but I couldn't find help on this matter.
How can I prove that $[(a,b)]+[(c,d)]=[(a+c,b+d)]$ is independent of the choice I make of representatives of the equivalence ...
1
vote
2answers
41 views
Function - Test of Transitivity
Relation R in the set N of natural numbers defined as
R = $\{(x, y): y = x + 5 $and $x < 4\}$
We can make set : (1,6)(2,7)(3,8)
Is this a transitive function please guide..
4
votes
1answer
31 views
Is this relation an Equivalence relation?
{(A,B) : A, B ⊆ X, there is a bijective f : A → B}, X is limited.
I have to show if this is (for proving that's an equivalence relation):
$R ⊆ X \times X$
I) reflexive (if $∀x ∈ X : (x, x) ∈ R$)
...
2
votes
1answer
37 views
Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.
Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.
First, I'm wondering if my proof is correct? Second, I'm really ...
1
vote
1answer
52 views
Equivalence relation homeomorphisms
Is said to be $X\approx Y$ ($X$ is homeomorphic to $Y$) iff exists a function $h: X \longrightarrow Y$ which is bijective and preserves open sets, this relationship is an equivalence relation on $Top$ ...
1
vote
2answers
34 views
Do not understand what this question is asking… or the notation, Discrete Structures/Relations
Let X = {1,2,....,10}
Define a relation R on X x X by (a,b)R(c,d) if a + d = b + c
I lose track of what it is asking on the part italicized.
I have a similar question that ends in ad = bc as well ...
3
votes
2answers
36 views
Functional relations : Trouble seeing transitivity
I've been given the following domain: $\;\{1,2,3,4\}$
And the following relation:
$$\{(1,1),(1,3),(1,5),(2,2),(2,4),(3,1), (3,3),(3,5),(4,2),(4,4),(5,1),(5,3),(5,5)\}$$
It states that this is an ...
1
vote
1answer
33 views
How can I show that this is a partial order?
Let $S$ be an arbitrary amount and define the relation $R \subseteq \mathcal{P}(S) \times \mathcal{P}(S)$ so that $(A,B) \in R$ if and only if $A \supseteq B$. Here $\mathcal{P}(S)$ is a spelling for ...
2
votes
2answers
36 views
Name of the order with irreflexivity, antisymmetry and transitivity?
I have an order otherwise poset aka partial order but it is irreflexive so relationships such as 1R1 and 2R2 are impossible. What is the name of this order?
1
vote
1answer
67 views
A generalization of Galois connections
Let $f(x)\ast y \Leftrightarrow x\ast g(y)$ for some binary relation $\ast$ and functions $f$ and $g$. This is a generalization of Galois connections.
Are things like this studied before?
Note that ...
1
vote
2answers
34 views
Equivalence relation proofs: general or specific?
I'm confused about whether a specific example must exist to prove an aspect of an equivalence relation.
For example: if a set, $A$, only contains one element, $A = \{1\}$, and a relation, $R$, on ...
0
votes
1answer
87 views
Relational Sets for Reflexive, Symmetric, Anti-Symmetric and Transitive
I just want to brush up on my understanding of Relations with Sets. Specifically with this set:
$\{ 1, 2, 3 \}$
I understand Reflexive, Symmetric, Anti-Symmetric and Transitive in theory. But if ...
4
votes
1answer
50 views
How does one charaterize functionhood (etc.) in the category of relations?
Question: How can I complete the following sentence: "For all $\mathsf{Rel}$-arrows $f : X \rightarrow Y$, $f$ is a function iff ..."?
Of course, this is easily done: "For all $\mathsf{Rel}$-arrows ...
1
vote
4answers
105 views
Is there a bijective function where $f: \mathbb Q \to \mathbb Q \setminus \{0\}$
$f(x) = {1\over x}$ should be wrong, as the function isn't defined for $0$. Another could be: $f(x) = 2^x$, but is there anything else except functions of this type?I was thinking of something with ...
0
votes
2answers
44 views
Proving symmetry of Relation and Inverse Relation
Why is this a flawed proof?
Knowing that $a$ is an element in $A$ and $b$ is an element in $B$. $R$ being a symmetric binary relation:
“Consider any $a$ and $b$ such that $aRb$.
Since $R$ is ...
2
votes
1answer
45 views
“Lexicographic order” without priority, but with ties, how to define / what's the name?
I'm searching for an ordering principle which combines two (or more) preorders, akin to the lexicographic order, but not quite: I'm looking for an ordering principle that does not priorities, but ...
0
votes
3answers
44 views
Relations: Reflexive, symmetric, transitive
I am having difficulties determining if this relation is reflexive, symmetric, transitive, or none of these.
Let A be the set of all strings of $0's$, $1's$, and $2's$ of length $4$. Define a ...
1
vote
1answer
74 views
Correct my proof : Reflexive, transitive, symetric closure relation
Let R be a relation on a set A. True or False ? If true give a proof else give a counter proof.
A) Let S be a reflexive closure of R, T is the symetric closure of S, U is the transitive closure of T. ...
1
vote
1answer
26 views
Binary Relations and Total Orders [duplicate]
This question has two parts:
1)
i) Given a relation $<$, define a relation $\leq$ by setting x $\leq$y if and only if x$<$y or x = y. Prove that if < satisfies transitivity and 'trichotomy' ...
1
vote
1answer
80 views
Determine the number of binary relations on $A \times A$ that satisfy the following: [duplicate]
Let $|A| = 8$.
Determine the number of binary relations on $A \times A$ that satisfy the following:
A) Symmetric
B) Neither reflexive or irreflexive
C) Reflexive and symmetric
D) Irreflexive and ...
0
votes
1answer
58 views
Rational Numbers and Equivalence Classes
Describe the rational numbers as the equivalence classes for an equivalence relation on certain pairs of integers.
0
votes
1answer
62 views
Proving $\;x-y \in2\pi \mathbb Z\;$ defines an Equivalence Relation
Prove that $\;x-y \in2\pi \mathbb Z\;$ defines an equivalence relation on $\;\mathbb R.$
0
votes
2answers
49 views
How can the graph of an equivalence relation be conceptualized?
Consider a generic equivalence relation $R$ on a set $S$. By definition, if we partition $S$ using the relation $R$ into $\pi_S$, whose members are the congruence classes $c_1, c_2...$ then
$aRb ...
1
vote
1answer
21 views
Classify relations “is greater than or equal to”
Classify the following relations as reflexive, irreflexive, symmetric, antisymmetric or transitive. Explain each property in the context of the question.
“is greater than or equal to” on the set of ...
