This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

0
votes
1answer
25 views

A question about indexed intersections and unions

I want to show that $X\cup \underset{i}{\large\cap} Y_i=\underset{i}{\large\cap}(X\cup Y_i)$ This is what I got, but I just want to know if I am going about this the correct way. $\begin{equation} ...
1
vote
2answers
86 views

Algebraic Structures: Does Order Matter?

(I want to link to similar question with a very good answer: Question about Algebraic structure?) An algebraic structure is an ordered tuple of sets. One of these is called the underlying set, and ...
0
votes
0answers
21 views

Is the Cardinality of the Set of Contingent Propositions the Same as the Cardinality of the Set of Tautologies?

By a "contingent proposition" I mean a proposition which is neither a tautology or contradiction. Or in other words, there exists at least one valuation of the variables such that the formula ...
0
votes
1answer
182 views

The “Empty Tuple” or “0-Tuple”: Its Definition and Properties

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)) In axiomatic (ZFC) set theory, we define ...
2
votes
1answer
34 views

Proving that $\bigcup\mathcal{A}\times\bigcap\mathcal{B}\subseteq\bigcup\{a\times b\mid a\in\mathcal{A}\land b\in\mathcal{B}\}$ is always true

The problem is to prove that the following expression is true for any families of sets $\mathcal{A}$ and $\mathcal{B}$ that are not empty. ...
0
votes
1answer
29 views

Common Binary Relation that is not a partial order

What is an example of a common binary relation on a set A that would not be partially ordered? The most common binary relations I've seen are $=, <, \leq$, but all of these are partial orders. ...
-3
votes
0answers
34 views

Prove or disprove conjecture [duplicate]

Prove or disprove conjecture $$A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$$ I don't know how to answer or where to start
-1
votes
3answers
41 views

Enumeration of a set

What do this statement mean: For any given $k\in \left[a,b\right]$, let $\left( x_n \right)_{n=1}^{\infty}$ be an enumeration of the set $\left\{c_jy_k^i:i,j\ge 1, \right\}$ where $c_j$ is a real ...
1
vote
2answers
43 views

What is the smallest infinite ordinal that is not order isomorphic to a reordering of the natural numbers?

I've been working on a particular set theory problem for a while and essentially I've hit a roadblock because of this question. I just need to know what this ordinal is, because I have a sneaking ...
2
votes
3answers
130 views

intro level set theory question.

I want to show that $X\cap(Y\cup Z) = (X\cap Y) \cup Z \ \iff Z\subseteq X$ I think I have figured out one direction: Assume $Z\subseteq X$ then $Z\cap X= Z$. We know $X\cap(Y\cup Z)=(X\cap Y)\cup ...
0
votes
0answers
12 views

If $V$ is a subspace of $\mathbb{R^n}$ and $V_B = \{[\vec{v}]_B : \vec{v} \in V\}$, $V_B$ is also a subspace of $\mathbb{R^n}$

Consider a basis $B$ of $\mathbb{R^n}$, $V$ a subspace of $\mathbb{R^n}$, and $V_B = \{[\vec{v}]_B : \vec{v} \in V\}$. Show that $V_B$ is also a subspace of $\mathbb{R^n}$ and dim$(V)$ = dim$(V_B)$. ...
1
vote
0answers
27 views

bijective function with powerset and symmetric difference

Let $X$ a set and $Y\subseteq X$ and $$f: \mathcal{P}(X)\rightarrow \mathcal{P}(X),\text{ with }A\in \mathcal{P}(X)\mapsto A\,\Delta\, Y$$ ($\Delta:=$ exclusive disjunction) Show that $f$ is ...
2
votes
2answers
33 views

2 element subsets of n elements?

the question is as follows: Give a recursive definition for the number of $2$-element subsets of $n$ elements. We started working this out in class and here is where we got too: -if $n = 0$, then ...
0
votes
1answer
58 views

Physical significance of the fact that the cardinality of the real number line is the same as a finite interval of the real number line

It is known that the cardinality of the real number line is the same as a finite interval of the real number line. Is there a physical meaning of this apparently conter-intuitive statement?
3
votes
3answers
116 views

Need a possible proof for $A\cap B=A\cup B$

I need to prove that- If $A,B\subseteq U$ where $U$ is the universal set, then $A\cap B=A\cup B$. I've been thinking a lot about it and I don;t think it's possible. Yet, I would like to confirm it ...
2
votes
3answers
37 views

The set of subsets of size $k$ in $\mathbb{N}$ is countable

Let $P_{k}(\mathbb{N}) = \{ A \subset \mathbb{N} \ | \ |A|=k \}$. I want to prove that $P_k$ is countable for each $k$. So I showed that this was a set of countable subsets, but I am not sure how to ...
0
votes
0answers
11 views

