Skip to content
June 10, 2009 / porton

Isomorphic filters – open problems

For filters on sets defined equivalence relation being isomorphic.

Posed some open problems like this: are every two nontrivial ultrafilters isomorphic?

Definition.
For any function f : A \rightarrow B we’ll define the function \left\langle f \right\rangle : \mathscr{P} A \rightarrow \mathscr{P} B by the formula (for any set X): \left\langle f \right\rangle X = \left\{ f x | x \in X \right\}.

Definition.
I call filters a and b directly isomorphic when there are a bijection f : \bigcup a \rightarrow \bigcup b such that \left\langle f \right\rangle |_a is a bijection from a to b.

Definition.
Let U, W are sets. Let \mathscr{P} U and \mathscr{P} W are the lattices of all subsets of these sets. Let a and b are filters on the lattices \mathscr{P} U and \mathscr{P} W correspondingly. I will call filters a and b isomorphic when there exist sets A \in a and B \in b such that filters a \cap \mathscr{P} A and b \cap \mathscr{P} B are directly isomorphic.

Obvious. Filters a and b are isomorphic iff there exist sets A \in a and B \in b such that there are a bijection f : A \rightarrow B such that \left\langle f \right\rangle |_{a \cap \mathscr{P} A} is a bijection from a \cap \mathscr{P} A to b \cap \mathscr{P} B.

Remark.
It seems that there exist a simpler definition of isomorphic filters in terms of reloids, but that stumbles on some open problems about reloids.

Proposition.
If two filters are directly isomorphic then they are isomorphic.

Proof.
Take A = \bigcup a, B = \bigcup b. Then a \cap \mathscr{P} A = a and b \cap \mathscr{P} B = b.

Example.
Let \mathscr{P} U is the lattice of all subsets of some set U. Then there are isomorphic filters on \mathscr{P} U which are not directly isomorphic.

Proof.
Consider two filters on \mathbb{N}: a = \left\{ \mathbb{N} \right\}, b = \left\{ \mathbb{N} \setminus \left\{ 0 \right\}, \mathbb{N} \right\}. There are no bijection from a to b because \mathrm{card} a \neq \mathrm{card} b. So a and b are not directly isomorphic.

Now let A = \mathbb{N}, B = \mathbb{N} \setminus \left\{ 0 \right\} and f : A \rightarrow B is defined by the formula f x = x + 1. Then a \cap \mathscr{P} A = \left\{ \mathbb{N} \right\} and b \cap \mathscr{P} B = \left\{ \mathbb{N} \setminus \left\{ 0 \right\} \right\}; f is a bijection from A to B and \left\langle f \right\rangle |_{a \cap \mathscr{P} A} = \left\langle f \right\rangle |_{\left\{ \mathbb{N} \right\}} is a bijection from a \cap \mathscr{P} A to b \cap \mathscr{P} B. So a \cap \mathscr{P} A and b \cap \mathscr{P} B are directly isomorphic, that is a and b are isomorphic filters.

Theorem.
Being directly isomorphic for filters is an equivalence relation.

Proof.

Reflexivity
Let a is a filter on some set A. Then the identity function \mathrm{Id}_A is a bijection from \bigcup a to \bigcup a. Evidently \left\langle \mathrm{Id}_A \right\rangle |_a is a bijection from a to a. So a and a are directly isomorphic.
Symmetry
Let filters a and b are directly isomorphic. Then exists a bijection f : \bigcup a \rightarrow \bigcup b such that \left\langle f \right\rangle |_a is a bijection from a to b. f^{- 1} : \bigcup b \rightarrow \bigcup a is a bijection. To finish the proof it is enough to show that \left\langle f^{- 1} \right\rangle |_b is a bijection from b to a. First \left\langle f^{- 1} \right\rangle |_b is a function with domain b. Let X, Y \in b; if X \neq Y then \left\langle f^{- 1} \right\rangle X \neq \left\langle f^{- 1} \right\rangle Y because f^{- 1} is a bijection, consequently \left\langle f^{- 1} \right\rangle |_b X \neq \left\langle f^{- 1} \right\rangle |_b Y. So \left\langle f^{- 1} \right\rangle |_b is an injection. Let X \in a; then \left\langle f \right\rangle X \in b that is \left\langle f \right\rangle X = Y where Y \in b; X = \left\langle f^{- 1} \right\rangle \left\langle f \right\rangle X = \left\langle f^{- 1} \right\rangle Y = \left\langle f^{- 1} \right\rangle |_b Y; that is \left\langle f^{- 1} \right\rangle |_b is a function onto a. So \left\langle f^{- 1} \right\rangle |_b is a bijection from b to a. Hence b and a are directly isomorphic.
Transitivity
Let filters a and b are directly isomorphic and filters b and c are directly isomorphic. Then exist bijections f : \bigcup a \rightarrow \bigcup b and g : \bigcup b \rightarrow \bigcup c such that \left\langle f \right\rangle |_a is a bijection from a to b and \left\langle g \right\rangle |_b is a bijection from b to c. The function g \circ f is a bijection from \bigcup a to \bigcup c. We have \left\langle g \circ f \right\rangle |_a = \left\langle g \right\rangle \circ \left\langle f \right\rangle |_a = \left\langle g \right\rangle |_b \circ \left\langle f \right\rangle |_a is a bijection as a composition of two bijections. So filters a and c are directly isomorphic.

