Articles of elementary set theory

Problems with the definition of transitive relation

Recently I found this problem, which made me realize I have some problems with relations that are vacuously transitive. Problem: Assume that $R$ is a relation on $A$ and define the relation $S$ as $$ S : = \{ (X, Y) \in \wp(A) \times\wp(A) : \exists x \in X, \exists y \in Y ((x,y) \in […]

Fun quiz: where did the infinitely many candies come from?

Story 1: Let there be a bowl $A$ with countably infinite many of candies indexed by $\mathbb{N}$. Let bowl $B$ be empty. After $1/2$ unit of time, we take candy number 1 and 2 from $A$ and put them in $B$. Then we eat candy 1 from bowl $B$. After $1/4$ unit of time, we […]

Count $k$-subsets with at least $d>1$ different elements (pairwise)

The problem of counting the number of $k$-subsets in a set of size $n$ is well known. The answer is ${n \choose k}$. But here, I want $k$-subsets with the property that any two of them have at least $d$ different elements. If we take the set $S = \{1, 2, 3, 4, 5, 6\}$ […]

Cardinality of Cartesian Product of Uncountable Set with Countable Set

Is it true that if $I$ is an infinite set, then $I\times \mathbb{N}$ has the same cardinality as $I$? I believe it, but I have minimal background in set theory. My guess is that we can construct an injection from $I\times \mathbb{N}$ to $I,$ but I don’t see an obvious way to do so.

common knowledge and concept of coarsening partition

Here is a proof of the equivalence between my definition and Aumann’s for “common knowledge”. I’m assuming some familiarity with set partitions. Aumann’s definition is in terms of the Kolmogorov model of probability. In particular, a proposition is identified with the set of possible worlds in which the proposition is true. Let P₁ be that […]

Ordinal Fractions

Is any fraction $\,{x}\big/ {y}\,$ an ordinal number and if so, does ordinal $\,1 = \big\lbrace0,\dots,y – 1\big/y\big\rbrace\,$ instead of $\,\left\lbrace0\right\rbrace\,$? “If (X, <=) is a well ordered set with ordinal number x, then the set of all ordinals < x is order isomorphic to X. This provides the motivation to define an ordinal as […]

Does $f\circ g$ injective imply $f$ injective for functions $f,g:A\to A$?

I have some problem with proof of the following question: I have two functions $f,g: A \to A$, I know that $(f \circ g)$ is injective, is it possible at all to prove that $f$ is injective? I know that if $g: A \to B$ and $f: B \to C$, I can find example which […]

Understanding $A^A$ in set theory

If $A=\left\{1,2,3\right\}$ so what will be $A^A$? What is the geometric interpretation for $A^A$? Thanks

Possible divisors of $s(2s+1)$

I write $\psi(s) = s(2s+1)$ and let $d$ be the divisor function. If $s$ is prime then 4 divides $d(\psi(s))$. For example if $s=37$ then $d(\psi(s)) = d(2775) = 12$ and $4|12$. Is this trivial? I am not sure how to attack and prove this. Here is my approach: Now I am thinking $d$ is […]

Cardinality of a $\mathbb Q$ basis for $\mathbb C$, assuming the continuum hypothesis

Prove that $\operatorname{tr.deg}(\mathbb{C/Q})=\mathfrak{c}$ (where $\mathfrak{c}$ is the cardinality of $\mathbb{R}$) using the continuum hypothesis. $Proposition$ If $E/F$ is an algebraic extension then $|E|=\aleph_0 |F|$ Proof: Let $S$ be a trancendental basis of the extension $\mathbb{C/Q}$.Then $|S| \leqslant \mathfrak{c}$.Suppose that $|S|< \mathfrak{c}$. Then, by the continuum hypothesis, $S$ is finite or countable. Let $S=\{s_1,s_2, \ldots \}$ […]