Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-set-theory]

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, differences and complements, De Morgan's laws, Venn diagrams, relations, etc. More advanced topics should use (set-theory) instead.

0
votes
0answers
5 views

Is the set of all choice sets on a infinite partition on $\mathbb N$ equal in cardinality to $\mathcal P(\mathbb N)$?

Let $\mathcal S=\{\{2n,2n+1\} |\ n \in \mathbb N\}$ Define: $X \text{ is a choice set on } \mathcal S \iff X \subset \mathbb N \wedge \forall s \in \mathcal S \exists! x \in X (x \in s)$ Define $\...
0
votes
3answers
31 views

How do I prove set inequality: $(A-B)-C=(A-C)-(B-C)$

We are letting A,B, and C be non-empty sets. My issue with this is that I do not know how to prove it formally. Intuitively I just say let $x\in (A-B)-C$, so it is clear to me that $x$ is in $A$ but ...
0
votes
0answers
16 views

Partition with possibly empty elements

Is there a name for $(A_i)_{i\in I}$ a family of subsets of $E$ such that the $A_i$'s don't intersect each other and the union of the $A_i$'s equals $E$?
0
votes
3answers
35 views

Is there any notation for testing if A is in B?

I want to do a union over sets $A_i$, but only if $A_i \in B_i$. I don't know any way to write this concisely. I was trying to write something with unions and intersections but I can never get it to ...
0
votes
0answers
24 views

Lemma for proving Zermelo's theorem

I'm trying to understand the following lemma in Bourbaki's set theory (chapter III, §2,no. 3,Lemma 3): Lemma 3: Let $E$ be a set, let $S$ be a subset of $P(E)$, and let $p$ be a mapping of $S$ into $...
0
votes
1answer
26 views

Find and prove that a proper subset $A\subset \Bbb N$ such that $A\approx \Bbb N$.

Can anyone check my working please? Find and prove that a proper subset $A\subset \Bbb N$ such that $A\approx \Bbb N$. Let $A$ be the set of even numbers, it is clear that $A\subset \Bbb N$ since ...
1
vote
1answer
31 views

Is there a paradox with the intuitive notion of set?

I understand that, first, the intuitive notion of a set is of a collection whose identity is entirely determined by its members. Second, that this implies that the set in this case is not defined by ...
2
votes
0answers
41 views

Proof verification- $ \sigma $ - Algebra, Algebra, Ring

I want to prove following for a set $ X \neq \emptyset $ : $ M \subset P(X) $, where $ P(X) $ is the power set. 1) Any Ring is an Algebra 2) Any Algebra is a Ring 3) Any Ring is a $ \sigma $ -...
3
votes
0answers
32 views

Mathematical meaning of repeated power set operations on $A\cup B$

Recognizing that $A\cup B$ contains elements in $A$ or $B$, $\mathscr{P}(A\cup B)$ contains subsets of the union, and $\mathscr{P}(\mathscr{P}(A\cup B))$ contains the ordered pair $(a,b)$ for some $a\...
3
votes
2answers
43 views

All sequences are sets?

I have learned that: A sequence is a function from a subset of natural numbers to some set A A function is a relation with certain properties A relation is a subset of a Cartesian product It seems, ...
-1
votes
1answer
74 views

Proving that $\text{Sym}(\emptyset)$ is a group without treating functions as sets

