This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

1
vote
0answers
46 views

Prove there is no one-to-one correspondence function $\colon X→ P(X)$

I'm stuck on the following question and would appreciate it if someone could show me how I can prove it. Let $X$ be any set and let $P(X)$ be the power set containing all subsets of $X$. Prove ...
1
vote
0answers
31 views

Given $A \subset U$ and $B \subset U$. Prove or disprove $A - B \ = \emptyset \implies A \subset B$ [duplicate]

Given $A \subset U$ and $B \subset U$. Prove or disprove $A - B \ = \emptyset \implies A \subset B$ I think this is the way to do it: $$ A = B \implies A \subset B \implies A' = B' \implies A-B = ...
0
votes
1answer
28 views

Can a finite set that is odd and a finite set that is even have the same number of subsets?

A more clear way of asking it I suppose would be. Supposing a finite set 'S' that is not empty, how would I be go about proving that the number of subsets of S if the total number of elements is odd, ...
2
votes
1answer
47 views

Cardinality of the set of functions $f: A \to B$ where where $|A|=\aleph_0$ and $|B|=2^{\aleph_0}$

Let $X$ be the set of all functions $f: A \to B$ where $|A|=\aleph_0$ and $|B|=2^{\aleph_0}$. Using some cardinal arithmetic, one can show that $|X|=2^{\aleph_0}$. However, I wanted to construct a ...
1
vote
1answer
39 views

Applying union and power set in different orders.

Show that $E$ is always equal to $ \bigcup\{x:x\in \mathcal{P}(E)\} $ but that the result of applying $\mathcal{P}$ and $\bigcup$ to $E$ in the other order is a set that includes $E$ as a subset, ...
1
vote
1answer
56 views

Should it be allowed to apply classical logic to set theory?

It is well known, that the generalized continuum hypothesis isn't provable from the standard axiom system ZFC. GCH (generalized continuum hypothesis). For every infinite set A, there isn't a set M ...
0
votes
1answer
67 views

Isn't x/E = y/ E ⇔ x E y deduced, not just x/E = y/ E ⇒ x E y from (a) x/ E≠ Ø, (b) x/E ∩ y/ E ≠ Ø ⇔xEy?

"Theorem 3. Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. Then (a) Each $x/\mathscr E$ is a nonempty subset of $X$. (b) $x/\mathscr E \cap y/\mathscr E \neq \emptyset$ if ...
-1
votes
1answer
28 views

Questions on symmetric difference of events

From a comment on my math overflow question: No, $P(A\bigtriangleup B)=0$ means $A$ and $B$ are essentially the same except in situations that almost surely do not happen. $P(A)=P(B)$ says much ...
0
votes
1answer
33 views

What is a first order formula for $\left\vert{S}\right\vert \equiv 0 \mod 2$ in set theory?

What is a first order formula for $\left\vert{S}\right\vert \equiv 0 \mod 2$ using only ZF axioms? My intuition makes me think about something like $\exists x \cdot \mathbb{P}(x) = S$, but this ...
0
votes
3answers
38 views

How to disprove $X ∩ Y ≠ ∅$ and $X ∩ Z ≠ ∅$ then $Y ∩ Z ≠ ∅$

For all sets $X,Y,Z$. If $X ∩ Y ≠ ∅$ and $X ∩ Z ≠ ∅$ then $Y ∩ Z ≠ ∅$. Would I take the contrapositive of the implication and disprove that?
1
vote
1answer
40 views

Proof for sets and functions.

I have been proving problems like this all day with ease, but this is is just puzzling to me. Where do I start? Also, a site with questions and answers to problems like these.
0
votes
3answers
57 views

What do the Squared Brackets stand for in $\mathbb{Z}[\mathrm{i}] $ [duplicate]

What do the Squared Brackets stand for in e.g. $\mathbb{Z}[\mathrm{i}] $?
4
votes
2answers
259 views

Countability of a Totally Ordered Set

Prove or disprove the following statement: If $X$ is a totally ordered set with the property that for every two elements $x$ and $y$ in $X$ such that $x<y$, there exists another element $z$ ...
3
votes
1answer
42 views

Countability of Collection of All Finite Subsets of a Countable Set

Let V be a countable set. Ok, first thing to say is that this isn't a question as to whether $S = \{ A \subseteq V \mid A \ \text{finite} \}$ is countable -- there are plenty of other duplicates on SE ...
0
votes
1answer
26 views

Difference finitely many and arbitrarily many

Is there a difference between "finitely many" and "arbitrarily many"? Some notes I am reading are making a point of distinguishing between the two and I thought they meant the same thing.
0
votes
1answer
27 views

neighborhood basis on a set

Given a topological space $(X,\tau)$ I know perfectly what is a neighborhood basis at $x\in X$. Now suppose that $X$ is just a set, fix a point $x\in X$ and consider a collection $\mathcal B(x)$ of ...
0
votes
3answers
47 views

