All Questions
Tagged with order-theory discrete-mathematics
260
questions
0
votes
3
answers
98
views
How to phrase the proof of $m \lt n$ if and only if $m \le n-1$
I have been reading Knuth's "The Art of Computer Programming" and in the mathematical preliminaries chapter of volume 1 there is on page 476 the answer to an exercise where he states
... ...
- 3
0
votes
0
answers
22
views
If sub-universe $S$ of lattice has congruence $\theta$, does the lattice have a congruence $\lambda = \theta \cap S^2$? [duplicate]
Let $(L, \lor , \land )$ be a lattice and $S$ a sub-universe of the lattice. A sub-universe of a lattice will be any subset of the lattice set that is non-empty and closed under $\land$ and $\lor$. ...
- 3,468
0
votes
0
answers
41
views
Understanding the definition of congruences over a lattice
Let $(L, \land, \lor)$ a lattice and $\theta$ a binary relation over $L$. We say $\theta$ is a congruence iff
$$
x_0\theta x_1, y_0 \theta y_1 \Rightarrow (x_0 \lor y_0)\theta(x_1 \lor y_1)
$$
(and ...
- 3,468
0
votes
1
answer
45
views
Number of lattices over a finite set
I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality.
For instance, how many lattices over $\{1, 2, 3\}$ are ...
- 3,468
0
votes
0
answers
20
views
Optimization of totally ordered set valued function.
I am familiar with the meaning of optimizing a function $f : \Omega \to \mathbb{R+}$. However I was just wondering if there's some theory of math explaining how to optimize mapping from $f : \Omega \...
- 5,317
0
votes
0
answers
19
views
$P = (X, \leq)$ ... vertex-edge partial order of the graph $W_4$, $\text{dim}(P)$=?
Let $P = (X, \leq)$ be a vertex-edge partial order of the graph $W_4$. Calculate $\text{dim}(P)$.
All the theory we have covered:
Let $G$ be a graph. The vertex-edge incidence partial order $P = (X, \...
user1308280
1
vote
0
answers
28
views
Relabel According to the Order of First Occurrence
Let $a\in\mathbb R^n$ be a tuple of length $n\in\mathbb Z_{>0}$. Let $X=\{a_i:1\le i\le n\}$ be the set of elements of $a$. For $x\in X$ let
$$i(x)=\min\{j:a_j=x\}$$
be the first occurence of $x$ ...
- 3,633
3
votes
2
answers
113
views
Is $\emptyset : \emptyset \to \emptyset$ an isomorphism from $(\emptyset, \leq)$ to $(\emptyset, \leq)$?
I was asked to determine whether the following statement is true:
If every function $F : P \to P$ is a homomorphism from $(P, \leq)$ to $(P, \leq)$, with $\leq$ an arbitrary order, then $|P| = 1$.
...
- 3,468
0
votes
0
answers
43
views
Proof of non-isomorphic orders
Task: Let $A = \{(n, k) ∈ N × N : k \leq n\}$ and $B = \{(n, k) ∈ N × N : n \leq k\}$. Consider the restriction of the lexicographic order $N ×_{lex} N $to these sets: a pair $(n_1, k_1)$ is less than ...
1
vote
1
answer
124
views
Partial orders and isomorphisms
Task: An element of order is called distant if it is greater than an infinite number of limit elements and less than an infinite number of limit elements.
a) Prove that with isomorphism
of orders, ...
4
votes
2
answers
116
views
Non-isomorphisms of orders
Task: Let A = $\{ (x, y) \in \mathbb{N} \times \mathbb{N} : x ⩾ y \}$ and
B = $\{ (x, y) \in \mathbb{N} \times \mathbb{N} : x ⩽ y\}$ . Consider the restriction
of the lexicographic order $\mathbb{N} \...
- 470
2
votes
0
answers
139
views
Partial orders and antichains
Task:
Let $(P, ⩽_{1} ), (P, ⩽_{2} )$ be such partial orders on one set (nonempty)
that the size of the maximum antichain in the first is $k_{1}$ , in the second is $k_{2}$ . Is it true that the size ...
- 470
1
vote
1
answer
233
views
Antichains and chains in partial orders
Task: Give an example of a partial order in which there are exactly two antichains of size 10, and these antichains do not intersect; and there are exactly 100 chains of size 3 (the size of the chain ...
5
votes
1
answer
113
views
Strict order and adjacent elements
Task: Prove that there is no strict order on 14 elements in which there are exactly 50 pairs of adjacent elements.
Some clarifications: Elements x, y of order (X, <) are adjacent if x < y and ...
- 470
2
votes
0
answers
88
views
Strict partial order and strict linear order
Task :
A binary relation on a set of 7 elements contains exactly 20 pairs.
Could it be :
a) a strict partial order relation?
b) a relation of strict linear order?
In strict linear order, any pair of ...
- 470