Consider the statement: "For each set $A$, there exists a function from the empty set to $A$." Can we determine whether this statement is true or false, without treating functions as sets (i.e. ...
0
votes
0answers
23 views

Does closed under unions of chains imply closed under unions of upward directed families of sets?

In the book "A Course in Universal Algebra" from Burris and Sankappanavar, in the section 1.5, during the exercises, there is something like that: "Given a set $A$ and a family $K$ of subsets if $A$, ...
0
votes
0answers
15 views

Cardinality of $[\lambda]^\kappa$

Let $\kappa \leq \lambda$ cardinals with $\lambda$ infinite, and $[\lambda]^\kappa=\{Y\subseteq\lambda : ot(Y,\in)=\kappa\}$. I want to show that $[\lambda]^\kappa \asymp\ ^\kappa\lambda$. I've ...
0
votes
0answers
23 views

Notation for the operator that transforms sets (unordered) into tuples (ordered)?

Take a set $\mathcal{A}\equiv \{a_1,a_2,a_3\}$ of real numbers. Is there any specific notation in math for the "operator" that transforms $\mathcal{A}$ into the 3-tuple (ordered) $$ (a_1,a_2,a_3) $$ ...
0
votes
2answers
31 views

How to show $\operatorname{card}(\omega+1)=\omega$

Apparently $\operatorname{card}(\omega+1)=\omega$. This means that there is an order $<$ on $\omega+1$ such that there is an isomorphism of ordered set $f$, $(\omega+1,<) \cong (\omega,\in)$, ...
-2
votes
1answer
48 views

Well order of naturals [on hold]

I have an exercise that asks me for 15 non-isomorphic well order types of natural numbers, I have some, can you help me with other well uncommon orders? Thank you
0
votes
0answers
34 views

Inverse function of a product space

I want to prove the continuity of a function $f: (X_1,\tau_1) \times (X_2,\tau_2) \rightarrow (X'_1,\tau'_1) \times (X'_2,\tau'_2)$ where $f(x,y) = (f_1(x),f_2(y))$ and my question is: What is $f^{-...
1
vote
4answers
47 views

Is the condition $x\in\mathbb{R}$ necessary to the set statement $\{x \in\mathbb{R} \vert x> 0\}$?

Forgive my ignorance. Is the condition $x\in\mathbb{R}$ necessary to the set statement $\{x \in\mathbb{R} \vert x> 0\}$? In other words, if $x$ is greater than zero, then is it not, by definition, ...
0
votes
1answer
29 views

If $A, B, C$ are three sets with $A \subseteq B$ and $B \in C$, does it follow that $A \subseteq C$?

Looking at this question, and by playing around with examples, it is clear to me that we can construct sets $A, B, C$ such that $A \subseteq B$ and $B \in C$ and $A \subseteq C$. But is this always ...
0
votes
1answer
23 views

Is a Relation to a certain power composed with itself commutative?

I'm doing some proof right now and I can't remember what my professor said in class regarding whether $$R^n\circ R = R\circ R^n$$ for an arbitrary n.
1
vote
2answers
46 views

Evaluating $|A\cup B|$

$A$ and $B$ are the subsets of the same universal set $$|A' \cap B| = 2$$ $$|B'-A| = 4$$ $$|A-B|' = 11$$ $$|B|' = 13$$ Evaluate $|A\cup B|$ There are too many equations so I ...
1
vote
2answers
30 views

Filtered colimits in the category of sets: an equivalence relation

A category $\mathsf{I}$ is filtered if it is nonempty, for any $i,j \in \mathsf{I}$ there is $k \in \mathsf{I}$ and morphisms $f\colon i\to k$ and $g\colon j\to k$, for any pair $f,g\colon ...
0
votes
1answer
44 views

Set theory proofs

Let $X$ be the set of $A, B \subseteq X$. Show that: a) $(A \cup B)^c = A^c \cap B^c$ b) If $A \subseteq B $, then $B^c \subseteq A^c$ c) $(A^c)^c = A$ d) $A - B = A \cap B^c$ Using the Venn ...
3
votes
1answer
61 views

Linearly ordering the power set of a well ordered set with ZF (without AC)

As the title says, my question is, how one can use only ZF-theory to prove that the power set of A, whereby (A, <) is a well-ordering, can be linearly ordered?
0
votes
3answers
62 views

Is ∅ ⊈ { ∅, 1, 2 } False?

Is this ∅ ⊈ { ∅, 1, 2 } true or false ? Also, I am confuse since this { ∅, 1, 2 } has already contain a ...
9
votes
3answers
893 views

Is $∅ ∈ \{ \{∅\} \}$ true?