Can one write an open interval as a union in two different ways?

Can one write an open interval say $(0,1)$ in the following two different manners: $\bigcup\limits_{n=1}^{\infty}(0,1-\frac{1}{n})$ and $\bigcup\limits_{n=1}^{\infty}(0,1-\frac{1}{n}]$. Are these two ...
1
vote
1answer
47 views

Proving a total-order is a well-order if and only if every initial segment is determined by an element

I managed to prove the $\longrightarrow$ part, but I'm not entirely sure how to prove the second part. I can assume by contradiction that the total order $(X, \leq)$ is not a well-order, which means ...
0
votes
2answers
33 views

Is it correct to say z $\in x/\mathscr E$ when x/$\mathscr E$={y∈X| y$\mathscr E$x}?

Relation R is a subset of cartesian product, which has ordered pairs as its elements. A relation R from A to B ⇔ R⊆ A×B ⇔ (a, b)$\in R$ ⇔ aRb ⇔ R={(a, b)| a, b ∈ A×B} ⇔ a is R- related to b In ...
0
votes
2answers
60 views

In the structure $\langle \mathbb{Q}, < \rangle$ which of the ZF axioms hold?

In the structure $\langle \mathbb{Q}, < \rangle$ which of the following axioms hold? How about when we use the weak versions of the axioms (all $\leftrightarrow$ replaced with $\rightarrow$ )? ...
5
votes
1answer
37 views

Axiom of Powers

Something I'm failing to understand from Halmos "Naive Set theory" book. If $\Phi $ is a collection of subsets of a set E (that is, $\Phi$ is a subcollection of $\rho (E)$), then write First of ...
-2
votes
0answers
36 views

Is it possible to have two difference (appropriate) universal sets for a collection of sets?

Is it possible to have two different (appropriate) universal sets for a collection of sets? Would having different universal sets create any problems? I'm not sure how to clarify it any more, all of ...
1
vote
1answer
33 views

Surjective function from a countable set

In Lang "Real and Functional analysis" is demonstrated that given a countable set $A$ and a function $f: A \rightarrow B$ which is surjective on $B$, then $B$ is finite or countable. Proof: Consider ...
1
vote
1answer
30 views

Three kinds of sub-structures on a set with an injective function?

Suppose we have an injective function $f: S \to S$ for non-empty $S$. Intuitively, it seems to me that the set $S$ can be partitioned into "sub-structures" using $f$ as a kind of successor function, ...
3
votes
1answer
103 views

Is ${\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},…\}} $ a set?

Define M: $$ \emptyset \in M \wedge \forall x\in M \rightarrow \{x\}\in M $$ How to construct this set in ZFC system? I know the axiom schema of replacement and the definition of recursion, but ...
3
votes
1answer
26 views

Symmetric difference and indicator function

