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.
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 ...
1
vote
2answers
57 views
What is the number of equivalence classes formed by a merge
I have this question related to the number of equivalence classes of equivalence relations. If $R_1$ and $R_2$ are two equivalence relations on a set $A$ with number of equivalence classes of $R_1 = ...
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 - ...
2
votes
1answer
44 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 ...
2
votes
1answer
25 views
Proof for a creating a partition of a countable set using chains in partial orders.
Definition: A partition of a set $A$ is a set of nonempty subsets of $A$ called the
blocks of the partition, such that
every element of $A$ is in some block, and
if $B$ and $B'$ are different ...
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
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 ...
1
vote
1answer
65 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
1answer
20 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 ...
1
vote
1answer
54 views
What's the payoff associated with the definition of a relation as an ordered triple?
We can define a binary relation as a set of ordered pairs. Alternatively, we can call the set of ordered pairs the "graph" of the relation, and define the relation itself as a triple $(X,Y,f)$, where ...
1
vote
1answer
72 views
Transitive closure and invertible function
I have some questions as follow...
1) How could I prove transitive closure $t(R)=R^+$, where $R^+=\bigcup_{k=1}^{\infty}R^k$, $R\subseteq A\times A$?
2) Prove or disprove: For any subset ...
0
votes
1answer
25 views
Prove that every antisymmetric relation is weakly antisymmetric
antisymmetric: if, for all x,y∈X, if xRy holds, then yRx does not
weakly antisymmetric: if, for all x,y∈X, if xRy and yRx hold, then x=y
0
votes
1answer
44 views
The proper subset relation and strict partial order
The proper subset relation, $\subset$, defines a strict partial order on the subsets of $[1,6]$, that is $pow[1,6]$.
(a) What is the size of a maximal chain in this partial order? Describe one.
(b) ...
0
votes
1answer
125 views
Construct a new relation from several relations
Let $f_0,\dots,f_{n-1}$ are relations, where $f_i$ is a relation of arity $m_i$ for every $i=0,\dots,n-1$.
How to construct an $(m_0+\dots+m_{n-1})$-ary relation from them?
For my previous erroneous ...
5
votes
0answers
182 views
How to prove an extension of ZFC is conservative
Working in ZFC.
I've defined a function-like binary predicate $R$ on a proper class. It has to be recursive; i.e. $R(a,b)$ must usually depend on one or more $R(c,d)$ for some $c$s and $d$s ...
4
votes
0answers
56 views
Directed and projective limit in Rel
I'm looking for the directed (or equivalently projective) limit of a directed family of relations in the category of sets with relations between them.
Consider a family $\{ R_{ij} \subseteq U_i ...
3
votes
0answers
47 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
0answers
118 views
Equivalence of norms is a equivalence relation
Two norms $||-||_1 $, $||-||_2$are equivalent if:
for two constants $a,b$ and $x$ from $V$ a vector space over a field it holds that : $$a||x||_1\leqslant ||x||_2\leqslant b||x||_1.$$
This is a ...
2
votes
0answers
139 views
Examples of proofs by induction with respect to relations that are not strict total orders.
I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
2
votes
0answers
66 views
What is a binary relation like whose reflexive transitive closure is a partial order?
Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order.
Intuitively, a ...
2
votes
0answers
136 views
How to describe all continuous maps from T to T'?
How to describe all continuous maps from $T'$ to $T$, where $T=\mathbb{R}$ with natural topology (base given by the intervals $(a,b)$ ), and $T'=\mathbb{R}$ with the topology with basis given ...
1
vote
0answers
44 views
Prove that for any $W\in Q$, there exist a bijection $f:[0]\to W$
Suppose $R$ be the relation on $[0,1)$ s.t. $aRb\iff a-b$ is rational. Let $[0]$ be the equivalence class with respect to relation $R$ on $[0,1)$. Let $Q$ be the set of all equivalence class on [0,1). ...
1
vote
0answers
52 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 ...
1
vote
0answers
69 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
0answers
37 views
Find the Equivalence Class of b.
Let $x,y \in \Bbb R$ and $xby \Leftrightarrow \exists k\in \Bbb Z \ tg(x)+k=tg(y)$.
Find $[x]_b$.
1
vote
0answers
70 views
Total order and inf,min,max,sup of set?
i have a relation $\mathbb{R\subseteq M\times M}$ , which is not even a partially order :
$M=\{x\epsilon\mathbb{R}$:$-3$$\leq x\leq3\}, R=\{(x,y):x>y\}$
Well what i'm trying to do; to make this ...
1
vote
0answers
73 views
Partially ordered set proof
I'm trying to proof if the following Relations R ⊆ M×M total order or partially order are.
$M = \{1,2,3\} , R = \{(x,y) : x|y\}$
$M = {\bf Z} , R = \{(x,y) : x\vert y\}$
$M = {\bf N}, R = \{(x,y): y ...
1
vote
0answers
57 views
Properties Of Relations
The question asks if there can be a relation on a set that is neither reflexive or irreflexive. The example the book give makes perfect sense: "Yes, for instance{(1,1)} on{1,2}."
I was wondering, if ...
1
vote
0answers
73 views
positive definite binary matrix
What are the conditions for a binary matrix $A$ (matrix with elements 0 or 1) to be positive definite (not even symmetric), i.e.
$\forall x\neq 0, x^TAx>0, A_{ij}\in \{0,1 \}$
Put it another way, ...
1
vote
0answers
38 views
Product of relations described in categorical terms?
Can cartesian product of several (not necessarily binary) relations be described in categorical terms?
Don't propose me direct product in the category Set, as it does not preserve the structure of ...
1
vote
0answers
59 views
About function inj, surj and something else. Is this exercise resolved correctly?
This is my problem:
For every couple of integers
$(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ we denote with
$r(a,b)$ the remainder of the division between $a$ and $b$. Consider
the ...
1
vote
0answers
50 views
Term for generalized antisymmetry?
As I understand it, a binary relation $R$ over a set $A$ is antisymmetric if for all $a, b \in A: aRb \land bRa$ implies $a = b$.
Now, suppose that I have an equivalence relation $E$ over the set ...
0
votes
0answers
51 views
Is lexicographic order complete?
I was wondering, if the lexicographic order in $\mathbb{R}^2$ is complete or not? I guess it isn't but I dont find any counterexample.
Complete means: For every partition of $M$ into two disjoint ...
0
votes
0answers
8 views
Given $R=(G_R,A,B)$ and $S=(G_S,A,B)$, how to prove that $(D_R-D_S)\subseteq D_{R-S}$
Recently, while looking for random relations exercises, I found this one:
Given $R=(G_R,A,B)$ and $S=(G_S,A,B)$, how to prove that
$(D_R-D_S)\subseteq D_{R-S}$
Which is different from any ...
0
votes
0answers
83 views
where are all Hasse diagram tables of n elements posets and lattices?
n=1,2,3 there are only 1 isomorphism lattice
n=4 there are all 2 kinds of isomorphism lattice
how about n=5,6,7....
I need the Hasse diagram below n=50 ,help me!
0
votes
0answers
106 views
Provide examples of non-equivalence of certain set-theoretic concepts
A free star $S$ on a set $A$ is a collection of subsets of $A$ such
that:
$\emptyset \notin S$;
$\forall X, Y \in \mathscr{P} A : X \cup Y \in S \Leftrightarrow X \in
S \vee Y \in S$.
Let $I$ is ...
0
votes
0answers
99 views
Simplify a set-theoretic formula
Let $a\in\mathscr{P}\prod A$ is an $n$-ary relation (where $A$ is an $n$-indexed family of sets) and $f$ is an $n$-indexed family of functions.
Can the formula defining the following predicate (for ...