If $ \{\emptyset\} ∈ \{\emptyset,\{\emptyset\}\} $ is true, does it mean this $ \emptyset \in \{\{\emptyset\}\} $ true ? If it is not, why it is false? Also, does $ \{\{\emptyset\}\}$ mean $\{\...
0
votes
3answers
42 views

Problem understanding the Cantor Theorem's proof

I can intuitevely picture the power set of A to be of a greater cardinality than A, as it permits multiple combinations of elements of A. However, I couldn't understand the usual proof that comes with ...
0
votes
1answer
24 views

Set theory operations proof

Demonstrate that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ How can I proof that? Well, if I pick up an $ x \in A$ and the same $ x \in B \cup C$, then $x \in (A \cap (B \cup C))$. If $ x \...
1
vote
1answer
52 views

Is there a notation for least/greatest element of partially ordered set?

Definition. Let $P=(S,\leq)$ be a partially ordered set. If it is true that $$(\exists s_0\in S)\ (\forall s\in S)\ \ s\leq s_0$$ then $s_0$ is said to be a greatest element of $S$. Of course, ...
0
votes
0answers
52 views

definition of countable infinite character without the use of N

Let's say a family of sets, $F$ has finite character iff $\forall X: [X \in F \leftrightarrow \forall E \subseteq X: E \, finite \rightarrow E \in F)$ or more precise: let's say a family $F$ has ...
2
votes
0answers
34 views

General colimits and filtered colimits in the category of sets

A category $\mathsf{I}$ is filtered if $\mathsf{Ob(I)} \neq \varnothing$, for any $i,j \in \mathsf{Ob(I)}$ there is $k \in \mathsf{Ob(I)}$ and morphisms $f\colon i\to k$ and $g\colon j\to k$...
0
votes
2answers
36 views

Proving a function of set is bijective.

I want to show that $\mathcal P(A\cup B)$ equipotent $\mathcal P(A)\times \mathcal P(B)$, with $A,B\neq\emptyset$ and $A\cap B=\emptyset$. So I have to find a bijective function from any side I want ...
0
votes
1answer
31 views

Elementary Set Theory : Are my proofs correct?

Prove that the arbitrary intersection indexed over the power set is the empty set and that the arbitrary union indexed over the power set is the entire set itself. $a) \bigcap_{A\in P(X)} A = \...
1
vote
1answer
34 views

How do I interpret the formating of these given structures and prove they are not isomorphic?

$(\Bbb{Z}^+,\cdot)$ and $(\Bbb{Q}^+,\cdot)$ First and foremost, I am not looking for a direct answer just a method of interpreting what these "structures" are, and some techniques I can use to prove ...
0
votes
3answers
33 views

Proof that $S=\{x\in\mathbb{R}^2 | x_1>0, x_2>0 \}$ is an open set

We have the following criteria: If $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ continuous, then the sets $S_1=\{x\in\mathbb{R}^n \ | \ f(x)>0 \}$, $S_2=\{x\in\mathbb{R}^n \ | \ f(x)<0 \}$, $...
2
votes
2answers
64 views

Finding $\phi^{-1}({id_{P(\mathbb{N})}})$, where $\phi:(\mathbb{N}\to\mathbb{N})\to(P(\mathbb{N})\to P(\mathbb{N}))$ and $\phi(f)(A) = f^{-1}(A)$

I have function $\varphi : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))$ and $\varphi(f)(A) = f^{-1}(A)$. I have to find $\varphi^{-1}({id_{P(\mathbb{N})}})$, and I don't have ...
0
votes
2answers
25 views

Determine if $R \subseteq A \times A$ is reflexive, transitive, symmetric, antisymmetric

Let A be the set of bit strings $a = a_1a_2 \ldots a_9$ of length 9. Let $R \subset A \times A$ be the set of pairs $(a, b)$ such that $a_1 = b_1$ or $a_2 = b_2$. Decide whether or not the relation $...
0
votes
1answer
24 views

Partition of an infinite set into two infinite sets

