Articles of elementary set theory

$F$ is a free abelian group on a set $X$ , $H \subseteq F$ is a free abelian group on $Y$, then $|Y| \leq |X|$

I am confused by the proof a proposition: $F$ is a free abelian group on a set $X$ and $H$ is a subgroup of $F$, then $H$ is free abelian on a set $Y$, where $|Y| \leq |X|.$ The proof is: Let $X$ be well-ordered in some fashion, say as $\{ x_{\alpha} | \alpha < […]

Lexicographical order – posets vs preorders

I found the following definition for lexicographical ordering on Wikipedia (and similar definitions in other places): Given two partially ordered sets $A$ and $B$, the lexicographical order on the Cartesian product $A \times B$ is defined as $(a,b) \le (a’,b’)$ if and only if $a < a’$ or ($a = a’$ and $b \le b’$). […]

To prove $f$ to be a monotone function

A open set is a set that can be written as a union of open intervals. If $f$ is a real valued continuous function on $\mathbb{R}$ that maps every open set to an open set, then prove that $f$ is a monotone function.

Is Cantor's Diagonal Argument Dependent on Tertium Non Datur

The standard presentation of Cantor’s Diagonal argument on the uncountability of (0,1) starts with assuming the contrary through “reduction ad absurdum”. The intuitionist schools of mathematical regards “Tertium Non Datur” (bijection from N to R either exists or does not exist) untenable for infinite classes. However, the argument can be modified by applying the diagonal […]

How to prove $\forall Y \subset X \ \forall U \subset X \ (Y \setminus U = Y \cap (X \setminus U))$?

How to prove that $$\forall Y \subset X \qquad \forall U \subset X \qquad(Y \setminus U = Y \cap (X \setminus U))$$ Intuitively it has something to do with the way $2^X$ models Boolean algebra, but I can’t make a precise argument. Any hint?

Intersect and Union of transitive relations

Let $R$ and $S$ be relations on a set $A$. Assume $A$ has at least three elements. These are my best guesses at these two proofs. The first one I don’t feel confident about at all, as it seems I’m making too many assumptions. If $R$ and $S$ are transitive, then $R \cap S$ is […]

The set of natural number functions is uncountable

I thought the set of natural number functions would be of the same cardinality as the countably infinite product of $\mathbb{N}$, which is countable. Each natural number function can be identified with an infinite-tuple of $\mathbb{N}$ by letting the $i$th entry be the image of the number $i$ under the function.

Proving $rank(\wp(x)) = rank(x)^+$

Enderton defines the rank of a set $A$ to be the least ordinal $\alpha$ such that $A \subseteq V_{\alpha}$ (equivalently, $A \in V_{\alpha^+}$). He the derives the following identity: $rank(A) = \bigcup \{ (rank(x))^+ : x \in A \}$ for all sets $A$. In Exercise 30 of Chapter 7, the reader is asked to prove […]

How to prove DeMorgan's law?

How to prove DeMorgan’s Law? $$A – (B \cup C) = (A – B) \cap (A – C)$$ $$A – (B \cap C) = (A – B) \cup (A – C)$$ EDIT: Here is what I have tried so far: Considering the first equation, assuming $x \in A – (B \cup C)$ then $x \in […]

Proof of compactness theorem

I wanted to prove the compactness theorem, p 79 Just/Weese: The (i) <= (ii) direction is not obvious to me. I thought I could prove it by showing not (i) implies not (ii) as follows: Assume $T$ does not have a model. Then for every $\varphi \in T$, $T \models \varphi$ and by completeness, $T […]