Stack Exchange Network

Stack Exchange network consists of 175 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
1answer
24 views

Prove a function is onto if its domain is a Cartesian product

I've been working on this problem: Suppose the function $f:\mathbb Z \times \mathbb Z \to \mathbb Z$ is defined by $f(n,m)=2nm-1$. Is this function onto? After a while, I figured out that $4$ can'...
0
votes
0answers
16 views

Cardinality of the unit square and union of sets of size $c$ are equal

So this is a simplified version of the theorem where union of sets of cardinality $c$ has cardinality $c$. $c$ refers to the continuum. We try to prove instead the union of sets of cardinality $c$ ...
0
votes
1answer
19 views

$\omega +1 $ is not isomorphic to $\omega$ (in the well-ordering by $\varepsilon$)

$\omega +1 $ is not isomorphic to $\omega$ (in the well-ordering by $\varepsilon$). I see that $\omega +1$ does have maximal element but $\omega$ is not so there is no ismorphism between $\omega +1 $ ...
1
vote
1answer
16 views

Why does $A_j \subseteq cl ( \bigcup_{m=1}^n A_m )$ imply $cl(A_j) \subseteq cl ( \bigcup_{m=1}^n A_m )$?

Why does $A_j \subseteq cl \bigg( \cup_{m=1}^n A_m \bigg)$ imply $cl(A_j) \subseteq cl \bigg( \cup_{m=1}^n A_m \bigg)$? This is intuitive, but I was thinking of whether one can be sure that there are ...
1
vote
2answers
18 views

$ A = (A\cap E^c) \cup (A\cap E)$?