I wanted to try and prove this statement which looks seemingly true. An infinite set $X$ can be partitioned in such a way that $X = X_1 \cup X_2$ where $X_1$ and $X_2$ are infinite subsets of $X.$ ...
-3
votes
1answer
35 views

Existence of set $B=\{x\in A\mid x\notin f(x)\}$ in Cantor's theorem.

For the proof in wiki: https://en.m.wikipedia.org/wiki/Cantor%27s_theorem $B=\{x\in A\mid x\notin f(x)\}$ Example, where $B$ does NOT exist: $A=\{a,b\}$ $P(A)=\{\{a\},\{b\},\{a,b\},\emptyset\}$ ...
1
vote
1answer
19 views

Set theoretic proof involving union and intersection identity

How to prove that $$A\cap(B\cup C)=(A\cap B)\cup C \implies C\subset A$$ without returning back to symbolic logic. I've tried expanding with the distributive identities but it's not very clear to me ...
2
votes
1answer
52 views

Show that the set of all algebraic numbers over the field of rationals is countable

An algebraic number over the field of rationals is defined as any root of a polynomial with real coefficients. That is an $x$ such that $p(x)=0$ where $p(x)$ is of the form $x^n+a_{n-1}x^{n-1}+...+...
1
vote
2answers
30 views

Inverse of set operations

$A \cup B \equiv C $ then what is $A$ in terms of $B,C$? I tried to use $A\cup B \equiv (A-B)\cup(A \cap B)\cup(B-A) $ to find a similar expression for $A \cap B$ but got nowhere. From the ...
0
votes
3answers
41 views

Does symmetry and transitivity imply reflexivity for nonempty binary relation?

I've seen a few answers to this, like here and but they are not satisfying to me (possibly too advanced). The definitions in my book are as follows: A binary relation $\mathrel{R}$ on two sets $A$ ...
0
votes
0answers
47 views

Define a subset from another set

I have a closed disc $D$ \begin{equation} D=\{(x,y) \in \mathbb{R}^{2}: (x-a)^{2}+ (y-b)^{2} \leq R^{2} \} \end{equation} centred at the origin $(a,b)=(0,0)$ and with radius $R=15$ [m]. I have ...
1
vote
1answer
11 views

Find an appropriate set and a function such that neither is a subset of the other.

I'm supposed to find a function $f:X\rightarrow Y$ and a set $A\subseteq X$ such that neither $f(A^{c})\subseteq f(A)^{c}$ nor $f(A)^{c}\subseteq f(A^{c})$. I really don't know what to look for or ...
-1
votes
1answer
32 views

On proving $\omega^{\epsilon} = \epsilon$

How can I prove that $$\omega^{\epsilon} = \epsilon$$ where $\omega =\{0, 1, 2, 3, 4, ...\}$ and $\epsilon = \{\omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \omega^{\omega^{\omega^\omega}}, ...\}...
1
vote
1answer
75 views

What is the definition of “equality”

I thought we could define "the equality on set $A$" by the relation $\{(a,a):a\in A\}\subseteq A^2$. However, no book has this definition. Moreover, some books say that this is the "diagonal relation"....
1
vote
3answers
43 views

What is the difference between “equality” and “equivalence relation”

I think equality is just an instance of equivalence relation. An equivalence relation can be defined in the set theory, but how can we define "equality"? I wonder what equality is.
1
vote
1answer
55 views

I heard that the empty set $\emptyset$ is bounded. But I think this statement is not correct.

In Rudin's "Principles of Mathematical Analysis", there is the following definition of bounded. Definition: Suppose $S$ is an ordered set, and $E \subset S$. If there exists a $\beta \in S$ such ...
2
votes
1answer
36 views

A sequence of $rs + 1$ real numbers has an increasing subsequence of length $r + 1$ or a decreasing subsequence of length $s + 1$.

Problem: Prove the following: a sequence of $rs + 1$ real numbers has an increasing subsequence of length $r + 1$ or a decreasing subsequence of length $s + 1$. Solution: Define a partial ordering on ...