1
vote
1answer
83 views

Hall's marriage Theorem and Tychonoff Theorem

I was reading this paper. In particular the second point. He proves the Hall's marriage Theorem for infinite family using the Tychonoff theorem on topological product of compact $T_2$ spaces and the ...
5
votes
1answer
193 views

Asymmetric roles that are symmetric in every instance

This is similar to something else I posted, but this time we'll pretend we've never heard of infinite sets or infinite series. \begin{align} & \sin(\alpha+\beta+\gamma+\delta+\varepsilon+\zeta) ...
1
vote
0answers
129 views

“Dual cardinality” in the graphs $(V_\alpha,\in_\alpha)$

04-25-2014 Enriched with more details Let define the graphs $(V_\alpha,\in_\alpha)$ in $ZFC$ $V_\alpha$ can be finite too $\in_\alpha \subseteq V_\alpha \times V_\alpha$ and ...
3
votes
1answer
88 views

R is countable using Zorn's Lemma?

I used Zorn's Lemma to cook up a proof that $\mathbb{R}$ is countable, and now I can't find a flaw in it. Can anyone help? Here it is... Denote by $\mathcal{A}$ the set of countable subsets of ...
6
votes
3answers
110 views

What is a Cantor-style proof of $2^n > n^k$?

Cantor's diagonalization argument shows that no function from an $n$-element set to its set of subsets hits every element. This is one way to see that $2^n > n$ for every $n$. The classic ...
1
vote
1answer
62 views

On the existence of a chain with empty intersection

Let $X$ be a family of sets such that each of them has more than one element and whenever $A\cup B$ is a partition of an element of $X$ then either $A \in X$ or $B\in X$. I am trying to show that ...
5
votes
1answer
121 views

Are there mathematical (combinatorial) objects to represent such set systems?

Background: This is a problem arising from my study on computer science. In its appearance, it involves set systems. A set system $\mathcal{S} = \{S_1, S_2, \ldots, S_m \}$ is a collection of ...
1
vote
1answer
95 views

Finding an element of the intersection of an infinite sequence of “compatible” sets of infinite sequences

Let $A$ be a set. Let $A^\omega$ denote the set of infinite sequences of members of $A$ (i.e., functions from $\omega$ to $A$). Define $\omega_n = \omega \setminus \{n\}$. Let $A^\omega_n$ denote the ...
1
vote
1answer
234 views

The number of equivalence classes of finite symmetric difference relation

Let $\Sigma$ be an infinite set. Let $A,B \subseteq \Sigma$ be of finite symmetric difference iff they have a finite difference, more formally: $A \sim B$ iff $|A \Delta B| \in \mathbb{N}$ How ...
2
votes
4answers
265 views

An infinite set having “one more element” than another infinite set

A classic example of homeomorphism is between a sphere missing one point and a plane To see this, place a sphere on the plane so that the sphere is tangent to the plane. Given any point in the plane, ...
2
votes
2answers
62 views

Cocountable fibers

Let $C$ be an uncountable set. Can we construct a set $A \subseteq C^2$ such that it has a cocountable number of cocountable horizontal fibers, and a cocountable number of countable vertical fibers?
1
vote
1answer
87 views

Hales Jewett regularity theorem

I am trying to read the Hales-Jewett regularity theorem given as Theorem 1 here. I have a doubt in the proof which I am hoping someone here can clarify. Here are some background definitions and a ...
1
vote
1answer
213 views

Combinatorial Set Theory - Ramsey's Theorem Related Question

For a set $A \subseteq \omega$, let $[A]^n$ denote the set of subsets of $A$ of size $n$. I am trying to prove Ramsey's Theorem, and it seems like the following fact is used in the proof I am reading ...
4
votes
2answers
472 views

Countable or uncountable set 8 signs

Let S be a set of pairwise disjoint 8-like symbols on the plane. (The 8s may be inside each other as well) Prove that S is at most countable. Now I know you can "map" a set of disjoint intervals in R ...
13
votes
1answer
661 views

Is it true that a connected graph has a spanning tree, if the graph has uncountably many vertices?

I found a proof that every connected graph (possibly infinite) has a spanning tree in Diestel's Graph Theory (Fourth Edition), Ch. 8 that uses Zorn's Lemma, but at a crucial step it seems to be ...
7
votes
1answer
226 views

On the existence of closed form solutions to finite combinatorial problems

Is it possible that a finite combinatorial problem may admit a closed form solution, and for it to be impossible in practice to prove the validity of this solution? I'm not sure if a rigorous ...