This is probably a pretty simple question, but I'm tying myself in knots over it.  We're all familiar with the Reflection Theorem, Lowenheim-Skolem Theorem, and Mostowski Collapse Lemma for getting countable transitive models of finite fragments of ZFC. You take a finite fragment $\Gamma$, use the reflection theorem to get that $\Gamma$ holds in some $V_\kappa$, Skolemise over $V_\kappa$, and then Collapse to a ctm.  My question. Is there (or could there be) a countable transitive model satisfying the same first-order truths as $V$? Obviously, by Tarski, such a countable transitive model is not first-order definable.  A possible route:  Suppose full second-order reflection is true of $V$. Let $A$ be a second-order parameter that contains a witness for every parameter-free sentence of first-order $ZFC$ true in $V$. Then, just reflect the sentence $x \in A$, Skolemise, and Collapse as normal (I feel like I might be pulling a fast-one here).
122923
From $\mathrm{ZFC},$ define a new theory $\mathrm{ZFC}^E$ by adjoining a constant symbol $E$ together with axioms to the effect that:   $E$ is countable and transitive $(E,\in)$ is an elementarily equivalent to $(V,\in).^*$ (This is an axiom schema).   Question. Is $\mathrm{ZFC}^E$ outright inconsistent?  Motivation. The idea (or motivation) is to have a "miniature copy" of the universe available, that is nonetheless "very small" from our omniscient $V$-like perspective.
95444
I'm stuck on the following problem (Source: Real Analysis for Graduate Students; Exercise 2.6; ):     Suppose $\mathcal A$ is a $\sigma$-algebra with the property that whenever $A \in \mathcal A$, there exists $B, C \in \mathcal A$ with $B \cap C = \emptyset$, $B \cup C = A$, and neither $B$ nor $C$ is empty. Prove that $\mathcal A$ is uncountable.   I think there is the added assumption that this is only true for $A \in \mathcal A$ having at least two elements, so it doesn't hold for singletons and the emptyset?  I tried to show this by way of contradiction and say that $\mathcal A = \{A_k\}$ is countable, but I didn't see how this could get me to a contradiction.  The other approach I tried was to look at $X = B_1 \cup C_1$ where $B_1 \cap C_1 = \emptyset$, then look at $B_1 = B_2 \cup C_2$ where $B_2 \cap C_2 = \emptyset$ and so on. If I look at the $C_k$'s they are pairwise disjoint and I either have a finite number of them or an infinite number of them in which case I've created a countable sequence of pairwise disjoint nonempty elements of $\mathcal A$. This path looked promising, but I couldn't see what to do next. Any ideas?  As a secondary question: I think this result is supposed to be used to show that if $\mathcal A$ is a $\sigma$-algebra with infinitely many elements, then it's uncountable, but I wasn't able to show that the property mentioned above (the one I'm trying to show) was satisfied in this case.
32015
So, as the title says I'd like to give a proof of the fact that if $C$ is an infinite set then it is equipotent or equivalent to its cartesian product $C\times C$ using Zorn's Lemma (and of course some of its implications like the fact that $C$ has an infinite countable subset which I think might be very useful).   The main problem that I have is that I'm not supposed to use any theorem or result involving cardinal numbers since I'm still taking an elementary set theory course which hasn't covered that topic yet and all the proofs that I've read so far use cardinals arithmetic at some point.   Another thing that I think might be useful is a lemma which was proved via Zorn's Lemma in an answer to the question   which states that given the infinite set $C$ there exists a non-empty set $B$ such that $B\times \mathbb{N}$ is equipotent to $C$. Then it suffices to give a bijection from $(B\times \mathbb{N})$ $\times$ $(B\times \mathbb{N})$ to $B\times \mathbb{N}$  So, any suggestion on the direct proof (without cardinals, unfortuntely) via Zorn's Lemma or an actual bijection from $(B\times \mathbb{N})$ $\times$ $(B\times \mathbb{N})$ to $B\times \mathbb{N}$ would be highly appreciated. Thanks in advance.
116387
We say that $\Gamma$ is consistent if for no $\phi$, then both $\Gamma\vdash \neg\phi$ and $\Gamma\vdash\phi$. We say that $\Gamma$ is satisfiable if there is a structure $M$ s.t. $\models_M\gamma[s]$ for alle $\gamma\in\Gamma$.  I want to show that if $\Gamma$ is satisfiable, then $\Gamma$ is consistent.  I'm thinking we assume that $\Gamma$ is not consistent, and then show that $\Gamma$ is not satisfiable. So if $\Gamma$ is not consistent then both $\Gamma\vdash \neg\phi$ and $\Gamma\vdash\phi$ for some $\phi$. But by soundness theorem then $\Gamma\models\neg\phi$ and $\Gamma\models\phi$, meaning for structure $M$, we have $\models_M\neg\phi[s]$ (whereas $\not\models_M\phi[s]$) and $\models_M\phi[s]$. So would this mean that $\Gamma$ is not satisfiable? I'm a little confused, because wouldn't this instead be a contradiction?
28598
Is it true that for any uncountable $S$, there exits two uncountable subsets $S_1,S_2 \subseteq S$ with $S_1 \cap S_2 = \emptyset$?   I can find no counter example, but no proof either.  I am aware of similar questions regarding the partition of uncountable subsets of the real line, and there are many examples of disjoints uncountable subsets of $\mathbb{R}$, say $R_1,R_2$.   It is not clear to me however whether this extends to any uncountable set. For uncountable sets $S$ with $S \succeq_{card} \mathbb{R}$, there exists an injection $f : \mathbb{R} \rightarrow S$ and choosing $S_1,S_2$ with $S_i = \{s\in S~|~ s = f(r_i) $ for some $ r_i \in R_i\}$, works.   But from what I understood of the continuum hypothesis, there might exist an uncountable sets $H$ with $\mathbb{R} \succeq_{card} H$. So using the above argument, one cannot infer that the property holds for every uncountable sets from observing that it holds for $\mathbb{R}$. Is this right? Are there other ways to prove or disprove the assertion?
39124
I'm studying Model Theory with the book of Chang-Keisler, and I'm trying to solve the following problem stated in Chapter 5:     The union of an elementary chain $(M_i)_{i &lt; \alpha}$ of $\alpha$-saturated models is also $\alpha$-saturated, if $\alpha$ is regular.   I'm considering the following definition:     $M$ is a $\alpha$-saturated model if for all $A \subset M$, $|A| &lt; \alpha$, every $1$-type $p$ in $A$ over $T(M) = \left \{ \varphi: M \models \varphi \right \}$ is realized in $M$, i.e. there exists $a \in M$ such that $M \models \varphi(a), \, \forall \varphi \in p.$   My attempt:  Let $(M_i)_{i &lt; \alpha}$ be an elementary chain of $\alpha$-saturated models and let $M = \bigcup_{i &lt; \alpha} M_i$. Given $A \subset M$ with $|A| &lt; \alpha$ and $p$ a $1$-type in $A$ over $T(M)$, if I prove that there exists $i &lt; \alpha$ such that $p$ is a type over $T(M_i)$, we could conclude that there exists $a$ in $M_i$, with $M_i \models \varphi(a)$ for all $\varphi \in p$. Hence $a \in M$ and $M \models \varphi(a)$, since $M_i$ is an elementary substructure of $M$.  So, how can I proof the existence of such $i &lt; \alpha$?
19974
I am having a difficulty setting up the proof of the fact that two basis of a vector space have the same cardinality for the infinite-dimentional case. In particular, let $V$ be a vector space over a field $K$ and let $\left\{v_i\right\}_{i \in I}$ be a basis where $I$ is infinite countable. Let $\left\{u_j\right\}_{j \in J}$ be another basis. Then $J$ must be infinite countable as well. Any ideas on how to approach the proof?
53285
I found this proposition and don't see exactly as to why it is true and even more so, why the converse is false:  Proposition 1. The equivalence between the proposition $z \in D$ and the proposition $(\exists x \in D)x = z$ is provable from the definitory equations of the existential quantifier and of the equality relation. If $D = \{t_{1},t_{2},...t_{n}\}$, the sequent $z = t_{1} \vee z = t_{2} \vee z \vee ... z = t_{n}  \vdash z \in D$ is provable from the definition of the additive disjunction $\vee$.  The converse sequent $z \in D \vdash z = t_{1} \vee z = t_{2} \vee ... z = t_{n}$ is not provable.  The author goes on to say:  "We adopt the intuitionistic interpretation of disjunction. With respect to it, one can characterize a particular class of finite sets"  On the first part of the proposition, well I am not sure what the point is as if we take an element z in D, then we could just call this element x and hence this x = z.  Is there something more to this?  On the second part of Proposition 1 since $z = \text{ some } t \in D$ since t is in the set of axioms and $t = z$, then $t \vdash z$ as z is derivable from t.  For the converse if $z \in D$ then why wouldn't z = some $t \in D$?  Is this because of the Incompleteness theorem?  That perhaps there D as a set of axioms has some consequence which can not be proven by the set of axioms in D?  Or perhaps I am way off here.  Any ideas?  Thanks,  Brian
102859
Theorem Let be $(X,\le)$ a totally ordered set: then for any not empty finite subset $A$ of $X$ there exist the maximum  element and minimum element. proof. Let be $(X,\le)$ a totally ordered set and we prove by induction that any not empty finite subset $A$ of $X$ has a minimum element. Since $X$ is a totally ordered set, previously we observe that any its subset $Y$ (finite or infinite) is a chain. Obviously any subset $A$ of one element $a$ has trivially a minimum. So we suppose that any subset of $n$ elements has a minimum element and then  we consider a subset $A$ of $n+1$ elements: since $A$ is finite there exists a bijection $\phi$ from $A$ onto some natural number $m$, that is the successor of $n$, and so we can organize the elements of $A$  in a finite succession, that is $A=\{a_1,...,a_{n+1}\}$. Now we consider the subset $B=\{a_h\in A:h\le n\}$: obviously $X$ is a subset of $A$ that has $n$ element and so it has a minimum element $b$; so since $A=B\cup\{a_{n+1}\}$ and since $A$ is a chain (remember what before we observed), it must be or $a_{n+1}\le b$ or $b&lt;a_{n+1}$ and so for the transitivity property of the order relation $\le$ in any case $A$ has a minimum element. So now we only have to prove that any not empty finite subset $A$ of $X$ has a maximum element. So we consider the inverse relation $\preccurlyeq$ defined as $x\preccurlyeq y\iff y\le x$ for any $x,y\in X$: clearly $\preccurlyeq$ is a total order, since indeed $\le$ is a total order, and any minimum in $\preccurlyeq$ is a maximum in $\le$ and so since any not empty finite subset $A$ has a minimum in $\preccurlyeq$ it follows that any not empty finite subset in $\le$ has a maximum element. So we concluded the proof.  Is my proof correct? If not how prove the theorem? Could someone help me, please?
108936
I want to prove that the cartesian product of a finite amount of countable sets is countable. I can use that the union of countable sets is countable.   My attempt:  Let $A_1,A_2, \dots, A_n$ be countable sets.   We prove the statement by induction on $n$  For $n = 1$, the statement clearly holds, as $A_1$ is countable. Now, suppose that $B := A_1 \times A_2 \times \dots A_{n-1}$ is countable.  We have: $$B \times A_n = \{(b,a)|b \in B, a \in A_n\}$$ $$= \bigcup_{a \in A_n} \{(b,a)|b \in B\}$$  and $\{(b,a)|b \in B\}$ is countable for a fixed $a \in A_n$, since the function $f_a: B \to B \times \{a\}: b \to (b,a)$ is a bijection, and $B$ is countable by induction hypothesis. Because the union of countable sets remains countable, we have proven that $(A_1 \times \dots A_{n-1}) \times A_n$ is countable, and because $f: (A_1 \times \dots A_{n-1}) \times B \to A_1 \times \dots A_{n-1} \times A_n: ((a_1, \dots, a_{n-1}),a_n) \mapsto (a_1, \dots, a_{n-1},a_n)$ is a bijection, the result follows.  Questions:        Is this proof correct/rigorous?     Are there other proofs that are   easier?    Someone pointed out that we can prove this theorem using the   'zigzag'-argument. Can someone provide this proof? I think this   zigzag-method is too graphical, and therefore not rigorous, so if   someone can clarify why this method is completely rigorous, I would be   more than glad to award him the bonus.
34301
My understanding of logic is really basic, and I ask this question out of curiosity.  Is there an explicit example of a statement whose proof uses the continuum hypothesis and is unprovable in $ZFC + \lnot CH$.   ADDED: Preferably I'm looking for an example outside set theory.
24061
It's true that a set with a linear order where every initial segment is finite is necessarily countable? I don't think so but I can't find a counterexample (or make a proof)
82384
The answer seems to be yes, judging from the following exercise I found in the book Mathematical Logic by H.D. Ebbinghaus, J. Flum, and W. Thomas:     Let $S$ be a finite symbol set and let $\mathfrak{U}$ be a finite $S$-structure. Show that there is an $S$-sentence $\varphi _{\mathfrak{U}}$ the models of which are precisely the $S$-structures isomorphic to $\mathfrak{U}$.   I think I have an idea of how to solve this exercise, but I seem to be unable to materialize it. Thanks.
30949
I have a question about the proof of the following:     (Lemma 37) Assume $\mathbf V = \mathbf L$, and let $\kappa$ be a cardinal. Then   $\mathcal P (\kappa ) \subseteq L_{\kappa^+}$.   Assume we have proved the following:      (Claim 38) There exists a finite subset $T$ of $ZF + (\mathbf V =  \mathbf L)$ such that whenever $x$ is transitive and $\langle x, \overline{\in} \rangle \models T$ then there exists $\gamma \in  \mathbf{ON}$ such that $x = L_\gamma$.      (Lemma 35) Let $\alpha \in \mathbf{ON}$ and $x, a_0, \dots , a_{k-1}  \in L_\alpha$ and let $\varphi(z, a_0, \dots ,a_{k-1})$ be a formula   of $L_S$. Then there exists a $\beta &gt; \alpha$ such that for every $z  \in x$: $$ \langle L_\beta , \overline{\in} \rangle \models \varphi  [z, a_0 , \dots, a_{k-1}]  \hspace{0.5cm} \text{ iff } \hspace{0.5cm}  \mathbf L \models \varphi [z, a_0 , \dots, a_{k-1}] $$     The proof in the book starts as follows: Suppose $\mathbf V = \mathbf L$ holds, let $\kappa$ be as in the assumptions of lemma 37 and suppose $\kappa \in \mathcal P ( \kappa )$. Fix an ordinal $\alpha &gt; \kappa$ such that $y \in L_\alpha$. Since the theory $T$ of claim 38 is finite we can form the conjunction $\varphi$ of all sentences in $T$.   Question: But what is $T$? I know that it's the theory from claim 38 but it's not clear to me how we can use an unknown theory to prove lemma 37. And why do we take the conjunction over $T$?  Then the proof proceeds: By lemma 35,    Question: How does $\gamma &lt; \kappa^+$ follow from $(2)$?  Many thanks for your help.
29994
One of the nicer consequences of compactness is that there is no statement in first-order logic whose content "$\leq$ is a well-order". So we can show that there are countable structure $(M,\leq)$ which are elementarily equivalent to $\Bbb N$, but not isomorphic to it.  What about adding $S,+,\cdot$ and $0$? Well. Also not very good. The theory of the structure $(\Bbb N,0,S,+,\cdot,\leq)$ has $2^{\aleph_0}$ non-isomorphic countable models. This shows that none of these additions get us any closer to finding an $\aleph_0$-categorical theory for $\Bbb N$.     Question. Is there a finite (or countable if needed) first-order language which includes $\leq$, and an $\aleph_0$-categorical theory $T$ whose countable structure is order isomorphic to $(\Bbb N,\leq)$?
2212
My question is about a proof of Theorem 4.12 given in the text Introduction to Set Theory by Hrbacek and Jech. The authors first prove Theorems 4.9, 4.10, and 4.11. For reference, I quote these theorems below.   Let $V$ be the class of all sets, $\operatorname{Ord}$ be the class of all ordinals, and $G:V\to V$ be a class function.  Theorem 4.9: Transfinite Recursion Theorem  There exists a class function $F:\operatorname{Ord}\to V$ such that $F(\alpha)=G(F\restriction \alpha)$ for all $\alpha\in\operatorname{Ord}$.  Theorem 4.10: Transfinite Recursion Theorem, Parametric Version  There exists a class function $F:\operatorname{Ord}\to V$ such that $F(z,\alpha)=G(z,F_z\restriction \alpha)$ for all $\alpha\in\operatorname{Ord}$ and $z\in V$ where $F_z\restriction \alpha:=\{\langle\beta,F(z,\beta)\rangle\mid\beta&lt;\alpha\}$.  Theorem 4.11:  Let $G_1,G_2,G_3$ be class functions from $V$ to $V$. There exists a class function $F:\operatorname{Ord}\to V$ such that (1) $F(0)=G_1(\emptyset)$ (2) $F(\alpha+1)=G_2(F(\alpha))$ for all $\alpha\in\operatorname{Ord}$ (3) $F(\alpha)=G_3(F\restriction\alpha)$ for all limit $\alpha\neq 0$   Then they say A parametric version of Theorem 4.11 is straightforward and we leave it to the reader. From my attempt, the parametric version of Theorem 4.11 is as follows (Honestly, I'm not sure if my attempt is correct or not)  Let $G_1,G_2,G_3$ be class functions from $V$ to $V$. There exists a class function $F$ such that, for all $z\in V$ $F(z,0)=G_1(z,\emptyset)$ $F(z,\alpha+1)=G_2(z,F_z(\alpha))$ for all $\alpha\in\operatorname{Ord}$ $F(z,\alpha)=G_3(z,F_z\restriction\alpha)$ for all limit $\alpha\neq 0$  Next they make use of this parametric version of Theorem 4.11 in the proof of Theorem 4.12. Theorem 4.12:  For any set $a$, there is a unique infinite sequence $(f_n\mid n\in \Bbb N)$ such that (1) $f_0=a$ (2) $f_{n+1}=G(f_n,n)$ for all $n\in \Bbb N$  The proof for Theorem 4.12 given in the text is as follows:  Let $G:V\to V$ be a class function. We want to find, for every set $a$, a sequence $(f_n\mid n\in \Bbb N)$ such that $f_0=a$ and $f_{n+1}=G(f_n,n)$ for all $n\in \Bbb N$. By the parametric version of the Transfinite Recursion Theorem 4.11, there is class function $F$ such that $F(0)=a$ and $F(n+1)=G(F(n),n)$ for all $n\in \Bbb N$. Now we apply the Axiom of Replacement: There exists a sequence $(f_n\mid n\in \Bbb N)$ that is equal to $F\restriction \omega$ and the Theorem follows.   I don't understand how the parametric version of Theorem 4.11 is used to derive the class function $F$ in the proof of Theorem 4.12. Can someone please help me fill in the blanks?
112355
Given a transitive set$$a,$$ I can prove that $$\bigcup a$$ is also transitive, but I don't quite like my method because I must first prove $$a \subseteq \mathcal{P}(\bigcup a)$$ to get at $$\bigcup a\subseteq \mathcal{P}(\bigcup a).$$ Could you please show me a smarter proof?