$ A = (A\cap E^c) \cup (A\cap E)$ ? is that correct for any sets A and E? Here is my proof: Let $x\in A$ since $A\subset A\cap E$ $\ x\in A\cap E \cup (A\cap E^c)$ now let $x\in (A\cap E^c) \cup (A\...
0
votes
1answer
21 views

If $A_n \subseteq B_n$, then $\cup_{n\in\mathbb{N}} A_n \subseteq \cup_{n\in\mathbb{N}} B_n$?

Is it true that if $A_n \subseteq B_n$ for all $n\in\mathbb{N}$, then $\cup_{n\in\mathbb{N}} A_n \subseteq \cup_{n\in\mathbb{N}} B_n$ and $\cap_{n\in\mathbb{N}} A_n \subseteq \cap_{n\in\mathbb{N}} B_n$...
0
votes
1answer
15 views

Prove semiring quality: If $A_k\in P$, all $k\in [1:n]$ then $\bigcup_{k}^n A_k = \bigcup_{k} \bigcup_{i=1}^N C_{ki}$

Let $X$ be a set, $P$ be semiring of $X$ subsets. Prove: If $\forall\ 1 \leq k \leq n, A_k\in P$, then $\bigcup_{k}^n A_k = \bigcup_{k} \bigcup_{i=1}^n C_{ki}$, here $C_{ki} \in P, C_{ki}$ - ...
0
votes
2answers
38 views

Can a element of a set be also a subset? (Set theory in predicate caculus)

I'm not even sure if this is the question I have to make... I'm trying to formalize (using first-order predicate calculus) a list of rules in a grammar of certain natural language. The first one is ...
0
votes
1answer
17 views

Cardinality: Injection between subsets of Uncountable set

assuming, S is infinite uncountable, I am trying to come up with injective f: (S union N) -> S. Where N is naturals. So far I created S0 which consists of infinite sequence of elements of S, such that ...
0
votes
1answer
32 views

Show $\exists X,Y,Z \subset S$ disjoint and $|X|=|Y|=|Z|=c$

Given $|S| = c$ and $c$ here represents the continuum. Given $x,y,z \in S$ distinct. Want to show $\exists X,Y,Z \subset S$ such that $|X|=|Y|=|Z|=c$ and $x \in X, y \in Y, z \in Z$. I tried ...
0
votes
1answer
29 views

Products and the axiom of choice

Here: Universal property of the direct product, proof verification Matematleta noted in the comments, that the definition of the product uses the axiom of choice by default. Why is that? The ...
-3
votes
1answer
19 views

Proving $A⊆B\Longrightarrow(C∩A)⊆(C∩B)$ [on hold]

Let $A$, $B$ and $C$ be sets. Let $U = A ∪ B ∪ C$ be the universal set. Prove$$A ⊆ B \Longrightarrow (C ∩ A) ⊆ (C ∩ B).$$
2
votes
1answer
27 views

Mapping to or from elements of a set, when that set is an element

This is an embarrassingly stupid question, but a colleague and I disagree, and it is relevant to what we are trying to do. The question is, suppose you have a pair of sets $A = \{1, 2, 3\}$ and $B = \{...
-3
votes
1answer
32 views

Help with the proof of Theorem 1 (Chapter 2) of Suppes' “Axiomatic Set Theory” [on hold]

See the proof of Theorem 1 : $x \notin 0$ page 21 and page 22. Anybody can help me with the first step of the proof. I don't understand why the author uses in this step "x belongs to empty set"...
-1
votes
2answers
27 views

Help proving the following using Archimedean Property of Reals [duplicate]

For each $n=1,\,2,\,3,\dots$, let $D_n = \displaystyle{\left(-\frac{1}{n},1+\frac{1}{n}\right)}$. Prove that $\displaystyle{\bigcap_{n=1}^\infty D_n} = [0,1]$. Hello, I've been stuck on this problem ...
0
votes
2answers
31 views

Syllogism question using set theory notation

i'm stuck on a question where I have to explain the set theory notation of the syllogism below; boats are vessles $(A ⊆ B)$ boats operate in water $(A ∈ C)$ or $(A ⊆ C)$ Some vessles operate in ...
0
votes
0answers
47 views

If $S$ is countable then $S_0 \subset S$ is countable.

Define "countable" in the following way: $S$ is said to be countable if $S$ is finite OR $|\mathbb{N}| = |S|$. So my textbook proves the theorem by considering two cases. Case 1: $S$ is finite. ...
0
votes
0answers
43 views

Is the set of all finite sets of powers of 2 countable?

Sort of confused on how to approach this question. I know that the set of powers of 2 is infinitely countable and the set of all sets of powers of 2 is the power set which isn't countable because it's ...
2
votes
1answer
22 views

Is the multivariate function $G:\mathbb{Q} $ x $ \mathbb{Q} \rightarrow \mathbb{R}$ where $G(x, y) = r + \sqrt 2 * s$ onto, one-to-one, or both?

I recently had a quiz in which I was given the following question: Define a function $G:\mathbb{Q} $ x $ \mathbb{Q} \rightarrow \mathbb{R}$ where $G(x, y) = r + \sqrt 2 s$. Is G onto, one-to-one, ...
2
votes
2answers
46 views

Is $\bigcup\limits_{i=1}^{\infty} \left(-\frac{1}{i},\frac{1}{i}\right)$ finite?

In a practice exam, there is a question asking if $$ \bigcup\limits_{i=1}^{\infty} \left(-\frac{1}{i},\frac{1}{i}\right) $$ is finite, countably infinite, or uncountable. The solution to the practice ...
7
votes
3answers
88 views

Connection between logic and set theory?

I just noticed there is a similarity between logic operations on propositions and the operations of set theory. It seems: $$\begin{array}{llll} \textrm{disjunction} & (-)\vee (-)& \textrm{...
-2
votes
2answers
41 views

Set $A$ is countably infinite if and only if there exists a bijection $f: \mathbb{N} \rightarrow A$

Using the fact that for any $A$, $A$ is countably infinite if there exists a bijection $f: A \rightarrow \mathbb{N}$, how do I prove the statement: $A$ is countably infinite if and only if $\exists$ ...
1
vote
2answers
58 views

Prove that $|\mathbb{N}\times \mathbb{R}| = |\mathbb{R}|$

I'm trying to prove the equality between the cardinalities: $|\mathbb{N}\times \mathbb{R}| = |\mathbb{R}|$ ($\mathbb{N}\times \mathbb{R}$ is cartesian product from $\mathbb{N}$ to $\mathbb{R}$). I ...
0
votes
0answers
32 views

linearly ordered family of sets cardinality greater than supremum of individual sets

Does there exist a set $X$ linearly ordered by $\subset$ where $|\bigcup X|>\sup\{|x|:x\in X\}$? I'm having trouble thinking around constructing one. I'm fairly certain that finite sets won't work,...
2
votes
2answers
35 views

Prove that if $\alpha \subseteq \mathbb{R}$ is *ideal* then $\alpha = \{0\}$ or $\alpha = \mathbb{R}$

This is a problem from an old homework assignment which I never got, and I've decided to go back and try again. As a side note, I'm quite new to writing proofs. Definition: $\alpha \subseteq \mathbb{...
0
votes
0answers
32 views

Is it meaningful to order infinite subsets of $\mathbb{N}$ by probabilistic density?

This is based on a recent question where is was pointed out that the probability of finding a prime tends to 0 as you move into larger and larger numbers. Conversely the probability of finding a ...
0
votes
0answers
34 views

How to represent equivalence relation as a function in set theory?

While writing a proof for below statement, I stuck at representing equivalence relation as a function. Let $f : A → B $ be a function and let G be an equivalence relation in B. Prove that the ...
2
votes
0answers
71 views

Can P vs NP be written as a statement in set theory?

For the problem of $P\neq NP$ it would be useful to have a precise mathematical statement of the question in some logic like set theory or some generalisation of it. And then we could ask given the ...
2
votes
1answer
99 views

Are there any simple and interesting conclusions from the Collatz Conjecture?

The Collatz Conjecture here is the original conjecture. For example, for which $n$'s we have $L(n)=L(n+1)$, where $L(n)$ is the steps needed to reach the integer 1 for the first time? I have examined ...
0
votes
1answer
18 views

Alternative definition of sigma algebra generated by random variable

Let $(\Omega, \mathcal F)$ be a measurable space (especially a probability space), and let $Y : \Omega \to \mathbb R$ be measurable. Then we define the sigma algebra generated by $Y$ to be $$ \sigma(Y)...
4
votes
3answers
309 views

Can we expand “induction principle” to a partial order $(X, \leq)$?

We know that every infinite can be made well-ordered with an unknown order. Also we can expand the induction principle on any infinite set in the sense that it can made well ordered. Now partially ...
1
vote
1answer
60 views

Is there any bijection between $\mathbb{R}$ and $\mathbb{R}^2$? [duplicate]

Is there any bijection between $\mathbb{R}$ and $\mathbb{R}^2$ ? If have then what is the mapping ? Please define the mapping. They have same cardinality then it is possible to have a bijection ...
0
votes
2answers
44 views

How to produce uncountable ordinal from universe?

A universe $U$ is defined as the following. (1) If $x\in u\in U$, then $x\in U$. (2) If $x\in U, u\in U$, then $\{x,u\}\in U,x\times u\in U$. (3) If $x\in U$, then power set $\mathcal{P}(x)\in U,\...
1
vote
2answers
30 views

Open and closed intervals are similar [on hold]

How to show that any open and closed intervals are similar...i.e, there is bijection between open and closed intervals?
1
vote
1answer
21 views

Help with union of intervals

I know nothing about intervals, and I need some help with them because I need them for some programming exercises. Let's say that we have these 3 intervals: [1,2) (-1,0] [-12,-4] {if there is [ ...
0
votes
1answer
38 views

Show that the power set of a set A has too many elements to be able to be put in a one-to-one correspondence with A

Show that the power set of a set $A$, finite or infinite, has too many elements to be able to be put in a one-to-one correspondence with A. Explain why this intuitively means that there are an ...
2
votes
1answer
80 views

Using union of countably infinite sets, I tried to prove that set of all real numbers in [0,1) is countable

Cantor's diagonal method shows that the set $S=\{x\in \Bbb R|x \in [0,1)\}$ is uncountably infinite, because there is no bijection between the set $S$ and the set of natural number $\Bbb N$. I came ...
0
votes
1answer
42 views

Please, help to simplify set theory expression

I need to simplify set theory expression: $ (\bar{B} \cap C) \cup \bar{D} \cup ((B \cup \bar{C}) \cap D) \cup (A \cup \bar{C} ) $ $ \bar{B} $ means not B I understand how to solve it graphically ...
0
votes
0answers
34 views

Is equipotent $\sim$ relation?

Problem: $\sim$ is the mark for bijection between two set. Let $A$, $B$, $C$ be sets. Then$$A \sim A\\A\sim B \Rightarrow B\sim A\\(A\sim B \land B\sim C )\Rightarrow A\sim C$$ I know that is not a ...
1
vote
0answers
44 views

Proof check: Prove that if there is a class $B$ such that $A \in B$ then $A$ is a set

I am reading through Notes on Set Theory, 2nd ed. by Moschovakis, and this is part of an exercise on classes, which the author defines it as "either a set or a unary definite condition which is not ...
0
votes
1answer
35 views

$\kappa\cdot\sum_{i\in I}\lambda_i=_c\sum_{i\in I} \kappa\cdot \lambda_i$

Moschovakis Exercise x4.20 Prove that for all indexed families of cardinals, $$\kappa\cdot\sum_{i\in I}\lambda_i=_c\sum_{i\in I} \kappa\cdot \lambda_i$$ We have $$\kappa\cdot\sum_{i\in I}\lambda_i=...
0
votes
1answer
31 views

$\prod_{i\in A} B=(A\to B)$

Moschovakis Exercise x4.3: Prove that for sets $A,B$, $$\prod_{i\in A} B=(A\to B)$$ where $(A\to B)$ is the set of functions $A\to B$. The product is defined for an indexed family of sets: An ...
1
vote
0answers
28 views

$\lambda\le_c\mu\implies \kappa^\lambda\le_c\kappa^\mu$

Moschovakis, (part of) Exercise x4.16: Prove that for all cardinal numbers $\kappa,\lambda,\mu$ $$\lambda\le_c\mu\implies \kappa^\lambda\le_c\kappa^\mu$$ provided $\kappa\ne 0$. $\le_c$ means "...
0
votes
1answer
35 views

demonstrate sets [closed]

Please help me, I need a clue to solve this, I have to show that the left side is the same as on the right side. I came to something meaningless $$\left \{ \left [ \left ( A\cup B \right ) \setminus \...
0
votes
2answers
24 views

Interperting $\bigcap_{J\subset I\\J<\infty}\sigma(\bigcup_{j\in I\setminus J}A_j)$ tail sigma-algebra

Tail $\sigma$-algebra. Let $I$ be a countably infinite index set and let $(\mathscr{A}_i))_{i\in\mathbb{N}}$ be a family of $\sigma$-algebras. Then: $T((\mathscr{A}_i)_{i\in\mathbb{N}})=\bigcap_{...
1
vote
0answers
22 views

Let $A$ be a finite set. Prove that there exists an $f:n \to A$ that is onto $A$ for some $n \in \omega$

Let $A$ be a finite set. Prove that there exists an $f:n \to A$ that is onto $A$ for some $n \in \omega$. Here by finite we mean: A set $X$ is finite iff there is a one-to-one function $f:X→n$ for ...
1
vote
1answer
33 views

Let $n \in \omega$. Suppose $f:n \to A$ is onto $A$. Prove that $A$ is finite.

Let $n \in \omega$. Suppose $f:n \to A$ is onto $A$. Prove that $A$ is finite. I have: Let $I_a = \{i \in n:f(i)=a\}$ for $a \in A$. Since $f$ is onto $A$, $I_a$ is nonempty, and by the well-...
-2
votes
1answer
14 views

proving bijectivity of function mapping from powerset to powerset

Let S be a set and consider f: $\mathcal P(S) \mapsto \mathcal P (S)$ with $f(A) = S\backslash A$. Prove f is a bijection With injectivity, I ended up at $\mathcal P(S) \backslash A_1 = \mathcal P(S) ...
0
votes
1answer
22 views

Mathematical Definition of a function with array domain and codomain

I know the definition of a simple function is: $f:\biggl\{\begin{array}{rl}R&\to R\\ x&\mapsto f(x)\end{array} $ But i want to define a function which get a set as input and make the result ...
-1
votes
3answers
54 views

If two sets are equivalent is it ok to write they are equal

I am trying to understand the proof of the following theorem: In the very first line of the proof, it is written that "It suffices to assume that $A_i=\mathbb{N}$" But I do not understand why....