Term of partially ordered set with “levels”

Suppose that we have a partially ordered set $(X,\leq)$ such that the following condition holds: There exists a disjoint partition $X = \bigcup_{ i \in \mathbb N_0 } X_i$ such that for $i < j$ we ...
0
votes
1answer
18 views

Sets with all or none of the elements also being subsets - Cohn - Classic Algebra Page 11

Give examples of sets such that $(i)$ all and $(ii)$ none of their members are also subsets Firstly I should make sure I understand this correctly: The subsets of the set $S=\{\emptyset,1,2,3\}$ ...
1
vote
3answers
43 views

Union of two points

So the union of two sets is just a set that included all the elements from them but what happens for two points? For example, the set $X = [1,2] \cup [3,4]$. What would be considered in this set?
2
votes
2answers
22 views

Write out the following set by listing its elements between braces.

Write out the following set by listing its elements between braces: $\begin{align} \{X \subseteq \mathbb{N}: |X| \leq 1 \} &=\{\emptyset,\{1\},\{2\},\{3\},\ldots\}\end{align} $ Is my answer ...
6
votes
3answers
412 views

Is O(n) a proper class or a set?

Is $O(n)$ as the collection of all functions that are bounded above by $n$ a proper class or just a set? What about $O(\infty)$?
6
votes
0answers
56 views

Name of a certain set

I want to know if there is any already-standard way to refer to the set described as follows. Take the set of all primes in $\mathbb{Z}$, call it $\mathbb{P}$. Take the set of all finite products of ...
0
votes
1answer
34 views

Properties of the relation {<1,0>} on the empty set??

Suppose you take the relation R containing just the ordered pair <1,0>. Can this be a relation on the empty set? One line of reasoning might be that R is an equivalence relation on the empty set, ...
2
votes
1answer
32 views

Set equality, help needed

I have to prove the following: Any hints on what should I do next?
0
votes
7answers
165 views

Infinite partition of $\mathbb N$ by infinite subsets

I am looking for an explicit partition of $\mathbb N$ with the following condition: $$\mathbb N=\bigsqcup_{i\in\mathbb N}A_i$$ where all the $A_i$'s are infinite. What I mean by explicit is a formula ...
3
votes
0answers
24 views

What is the product of an empty family of similiar algebras, that is $\prod\langle \mathbf{A}_i \ | \ i \in I \rangle $, where $I = \emptyset$?

What is the product of an empty family of similiar algebras, that is $\prod\langle \mathbf{A}_i \ | \ i \in I \rangle $, where $I = \emptyset$? The family $\langle \mathbf{A}_i \ | \ i \in ...
2
votes
1answer
62 views

Is an ordered pair a set?

I'm having a problem with a homework. The task is to show whether the expression $$\bigcup\mathcal{A}\times\bigcap\mathcal{B}\subseteq\bigcup\{a\times b\mid a\in\mathcal{A}\land b\in\mathcal{B}\}$$ ...
1
vote
3answers
57 views

Can I use Gödel numbering to prove a set is countable?

We're studying the basics of set theory (introducing ZFC, defining countability, etc.) and in one of my homework questions I am asked to prove that given a finite set of symbols $a_1, a_2, \cdots, ...
0
votes
3answers
34 views

Subset of a Cartesian product? [duplicate]

Is it true the following $ R \subset R^2$ ? (If yes, I would like to see a rigorous proof.)
0
votes
3answers
22 views

Proving the cartesian product of the union of two sets A,B and the set C is equal to the union of two cartesian products

