Articles of elementary set theory

Example of an injective function $g$ and function $f$ such that $g\circ f$ is not injective

Give an example of a function $g$ which is injective, but for which its composition with $f$ is not, namely $g\circ f$. I suspect that $f(x)=0$ and $g(x)=x$ will do, am I right?

Proving $a\le f(a)$ for a monotonically increasing function on a well-ordered set

Let $(x,\le)$ be well-ordered set and let $f: \ x \rightarrow x$ be monotonically increasing function. Prove that $\forall a \in x$ $$a \le f(a)$$ Find an example of set $x$ linearly ordered such that the statement doesn’t hold. My try: Assume $X=\{a \in x \ : \ a \ge f(a) \}$ is non-empty set […]

Show that $A\cap B\subseteq A$ and $A\subseteq A\cup B$

$$A \cap B \subseteq A$$ My first step would be to write it as $(x \in A \land x \in B) \subseteq A$. Then I know by the following implication that is always true $P \land Q \implies P$. But I am not sure how to write it down mathematically correct. $$A \subseteq A \cup […]

Fixed points and cardinal exponentiation

Let the function $F: On \rightarrow On$ be defined by the following recursion: $F(0) = \aleph_0$ $F(\alpha+1) = 2^{F(\alpha)}$ (cardinal exponentiation) $F(\lambda) = \sup\{F(\alpha):\alpha \in \lambda\}$ for $\lambda$ a limit ordinal Prove that there is a fixed point for $F$, i.e. an ordinal $\kappa$ with $F(\kappa) = \kappa$. Are such fixed points always cardinals? Thoughts: […]

Bijection from $\mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$

My goal here is to find a bijection from $\mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$ (this is letting $0 \in \mathbb{Z}$ Here’s what I have so far: Let $$A = \{ x^2 – x \mid x \in \mathbb{Z} \} $$ and let $g: \mathbb{Z} \to \mathbb{Z}$, $g(x) = a \in A$, $a$ is the greatest element […]

Working with Equivalence Classes and Quotient Sets

I have a doubt about working with equivalence classes and quotient sets. The definition that I know, is that given an equivalence relation $\sim$ on a set $A$, the set of all elements of $A$ equivalent to a certain element $x$ is the set $\left[x\right]\subset A$ which is called the equivalence class of $x$. The […]

How is a set subset of its power set?

This question is from S C Kleene’s Introduction to Metamathematics, page 38: If we prescribe as admissible elements of sets (a) $\varnothing$ and (b) arbitrary sets whose members are admissible elements, so that sets have only sets as members, then when $M$ is the set of all sets, $ P(M)=M$. (Here $P(X)$ is power set […]

Axiom of Replacement (Question of notation)

For each formula $\phi$ without $Y$ free, the universal closure of the following is an axiom: $\forall x\in A \exists !y \phi(x,y) \Longrightarrow \exists Y \forall x\in A \exists y\in Y \phi(x,y)$ My question is about the $!$, does that mean that $y$ is bound in $\phi$? What does the exclamation mark mean? Is it […]

Set of natural numbers

Let $A$ be a nonempty subset of $\omega$, the set of natural numbers. If $\bigcup A=A$ then $A=\omega$. I have proved ‘$\bigcup n^+ = n$ for any $n\in\omega$’ and ‘$\bigcup\omega = \omega$’ I think this question should be proved with the above results.. Help please

Find the $\bigcap_{n = 1}^{\infty} (-\frac{1}{n}, \frac{2}{n})$

Find the $\bigcap_{n = 1}^{\infty} (-\frac{1}{n}, \frac{2}{n})$ So the way I understand it is that I’m trying to find $(\frac{-1}{1}, \frac{2}{1}) \bigcap (\frac{-1}{2}, \frac{2}{2}) \bigcap (\frac{-1}{3}, \frac{2}{3})\bigcap …$ and so forth. Then the intersection would be $\varnothing$ right? Can I prove this by just writing out the first few elements and seeing that they do […]