Associativity of symmetric difference of sets In that post it said the symmetric difference is $$1_{A\mathbin{\Delta} B} = 1_A + 1_B - 1_{A\cap B}$$ Why is it not $$1_{A\mathbin{\Delta} ...
1
vote
1answer
27 views

Multiplication Principle Proof

I am trying to prove the following; If $X$ and $Y$ are finite, then $|X \times Y| = |X||Y|$. Now, I'll define a bijection $g:\mathbb{N_{n}} \rightarrow X$ and a bijection $f: \mathbb{N_{m}} ...
0
votes
0answers
57 views

I can't understand the formal definition of $\mathbb{R}$

I've always intuitively understood this set in intuitive sense, as "all numbers on the number line". However, now I want to know the formal definition: Consider the set of rational numbers, ...
0
votes
0answers
44 views

Finding cardinality of a set which sum of its elements equal to an integer

Let $A_m$ be a set such that $$ A_m = \left\{(a_1,a_2,\ldots, a_n)\in \mathbb{N}^n |\, a_1 + a_2 + \ldots + a_n = m \right\} $$ Can we calculate cardinality of $A_m$, i.e Card(A_m) = |A_m| = ? Thank ...
0
votes
3answers
33 views

Is “$A_i=A_j$” in the definition of a partition correct?

"Definition 5 Let X be a nonempty set. By a partician P of X we mean a set of nonempty subsets of X such that: (a) If A, B$\in$P and A$\neq$B, then A$\bigcap$B=$\emptyset$ (b) $\bigcup \limits_{C ...
0
votes
1answer
39 views

$\{x|x$ is a positive integer definable in one line of type $\}$

$\{x|x$ is a positive integer definable in one line of type $\}$ I found this example in Enderton's book of set theory ! What does it mean ? I have no idea about "definable" and "in one line of ...
3
votes
6answers
89 views

Why $\{ \emptyset \} $ is not a subset of $\{ \{\emptyset \} \} $ [duplicate]

Following are two statements from Enderton's book on set theory, I fail to understand that if empty set is a subset of every set then why can't it be a subset of $\{ \{ \emptyset \} \} $ (1) ...
2
votes
1answer
85 views

What does ≺ represent?

I've been reading through Axiomatic Set Theory by Patrick Suppes and stumbled upon this symbol, ≺, on page 97. The definition reads as follows: We now define in the expected manner the relation ≺ of ...
3
votes
1answer
44 views

Is there a general term for $A\oplus B = \{a \oplus b | a\in A, b\in B\} $?

Is there a general term that specifies that if an operator $\oplus$ is applied to two sets, it's actually applied to all possible pairs of elements of the two sets? Or is that always the case and ...
0
votes
2answers
42 views

Mapping from the integers to rationals

My book gives the following definition of mapping: Definition: If $S$ and $T$ are nonempty sets then a mapping from $S$ to $T$ is a subset, $M$, of $S \times T$ such that for every $s \in S$ ...
1
vote
2answers
43 views

Can the Recursion Theorem be proved in Peano Arithmetic?

A recursive function on $\mathbb{N}$ can be defined as follows: Given an element $a \in \mathbb{N}$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we can define a function ...
2
votes
3answers
82 views

Set Theory: Proof of existence of surjection

As part of a larger proof, I have to show that there does not exist a surjection $\pi: A \rightarrow P(A)$, where $P(A)$ is the power set of the set $A$. I am having a problem with the proof given in ...
1
vote
2answers
88 views

How to formally write down mapping to a category with math notation?

I'm writing a paper and would like to describe my approach with formulas too. However, I have a problem with writing down the following mapping step (just a tiny step of my algorithm). Imagine, that ...
1
vote
1answer
48 views

How can I find the size of this set?

I'm sorry in advance for my bad english. I got this question for homework and just can't solve it: There are 2 sets, $A$ and $B$ which are contained in $\mathbb{N}$ (the set of all natural ...
1
vote
1answer
43 views

Textbook Accompanying Naive Set Theory

I'm in the process of self-studying from the very popular Halmos book "Naive Set Theory" and I must say I can say only the best about the book. However, although the book has some excercises I would ...
0
votes
1answer
18 views

Proving a statement from two basic ones using the logical equivalences

Take as a known fact that, for any sets A and B, A ⊆ B if and only if A ∩ B = A: Let X, Y , and Z be sets and ...
1
vote
1answer
26 views

How to proof that $f^{-1}(\sigma(\mathcal C))\subseteq\sigma(f^{-1}(\mathcal C))$?

Let $f:X\to Y$ be a function, $\mathcal C$ be a family of subsets of $Y$. I am convinced that $f^{-1}(\sigma(\mathcal C))=\sigma(f^{-1}(\mathcal C))$, where $\sigma(\mathcal A)$ is the ...
0
votes
4answers
45 views

Proof verification for $A \subset B$ iff $A - B = \varnothing$

I am trying to write a proof for $$A \subset B\quad\text{if and only if}\quad A - B = \varnothing$$ Starting from the left side: $$x \in A \subset B$$ $$x \in A \land x \in B$$ $$x \in A \cap B$$ ...
1
vote
1answer
41 views

$∂(A\cup B)$ is a subset of $∂A \cup ∂B$

Please let me know if you think my proof of the above is correct. ($∂A$ denotes the boundary of $A$). Suppose $\vec{x}\in ∂(A\cup B)$. Then $\vec{x}\in \overline{A \cup B}=\bar{A}\cup\bar{B}$ and ...
0
votes
1answer
22 views

is N~N-{1,2,3…n|n is in N}

so i figured this was a special case of the proof of the compliment of a countable set X and finite subset A is countable so i start by assuming that N-{1,2,3...n} is finite. then ...
0
votes
2answers
56 views

Nothing contains everything

"It follows that, whatever the set $A$ may be, if $B = \{x \in A: x \notin x \}, $ then, for all $y$, (*) $ y\in B $ if and only if $(y \in A$ and $y \notin y)$ Can it be that $B \in A$? ...
0
votes
2answers
36 views

In the construction of integers, is the existence of an additive inverse assumed?

In all the constructions of the integers I've seen they seem to assume the existence of an additive inverse but I think I'm missing something because all the constructions start only with the set of ...
0
votes
1answer
32 views

Convention about distinctness of the elements of a set

Sooo...if we write something as: Let $$A=\{a,b,c\}$$, does it implicitly mean that a,b,c are distinct from each other? If the problem does not explictily state this? And i've encountered a context ...
1
vote
0answers
37 views

Proving the Commutativity of Set intersection.

Hi this is basically the question: Write down a formula which states that for any two sets $X$ and $Y$ , the set $X \cap Y$ is the same as the set $Y \cap X$. Then, prove this statement. The union ...
0
votes
2answers
62 views

Proof for $A \cup B = B$ if and only if $A \subset B$

I am trying to define a proof for $A \cup B = B$ if and only if $A \subset B$ I started with: $$A \cup B$$ $$x \in A \lor x \in B$$ but I am unsure on how to continue.