$(A \cup B) \times C = (A \times B) \cup (B \times C)$ So far I have: $x \in (A \times B)$ or $x ∈ (B \times C)$ [definition U] $(x ∈ A \quad \text{and}\quad x ∈ B)$ or $(x ∈ B \quad ...
1
vote
2answers
97 views

Proving set equality

I'm trying to prove two sets are equal, and I am wondering if my method of proof is ok. I know the "standard" way to show two sets are equal is to show that each is a subset of the other. Doing this ...
0
votes
4answers
41 views

Prove that if P(X) is a subset of P(Y) then X is a subset of Y.

Seems obvious: Prove that if $\mathscr{P}(X)$ is a subset of $\mathscr{P}(Y)$, then $X$ is a subset of $Y$. How to write a formal undeniable proof? Here $\mathscr{P}(X)$ is the power set of ...
1
vote
1answer
24 views

Prove that if X is a subset of Y then X intersect Z is a subset of Y intersect Z for all sets X, Y, Z.

How do you write this proof? Say Y = {a, b, c, d} and X = {a, c} and Z = {a, d, e}. Then X is indeed a subset of Y, however, Z intersect Y is {a, d}, and Z intersect X is just {a}, which is of course ...
0
votes
1answer
42 views

How ae these three order types on $Z_+ \times Z_+$ different?

Let $Z_+$ denote the set of positive integers. Consider the following relations on $Z_+ \times Z_+$: The dictionary order; that is, $(x_0,y_0) < (x_1,y_1)$ if either $x_0 < x_1$, or $x_0 = ...
1
vote
2answers
75 views

How did we conclude that it is a set? [closed]

I am looking at the proof of the theorem: The set of all the sets does not exist. Proof: We suppose that the set of all the sets, let $V$, exists.So, for each set $x, x \in V$. We define the type ...
0
votes
1answer
25 views

How I can justify the first choice $T$ to garantee that all the elements are not zeros?

Let $A$ be a finite set, then it is possible to find a bijection $$θ:A→T={1,2,...,n}$$ where $T$ is a finite part of natural numbers ℕ. Also, it is possible to find a bijection ...
0
votes
4answers
71 views

The intersection of an empty family of sets [duplicate]

I am confused about the following. Could you explain me why if $A=\varnothing$,then $\cap A$ is the set of all sets? Definition of $\cap A$: For $A \neq \varnothing$: $$x \in \cap A ...
3
votes
1answer
145 views

Complement of a set is not a set

How does one prove that for all sets S, there is no set T that contains all x not in S? This is working in ZFC, of course.
3
votes
1answer
66 views

Lindelof's Covering Theorem

If $A \in \mathbb R^n$ and $F$ be an open covering of $A$. Then there is a countable subcollection of $F$ which also covers $A$. Proof: Let $G=\{A_1,A_2, \cdots\}$ denote the countable collection of ...
-1
votes
2answers
41 views

Prove that $1_{A \Delta B} = 1_A + 1_B - 2\cdot 1_{A \cap B}$

Suppose $A, B \subset X$. If $A \Delta B= (A-B) \cup (B-A)$, then $$1_{A \Delta B} = 1_A + 1_B - 2\cdot 1_{A \cap B}$$ I got this identity from this site some time ago. I can't find the link to see ...
6
votes
0answers
80 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
0
votes
1answer
11 views

Set theory, injection's existence

Let $A^B$ be the set of all functions from $B$ to $A$, and $A \precsim B$ denotes the existence of an injection from $A$ to $B$. I need to prove that if the $ B \precsim C$ exists, so the $B^A ...
0
votes
1answer
33 views

Question on the proof of the following theorem : the image of a compact set under a continuous function is compact

Theorem : Let $f: S \rightarrow T$ be a function from one metric space $(S,d_s)$ to an another metric space $(T,d_t)$. If $f$ is continuous on a compact subset $X$ of $S$, then the image $f(X)$ is a ...
0
votes
0answers
19 views

How to express this set in terms of the given three sets? [duplicate]

Given the sets $A$, $B$, and $C$, let the set $D$ be defined as follows: $$ D \colon= \{ x | \, x \in A \, \land \, (x \in B \implies x \in C) \, \}.$$ Then how to express the set $D$ in terms of ...
1
vote
0answers
26 views

Am I right about these implications, equalities, and inclusions about sets and Cartesian products?

I'm reading James R. Munkres' TOPOLOGY, 2nd edition, but I have neither access to any turorial support nor any sort of a solutions manual. So I would from time to time like to keep posting any ...
1
vote
1answer
27 views

If $X= f^{-1}(Y)$, then $f(X) \subseteq Y$

I apologize if this is too basic but I have trouble understanding the following theorem : Theorem : If $X= f^{-1}(Y)$, then $f(X) \subseteq Y$ $f^{-1}(Y) = \{x : x \in S ~And~ f(x) \in Y\}$ With ...
1
vote
0answers
32 views

What operation is being done for this set of values?

I have a table that looks like the following: A B C A | B A C B | A C A C | C A B Some operation is being done between an element in the ...
-2
votes
0answers
25 views

How to prove that a finite integral domain is a field.

I am able to follow the proof given here except one thing why we need to have a set finite to imply surjectivity from injectivity to itself.....Please let me know as nobody has explicity mentioned why ...
0
votes
3answers
47 views

Cantor's Theorem (surjection vs bijection)

Let me state Cantor's Theorem first: Given any set $A$, these does not exist a function $f:A \rightarrow P(A)$ that is surjective. I understand the proof of this theorem, but I'm wondering why it's ...
0
votes
1answer
23 views

Equinumerous sets Examples

How do I show that the following sets are equinumerous or not? I know that $[0,\infty)$ has cardinality of the continuum, but I do not understand much of the notation $[0,1]^{\mathbb{N}}$, does it ...