Lemma.
If a \cap \mathscr{P} A and b \cap \mathscr{P} B are directly isomorphic, then for any A' \in a \cap \mathscr{P} A there exists B' \in b \cap \mathscr{P} B such that a \cap \mathscr{P} A' and b \cap \mathscr{P} B' are directly isomorphic.

Proof.
Let a \cap \mathscr{P} A and b \cap \mathscr{P} B are directly isomorphic; let A' \in a \cap \mathscr{P} A. Then there are a bijection f : A \rightarrow B such that \left\langle f \right\rangle |_{a \cap \mathscr{P} A} is a bijection from a \cap \mathscr{P} A to b \cap \mathscr{P} B. a \cap \mathscr{P} A' \subseteq a \cap \mathscr{P} A; hence \left\langle f \right\rangle |_{a \cap \mathscr{P} A'} is an injection defined on the set a \cap \mathscr{P} A'. Let B' = \left\langle f \right\rangle A'. We have B' \subseteq B. Let Y \in b \cap \mathscr{P} B'; then Y \in b \cap \mathscr{P} B; by definition of directly isomorphic exists X \in a \cap \mathscr{P} A such that \left\langle f \right\rangle X = Y. We have X \subseteq A' because Y \subseteq B' and because f is a bijection. So X \in a \cap \mathscr{P} A'. Thus \left\langle f \right\rangle |_{a \cap \mathscr{P} A'} is a function onto b \cap \mathscr{P} B'. So \left\langle f \right\rangle |_{a \cap \mathscr{P} A'} is a bijection.

Theorem.
Being isomorphic for filters is an equivalence relation.

Proof.

Reflexivity
Let a is a filter. Let A = \bigcup a. Then a = a \cap \mathscr{P} A is directly isomorphic to itself. Consequently a is isomorphic to itself.
Symmetry
Let filters a and b are isomorphic. Then there exist sets A \in a and B \in b such that filters a \cap \mathscr{P} A and b \cap \mathscr{P} B are directly isomorphic. By proved above b \cap \mathscr{P} B and a \cap \mathscr{P} A are directly isomorphic. But this means that b and a are isomorphic.
Transitivity
Let filters a and b are isomorphic and filters b and c are isomorphic. Then a \cap \mathscr{P} A and b \cap \mathscr{P} B_1 are directly isomorphic and b \cap \mathscr{P} B_2 and c \cap \mathscr{P} C are directly isomorphic where A \in a, B_1, B_2 \in b, C \in c. Let B_0 = B_1 \cap B_2. We have B_0 \in b. By the lemma (taking in account also symmetry proved above) there exist sets A_0 \in a \cap \mathscr{P} A and C_0 \in c \cap \mathscr{P} C such that a \cap \mathscr{P} A_0 and b \cap \mathscr{P} B_0 are directly isomorphic and b \cap \mathscr{P} B_0 and c \cap \mathscr{P} C_0 are directly isomorphic. By transitivity of being direct isomorphic we have that a \cap \mathscr{P} A_0 and c \cap \mathscr{P} C_0 are directly isomorphic. Hence a and c are isomorphic.

Proposition.

  1. Principal filters, generated by sets of the same cardinality, are isomorphic.
  2. If a filter is isomorphic to a principal filter, then it is also a principal filter with the same cardinality of the sets which generate these principal filters.

Proof.

  1. Let a and b are principal filters. Let they are generated by the sets A and B correspondingly where \mathrm{card} A = \mathrm{card} B. Enough to prove that a \cap \mathscr{P} A and b \cap \mathscr{P} B are directly isomorphic. But this follows from a \cap \mathscr{P} A = \left\{ A \right\} and b \cap \mathscr{P} B = \left\{ B \right\} and \mathrm{card} A = \mathrm{card} B, because any bijection from A to B sends \left\{ A \right\} to \left\{ B \right\}.
  2. Let a is a principal filter generated by a set A, let b is a filter isomorphic to a. We shall prove that b is principal and is generated by a set B such that \mathrm{card} B = \mathrm{card} A. Let A \in a and B \in b and f is a bijection from A to B such that \left\langle f \right\rangle |_{a \cap \mathscr{P} A} is a bijection from a \cap \mathscr{P} A to b \cap \mathscr{P} B. We have b \cap \mathscr{P} B = \left\{ \left\langle f \right\rangle |_{a \cap \mathscr{P} A} X |  X \in a \cap \mathscr{P} A \right\} = \left\{ \left\langle f \right\rangle X | X \in a \cap \mathscr{P} A \right\}. So b \cap \mathscr{P} B has the smallest element \left\langle f \right\rangle A. Consequently b has the smallest element \left\langle f \right\rangle A and so b is a principal filter generated by the set B = \left\langle f \right\rangle A whose cardinality is \mathrm{card} A.

Proposition.
A filter isomorphic to a nontrivial ultrafilter is a nontrivial ultrafilter.

Proof.
Let a is a nontrivial ultrafilter and let b is isomorphic to a. Then there are sets A \in a and B \in b and a bijection f : A \rightarrow B such that \left\langle f \right\rangle |_{a \cap \mathscr{P} A} is a bijection from a \cap \mathscr{P} A to b \cap \mathscr{P} B.

The filter b cannot be a trivial ultrafilter because otherwise a would be also a principal filter. So it’s enough to prove that b is an ultrafilter. We will prove that for any set Y \in \mathscr{P} \bigcup b either Y or ( \bigcup b) \setminus Y is an element of b.

Let Y \in \mathscr{P} \bigcup b. Then Y' = Y \cap B \in \mathscr{P} B; Y' = \left\langle f \right\rangle X' for some X' \in \mathscr{P} A. Because a is an ultrafilter, either X' \in a or ( \bigcup a) \setminus X' \in a. If X' \in a then X' \in a \cap \mathscr{P} A and so Y' = \left\langle f \right\rangle X' = \left\langle f \right\rangle |_{a \cap \mathscr{P} A} X' \in b \cap \mathscr{P} B and consequently Y \in b. If ( \bigcup a) \setminus X' \in a then A \setminus X' \in a \cap \mathscr{P} A; consequently \left\langle f \right\rangle |_{a \cap \mathscr{P} A} (A \setminus X') \in b \cap \mathscr{P} B; \left\langle f \right\rangle |_{a \cap \mathscr{P} A} (A) \setminus \left\langle f \right\rangle |_{a \cap \mathscr{P} A} (X') \in b \cap \mathscr{P} B; B \setminus Y' \in b; ( \bigcup b) \setminus Y \in b.

And as the culmination of this passage about isomorphic filters, several (related) open problems:

Question. Are any two nontrivial ultrafilters isomorphic?

Question. Are any two nontrivial ultrafilters on the same set directly isomorphic?

Question. Are any two nontrivial ultrafilters on \mathbb{N} isomorphic?

Question. Are any two nontrivial ultrafilters on \mathbb{N} directly isomorphic?

(These are open problems for me, the author of this text. If someone knowing the solutions of these problems, please contact me.)

Advertisements

One Comment

Leave a Comment
  1. porton / Jun 11 2009 18:45

    In this newsgroup thread is proved that there are non-isomorphic non-trivial ultrafilters on \mathbb{N}. This solves all four open problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: